The encyclopedia · Engineering & Operations · Technical decision · 1996
The LSM-tree turned random database writes into sequential ones
LSM-trees buffer writes in memory, flush them as sorted immutable runs, then merge in the background, so a disk sees sequential I/O.
University of Massachusetts Boston / Informix
the move
On a disk, a random update to a B-tree page is a seek plus a small write, and an application that keeps updating the same keys pays that cost many times. Throughput collapses because the disk is doing tiny scattered I/O.
The LSM-tree recasts the problem. Writes first go into a sorted in-memory structure and are flushed as ordered immutable files, so the disk sees a stream of large, sequential writes. Older runs are later merged and compacted in the background.
This trade of occasional expensive merges for cheap sequential writes is also why the structure is called log-structured: the write path is an append-only log, and the real sorting happens on the read and compact side.
why it works
- Sequential disk I/O is orders of magnitude faster than random seeks.
- Writes are batched into big immutable runs rather than small in-place updates.
- Background merging hides the compaction cost from the write path.
what transfers
If a workload does many tiny random writes, restructure so it commits sequentially and compensates later; the expensive work becomes a batch you can schedule, not a cost you pay per write.
what came after
The LSM architecture became the basis of high-write storage systems including LevelDB, RocksDB, Cassandra, HBase and LevelDB-like engines in many data stores.
references
spotted an error? The archive wants to know.