The Design and Implementation of a Log-Structured File System

This book introduces the log-structured file system (LFS), a novel approach to disk storage management where all modifications are written sequentially in a log-like structure.

This design significantly speeds up file writing and crash recovery compared to traditional Unix file systems.

The log contains indexing information for efficient file retrieval.

To maintain large free areas for fast writing, the log is divided into segments, and a segment cleaner compresses live data from fragmented segments.

The authors implemented a prototype called Sprite LFS, which outperforms Unix file systems by an order of magnitude for small-file writes while matching or exceeding performance for reads and large writes.

Even with cleaning overhead, Sprite LFS can utilize 70% of disk bandwidth for writing, compared to 5-10% for Unix systems.

The book includes simulations demonstrating the efficiency of cleaning policies and discusses the design, motivation, and analysis of LFS, which has influenced many modern file and storage systems.