Search tools and guides ⌘K
Storage & Databases also: Log-Structured Merge-Tree

LSM-tree

Append-only writes flushed and merged in the background.

In plain terms

O'Neil et al, 1996. RocksDB, LevelDB, Cassandra, BigTable. Trades write amp for sequential I/O — SSDs love it.

Origin

Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil, "The Log-Structured Merge-Tree (LSM-tree)," 1996. Inspired by log-structured filesystems (Rosenblum & Ousterhout 1991). Sleeping idea until SSDs and write-heavy workloads (Bigtable, 2006) made it practical.

Where it shows up in production
  • Cassandra & ScyllaDB LSM is the on-disk format. SSTables flushed from memtable; background compaction merges them.
  • RocksDB & LevelDB Embedded LSM stores; behind everything from Kafka indexes to TiDB to MongoDB WiredTiger.
  • BigTable & HBase The original cloud-scale LSM deployment; described in the 2006 Bigtable paper.
On Semicolony
Paper papers Data structures data structures
Sources & further reading
Related Concepts Related Concepts
Simulator B-Tree Simulator — the read-heavy alternative Visualize Bloom Filter Visualizer — read-path optimisation Study Path LSM Tree — codex deep dive Simulator Storage Engine Simulator — B-tree vs LSM head-to-head Study Path Database Internals Study Path
Found this useful?