Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a new technique for disk storage management called a log-structured file system. A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, we divide the log into segments and use a segment cleaner to compress the live information from heavily fragmented segments. We present a series of simulations that demonstrate the efficiency of a simple cleaning policy based on cost and benefit. We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes. Even when the overhead for cleaning is included, Sprite LFS can use 70% of the disk bandwidth for writing, whereas Unix file systems typically can use only 5--10%.

REFERENCES

• 1: 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
• 2: Michael L. Kazar, Bruce W. Leverett, Owen T. Anderson, Vasilis Apostolides, Beth A. Bottos, Sailesh Chutani, Craig F. Everhart, W. Anthony Mason, Shu-Tsui Tu, and Edward R. Zayas, "DEcorum File System Architectural Overview," Proceedings of the USENIX 1990 Summer Conference, pp. 151-164 (Jun 1990).
• 3: 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
• 4: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 5: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 6: 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
• 7: M. Satyanarayanan, A study of file sizes and functional lifetimes, Proceedings of the eighth ACM symposium on Operating systems principles, p.96-108, December 14-16, 1981, Pacific Grove, California, United States
• 8: Edward D. Lazowska , John Zahorjan , David R. Cheriton , Willy Zwaenepoel, File access performance of diskless workstations, ACM Transactions on Computer Systems (TOCS), v.4 n.3, p.238-268, Aug. 1986 [doi>10.1145/6420.6423]
• 9: Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
• 10: R. Sandberg, "Design and Implementation of the Sun Network Filesystem," Proceedings of the USENIX 1985 Summer Conference, pp. 119-130 (Jun 1985).
• 11: John K. Ousterhout, "Why Aren't Operating Systems Getting Faster As Fast as Hardware?," Proceedings of the USENIX 1990 Summer Conference, pp. 247-256 (Jun 1990).
• 12: Margo I. Seltzer, Peter M. Chen, and John K. Ousterhout, "Disk Scheduling Revisited," Proceedings of the Winter 1990 USENIX Technical Conference, (January 1990).
• 13: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 14: A. Chang , M. F. Mergen , R. K. Rader , J. A. Roberts , S. L. Porter, Evolution of storage facilities in AIX Version 3 for RISC System/6000 processors, IBM Journal of Research and Development, v.34 n.1, p.105-110, Jan. 1990
• 15: Marshall Kirk McKusick, Willian N. Joy, Samuel J. Leffler, and Robert S. Fabry, "Fsck - The UNIX File System Check Program," Unix System Manager's Manual - 4.3 BSD Virtual VAX-11 Version, USENIX, (Apr 1986).
• 16: Larry McVoy and Steve Kleiman, "Extent-like Performance from a UNIX File System," Proceedings of the USENIX 1991 Winter Conference, (Jan 1991).
• 17: D. Reed and Liba Svobodova, "SWALLOW: A Distributed Data Storage System for a Local Network," Local Networks for Computer Communications, pp. 355-373 North-Holland, (1981).
• 18: R. Finlayson , D. Cheriton, Log files: an extended file service exploiting write-once storage, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.139-148, November 08-11, 1987, Austin, Texas, United States
• 19: H.G. Baker, "List Processing in Real Time on a Serial Computer," A.I. Working Paper 139, MIT-AI Lab, Boston, MA (April 1977).
• 20: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 21: Brian M. Oki , Barbara H. Liskov , Robert W. Scheifler, Reliable object storage to support atomic actions, Proceedings of the tenth ACM symposium on Operating systems principles, p.147-159, December 1985, Orcas Island, Washington, United States
• 22: 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
• 23: Kenneth Salem and Hector Garcia-Molina, "Crash Recovery Mechanisms for Main Storage Database Systems," CS-TR-034-86, Princeton University, Princeton, NJ (1986).
• 24: R B Hagmann, A crash recovery scheme for a memory-resident database system, IEEE Transactions on Computers, v.35 n.9, p.839-843, Sept. 1986 [doi>10.1109/TC.1986.1676845]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.3 File Systems Management
          Subjects: Directory structures
      D.4.5 Reliability
          Subjects: Checkpoint/restart

General Terms:
Design, Performance