article

Free access

The design and implementation of a log-structured file system

Editor: Anita K. Jones Authors:

Mendel Rosenblum,

John K. OusterhoutAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 10, Issue 1

Pages 26 - 52

https://doi.org/10.1145/146941.146943

Published: 01 February 1992 Publication History

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 intosegmentsand 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]

BAKER, H. G. List processing in real time on a serial computer. A.I. Working Paper 139, MIT-AI Lab, Boston, MA, Apr. 1977.

[2]

BAKER, M. G., HARTMAN, J. H., KUPFER, M~ D., SHIRRIFF, K. W., AND OUSTERHOUT, J. K. Measurements of a distributed file system. In Proceedings of the 13th Symposium on Operating Systems Principles (Pacific Grove, Calif., Oct. 1991), ACM. pp. 198-212.

[3]

CHANG, A., MERGEN, M. F., RADER, R. K~, ROBERTS, J. A., AND PORTER, S.L. Evolution of storage facilities in AIX Version 3 for RISC System/6000 processors. IBM J. Res. Dev. 34, 1 (Jan. 1990), 105-109.

[4]

DEWITT, D. J., KATZ, R. H., OLKEN, F., SHAPIRO. L. D., STONEBRAKER M. R., AND WOOD, D. Implementation techniques for main memory database systems. In Proceedings of SIGMOD 1984 (Jun. 1984), pp. 1-8.

[5]

FINLAYSON, R. S. AND CHERITON, D. R. Log files: An extended file service exploiting write-once storage. In Proceedings of the 11th Sympostum on Operating Systems Principles (Austin, Tex., Nov. 1987), ACM, pp. 129-148.

[6]

GRAY, J. Notes on data base operating systems. In Operating Systems, An Advanced Course. Springer-Verlag, Berlin, 1979, pp~ 393-481.

[7]

HAaMANN, R.B. A crash recovery scheme for a memory-resident database system, IEEE Trans. Comput. C-35, 9 (Sept. 1986), 000-000.

[8]

HAGMANN, R.B. Reimplementing the cedar file system using logging and group commit. In Proceedings of the 11th Symposium on Operating Systems Principles (Austin, Tex., Nov. 1987), pp. 155-162.

[9]

KAZAR, M. L, LEVERETT, B. W., ANDERSON, O. T, APOSTOLIDES, V., BOTTOS, B. A CHUTANI, S., EVERHART, C. F., MASON, W. A., Tu, S. T., AND ZAYAS, E. R. Decorum file system architectural overview. In Proceedings of the USENIX 1990 Summer Conference (Anaheim, Calif., Jun. 1990), pp. 151-164.

[10]

LAZOWSKA, E. D., ZAHORJAN, J., CHERITON, D. R., AND ZWAENEPOEL, W. File access performance of diskless workstations. Trans. Comput. Syst. 4, 3 (Aug. 1986), 238-268.

[11]

LIEBERMAN, H AND HEWITT, C. A real-time garbage collector based on the lifetimes of objects. Commun. ACM. 26, 6 (June 1983), 419-429.

[12]

McKumcK, M. K. A fast file system for Unix. Trans. Comput. Syst. 2, 3 (Aug. 1984), 181-197.

[13]

McKusIcK, M K., JoY, W. N., LEFFLER~ S. J., AND FABRY, R. S. Fsck--The UNIX file system check program. Unix System Manager's Manual--4.3 BSD Virtual VAX-11 Version, USENIX, Berkeley, Calif., Apr. 1986.

[14]

McVoY, L. AND KL~mAN, S. Extent-like performance from a UNIX file system. In Proceedings of the USENIX 1991 Winter Conference (Dallas, Tex., Jan. 1991).

[15]

OKI, B. M., LISKOV, B. H., AND SCHEIFLER, R.W. Reliable object storage to support atomic actions. In Proceedings of the lOth Symposium on Operating Systems Principles (Orcas Island, Wash., Dec. 1985) ACM, pp. 147-159.

[16]

OUSTERHOU% J. K. Why aren't operating systems getting faster as fast as hardware? In Proceedings of the USENIX 1990 Summer Conference (Anaheim, Calif., Jun. 1990), pp. 247-256.

[17]

OUSTERHOUT, J. K, CHERENSON, A, R., DOUGLIS, F., NELSON, M N, AND WELCH, B.B. The Sprite Network Operating System. IEEE Comput. 21, 2 (Feb. 1988), 23 36.

[18]

OUSTERHOUT, J. K, DA COSTA, H., HARRISON, D., KUNZE, J A., KUPFER, M., AND THOMPSON, J. G A trace-dmven analysis of the Unix 4.2 BSD file system. In Proceedings of the lOth Symposium on Operating Systems Principles (Orcas Island, Wash., 1985), ACM, pp. 15-24.

[19]

PATTERSON, D. A., Gmsor4, G., AND KATZ, R. H A case for redundant arrays of inexpensive disks (RAID). ACM SIGMOD 88, pp. 109-116, (Jun. 1988).

[20]

REED, D. AND SVOBODOVA, L. SWALLOW: A distributed data storage system for a local network. In Local Networks for Computer Communications. North-Holland, 1981, pp. 355-373.

[21]

SANDSERG, R. Design and implementation of the Sun network filesystem. In Proceedings of the USENIX 1985 Summer Conference (Portland, Ore, Jun. 1985) pp. 119-130.

[22]

SALEM, K. AND GARCIA-MOLINA, H. Crash recovery mechamsms for main storage database systems. CS-TR-034-86, Princeton Univ., Princeton, NJ 1986.

[23]

SATYANARAYANAN, M A study of file sizes and functional lifetimes. In Proceedings of the 8th Symposium on Operating Systems Principles (Pacffic Grove, Calif., Dec. 1981), ACM, pp. 96-108.

[24]

SELTZER, M. I., CHEN, P. M., AND OUSTERHOUT, J. K Disk scheduling revisited. In Proceedlngs of the Winter 1990 USENIX Techmcal Conference (Jan. 1990), pp.

Cited By

Ashutosh Kumar Ankit Kumar Singh Ashima Mehta (2024)AI based Operating SystemInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-17449(291-298)Online publication date: 18-Apr-2024
https://doi.org/10.48175/IJARSCT-17449
Hwang IKim SEom HSon Y(2024)Sequentialized Virtual File System: A Virtual File System Enabling Address Sequentialization for Flash-Based Solid State DrivesComputers10.3390/computers1311028413:11(284)Online publication date: 2-Nov-2024
https://doi.org/10.3390/computers13110284
Huang JLiu TChen YPeng HHuang TLei CHuang CFournaris APalmieri P(2024)Time Machine: An Efficient and Backend-Migratable Architecture for Defending Against Ransomware in the HypervisorProceedings of the 2024 on Cloud Computing Security Workshop10.1145/3689938.3694780(66-79)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3689938.3694780
Show More Cited By

Index Terms

The design and implementation of a log-structured file system

Recommendations

The design and implementation of a log-structured file system
SOSP '91: Proceedings of the thirteenth ACM symposium on Operating systems principles

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 ...
The logical disk: a new approach to improving file systems

The Logical Disk (LD) defines a new interface to disk storage that separates file management and disk management by using logical block numbers and block lists. The LD interface is designed to support multiple file systems and to allow multiple ...
The logical disk: a new approach to improving file systems
SOSP '93: Proceedings of the fourteenth ACM symposium on Operating systems principles

The Logical Disk (LD) defines a new interface to disk storage that separates file management and disk management by using logical block numbers and block lists. The LD interface is designed to support multiple file systems and to allow multiple ...

Reviews

Reviewer: Charles N. Schroeder

This well-written paper is of particular interest at this time since it deals with a much-improved disk storage management system for UNIX-based systems. The system described shows an order of magnitude increase in performance over traditional log systems; it is of particular interest to system administrators of UNIX-based systems. As indicated in the abstract, “the log-structured file system writes 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 files can be read back from the log efficiently.” In order to maintain large free areas on the disk for fast writing, the log is divided into segments and a segment cleaner is used to compress fragmented segments. The authors describe a prototype of the log-structured file system and give performance comparisons to current UNIX file systems. The results are impressive and indicate that this system has definite potential for increasing the performance of file systems.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 10, Issue 1

Feb. 1992

77 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/146941

Editor:
Anita K. Jones
Univ. of Virginia, Charlottesville

Issue’s Table of Contents

Copyright © 1992 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1992

Published in TOCS Volume 10, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,224
Total Citations
View Citations
12,764
Total Downloads

Downloads (Last 12 months)1,299
Downloads (Last 6 weeks)181

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ashutosh Kumar Ankit Kumar Singh Ashima Mehta (2024)AI based Operating SystemInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-17449(291-298)Online publication date: 18-Apr-2024
https://doi.org/10.48175/IJARSCT-17449
Hwang IKim SEom HSon Y(2024)Sequentialized Virtual File System: A Virtual File System Enabling Address Sequentialization for Flash-Based Solid State DrivesComputers10.3390/computers1311028413:11(284)Online publication date: 2-Nov-2024
https://doi.org/10.3390/computers13110284
Huang JLiu TChen YPeng HHuang TLei CHuang CFournaris APalmieri P(2024)Time Machine: An Efficient and Backend-Migratable Architecture for Defending Against Ransomware in the HypervisorProceedings of the 2024 on Cloud Computing Security Workshop10.1145/3689938.3694780(66-79)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3689938.3694780
Jia ZWitchel E(2024)The Key Ideas Behind Boki's Shared LogsACM SIGOPS Operating Systems Review10.1145/3689051.368905458:1(7-14)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.1145/3689051.3689054
Choi JJun YKim JJeong JSeo E(2024)An Adaptive Zone-Grouping Scheme Enabling General-Purpose File Systems on ZNS SSDsProceedings of the 17th ACM International Systems and Storage Conference10.1145/3688351.3689151(132-145)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1145/3688351.3689151
Wang SZhang ZZhang Y(2024)OnionDisk: A Log-Structured Write-Optimal Virtual Block DeviceProceedings of the 15th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3678015.3680489(136-143)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1145/3678015.3680489
Zhou RZhang YLi CZhou KWang PZhang GZhang JZhang G(2024)HyperDB: a Novel Key Value Store for Reducing Background Traffic in Heterogeneous SSD StorageProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673153(453-463)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673153
Chen PSeo DSung CPark JLee MLi HBjørling MDutt N(2024)ZoneTrace: Zone Monitoring Tool for F2FS on ZNS SSDsACM Transactions on Design Automation of Electronic Systems10.1145/365617229:5(1-15)Online publication date: 5-Apr-2024
https://dl.acm.org/doi/10.1145/3656172
Li HZhang ZYuan YDu RMa KLiu LZhang YHsu W(2024)Block-level Image Service for the CloudACM Transactions on Storage10.1145/362067220:1(1-28)Online publication date: 30-Jan-2024
https://dl.acm.org/doi/10.1145/3620672
Zhang YZhang HCao WHe XPark DChoi JPark STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)LazyBarrier: Reconstructing Android IO Stack for Barrier-Enabled Flash StorageProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640370(601-615)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640370
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents