Log-structured File System (BSD)

The Log-Structured File System (or LFS) is an implementation of a log-structured file system (a concept originally proposed and implemented by John Ousterhout), originally developed for BSD. It was removed from FreeBSD and OpenBSD; the NetBSD implementation was nonfunctional until recent work leading up the 4.0 release made it viable again as a production file system. [cite web|title = NetBSD 4.0 Release CHANGELOG|url = ftp://ftp.netbsd.org/pub/NetBSD/NetBSD-4.0/CHANGES-4.0|accessdate = 2008-01-26|date = 2007-12-15|first = Manuel|last = Bouyer.]

Design

Most of the on-disk format of LFS is borrowed from UFS. The indirect block, inode and directory formats are almost identical. This allows well-tested UFS file system code to be re-used; current implementations of LFS replace the lower-level Berkeley FFS code in UFS with LFS code, and share the higher-level UFS code with FFS.

LFS divides the disk into "segments", only one of which is active at any one time. Each segment has a header called a "summary block". Each summary block contains a pointer to the next summary block, linking segments into one long chain that LFS treats as a linear log. The segments do not necessarily have to be adjacent to each other on disk; for this reason, larger segment sizes (between 384KB and 1MB) are recommended because they amortize the cost of seeking between segments.citation|last1 = Rosenblum|first1 = Mendel|last2 = Ousterhout|first2 = John K|date = February 1992|url = http://www.hhhh.org/perseant/lfs/lfsSOSP91.ps.gz|title = The Design and Implementation of a Log-Structured Filesystem|journal = ACM Transactions on Computer Systems|volume = 10|issue = 1|pages = 26-52.]

Whenever a file or directory is changed, LFS writes to the head of this log:
# Any changed or new data blocks.
# Indirect blocks updated to point to (1).
# Inodes updated to point to (2).
# Inode map blocks updated to point at (3). [citation|last1 = Rosenblum|first1 = Mendel|last2 = Ousterhout|first2 = John K|date = June 1990|url = http://www.hhhh.org/perseant/lfs/lfs-storage.ps.gz|title = The LFS Storage Manager|journal = Proceedings of the 1990 Summer Usenix|pages = 315-324.]

Unlike UFS, inodes in LFS do not have fixed locations. An inode map—a flat list of inode block locations—is used to track them. As with everything else, inode map blocks are also written to the log when they are changed.

When a segment is filled, LFS goes on to fill the next free or "clean" segment. Segments are said to be "dirty" if they contain "live" blocks, or blocks for which no newer copies exist further ahead in the log. The LFS "garbage collector" turns dirty segments into "clean" ones by copying live blocks from the dirty segment into the current segment and skipping the rest. The summary block in each segment contains a map to track live blocks.

Generally, garbage collection is delayed until there are no clean segments left; it can also be deferred for when the system is idle. Even then, only the least-dirty segments are picked for collection. This is intended to avoid the penalty of cleaning full segments when I/O bandwidth is most needed.

At a "checkpoint" (usually scheduled about once every 30 seconds), LFS writes the last known block locations of the inode map and the number of the current segment to a "checkpoint region" at a fixed place on disk. There are two such regions; LFS alternates between them each checkpoint. Once written, a "checkpoint" represents the last consistent snapshot of the file system. Recovery after a crash and normal mounting work the same way—the file system simply reconstructs its state from the last checkpoint and resumes logging from there.

Disadvantages

* There can be severe file system fragmentation in LFS, especially for slowly-growing files or multiple simultaneous large writes. This inflicts a severe performance penalty, even though the design rationale for log-structured file systems assumes disk reads will mostly be cached away.
* LFS becomes progressively less efficient as it nears maximum capacity, when the garbage collector has to run almost constantly to make clean segments available.
* LFS does not allow snapshotting or versioning, even though both features are trivial to implement in general on log-structured file systems.

References

* Seltzer, Margo, Bostic, K., McKusick, M. and Staelin, C. (January 1993). " [http://www.hhhh.org/perseant/lfs/lfs_for_unix.ps.gz The Design and Implementation of the 4.4BSD Log-structured File System] ". "Proceedings of the 1993 Winter Usenix."
* McKusick, M. et al (1996). " [http://www.freebsd.org/doc/en_US.ISO8859-1/books/design-44bsd The Design and Implementation of the 4.4BSD Operating System] ." Addison Wesley. ISBN 0-201-54979-4.
* J. Matthews, D. Roselli, A. Costello, R. Wang, and T. Anderson (October 1997). " [http://www.cs.princeton.edu/~rywang/berkeley/papers/sosp97.ps Improving the Performance of Log-Structured File Systems with Adaptive Methods] ", "Proceedings of the Sixteenth ACM SOSP".