Log-structured file system

From Free net encyclopedia

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.

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 a 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. Thus, a log-structured file system is a journaling filesystem in that the entire file system is a journal.

Such filesystems:

• May allow access to old versions of files, a feature sometimes called time-travel or snapshotting.
• Recover quickly after crashes because no consistency checks are needed. Instead, the file system simply rolls forward from the last consistent point in the log.
• 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. An implementation by Margo Seltzer, the Log-structured File System, was added later to 4.4BSD, and thence was ported to NetBSD.

NILFS is a log-structured file system implementation for Linux which supports snapshots. As of April 2006, however, it is still in alpha and not ready for production use.

More recently, log-structured file systems have 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 which provide better wear levelling on such media in that they do not update data structures in-place as frequently as conventional file systems do.

References

• Rosenblum, Mendel and Ousterhout, John K. (June 1990). "The LFS Storage Manager." Proceedings of the 1990 Summer Usenix. 315-324.
• Rosenblum, Mendel and Ousterhout, John K. (February 1992). "The Design and Implementation of a Log-Structured Filesystem." ACM Transactions on Computer Systems. 10(1). 26-52.