< Back to index

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 file systems 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 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 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.

Due to the seek and rotational latencies of disk access, write operations in traditional file systems are slow and do not fully utilize data bus capacities. With long sequential writes, log-structured file systems more fully utilize data bus capacities.

Such filesystemsRosenblum, Mendel and Ousterhout, John K. (February 1992) - "[http://www.hhhh.org/perseant/lfs/lfsSOSP91.ps.gz The Design and Implementation of a Log-Structured File System]". ACM Transactions on Computer Systems, Vol. 10 Issue 1. pp26-52.):
* 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.Rosenblum, Mendel and Ousterhout, John K. (June 1990) - "[http://www.hhhh.org/perseant/lfs/lfs-storage.ps.gz The LFS Storage Manager]". Proceedings of the 1990 Summer Usenix. pp315-324.)
* 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 is a log-structured file system, but it calls the concept "wandering logs". It has no support snapshotting, yet.
* 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.
* There is a log-structured file system in development at Charles University, Prague. [http://aiya.ms.mff.cuni.cz/lfs/]It is available for recent versions of the Linux kernel. The major features of this project are a working garbage collector, snapshots and indexed directories.

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:
* UDF, and
* JFFS2 are both log-structured file systems.
Compared to conventional file systems, these file systems use fewer in-place writes, improving wear levelling and prolonging the life of the device.

Disadvantages of a log-structured file system



* It consists of a sequential log of different data files chained together. When you delete any file you will create holes in the log and to access this space later we need to have indirect addressing in place which adds overhead. This is solved in modern log-structured file systems by using a garbage collector that defragments the log.
This entry uses material from from Wikipedia, the leading user-contributed encyclopedia. It is licensed under the GNU Free Documentation License. Disclaimer.