LSM Trees
Understand how write-optimized storage turns random updates into sequential writes and pays later through compaction.
2–5 minute refresher
Write→WAL→Memtable→ flush →SSTablesbackground compaction ↓Sorted levels
Log safely → buffer in memory → flush sorted files → compact levels
30second
refresher
refresher
An LSM tree records writes in a write-ahead log, applies them to an in-memory sorted structure, then flushes immutable sorted-string tables (SSTables). Background compaction merges tables, discards overwritten values, and reclaims tombstones.
What problem does it solve?
Updating data in place causes random I/O. LSM trees batch and sort changes so the storage engine performs large sequential writes, which is especially effective for write-heavy workloads.
Decision guide
Key trade-offs
| Choice | What you gain | What it costs |
|---|---|---|
| Size-tiered compaction | High write throughput | More space and overlapping files during reads |
| Leveled compaction | Predictable reads and lower space amplification | Higher write amplification |
| Large memtable | Fewer, larger flushes | More memory and longer recovery replay |
What happens if?
The process crashes before a memtable flush
Recovery replays the durable WAL into memory. Acknowledging before the WAL is safely persisted can lose writes even though the client saw success.
What happens if?
Compaction cannot keep up
SSTables accumulate, reads touch more files, tombstones remain, and free disk space collapses. Backpressure must slow ingestion before the node enters an unrecoverable spiral.
Intermediate interview modeWhy do LSM trees need Bloom filters?Show answer
A Bloom filter can prove that an SSTable definitely does not contain a key, avoiding unnecessary disk reads. False positives still cause reads, but false negatives are not allowed.