The encyclopedia · Engineering & Operations · Technical decision · 1996-2010s
The LSM-tree made randomly-written databases cheap by never updating in place
O'Neil's log-structured merge tree buffered writes and merged them, turning billions of random disk writes into big sequential ones.
O'Neil · LevelDB · RocksDB
the move
Maintaining an index in place costs a random disk read plus a random disk write per insert, and on a large index the leaf page is touched too rarely to stay cached. The result is very expensive as writes grow.
The log-structured merge tree (LSM-tree) by O'Neil, Cheng, Gawlick and O'Neil in 1996 changes the shape: writes land in memory, then are flushed to disk as large sorted components that are merged in the background. This amortizes the cost of indexing an insert by the batching factor of the merge.
The insight became the storage engine for LevelDB, RocksDB, Cassandra, HBase and Bigtable: write fast, merge lazily, and pay with extra read amplification and occasional compaction.
why it works
- Disk seeks are expensive per byte, so doing one large sequential write per batch is far cheaper than many small random writes.
- Batching many new records into a single merged block spreads the arm cost across them.
- Keeping C0 in memory removes the immediate write and lets the flush happen in bulk.
- The trade is a read that may check several components, which became acceptable when storage got fast.
what transfers
When the cost is a random operation, reshape the work into big sequential chunks merged in the background, and pay where you mind it least.
what came after
The LSM-tree became the storage shape underneath LevelDB, RocksDB, Cassandra, HBase and Google's Bigtable, and it reshaped how write-heavy databases were built, though its read and write trade-offs have to be re-derived as hardware changes.
references
- The Log-Structured Merge-Tree (O'Neil et al., 1996) — Annotated, with the Original PDF
- LSM-Trees Explained — Memtable, SSTables, Compaction, RocksDB
spotted an error? The archive wants to know.