Log-structured file system

A log-structured filesystem is a file system design first proposed by John K. Ousterhout and Fred Douglis. Designed for high write throughput, all updates to data and metadata are written sequentially to a continuous stream, called a log.

Rationale

Conventional file systems tend to lay out files with great care for spatial locality and make in-place changes to their data structures in order to perform well on magnetic disks, which tend to seek relatively slowly.

The design of log-structured file systems is based on the hypothesis that this will no longer be effective because ever-increasing memory sizes on modern computers would lead to I/O becoming write-heavy because reads would be almost always satisfied from memory cache. A log-structured file system thus treats its storage as a circular log and writes sequentially to the head of the log. This maximizes write throughput on magnetic media by avoiding costly seeks.

Keeping a log has several important side effects:
* Writes create multiple, chronologically-advancing versions of both file data and meta-data. Some implementations make these old file versions nameable and accessible, a feature sometimes called time-travel or snapshotting. This is very similar to a versioning file system.
* Recovery from crashes is simpler. Upon its next mount, the file system does not need to walk all its data structures to fix any inconsistencies, but can reconstruct its state from the last consistent point in the log.
* Free space must be constantly reclaimed from the tail of the log to prevent the file system from becoming full when the head of the log wraps around to meet it. The tail itself can skip forward over data for which newer versions exist farther ahead in the log; the remainder is simply moved out of the way by appending it back to the head. To minimize the overhead incurred by this garbage collection, most implementations avoid purely circular logs and divide up their storage into segments or extents. The head of the log can then advance onto non-adjacent segments which are already free or which are less full than at the tail, thus reducing the amount of garbage collection I/O needed to reclaim space.

Implementations

* John K. Ousterhout and Mendel Rosenblum implemented the first log-structured file system for the Sprite operating system in 1992.Rosenblum, Mendel and Ousterhout, John K. (June 1990) - " [http://citeseer.ist.psu.edu/rosenblum90lfs.html The LFS Storage Manager] ". "Proceedings of the 1990 Summer Usenix". pp315-324.] Rosenblum, Mendel and Ousterhout, John K. (February 1992) - " [http://citeseer.ist.psu.edu/rosenblum91design.html The Design and Implementation of a Log-Structured File System] ". "ACM Transactions on Computer Systems, Vol. 10 Issue 1". pp26-52.]
* BSD-LFS, an implementation by Margo Seltzer was added to 4.4BSD, and was later ported to 386BSD. It lacked support for snapshots. It was removed from FreeBSD and OpenBSD, but still lives on in NetBSD.
* Plan 9's Fossil file system is also log-structured and supports snapshots.
* NILFS is a log-structured file system implementation for Linux by NTT/Verio which supports snapshots. As of May 2007, it is still in alpha and not ready for production use.
* LinLogFS (formerly dtfs) and LFS ( [http://logfs.sourceforge.net/ http://logfs.sourceforge.net/] ) are log-structured file system implementations for Linux. The latter was part of Google Summer of Code 2005. Both projects have been abandoned.
* [http://aiya.ms.mff.cuni.cz/lfs LFS] is another log-structured file system for Linux developed by Charles University, Prague. It was to include support for snapshots and indexed directories, but development has since ceased.
* [http://logfs.org/logfs/ LogFS] is a scalable flash filesystem for Linux, intended to replace JFFS2. Early in development.

Some kinds of storage media, such as flash memory and CD-RW, degrade slowly as they are written to and have a limited number of erase/write cycles at any one location. Log-structured file systems are sometimes used on these media because they make fewer in-place writes and thus prolong the life of the device by wear levelling. The more common such file systems include:

* UDF is a file system commonly used on optical discs.
* JFFS and its successor JFFS2 are simple Linux file systems intended for flash-based devices.
* YAFFS is a NAND flash-specific file system for many operating systems (including Linux).

Disadvantages

* The design rationale for log-structured file systems assumes that most reads will be optimized away by ever-enlarging memory caches. This assumption does not always hold:
** On magnetic media—where seeks are relatively expensive—the log structure may actually make reads much slower, since it fragments files that conventional file systems normally keep contiguous with in-place writes.
** On flash memory—where seek times are usually negligible—the log structure may not confer a worthwhile performance gain because write fragmentation has much less of an impact on write throughput.

References

See also

* Comparison of file systems