The design and implementation of a log-structured file system

TLDR

A log‑structured file system writes all modifications sequentially in a log‑like structure, speeding up file writes and crash recovery, and uses a single log that contains indexing information for efficient file retrieval. The paper introduces a log‑structured file system and presents simulations demonstrating the efficiency of a simple cleaning policy based on cost and benefit. The design segments the log and employs a segment cleaner to compress live data from heavily fragmented segments, preserving large free areas for rapid writes. The prototype Sprite LFS outperforms current Unix file systems by an order of magnitude for small‑file writes, matches or exceeds Unix performance for reads and large writes, and can use 70% of disk bandwidth for writing even when cleaning overhead is included, compared to 5–10% for Unix systems.

Abstract

This paper presents a new technique for disk storage management called a log-structured file system. A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, we divide the log into segments and use a segment cleaner to compress the live information from heavily fragmented segments. We present a series of simulations that demonstrate the efficiency of a simple cleaning policy based on cost and benefit. We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes. Even when the overhead for cleaning is included, Sprite LFS can use 70% of the disk bandwidth for writing, whereas Unix file systems typically can use only 5--10%.