LSM Tree + Compaction
TechniqueDatabase InternalsMidSeniorUpdated
Buffer writes in an in-memory memtable, flush sorted runs (SSTables) to disk, then merge them in background compaction passes.
When to Use LSM Tree + Compaction
Write-heavy workloads where sequential I/O dominates: RocksDB, LevelDB, Cassandra, ScyllaDB, HBase. Trades read amplification (multiple levels to probe) and space amplification (during compaction) for write throughput.
In Practice
RocksDB: memtable -> L0 (overlapping SSTables) -> L1..Ln (each level ~10x larger, non-overlapping). Leveled compaction keeps read amp of the LSM (Log-Structured Merge-tree) roughly O(L) levels.
How LSM Tree + Compaction Comes Up in Interviews
Scenario
A RocksDB workload does many point GETs for keys that don't exist. p99 read latency is terrible. Which tuning helps most?
Without bloom filters, a missing key forces a probe of every SSTable on every level. A 10-bits-per-key filter brings false positives to ~1%, so a 7-level LSM probes ~1 SSTable instead of 7.
Whole-key bloom filters help GETs; prefix bloom filters help bounded prefix iterators. They cost memory (~1.25 bytes/key for ~1% FPR) and add nothing to range scans.