Hall of FameMendel Rosenblum, John K. Ousterhout199153 min readpaperadvanced
The Design and Implementation of a Log-Structured File System
Summary
The paper introduces a log‑structured file system (LFS) that writes all data sequentially to a log and uses a segment cleaner to reclaim space. In the Sprite LFS prototype, write throughput reaches 65‑75 % of raw disk bandwidth, an order of magnitude faster than Unix for small files, while reads remain comparable.
- LFS stores all file data and metadata in a single on‑disk log, eliminating random writes and seeks.
- Segments are cleaned by a cost‑benefit algorithm that separates hot (young) and cold (old) data.
- Crash recovery only scans the tail of the log, making it much faster than traditional file‑system scans.
- Sprite LFS achieves ~70 % of disk bandwidth for writes versus 5‑10 % for Unix FFS, especially for small files.
File‑system engineers and storage researchers should study LFS because its log‑based design and cleaning policy underpin many modern systems such as SSD write‑amplification mitigation and log‑structured merge trees.
9/10
