System Design Storage

Log-Structured Merge Trees

A metrics pipeline writes millions of points per second. Updating a B+ tree leaf for every point would thrash random pages. An appends to a , inserts into a , and later flushes immutable that reorganizes in the background.

The storage-engines overview names the pieces. This note goes deeper: amplification math, leveled vs tiered policies, tombstone safety, L0 debt, stalls, and how Bloom filters change the read path. Use it when you must choose and operate an LSM, not only name it.

Write → read journey

WAL first, then memtable; ack per durability policy.

Frozen memtable becomes an L0 SSTable.

Merge, drop dead versions, shape levels.

Newest-first GET

Memtables → L0 → deeper levels; filters skip misses.

What actually happens

An LSM never updates a key by seeking to its old disk location and overwriting bytes. It records a newer version. That single choice explains sequential ingest, multi-version reads, tombstones, and why compaction is not optional housekeeping—it is how the structure stays finite.

Durability still needs a (or an equivalent durable log) if you acknowledge before the memtable reaches disk. Crash recovery rebuilds memtable state from the log, then continues. Manifest/metadata commits decide which SST files belong to the live database version; copying random files out of a live directory is not a consistent backup.

The operating craft is balancing three amplifications: , , and . Compaction policy moves cost among them. Stalls appear when writers create debt faster than compactors repay it.

Write path in detail

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
  W["Client write"] --> WAL["Append WAL\n(fsync per policy)"]
  WAL --> MT["Insert memtable"]
  MT --> Full{"Memtable full?"}
  Full -->|No| Ack["Ack client"]
  Full -->|Yes| Freeze["Freeze → immutable MT\nopen new mutable MT"]
  Freeze --> Ack
  Freeze --> Flush["Flush → L0 SSTable"]
  Flush --> Comp["Background compaction"]

plaintext

Typical write steps:
1. Append to WAL (group commit / fsync policy)
2. Insert (key, seqno, value|tombstone) into mutable memtable
3. If memtable hits size limit:
     - mark immutable, allocate new mutable
     - schedule flush of immutable → L0 SST
4. Ack according to durability (memory-only vs WAL fsync)

Flush output (conceptual SST):
  data blocks (sorted keys)
  sparse index / restart points
  Bloom filter
  footer / checksums
  metadata registered in MANIFEST

Sequence numbers (or hybrid timestamps) order versions. A snapshot read ignores versions newer than its snapshot. That is why compaction cannot simply “keep only the newest key on disk” while old snapshots or MVCC readers still need older versions.

Read path in detail

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
  G["GET key K"] --> M["Check mutable memtable"]
  M --> I["Check immutable memtables"]
  I --> L0["Probe L0 SST files\n(Bloom → index → block)"]
  L0 --> Ln["Probe deeper levels\n(one file per level if leveled)"]
  Ln --> Pick["Pick newest visible version\nrespect snapshot / tombstone"]

L0 files often overlap in key range because each is a flush of whatever was in memory. That is why L0 count is a first-class health metric: every overlapping L0 file is a candidate for every point get until compaction drains them into deeper, non-overlapping levels.

A per-file turns “open this SST” into “skip with high probability” for absent keys. At 1% false positives, 100 candidate files still mean about one false-positive index check in expectation—not zero work. Range scans cannot skip via Bloom the same way; they merge iterators.

plaintext

Point GET cost (leveled, healthy):
  memtables + #L0_overlapping + ~1 file per deeper level
  + Bloom CPU + occasional block reads

Point GET cost (unhealthy):
  dozens of L0 files, each a maybe → RA explodes
  → latency cliff → often precedes write stalls

Range SCAN:
  merge-iterator across all overlapping runs
  apply snapshot visibility + tombstones
  Bloom barely helps; key-range metadata helps more

Amplification math you can defend

plaintext

Definitions (pick a boundary and stick to it):
WA = bytes_written_to_disk / logical_bytes_ingested
RA = bytes_or_files_read / logical_result_bytes
SA = bytes_on_disk / live_logical_bytes

Toy leveled model (size ratio R=10, update-heavy):
  A key updated uniformly may be rewritten once per level
  Rough WA ≈ O(R × #levels) in pessimistic sketches
  Practice: measure; workloads and compression dominate

Toy tiered model:
  Merge N equal runs → each byte rewritten less often
  Lower WA, higher RA (more runs to probe), higher peak SA

Worked space example:
  Live data = 500 GB
  SA = 1.3 → ~650 GB occupied (leveled-ish)
  SA = 3.0 → 1.5 TB occupied (debt / tiered / tombstones)
  Disk headroom must also absorb compaction temps

Policy	WA tendency	RA tendency	SA tendency
	Higher	Lower (stable)	Lower (~1.x–2×)
	Lower	Higher	Higher peaks
Time-window / FIFO	Low if immutable windows	Depends on windows	Bounded by retention

Leveled vs tiered: picking a shape

Choose leveled when

Point-read latency and stable RA matter more than peak ingest
You can spare sustained compaction bandwidth
Disk space is tighter than CPU/IO rewrite budget

Choose tiered-like when

Ingest dominates and reads tolerate more runs
You have headroom for temporary merge space
Bulk loads and immutable time series fit the shape

Production engines blur the line (universal compaction, hybrid leveled+L0 thresholds, per-CF policies). In an interview, state the WA/RA/SA movement first, then name the engine’s concrete policy as an example—not as a universal law.

Tombstones, snapshots, and resurrection

Deleting key K appends a . Compaction may drop older values only when no retained snapshot still needs them, and may drop the tombstone only when no older file that still contains K could become visible again without the marker.

plaintext

Unsafe early drop:
  File_old:  K=v1
  File_new:  K=<tombstone>   ← compacted away too soon
  Later read sees File_old only → K resurrects as v1

Replica hazard:
  Node A deletes K; Node B still has K=v1
  Repair without tombstone/version rules can reintroduce v1

gc_grace / snapshot retention:
  Keep tombstones until anti-entropy and snapshot windows close

Write stalls and operational signals

L0 file count

Rising L0 means flushes outpace L0→L1 compaction. Reads slow first; then kick in. Fix ingest rate, raise compaction concurrency carefully, or reduce per-flush size only with eyes on WA.

Pending compaction bytes

Bytes scheduled to rewrite estimate how long recovery to a healthy shape will take. Compare to device write bandwidth with headroom for the foreground WAL/flush path.

Immutable memtable pile-up

If flushes cannot keep up, immutable memtables accumulate and memory pressure rises. Stall thresholds exist so the process does not OOM while pretending to accept more writes.

Disk headroom

Compaction needs temporary space for output files. Running disks at 95% full turns routine merges into outages. Budget for SA peaks plus compaction temps, not only live size.

Sizing sketches for interviews

plaintext

Ingest: 50k writes/sec × 500 B ≈ 25 MB/s logical
WAL fsync path must sustain ≥25 MB/s (+overhead)
If leveled WA ≈ 15× on updated keys, steady disk write≈ 375 MB/s
  → need device + compaction budget that fits, or accept debt

Memtable 128 MB → flush every 128MB/25MB/s ≈ 5 s
  → L0 accumulates 12 files/min if L0 compaction lags

Bloom memory:
  200 SST files × 10M keys × 10 bits ≈ rough upper bound;
  real filters cover per-file key counts; size from measured keys
  10 bits/key @ 1% FP is the usual starting rule of thumb

Block cache:
  Size for hot data blocks + indexes + filters
  Filters in cache matter as much as data for negative-heavy GET

Measure WA

bytes_written / logical_ingest over a steady window.

Watch L0

L0 count predicts read latency and impending stalls.

Budget space

live × SA_peak + compaction temps + growth.

Where LSMs show up

Wide-column and KV stores: Cassandra, Scylla, Bigtable-style systems flush memtables to immutable files and compact. RocksDB underpins many products (MyRocks, Cockroach storage engines historically, TiKV, etc.).

Search and analytics adjacent: Lucene’s segment merge is LSM-shaped (immutable segments + merges). Time-series stores often pair LSM or segment merge with time partitioning.

Embedded / mobile: LevelDB/RocksDB-style engines when write buffering and crash recovery matter more than classic B-tree update-in-place.

Contrast remains: if your workload is update-heavy OLTP with many secondary indexes and tight p99 point reads on a hot working set, a B+ tree engine may still be the better default. LSM is not “newer therefore better”; it is a different amortization of I/O.

Trade-offs checklist

Ingest vs rewrite. Sequential writes look cheap until compaction tax is included in the capacity plan.

Freshness of shape vs CPU. More aggressive compaction lowers RA/SA now and burns bandwidth now.

Filters vs memory. Lower false-positive targets multiply bits per key across every SST.

Large values. Rewriting multi-MB values through levels dominates WA; consider blob separation / value log designs when payloads dwarf keys.

Choosing and explaining LSM trees

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

An LSM writes to a WAL and memtable, flushes immutable sorted SSTables, and compacts them in the background instead of updating pages in place.

Reads search newest-first across memtables and files; Bloom filters skip files that definitely lack the key.

Compaction policy trades write, read, and space amplification; stalls appear when debt exceeds configured limits.

When it belongs

High sustained write throughput matters and sequential I/O is available.

You are designing or operating Cassandra/RocksDB-style storage.

You need to explain why write-heavy systems still burn disk bandwidth at idle (compaction).

How it fails

L0 / compaction debt → read latency spikes and write stalls.

Tombstones dropped too early → data resurrection locally or via repair.

Disk full during compaction temps → merge failures and outages.

Trade-offs to weigh

Leveled: lower RA/SA, higher WA. Tiered: lower WA, higher RA and SA peaks.

Larger memtables: fewer flushes, bigger flush latency and recovery chunks.

Stronger Bloom filters: fewer disk touches, more RAM.

Common misunderstandings

Confusing flush with compaction.

Claiming Bloom filters make range scans cheap.

Sizing disks for live data only and ignoring SA + compaction headroom.

Saying LSM has no write amplification because the client write was an append.

Wrap-up

Operate LSMs by watching L0, pending compaction, SA, and stall metrics—not only QPS. Choose the compaction shape for the amplification mix you can afford, and treat tombstones as distributed correctness state, not local garbage.

Primary sources

Key takeaway

LSM trees amortize writes by appending and merging later. Your job is to budget the merge tax (WA), keep read paths from drowning in overlapping files (RA), leave disk for debt and temps (SA), and never drop tombstones before every older version is truly gone.