LFS introduces a new approach to updating the disk. Instead of overwriting files in places, LFS always writes to an unused portion of the disk, and then later reclaims that old space through cleaning. This approach, which in database systems is called shadow paging“Physical Integrity in a Large Segmented Database” by R. Lorie. ACM Transactions on Databases, Volume 2:1, 1977. The original idea of shadow paging is presented here. and in file-system-speak is sometimes called copy-on-write, enables highly efficient writing, as LFS can gather all updates into an in-memory segment and then write them out together sequentially.
The large writes that LFS generates are excellent for performance on many different devices. On hard drives, large writes ensure that positioning time is minimized. On parity-based RAIDs, such as RAID-4 and RAID-5, they avoid the small-write problem entirely. Recent research has even shown that large I/Os are required for high performance on Flash-based SSDs“The Unwritten Contract of Solid State Drives” by Jun He, Sudarsun Kannan, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. EuroSys ’17, April 2017. Which unwritten rules one must follow to extract high performance from an SSD? Interestingly, both request scale (large or parallel requests) and locality still matter, even on SSDs. The more things change …. Thus, perhaps surprisingly, LFS-style file systems may be an excellent choice even for these new mediums.
The downside to this approach is that it generates garbage; old copies of the data are scattered throughout the disk, and if one wants to reclaim such space for subsequent usage, one must clean old segments periodically. Cleaning became the focus of much controversy in LFS, and concerns over cleaning costs“File system logging versus clustering: a performance comparison” by Margo Seltzer, Keith A. Smith, Hari Balakrishnan, Jacqueline Chang, Sara McMains, Venkata Padmanabhan. USENIX 1995 Technical Conference, New Orleans, Louisiana, 1995. A paper that showed the LFS performance sometimes has problems, particularly for workloads with many calls to fsync() (such as database workloads). The paper was controversial at the time. perhaps limited LFS’s initial impact on the field. However, some modern commercial file systems, including NetApp’s WAFL“File System Design for an NFS File Server Appliance” by Dave Hitz, James Lau, Michael Malcolm. USENIX Spring ’94. WAFL takes many ideas from LFS and RAID and puts it into a high-speed NFS appliance for the multi-billion dollar storage company NetApp., Sun’s ZFS“ZFS: The Last Word in File Systems” by Jeff Bonwick and Bill Moore. Copy Available: http://www.ostep.org/Citations/zfs_last.pdf. Slides on ZFS; unfortunately, there is no great ZFS paper (yet). Maybe you will write one, so we can cite it here?, and Linux btrfs“BTRFS: The Linux B-Tree Filesystem” by Ohad Rodeh, Josef Bacik, Chris Mason. ACM Transactions on Storage, Volume 9 Issue 3, August 2013. Finally, a good paper on BTRFS, a modern take on copy-on-write file systems., and even modern flash-based SSDs, adopt a similar copy-on-write approach to writing to disk, and thus the intellectual legacy of LFS lives on in these modern file systems. In particular, WAFL got around cleaning problems by turning them into a feature. By providing old versions of the file system via snapshots, users could access old files whenever they deleted current ones accidentally.
TIP: TURN FLAWS INTO VIRTUES
Whenever your system has a fundamental flaw, see if you can turn it around into a feature or something useful. NetApp’s WAFL does this with old file contents; by making old versions available, WAFL no longer has to worry about cleaning quite so often (though it does delete old versions, eventually, in the background), and thus provides a cool feature and removes much of the LFS cleaning problem all in one wonderful twist. Are there other examples of this in systems? Undoubtedly, but you’ll have to think of them yourself because this chapter is over with a
capital “O”. Over. Done. Kaput. We’re out. Peace!