Weekly Paper Notes — 🔁 Seminal Paper of the Week, 2026-08-01. Area: Operating Systems / Storage.
Authors: Mendel Rosenblum, John K. Ousterhout (University of California, Berkeley) Published: ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992 (SOSP ‘91) DOI: 10.1145/146941.146943
Why this paper still matters
Almost every high-performance storage system built in the last fifteen years is a log-structured file system wearing a different name. LevelDB, RocksDB, Cassandra, HBase, Kafka, every SSD’s flash translation layer, ZFS’s copy-on-write, btrfs, WiredTiger, Lucene’s segment merges — all of them convert random writes into sequential appends and then run a background process to reclaim space. That entire design lineage traces back to one 1991 SOSP paper that was, at the time, arguing against the prevailing consensus about what a file system should do.
What makes it worth rereading isn’t the mechanism, which you’ve absorbed by osmosis if you’ve touched any modern storage engine. It’s the argument. Rosenblum and Ousterhout didn’t start from “sequential writes are faster than random writes” — everyone knew that. They started from a prediction about how hardware trends would reshape workloads, and they were right in a way that turned out to be robust across three subsequent hardware revolutions none of them anticipated.
The setup: a bet on where the bottleneck was going
The prediction had three parts.
One: CPU speed was growing much faster than disk access time. Disk transfer bandwidth improves steadily with density; seek time and rotational latency are mechanical and barely improve at all. So any workload dominated by seeks would fall further behind the CPU every year.
Two: main memory was growing fast, and memory would be spent on file caches. This was the crucial move. If caches get large enough, reads mostly stop hitting the disk. The disk stops being a read-service device and becomes almost purely a write-service device — an archive that absorbs the residue of what the cache can’t hold.
Three: therefore, disk traffic would become write-dominated, and write performance would become the whole ballgame.
Against that, look at what the Berkeley Fast File System — the state of the art, and the direct ancestor of every Unix file system in production — actually did. FFS laid out files with careful attention to locality, and it was genuinely good at reading a large file. But creating a small file in FFS meant writing at least four things in four different places: the file’s inode, the file’s data block, the directory’s data block, and the directory’s inode. Each in a different region of the disk. Each preceded by a seek.
The paper’s measurement of this is the number that motivates the design: FFS spent under 5% of the disk’s potential bandwidth doing useful work on a small-file workload, and used the rest seeking. The disk was idle-by-mechanics roughly 95% of the time. And worse, FFS wrote metadata synchronously, so applications blocked on those seeks rather than letting the OS batch them.
The core idea
Buffer all changes — data blocks, inodes, directory entries, everything — in memory, and periodically write them out in one large sequential transfer to the end of a log. The log is the file system. There is no other copy. Nothing is ever updated in place.
That’s it. The idea is small enough to state in two sentences, and almost all of the paper’s difficulty lives in the consequences.
The four problems that fall out of it
1. Where did the inode go?
In FFS, inodes live at fixed disk addresses computed from the inode number. In LFS, an inode moves every time it’s written, because writes always go to the log’s head. So LFS adds an inode map: a table mapping inode number to the current disk address of that inode. The inode map is itself written to the log in blocks, but it’s small enough to be kept almost entirely cached in memory, so the extra indirection costs essentially nothing on the read path. A fixed-location checkpoint region holds the addresses of the inode map blocks — the one and only piece of the file system at a known address.
This is the same trick, structurally, that an SSD’s flash translation layer plays with logical-to-physical page mapping. The problem is identical: the thing moved, and something has to remember where.
2. Free space fragments — the cleaner
A log that only appends eventually runs out of disk. The space occupied by superseded blocks — old versions of files that have since been rewritten — is dead but scattered throughout the log. You cannot simply reuse a dead block, because then your writes stop being sequential and you’ve reinvented FFS.
LFS divides the disk into large fixed-size segments (512 KB or 1 MB) and requires that a segment be written sequentially in its entirety. A background cleaner reads several partially-live segments, identifies the blocks still in use, writes those live blocks compacted into a new segment, and marks the source segments free. Reading three segments that are 25% live yields one full segment of live data and two entirely free segments.
To do this, the cleaner has to answer “is this block still live, and which file does it belong to?” without consulting every inode on the disk. LFS’s answer is the segment summary block: each segment carries a header identifying, for every block within it, the inode number and block offset it belongs to. Liveness is then a single check — look up the inode, ask whether it still points at this address. If it points somewhere else, the block is garbage. This also means the file system needs no free-block list and no bitmap; segment summaries carry the information.
3. Which segments to clean, and when — the part that took real work
This is where the paper does its best empirical work, and the part most often skipped in summaries.
The obvious policy is greedy: always clean the segment with the least live data. The paper’s simulations show this performs worse than expected, and the diagnosis is subtle. Under a workload with hot and cold files, cold segments — those holding data that rarely changes — decay very slowly toward zero liveness. Greedy cleaning keeps deferring them in favour of hot segments, but hot segments will free themselves shortly anyway, since their blocks are about to be overwritten. Cleaning a hot segment early wastes work that the workload would have done for free.
The insight is that free space in a cold segment is more valuable than free space in a hot segment, because it stays free longer. So LFS uses a cost-benefit policy:
benefit / cost = ( (1 - u) * age ) / (1 + u)
where u is the segment’s utilisation (fraction still live) and age is the time since the youngest block in it was written. The (1-u) term is the free space you’d recover; age weights toward stable data; the (1+u) denominator charges for the read-and-rewrite cost of the live blocks. Clean the segment with the highest ratio.
This one formula moved the simulated system from roughly 50% of bandwidth wasted on cleaning to about 20%. It also introduced the design pattern — cost-benefit segment selection with an age term — that every LSM-tree compaction policy has been reinventing ever since. If you have ever tuned RocksDB compaction and felt the tension between write amplification and space amplification, you are standing in the crater this paper left.
The paper also adds the age sort: when the cleaner rewrites live blocks, it groups them by age, so that stable data collects into stable segments and volatile data into volatile ones. Segregating hot from cold makes the cost-benefit policy sharper over time. Modern flash controllers do exactly this and call it wear-levelling-aware data placement.
4. Crash recovery becomes almost trivial
This is the underrated payoff. In FFS, a crash leaves the disk in an arbitrary state and recovery means fsck — scanning the entire disk to reconstruct consistency, taking time proportional to file system size, and taking longer every year as disks grew.
In LFS, the log is the recovery structure. Recovery reads the last checkpoint region and then rolls forward through the segments written after it, using segment summary blocks to reconstruct what happened. Recovery time is proportional to the amount of data written since the last checkpoint, not to disk size. The paper reports recovery times measured in seconds where FFS would take minutes to hours.
Journaling file systems reached a similar destination — ext3, NTFS, JFS — but by a different route: keep the update-in-place structure and bolt on a write-ahead log for consistency. LFS’s claim is that if you’re going to maintain a log anyway, you may as well let it be the file system and skip writing everything twice.
The results, and the honest caveat
Sprite LFS wrote small files roughly ten times faster than SunOS’s FFS, and used around 70% of raw disk bandwidth on write-heavy workloads against FFS’s 5–10%. On large-file reads and writes it was comparable, and on sequential reads of files that had been written randomly, it was somewhat worse — because logical order and physical order diverge, which is the intrinsic cost of the design.
The famous caveat came four years later. Seltzer et al.’s 1995 evaluation of BSD-LFS showed that under sustained write pressure on a nearly-full disk with a transaction-processing workload, cleaning overhead could consume enough bandwidth to erase the advantage entirely. That critique is correct and it is the reason LFS never displaced FFS as a general-purpose Unix file system. It is also the reason every LSM engine ships with compaction tuning knobs and every SSD vendor cares about over-provisioning: the cleaner is not free, and its cost is a function of how full and how hot your storage is.
Why this design has outlasted everything around it
Rosenblum and Ousterhout were right about the trend and wrong about the medium, and the design survived that anyway — which is the strongest possible evidence that they’d found something structural.
They bet that memory growth would make disks write-dominated. That happened. Then flash arrived, and flash has a property nobody was modelling in 1991: you cannot overwrite a page in place at all, you must erase a whole block first. Which means every SSD ever shipped contains a log-structured file system in its firmware, whether or not the OS above it knows. The FTL buffers writes, appends them to a log of free pages, maintains a mapping table (the inode map, renamed), and runs garbage collection (the cleaner, renamed) with a victim-selection policy that trades recovered space against copy cost (cost-benefit, renamed).
Then distributed storage arrived, and the same shape appeared again for a third reason: replicated systems want an append-only durable record so replicas can be brought into agreement by replaying it. Bigtable’s SSTables, Cassandra’s commit log and memtables, Kafka’s partition logs, every write-ahead log in every database. The reason keeps changing — mechanical seek cost, then flash erase-block granularity, then replication and recovery semantics — but the answer keeps being the same: append sequentially, remember where things went, compact in the background.
That’s what makes it seminal rather than merely influential. A paper that solves the problem it was aimed at is good work. A paper whose solution turns out to be the right answer to two more problems that didn’t exist yet has found something true about the structure of storage, not about 1991’s disks.
Read alongside
- McKusick, Joy, Leffler & Fabry, “A Fast File System for UNIX” (TOCS 1984) — FFS, the system LFS is arguing against. Read this first; the LFS argument doesn’t land without it.
- Seltzer, Bostic, McKusick & Staelin, “An Implementation of a Log-Structured File System for UNIX” (USENIX 1993) and Seltzer et al., “File System Logging Versus Clustering” (USENIX 1995) — the rigorous critique of cleaning overhead. Essential counterweight.
- O’Neil, Cheng, Gawlick & O’Neil, “The Log-Structured Merge-Tree” (Acta Informatica 1996) — LFS’s ideas applied to indexed data; the direct ancestor of LevelDB, RocksDB, and Cassandra.
- Chang et al., “Bigtable” (OSDI 2006) — where the log-structured pattern entered mainstream distributed systems practice.
- Bonwick & Moore, “ZFS: The Last Word in File Systems” (2004) — copy-on-write at file-system scale, the other branch of the family tree.
- Agrawal et al., “Design Tradeoffs for SSD Performance” (USENIX ATC 2008) — the flash translation layer as a log-structured file system, made explicit.
Links
📄 ACM DOI 10.1145/146941.146943 · 📄 PDF (Stanford)
Part of the Weekly CS Paper Digest series. Diagram is original work for this post.