LSM Trees — MemTable, SSTables & Compaction
MemTable → immutable → flush SSTable; leveled vs size-tiered compaction; blooms; RocksDB/Cassandra model.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Leveled default vs size-tiered ingest
Prefer
Leveled compaction when point reads matter (RocksDB default-ish)
Lower levels keep non-overlapping key ranges. Read amp stays bounded. You pay more rewrite — that is the WA side of the triangle.
- L0 may overlap; L1..Ln target a size ratio (often ~10×).
- Blooms skip files; block cache serves hot blocks.
- Tune MemTable and L0 file count before you blame SSD.
Alternative
Size-tiered as a silent default on a read-heavy API
Similar-sized runs merge cheaply (often lower WA) but overlap explodes RA and transient space amp. Fine for some Cassandra ingest tables; painful for point-lookup SLOs.
- Tombstones linger until compaction past retention rules.
- Flushes outpacing compaction → L0 debt → write stall.
- A pure append log without indexes is ingest-only, not a store.
Put, then get
Writes are sequential. Reads merge versions. Compaction is the janitor.
- 1
WAL then MemTable
Skiplist / in-memory tree. Optional only if replicas alone are durability. - 2
Freeze and flush
Immutable MemTable → sorted SSTable (data + index + filter) into L0. - 3
Compact when a level is too large
Merge, drop obsolete keys and eligible tombstones, write new SSTables. - 4
Read: newest wins
MemTables → L0 → lower levels. Blooms cut negative I/O.
Overview
Log-Structured Merge-Trees buffer writes in a MemTable, freeze it to an immutable MemTable, then flush sorted SSTables (runs) on disk. Background compaction merges runs across levels, reclaiming space and dropping obsolete versions/tombstones. Reads check memory, then multiple levels (bloom filters + block cache cut I/O). RocksDB and Cassandra are the mental models.
LSM explains Cassandra/Scylla write paths, RocksDB in MyRocks/TiKV/etc., and many time-series/search stores. Interviews probe MemTable → flush → compaction, leveled vs size-tiered tradeoffs, and the write/read/space amplification triangle. Production pain is usually compaction debt (write stalls) or tombstone/GC lag — not the MemTable itself.
Core mechanism
- Write: append to WAL (optional but common) → insert into MemTable (skiplist / B-Tree in RAM).
- MemTable full: mark immutable, allocate a new MemTable; flush immutable to an SSTable (sorted string table: data + index + filter).
- Levels: L0 may hold overlapping files; L1..Ln in leveled compaction have non-overlapping key ranges targeting size ratios (e.g. 10×).
- Compaction: merge inputs → new SSTables; drop overwritten keys and eligible tombstones.
- Read path: MemTable(s) → L0 → lower levels; bloom filters skip files; block cache serves hot blocks; merge iterators pick the newest version.
- Deletes: write tombstones; space frees only after compaction past tombstone retention rules.
Compaction styles
- Size-tiered: compact similar-sized runs; lower write amp sometimes, worse read amp / space.
- Leveled (RocksDB default-ish): compact into the next level keeping ranges partitioned; higher write amp, lower read amp.
Quantified triangle: amplification.
Comparative
| Approach | Pros | Cons |
|---|---|---|
| LSM leveled | Sequential writes; tunable read amp | Compaction write amp; stalls if debt grows |
| LSM size-tiered | Often lower write amp | Higher read amp; space amp |
| B-Tree | Stable point-read locality | Random writes; split amp — B-Tree internals |
| Pure append log | Fastest ingest | Terrible reads without indexes |
Write and compaction path
Decisions
- 1
1. Client put or delete
- next2. WAL append
- 2
2. WAL append
- next3. MemTable insert
- 3
3. MemTable insert
- next4. MemTable full?
- ?
4. MemTable full?
- no5. Ack per sync policy
- yes6. Freeze immutable MemTable
- 5
5. Ack per sync policy
- 6
6. Freeze immutable MemTable
- next7. Flush to L0 SSTable
- 7
7. Flush to L0 SSTable
- next8. Level too large?
- ?
8. Level too large?
- yes9. Compaction merge to next level
- no5. Ack per sync policy
- 9
9. Compaction merge to next level
- next10. Drop obsolete keys and tombstones
- 10
10. Drop obsolete keys and tombstones
- next5. Ack per sync policy
- 11
READ
- next11. MemTables + bloom + levels merge
- 12
11. MemTables + bloom + levels merge
- next12. Newest value wins
- 13
12. Newest value wins
Lesson map
LSM Trees — MemTable, SSTables & Compaction
MemTable → immutable → flush SSTable; leveled vs size-tiered compaction; blooms; RocksDB/Cassandra model.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1. Client put or delete"] b["2. WAL append"] c["3. MemTable insert"] d["4. MemTable full?"] a -->|1. Client put or delete| b b -->|2. WAL append to 3. MemTable insert| c c -->|3. MemTable insert| d
Sandbox: flush + naive compaction (Python)
Tiny in-memory LSM. Tombstones drop on compact.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Read-path merge (TypeScript)
Newest sequence number wins; null is a tombstone.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Why is LSM write-friendly?
Answer
Most user writes become sequential appends (WAL + flush of sorted runs) instead of in-place random page updates.
What is a tombstone?
Answer
A delete marker. The key stays until compaction proves no older value can be seen, then space can be reclaimed. Queries may still pay RA until then.
Leveled vs size-tiered compaction?
Answer
Leveled keeps lower read amp / clearer ranges at the cost of more rewrite (write amp). Size-tiered is often the opposite. Pick from the amp triangle, not from a default.
Role of bloom filters?
Answer
Probabilistic "key not in this SSTable" → skip disk reads on negative/point lookups. They cut RA without changing WA much.
What is compaction debt / write stall?
Answer
Flushes outpace compaction → too many L0 files → the engine throttles or stalls writes to protect read amp. This is the LSM cousin of B-Tree dirty-page flush latency.
Does LSM still need a WAL?
Answer
Typically yes for MemTable durability across crash before flush (unless replicas alone are the durability story). WAL.
How do reads find the newest value?
Answer
Merge by key with sequence numbers; first hit in the newest MemTable/L0 wins; else deeper levels.
Cassandra vs RocksDB mental model?
Answer
Both LSM-family. Cassandra: memtable + commitlog + SSTables + compaction strategies per table. RocksDB: rich leveled compaction controls, often embedded (MyRocks, TiKV).
Pitfalls
Whiteboard a key that was overwritten twice and deleted once. Place versions in MemTable, L0, and L1. Walk get() with and without a bloom miss. Then say what happens if L0 has 40 overlapping files.