The Rio file cache: surviving operating system crashes

ABSTRACT

One of the fundamental limits to high-performance, high-reliability file systems is memory's vulnerability to system crashes. Because memory is viewed as unsafe, systems periodically write data back to disk. The extra disk traffic lowers performance, and the delay period before data is safe lowers reliability. The goal of the Rio (RAM I/O) file cache is to make ordinary main memory safe for persistent storage by enabling memory to survive operating system crashes. Reliable memory enables a system to achieve the best of both worlds: reliability equivalent to a write-through file cache, where every write is instantly safe, and performance equivalent to a pure write-back cache, with no reliability-induced writes to disk. To achieve reliability, we protect memory during a crash and restore it during a reboot (a "warm" reboot). Extensive crash tests show that even without protection, warm reboot enables memory to achieve reliability close to that of a write-through file system. Adding protection makes memory even safer than a write-through file system while adding essentially no overhead. By eliminating reliability-induced disk writes, Rio performs 4-22 times as fast as a write-through file system, 2-14 times as fast as a standard Unix file system, and 1-3 times as fast as an optimized system that risks losing 30 seconds of data and metadata.

REFERENCES

• Abbott94: M. Abbott, D. Har, L. Herger, M. Kauffmann, K. Mak, J. Murdock, C. Schulz, B. Smith, B. Tremaine, D. Yeh, and L. Wong. Durable Memory RS/6000 System Design. In Proceedings of the 1994 International Symposium on Fault-Tolerant Computing, pages 414-423, 1994.
• APC96: The Power Protection Handbook. Technical report, American Power Conversion, 1996.
• Baker91: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• Baker92a: Mary Baker , Satoshi Asami , Etienne Deprit , John Ouseterhout , Margo Seltzer, Non-volatile memory for fast, reliable file systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.10-22, October 12-15, 1992, Boston, Massachusetts, United States
• Baker92b: Mary Baker and Mark Sullivan. The Recovery Box: Using Fast Recovery to Provide High Availability in the UNIX Environment. In Proceedings USENIX Summer Conference, June 1992.
• Baker94: Mary Louise Gray Baker. Fast Crash Recovery in Distributed File Systems. PhD thesis, University of California at Berkeley, January 1994.
• Banatre91: Michel Banatre, Gilles Muller, Bruno Rochat, and Patrick Sanchez. Design decisions for the FTM: a general purpose fault tolerant machine. In Proceedings of the 1991 International Symposium on Fault-Tolerant Computing, pages 71-78, June 1991.
• Barton90: J. H. Barton , E. W. Czeck , Z. Z. Segall , D. P. Siewiorek, Fault Injection Experiments Using FIAT, IEEE Transactions on Computers, v.39 n.4, p.575-582, April 1990 [doi>10.1109/12.54853]
• Chapin95: J. Chapin , M. Rosenblum , S. Devine , T. Lahiri , D. Teodosiu , A. Gupta, Hive: fault containment for shared-memory multiprocessors, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.12-25, December 03-06, 1995, Copper Mountain, Colorado, United States
• Chen96: Peter M. Chen, Wee Teck Ng, Gurushankar Rajamani, and Christopher M. Aycock. The Rio File Cache: Surviving Operating System Crashes. Technical Report CSE-TR- 286-96, University of Michigan, March 1996.
• Copeland89: G. Copeland , T. Keller , R. Krishnamurthy , M. Smith, The case for safe RAM, Proceedings of the 15th international conference on Very large data bases, p.327-335, July 1989, Amsterdam, The Netherlands
• DEC94: DEC 3000 300/400/500/600/700/800/900 AXP Models System Programmer's Manual. Technical report, Digital Equipment Corporation, July 1994.
• DeWitt84: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Gait90: Jason Gait, Phoenix: a safe in-memory file system, Communications of the ACM, v.33 n.1, p.81-86, Jan. 1990 [doi>10.1145/76372.76378]
• Ganger94: Gregory R. Ganger and Yale N. Patt. Metadata Update Performance in File Systems. 1994 Operating Systems Design and Implementation (OSDI), November 1994.
• Gray90: Jim Gray. A Census of Tandem System Availability between 1985 and 1990. IEEE Transactions on Reliability, 39(4), October 1990.
• Hagmann87: R. Hagmann, Reimplementing the Cedar file system using logging and group commit, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.155-162, November 08-11, 1987, Austin, Texas, United States
• Hartman93: John H. Hartman and John K. Ousterhout. Letter to the Editor. Operating Systems Review, 27(1):7-9, January 1993.
• Hennessy90: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• Howard88: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• Johnson82: Mark Scott Johnson, Some requirements for architectural support of software debugging, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.140-148, March 01-03, 1982, Palo Alto, California, United States
• Kanawati95: Ghani A. Kanawati , Nasser A. Kanawati , Jacob A. Abraham, FERRARI: A Flexible Software-Based Fault and Error Injection System, IEEE Transactions on Computers, v.44 n.2, p.248-260, February 1995 [doi>10.1109/12.364536]
• Kane92: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Kao93: Wei-lun Kao , Ravishankar K. Iyer , Dong Tang, FINE: A Fault Injection and Monitoring Environment for Tracing the UNIX System Behavior Under Faults, IEEE Transactions on Software Engineering, v.19 n.11, p.1105-1118, November 1993 [doi>10.1109/32.256857]
• Kessler90: Peter B. Kessler, Fast breakpoints: design and implementation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.78-84, June 1990, White Plains, New York, United States
• Lee93: Inhwan Lee and RavishankarK. Iyer. Faults, Symptoms, and Software Fault Tolerance in the Tandem GUARDIAN Operating System. In International Symposium on Fault-Tolerant Computing (FTCS), pages 20-29, 1993.
• Leffler89: Samuel J. Leffier, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System. Addison-Wesley Publishing Company, 1989.
• Liskov91: Barbara Liskov , Sanjay Ghemawat , Robert Gruber , Paul Johnson , Liuba Shrira, Replication in the harp file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.226-238, October 13-16, 1991, Pacific Grove, California, United States
• McKusick90: Marshall Kirk McKusick, Michael J. Karels, and Keith Bostic. A Pageable Memory Based Filesystem. In Proceedings US- ENIX Summer Conference, June 1990.
• Moran90: J. Moran, Russel Sandberg, D. Coleman, J. Kepecs, and Bob Lyon. Breaking Through the NFS Performance Barrier. In Proceedings of EUUG Spring 1990, April 1990.
• Ohta90: Masataka Ohta and Hiroshi Tezuka. A Fast /tmp File System by Delay Mount Option. In Proceedings USENIX Summer Conference, pages 145-150, June 1990.
• Ousterhout85: John K. Ousterhout , Hervé Da Costa , David Harrison , John A. Kunze , Mike Kupfer , James G. Thompson, A trace-driven analysis of the UNIX 4.2 BSD file system, Proceedings of the tenth ACM symposium on Operating systems principles, p.15-24, December 1985, Orcas Island, Washington, United States
• Rosenblum92: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.26-52, Feb. 1992 [doi>10.1145/146941.146943]
• Silberschatz94: Abraham Silberschatz , James L. Peterson , Peter B. Galvin, Operating system concepts (3rd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• Sites92: Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
• SPE91: SPEC SDM Release 1.0 Technical Fact Sheet. Technical report, Franson and Haggerty Associates, 1991.
• Sullivan91a: Mark Sullivan , Michael Stonebraker, Using Write Protected Data Structures To Improve Software Fault Tolerance in Highly Available Database Management Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.171-180, September 03-06, 1991
• Sullivan91b: Mark Sullivan and R. Chillarege. Software Defects and Their Impact on System Availability-A Study of Field Failures in Operating Systems. In Proceedings of the 1991 International Symposium on Fault-Tolerant Computing, June 1991.
• Tanenbaum95: Andrew S. Tanenbaum, Distributed operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• Wahbe92: Robert Wahbe, Efficient data breakpoints, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.200-212, October 12-15, 1992, Boston, Massachusetts, United States
• Wahbe93: Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.203-216, December 05-08, 1993, Asheville, North Carolina, United States
• Wu94: Michael Wu , Willy Zwaenepoel, eNVy: a non-volatile, main memory storage system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.86-97, October 05-07, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Backup procedures

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Design, Performance, Reliability, Security