- This is about the concept of a log-structured file system. For the NetBSD file system, see Log-structured File System.
A log-structured filesystem is a file system design first proposed by John K. Ousterhout and Fred Douglis. It writes data to the file system in a sequential "log" format, as opposed to the normal scattered blocks format.
Rationale
Conventional filesystems tend to lay out files on disk with great care for spatial locality and make in-place changes to data structures on disk in order to perform well on magnetic disks, which tend to seek relatively slowly.
The design of log-structured filesystems is based on the hypothesis that this will no longer be effective because ever-increasing memory sizes on modern computers would lead to disk I/O becoming write-heavy because disk reads would be almost always satisfied from memory cache.
To maximize write throughput, a log-structured file system treats the disk as a circular log and writes sequentially to the head of the log. This has the side effect of creating multiple, chronologically-advancing versions of both file data and meta-data. This log is undoable.
Such filesystems:
- May allow access to old versions of files or the filesystem, a feature sometimes called time-travel or snapshotting.
- Recover quickly after crashes because consistency checks are needed only from the last consistent point in the log. (Called roll-forward, this mechanism is explained on the talk page.)
- Tend to have good write performance.
Implementations
- John K. Ousterhout and Mendel Rosenblum implemented the first log-structured file system for the Sprite operating system in 1992.[1]
- BSD-LFS, an implementation by Margo Seltzer was added to 4.4BSD, and was later ported to 386BSD. It lacks 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 snapshotting.
- NILFS is a log-structured file system implementation for Linux by NTT/Verio which supports snapshots. It is still in development stage and not ready for production use.
- LogFS and LinLogFS are names used for various Linux log-structured file system implementations, the latest one written for Google Summer of Code 2005, however all of these projects were cancelled.
- Reiser4 calls the concept "wandering log". It has no support for snapshotting.
- ZFS from Sun is a log-structured file system which supports snapshotting. However, it uses reference-counting instead of garbage collection to manage free space.
Log-structured file systems have also been used on storage media like flash memory and CD-RW for entirely different reasons. These degrade slowly as they are written to and have a limited number of erase/write cycles:
Compared to conventional file systems, these file systems use fewer in-place writes, improving wear levelling and prolonging the life of the device.
References
- Rosenblum, Mendel and Ousterhout, John K. (February 1992) - "The Design and Implementation of a Log-Structured File System". ACM Transactions on Computer Systems, Vol. 10 Issue 1. pp26-52.
- Rosenblum, Mendel and Ousterhout, John K. (June 1990) - "The LFS Storage Manager". Proceedings of the 1990 Summer Usenix. pp315-324.