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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.