Log-Structured Storage

In one sentence

You think log-structured storage is a magic trick for making writes fast. It is really a single trade: replace "random in-place update" with "sequential append plus merge-after-the-fact." None of the write cost disappears — all of it is charged to read amplification and space amplification, and repaid in instalments by background compaction.

Glossary

Where it sits

This is the closing chapter of Part I, "Storage Engines." Chapters 2–6 covered the B-Tree lineage: sorted, updated in place. Chapter 6's copy-on-write and Bw-Tree were already edging toward "stop updating in place," and this chapter takes that road to its end — never update in place at all, only append. It maps onto the whole write-optimized branch of real systems: LevelDB, RocksDB, Cassandra, HBase. Next comes Part II: distributed systems.

The problem it solves

The pain is in the B-Tree write path. To increment an 8-byte counter it must read the whole page into memory (pages are typically 4KB–16KB), change those 8 bytes, and write the whole page back — and for crash safety it must first append to the WAL. An 8-byte logical write becomes tens of kilobytes of physical writes, and because those pages are scattered through the file, the writes are random.

How far apart are random and sequential? Spinning disks manage random IOPS in the 100–200 range while sequential bandwidth comfortably exceeds 100MB/s; SSDs have no head, but flash's "erase only in whole blocks" rule makes small random writes expensive in its own way. The gap is two to three orders of magnitude. So write-heavy workloads — time-series metrics, logs, chat messages, social counters — hit the wall on the write path first: not because the CPU is short, but because the disk is being forced to do the thing it is worst at. This chapter's bet is blunt: turn every write into a sequential append, and find another way to pay for reads and space.

The core, explained

1. One mutable table in memory, many immutable tables on disk

An LSM-tree (log-structured merge-tree) splits storage into two components with opposite temperaments. The in-memory table is mutable — that is the memtable, which stays sorted as writes are inserted. Everything on disk is immutable — a full memtable is frozen and written out in one sequential pass as an SSTable, after which not a byte changes.

Crash safety comes from the WAL: a write is appended to the log before entering the memtable, so a crash is repaired by replay; once the memtable has been flushed successfully, its WAL segment can be discarded. Across the whole write path the disk does exactly two things: append to the WAL, and write out an SSTable sequentially — never an in-place modification.

2. Updates and deletes: everything is an append, deletion is a tombstone

If files are immutable, "change" and "delete" need new definitions. An update writes a new version while the old one still sits in an older SSTable. A delete writes a tombstone — the book calls it a "dormant certificate": it removes nothing, it only declares that from this timestamp onward the key is void.

That yields a counter-intuitive rule: deleting data in an LSM makes the disk footprint grow first; real reclamation waits for compaction to roll over it. And deciding when a tombstone may itself be dropped needs care: as long as any older SSTable might still hold an earlier value for that key, the tombstone must stay. Drop it early and the old value resurfaces — resurrected data. Cassandra's gc_grace_seconds (ten days by default) is exactly that safety window.

3. The read path: merging, reconciliation, and that cheat-strip

Writes got simple, so reads got complicated. A key may live in the memtable and in several SSTables at once, so a read does two things. Merge-iteration — each SSTable is internally sorted but their key ranges may overlap, so a priority queue (min-heap) drives a k-way merge: repeatedly take the smallest key across the per-table cursors and advance that one, which turns many sources into a single globally ordered stream with one cursor per table. Reconciliation — when several records for the same key come out, the newest by timestamp / epoch wins, and if the newest is a tombstone the key counts as absent. "Newest wins" is the bedrock that makes the whole design consistent with itself.

In the worst case a point lookup touches every SSTable — that is read amplification. The first wall against it is the Bloom filter: one per SSTable, a handful of hash functions map the key into a bit array, and a single zero bit proves the key is definitely not in this file, so the file is skipped entirely; all ones still only means "maybe." The cost is a direct trade of memory against false-positive rate — RocksDB's own table puts 9.9 bits per key at roughly 1% false positives. A hundred million keys at 10 bits each is only ~125MB of memory to eliminate 99% of pointless file reads, which is an extremely good deal. But it only helps point lookups; range scans get nothing from it.

4. Compaction: the repayment mechanism

What happens without it? SSTables multiply without bound, read amplification degrades linearly, and overwritten versions and tombstones occupy disk forever. So the background is always doing the same job: read several SSTables → merge → reconcile → drop expired versions and eligible tombstones → write new files → delete the old ones. The elegant part is that immutability makes compaction unusually easy to write: sorted inputs mean sequential reads, a fresh output file means sequential writes, and no data locking is needed at all — most of the concurrency and torn-page trouble that Chapter 5's B-Tree recovery had to handle is dissolved by the structure itself.

Compaction strategy is the selection decision worth memorizing from this chapter. Three dominate:

• Leveled — the LevelDB / RocksDB default and Cassandra's LCS. Apart from L0, which is allowed to overlap, key ranges never overlap within a level, and each level is about 10× the capacity of the one above. LevelDB's implementation doc is very concrete: a log becomes an SSTable at about 4MB, more than 4 files at L0 triggers compaction, and level L is capped at 10^L MB. The payoff is at most one file per level; the price is that the same row is rewritten again and again as it descends.
• Size-tiered — Cassandra's STCS and RocksDB's universal compaction. Once enough similarly sized SSTables have accumulated (4 by default in Cassandra) they are merged into a bigger one, and so on up. Write amplification is far lower, but one key may be spread over many tables, and a big merge keeps old and new alive at once, briefly nearly doubling disk usage.
• Time-window (TWCS) — built for time-series and TTL data: bucket SSTables by time window and compact each window into a single SSTable at its end. Data lives and dies in batches, so an expired file is simply deleted whole. It assumes data arrives roughly in time order.

5. Three amplifications and the RUM conjecture

The ledger can now be closed. Judging a storage engine comes down to three numbers — read, write and space amplification — and they cannot all be optimal at once; you get to pick two. That is the RUM conjecture the chapter cites (Athanassoulis et al., EDBT 2016): of Read, Update and Memory overheads, driving two down necessarily pushes the third up. B-Trees sit in the read-optimized corner — read amplification near 1, space compact, write amplification high. LSM-trees sit in the write-optimized corner — a fully sequential write path, but reads must merge and the disk holds several versions. Compaction strategy is how you fine-tune that mix inside the LSM corner.

6. Unordered log structures, and the logs beneath your log

A log structure does not have to be sorted. Bitcask (Riak's storage engine) takes that to the extreme: on disk it is a chain of purely appended, entirely unsorted data files, while memory holds a hash table called the keydir recording which file and offset holds each key's current value. Every read is therefore one in-memory hash lookup plus one positioned disk read. The price is equally blunt: every key must stay resident in memory, and range scans are not supported. WiscKey is the compromise: key-value separation keeps the key and a pointer in the LSM-tree while the value goes into an append-only vLog, so compaction moves keys but not values and write amplification drops sharply, at the cost of turning range scans into many random reads of the vLog. The rule is clear: the larger the values, the more key-value separation pays.

The last section is the most "database internals" of all: there are more logs beneath your log. The filesystem may itself be log-structured, and an SSD's FTL certainly is — flash erases in blocks and writes in pages, so it never updates in place; it writes to a free page, marks the old one invalid, and collects garbage later. The nasty part is that write amplification across layers multiplies rather than adds: an LSM rewriting a record 10 times, times whatever the FTL's garbage collection adds, can land tens of times the logical write volume on the flash cells. Worse, each layer's garbage collection is blind to the others — the database may have just declared a batch of data dead while the FTL is busy relocating it to a fresh block. The book's direction is to flatten the stack: bypass the filesystem and FTL and manage raw flash directly. The lesson generalizes — "sequential writes" is an assumption that may simply not hold in a layer you cannot see.

Key trade-offs and how to choose

An anchor scenario first: an IoT platform with 500,000 devices reporting every 10 seconds — a steady 50,000 writes/sec — where queries are almost entirely "the last 24 hours for one device" and data expires after 30 days. A B-Tree collapses on the write path here: a few dozen bytes of point write drags a multi-kilobyte page, randomly. An LSM makes every write sequential, and TWCS lets each batch of expired data be deleted as a whole file. Conversely, an account balance table that is read-heavy and reconciled by primary-key ranges is still far easier on a B-Tree.

Table 1 · LSM-tree vs. B-tree (this chapter against Chapters 2–6)

Table 2 · Choosing a compaction strategy (defaults as stated in each project's own docs)

Table 3 · Sorted vs. unsorted: the second fork in log-structured design

Why it matters / in real systems

The weight of this chapter is that nearly every write-optimized store you use today is an instance of it. The lineage starts with Google's Bigtable (OSDI 2006), which fixed the memtable + SSTable + compaction skeleton; LevelDB turned it into an implementation anyone can read; Meta forked RocksDB from LevelDB, and it became a storage substrate embedded almost everywhere — MyRocks, TiKV, CockroachDB's Pebble, stream-processing state stores. Cassandra, HBase and ScyllaDB are the other branch of the same family.

For day-to-day decisions it hands you a set of criteria you can say out loud: when choosing, ask "what is the read/write ratio, how big are the values, do we need range scans?"; when debugging, ask "which amplification is hurting right now — read, write or space?" Asked in an interview why LSM writes are fast, the answer is not "because they are sequential" but "because it swapped random writes for sequential ones and deferred the cost into compaction" — the second half is what separates answers.

Pitfalls and disputes

• "LSM writes are simply faster than B-tree writes" — half true. It only swaps random writes for sequential ones; the total volume written is actually larger. Under sustained write pressure, compaction competes with the foreground for IO and shows up as latency spikes or outright write stalls.
• "Deleting should free space" — wrong. A delete writes a tombstone, so the footprint grows before it shrinks; "we deleted a lot of data and the disk filled up" is the classic operational surprise. The mirror-image mistake is reclaiming tombstones too early: while any older SSTable might still hold a previous value, dropping the tombstone resurrects deleted data — which is why deletes in Cassandra must be planned alongside the repair cycle.
• "Add a Bloom filter and slow reads are cured" — only half of them. It helps point lookups and does nothing for range scans, and it can only ever prove absence, never presence.
• "Pick a compaction strategy once and you're done" — no. This book was written in 2019; Cassandra has since introduced the Unified Compaction Strategy (UCS), and its docs now call it "the best recommendation for all workloads today." The three-way split is still the right way to understand the space, but it is no longer the latest answer.
• RUM is a conjecture, not a theorem. It has no rigorous proof and is a qualitative description of the design space — better used to ask ("which of the three did I just sacrifice?") than to conclude.

Takeaways