Beating the I/O bottleneck: a case for log-structured file systems

ABSTRACT

CPU speeds are improving at a dramatic rate, while disk speeds are not. This technology shift suggests that many engineering and office applications may become so I/O-limited that they cannot benefit from further CPU improvements. This paper discusses several techniques for improving I/O performance, including caches, battery-backed-up caches, and cache logging. We then examine in particular detail an approach called log-structured file systems, where the file system's only representation on disk is in the form of an append-only log. Log-structured file systems potentially provide order-of-magnitude improvements in write performance. When log-structured file systems are combined with arrays of small disks (which provide high bandwidth) and large main-memory file caches (which satisfy most read accesses), we believe it will be possible to achieve 1000-fold improvements in I/O performance over today's systems.

REFERENCES

• 1: [1] Amdahl, G. "Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities." Proc. AFIPS 1967 Spring Joint Computer Conference, Atlantic City, N.J., April 1967.
• 2: 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
• 3: Jason Gait, The Optical File Cabinet: A Random-Access File System for Write-Once Optical Disks, Computer, v.21 n.6, p.11-22, June 1988 [doi>10.1109/2.947]
• 4: [4] Garfinkel, S., and Love, J. "A File System for Write-Once Media." MIT Media Lab report, October 1986.
• 5: 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
• 6: 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]
• 7: M Y Kim, Synchronized Disk Interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, November 1986 [doi>10.1109/TC.1986.1676699]
• 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: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 11: 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
• 12: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), ACM SIGMOD Record, v.17 n.3, p.109-116, June 1988
• 13: 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
• 14: Michael D. Schroeder , David K. Gifford , Roger M. Needham, A caching file system for a programmer's workstation, Proceedings of the tenth ACM symposium on Operating systems principles, p.25-34, December 1985, Orcas Island, Washington, United States
• 15: Liba Svobodova, A reliable object-oriented data repository for a distributed computer system, Proceedings of the eighth ACM symposium on Operating systems principles, p.47-58, December 14-16, 1981, Pacific Grove, California, United States
• 16: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Machine-independent complexity**

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization; Directory structures

General Terms:
Design, Performance