Designing an LSM Storage Engine: Memtables, SSTables, and Compaction

B-trees update data in place: find the page, modify it, write it back — random I/O on every write. The log-structured merge tree refuses in-place updates entirely: every write is an append somewhere, and "the value of key K" becomes a question answered by merging what multiple immutable files say about K. That one refusal — never overwrite — is why LSM engines (RocksDB, LevelDB, Cassandra, HBase, Pebble) own the write-heavy half of the database world, and why they pay for it at read time. If you design storage in an interview, this trade is the whole conversation.

The write path: memory, then immutable files

write(k,v):  append to WAL (durability) -> insert into memtable (sorted, in-memory)
memtable full (~64MB): freeze -> flush to disk as an SSTable -> new memtable

The memtable is a sorted structure (skip list, typically) absorbing writes at memory speed. The SSTable it flushes to is a sorted, immutable file of key-value pairs with a sparse index and per-block compression. Every write is sequential I/O — the WAL append and the eventual flush — which is the entire performance thesis: disks and SSDs both reward sequential writes, and SSDs additionally punish in-place rewrites (write amplification inside the FTL). Deletes fit the model as tombstones — a delete is a write that says "gone," merged like any other value and physically removed only when compaction can prove no older copy survives below it. (Deletion as a message, again.)

The read path: where the bill arrives

A key might live in the memtable, or any of dozens of SSTables. A read checks newest-to-oldest and returns the first hit:

read(k): memtable -> immutable memtables -> L0 files -> L1 -> ... -> Ln

Unmitigated, that's many file probes per read — read amplification. Three standard mitigations: Bloom filters per SSTable (skip files that definitely lack the key — one memory test kills most probes), the sparse index + block cache (a hit costs one block read), and — the big one — compaction, which bounds how many files can contain any key.

Compaction: the engine inside the engine

Compaction merges SSTables — dropping shadowed values and expired tombstones, producing fewer, sorted, non-overlapping files. It is also where the design fork lives, expressed as the amplification triangle: write amplification (bytes rewritten per byte ingested), read amplification (files consulted per read), space amplification (dead data awaiting merge). You can't win all three; compaction strategy chooses which two.

Strategy	How	Wins	Pays
Leveled (RocksDB default)	L1..Ln, each level 10× bigger, non-overlapping within a level	Reads (≤1 file/level), space	Write amp ~10× per level — data rewritten as it sinks
Size-tiered (Cassandra default)	Merge similar-sized files when enough accumulate	Writes (each byte rewritten few times)	Reads (overlapping files), space spikes ~2× during merges
FIFO / time-windowed	Never merge across time windows; expire whole files	Time-series/TTL data — near-zero amp	Only works when data dies by age

The interview-signal sentence: leveled compaction for read-heavy or space-tight workloads, size-tiered for ingest firehoses, time-windowed when data expires — and mixed levels (tiered upper, leveled lower) are what production engines actually run.

Compaction is background work competing with foreground traffic for disk and CPU, so it needs its own operability story: rate limiting, priority (L0→L1 first — L0 files overlap, and L0 buildup is the read-latency cliff), and write stalls as the backpressure of last resort: if flushes outpace compaction, the engine deliberately slows or blocks writers rather than letting read amplification grow unboundedly. When RocksDB "randomly gets slow," the answer is almost always in the compaction stats, and saying so out loud is operational credibility.

The knobs that matter

Range scans favor leveled layouts (fewer overlapping files to heap-merge) and are the one place B-trees still clearly win — an LSM range scan k-way-merges every level. Prefix Bloom filters recover some of it for prefix scans. memtable size trades recovery time (WAL replay) and flush frequency; level0_slowdown/stop set the stall thresholds; per-level compression (none on L0/L1, ZSTD below) trades CPU for the 10× level fan-out. And because SSTables are immutable, snapshots and backups are nearly free (hard-link the files), checksums live per block, and replication can ship whole files — immutability keeps paying dividends beyond the write path.

Interview probe	Answer sketch
Why do writes stall under sustained load?	Compaction debt: L0 file count crossed threshold — the engine is protecting reads
Point read p99 suddenly 10×?	Bloom filter false-positive storm, cold block cache, or L0 pileup — check files-per-read stat
LSM vs B-tree, one sentence?	LSM buys sequential writes with deferred merge cost; B-tree buys stable reads with random-write cost — pick by write:read ratio and scan needs
Where do secondary indexes live?	As another LSM (index entries are just writes) — with the same async-vs-sync consistency choice every indexed store makes

The durable idea: turn every mutation into an append, keep everything immutable, and move the cost of order from write time to a background merge you can schedule, throttle, and reason about. Once you see that shape, Kafka segments, snapshot-based replication, and even data-lake table formats read as the same design at different altitudes.