Section 8: Where a Write Becomes a Promise - Deep Dive: The Storage Engine (LSM)

Executive Summary: This section descends into a single node and answers the question Section 7 left at the door: how does a random write become durable in under 20ms, thousands of times per second, on one commodity machine? We derive the log-structured merge tree from that constraint rather than reciting it — WAL, memtable, SSTables, leveled compaction — then price what the structure costs: bloom-filter RAM measured in gigabytes, write amplification measured in terabytes per day, and compaction debt as the operational metric that actually pages Mira. We close with the honest paragraph most candidates skip: the workload where a B-tree would have been the right answer.

Section 7 walked the write down to the last hop: the coordinator fans put(cart:8842) to three replicas, and node n17 must append the bytes, fsync, and ack — its slice of a write p99 budget of 20ms, with the quorum round trip already spending part of it. Now zoom all the way in. The interviewer draws a box labeled "storage engine" and says: "Open it." This is where the Single-Node Thinker finally gets to shine — and where the Paper Reciter, who can chant "LSM tree" but not say why, runs out of paper.

Deriving the Engine from the Constraint

Start from the workload, not the acronym. This fleet absorbs 100K writes/s on average and 300K/s at peak, spread across 64 nodes — each node sustaining up to ~10K writes/s of 1KB values, dominated by overwrites and TTL churn against keys scattered uniformly by the hash ring. Uniformly scattered is the killer word: consistent hashing deliberately destroyed all locality, so every write lands at a random point in a ~4.7TB per-node keyspace.

Now try the naive design: a sorted on-disk structure updated in place. Every random write becomes read-modify-write of a page somewhere in those terabytes, plus an fsync to make it durable. Even NVMe, which forgives random reads, punishes scattered small writes — and an fsync per write caps you far below 10K/s. A hash-file store à la Bitcask fixes the write path (append-only) but demands the entire key index in RAM — and this node's share of 100 billion keys does not fit. Rejected for a reason, not by fashion.

The remaining door is the one every high-churn store walks through: never update in place; only append sequentially, and sort later. That sentence is the LSM tree. Everything else is bookkeeping:

1. WAL append — the write is appended to a write-ahead log and fsynced. This is the durability point: once the fsync returns, n17 can ack, and the acked write survives a power cut. Fsyncs are group-committed — dozens of writes share one flush every millisecond or two — so durability costs ~1–2ms amortized, comfortably inside the 20ms budget even after the quorum round trip.
2. Memtable — the same write goes into a sorted in-memory structure (typically a skiplist). Reads see it instantly; the disk hasn't been asked to do anything random.
3. Flush — when the memtable reaches 128MB, it is written out as one long sequential burst into an immutable, sorted SSTable, and a fresh memtable takes over. Sequential, large, append-only: the one I/O pattern every storage device loves.
4. Compaction — SSTables pile up, so a background process continually merges them level by level (leveled compaction), discarding overwritten versions, expired TTLs, and aged-out tombstones, keeping ~90% of the data in the bottom level as a few large, sorted, non-overlapping files.

Key Insight: The LSM tree is not a data structure you choose; it is the conclusion of an argument. Random durable writes at ~10K/s per node on terabytes of data force sequential append plus deferred sorting. A candidate who can run that derivation on the whiteboard owns the mechanism; one who can only name it is reciting the Dynamo reading list.

Quick check before moving on: