Data Stores

LSM Tree (Log-Structured Merge Tree)

Also known as: log-structured merge tree, LSM

Definition

An LSM tree buffers writes in an in-memory table, flushes them to immutable sorted files, and merges those files in the background. It converts random writes into sequential ones, giving very high write throughput at the cost of read amplification and periodic compaction stalls.

Last reviewed · Part of the Architecture Glossary

In practice

The write path: memtable (sorted, in memory) plus a write-ahead log for durability. When the memtable fills it is flushed as an immutable SSTable. Background compaction merges SSTables into larger ones, discarding overwritten and deleted keys.

The consequence is a set of trade-offs a B-tree does not have:

  • Write amplification — each key is rewritten every time it participates in a compaction. Levelled compaction gives amplification around 10-30x; size-tiered is lower on writes and worse on reads and space.
  • Read amplification — a key may live in any level, so a read checks several SSTables. Bloom filters cut the misses, but a range scan still merges across levels.
  • Compaction stalls — a burst of writes can outrun compaction, and the engine throttles or stalls writes to let it catch up. This is the p99 spike that appears with no change in query mix.
  • Deletes are writes. A delete inserts a tombstone; the space is reclaimed only at compaction. Bulk-deleting then range-scanning that key range is famously slow in Cassandra for exactly this reason.

When it matters

RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, and the storage engines under many time-series and streaming systems.

Common mistake

Benchmarking on an empty database. LSM performance before the first major compaction is not the steady state — run the load long enough to reach it, or the numbers will not survive week two.

See also

Go deeper