Notesstorage🌱 seedling
LSM-Tree
Also: Log-Structured Merge-Tree · LSM · Log-Structured Storage
A storage engine that never updates data in place: writes go to an in-memory [[Memtable]], which is flushed as sorted, immutable [[SSTable]]s that background [[Compaction]] merges. It trades extra background work and read effort for very cheap, sequential writes.
Why it exists
Updating pages in place means random writes and a page rewrite per small change. Buffering writes in memory and emitting large sorted files turns a random-write workload into a sequential one, which every disk handles best.
How it works
- Write: append to the Write-Ahead Log, insert into the memtable. No data file is touched.
- Flush: a full memtable is written out as an SSTable in level 0.
- Read: memtable first, then SSTables newest to oldest; per-file Bloom Filters skip files that can't hold the key. The first hit wins.
- Delete: write a tombstone that shadows older values.
- Compaction: merge-sort files, keep the newest version of each key, drop tombstones once nothing older remains.
Trade-offs
| Gains | Costs |
|---|---|
| very high write throughput; sequential I/O | reads may check several files |
| dense files that compress well | background compaction competes for disk and CPU |
| no in-place overwrites, no torn pages in data files | latency spikes or write stalls if compaction falls behind |
In practice
- RocksDB is the reference engine, embedded in MyRocks, Kafka Streams, Flink, TiKV and more; Cassandra, ScyllaDB and HBase are LSM-based too.
- CockroachDB runs on Pebble, a RocksDB-inspired LSM written in Go.
- Facebook moved its main user database from InnoDB to MyRocks (MySQL on RocksDB) and halved its storage use.
Pitfalls
- Benchmarks run before compaction reaches steady state flatter LSMs badly.
- Deletes and overwrites cost space until compaction reclaims it; tombstone-heavy scans are slow.
Connections
- Part of
- Storage
- Contains
- Compaction
- Contrasts with
- B-Tree
- Related
- Bloom FilterColumn-Oriented StorageInverted IndexWrite AmplificationStateful Stream Processing
- In real systems
- RocksDBCassandraCockroachDBClickHouse
- Mentioned
- Write-Ahead Log
Recall
These cards are also in your review deck, scheduled with spaced repetition.