30-Second Glance
- LSM-trees turn random writes into sequential ones: buffer in a MemTable, flush to immutable sorted files (SSTables), merge in the background.
- Reads check MemTable → newest SSTable → oldest, using Bloom filters and block indexes to skip files; writes are ~10× faster than B-Trees, reads pay merge cost.
- Compaction (size-tiered vs leveled) bounds file count and reclaims overwrites — at the price of write amplification of 10–50×.
- Powers Cassandra, RocksDB, LevelDB, Bigtable, ScyllaDB: the default for write-heavy sorted data (metrics, feeds, event logs).
The Core Trick
A Log-Structured Merge-tree splits the index into a small mutable in-memory part and many immutable on-disk parts. Writes go to an in-memory balanced tree (MemTable, often a skip list or red-black tree) and to an append-only commit log for crash recovery. When the MemTable hits a threshold (e.g. 64–256 MB in RocksDB, up to 1 GB in Cassandra), it is frozen, flushed as a Sorted String Table (SSTable) — keys sorted, written sequentially — and the commit log segment is discarded. No random disk writes ever occur on the write path.
An SSTable is self-describing: sorted key → value pairs in blocks (e.g. 4–64 KB), a sparse block index (every Nth key → block offset), per-file Bloom filter, and min/max key metadata. Deletes are tombstones — a marker value that compacts away the old versions only when compaction merges past them.
Read Path: Merge Across Levels
A point read must find the newest version, so it checks MemTable first, then SSTables newest-to-oldest, stopping at the first hit (or tombstone = "not found"). Without help this is O(#files) I/O — the read amplification problem. Three structures keep it affordable:
| Optimization | What it does | Typical effect |
|---|---|---|
| Bloom filter per SSTable | Probabilistic "key definitely absent" test in RAM | ~1% false-positive rate at ~10 bits/key; skips ~99% of files |
| Sparse block index + block cache | One index lookup → one block read, cached in RAM | Hot blocks served without disk |
| Partitioned / leveled layout | Bounds files overlapping any key range | Leveled: ≤ ~1 file per level per key; keeps worst-case reads to ~levels count |
Range scans merge-sort across all levels with a heap iterator — correct but CPU- and I/O-heavy, which is why LSM range scans lag B-Trees on read-heavy workloads.
Compaction: Size-Tiered vs Leveled
Compaction merges SSTables, drops overwritten keys and expired tombstones, and keeps file count bounded. The strategy choice is the main tuning knob:
| Strategy | Merge rule | Write amp | Read amp | Space amp | Used by |
|---|---|---|---|---|---|
| Size-tiered (STCS) | Merge N same-size files into one bigger file | Low (~2–5×) | High (many overlapping files) | High (~50%+ stale) | Cassandra default, ScyllaDB |
| Leveled (LCS) | Each level 10× previous; files non-overlapping within a level | High (~10–50×) | Low (≤1 file/level/key) | Low (~10%) | RocksDB, LevelDB |
| Tiered+leveled hybrid (TWCS/universal) | Time-window or size-ratio tiers | Middle | Middle | Middle | Time-series in Cassandra/RocksDB |
Concrete feel: RocksDB leveled compaction with 10× level growth and 4 levels rewrites each byte ~10–40 times before it settles (write amplification 10–50× measured end-to-end). That is the tax funding 100K–1M+ writes/sec/node on commodity SSDs — B-Trees doing in-place page updates with fsyncs typically top out an order of magnitude lower on the same hardware.
Concrete Numbers
| Quantity | Typical value | Why it matters |
|---|---|---|
| MemTable size | 64–256 MB (RocksDB), 512 MB–1 GB (Cassandra) | Bigger = fewer flushes, more recovery replay, more RAM |
| SSTable block | 4–16 KB; block index sparse every 16th key | One disk read per point lookup after Bloom pass |
| Bloom filter | ~10 bits/key → 1% FPR | 100M keys ≈ 120 MB of filters — the real RAM cost of LSM |
| Write throughput | 100K–1M+ ops/s/node (SSD) | Sequential flush + no splits; WAL is the only sync cost |
| Write amplification | 2–5× (tiered) / 10–50× (leveled) | SSD wear + compaction CPU; the headline trade-off |
| Flush/compaction debt signal | Pending-compaction bytes growing | If compaction can't keep up, reads degrade then writes stall |
Crash Safety and Tuning Pitfalls
Durability = commit log (WAL) fsync policy. fsync every write = safe, ~1–10K ops/s; group-commit / interval fsync (e.g. every 10 ms) = 100K+ ops/s with a small loss window. Every production LSM incident story involves one of: compaction falling behind (disk fills with overlapping SSTables, p99 explodes), Bloom filters mis-sized (RAM blowout or useless 10%+ FPR), or tombstone buildup (uncompacted deletes inflate scans — Cassandra's infamous "tombstone warnings" past 1000/partition).
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| LSM-tree | Max ingest rate; sequential writes; good compression (sorted runs); cheap snapshots | Read/space/write amplification trilemma; compaction ops burden; tombstone quirks | Write-heavy sorted data: metrics, events, feeds, inboxes |
| B+Tree | Predictable reads; in-place updates; no compaction cliffs | Random-write I/O caps throughput; splits fragment | Balanced/read-heavy OLTP — see B-Tree Indexes |
| Hash index | Fastest point lookups, simplest code | No ordering; RAM-bound keyspace | Point-only KV — see Hash Indexes |
Interview One-Liners
- Q: LSM-tree in one sentence? A: Buffer writes in a sorted MemTable, flush to immutable sorted SSTables, and merge them in the background — random writes become sequential.
- Q: What is an SSTable exactly?
A: An immutable sorted
key → valuefile with block index + Bloom filter + tombstones, produced by flushing a MemTable. - Q: Why are LSM writes faster than B-Tree writes? A: No page reads, splits, or seeks on the write path — just a WAL append and an in-memory insert; disk I/O is deferred to batched sequential flushes/compactions.
- Q: What does a read cost in an LSM-tree? A: MemTable + Bloom-gated check of overlapping SSTables newest-first; Bloom filters make the common case ~1 block read, worst case O(levels).
- Q: Size-tiered vs leveled compaction? A: Size-tiered minimizes write amplification (merge same-size runs) at the cost of read/space amp; leveled minimizes read/space amp (non-overlapping levels) at 10–50× write amp.
- Q: Where do tombstones bite? A: Deletes persist as markers until compaction passes the oldest overlapping SSTable — uncompacted tombstones inflate scans and storage (Cassandra partition-tombstone failures).
- Q: Name three production LSM engines and their bias? A: RocksDB/LevelDB (leveled, read-balanced embeddable), Cassandra/ScyllaDB (tiered default, ingest-first distributed).