The Log-Structured Merge-Tree (LSM-Tree)
1996 · Acta Informatica · ~12 min read
Read the original paperDisks are fast at writing in order and slow at writing in place. The LSM-tree turns every write into an append and sorts later, which is why the stores behind modern systems can absorb a firehose.
The problem: a disk arm cannot keep up with inserts
The paper’s motivating example is a bank’s transaction history: every account movement appended to a table that must also be searchable by account. A B-tree index handles the search beautifully and the inserts terribly, because each new record lands on an effectively random leaf page, and a random write on a 1996 disk means moving the arm, which costs about ten milliseconds. A busy system generating thousands of inserts a second was paying for a seek on every one. Meanwhile the same disk could stream hundreds of megabytes a second sequentially. The hardware was fast; the access pattern was wrong.
The idea: never write in place; sort later, in bulk
O’Neil and colleagues proposed keeping the newest data in a small in-memory tree (C0) and the bulk on disk in a larger tree (C1), and never inserting into C1 directly. When C0 fills, a rolling merge streams its contents into C1 in sorted order, rewriting C1’s pages sequentially like the merge step of a merge sort. Inserts cost a memory operation and an amortised share of a sequential merge; the random seek is gone. Add more levels, each roughly ten times larger than the one above, and the merges stay cheap all the way down.
How it works
In today’s engines the components have names the paper did not use but the structure is the same. Writes are appended to a log for durability and inserted into a sorted memtable. When the memtable reaches a few megabytes it is written out as an SSTable, a sorted, immutable file with an index. Runs accumulate in level 0; compaction merges them with the level below, discarding versions that have been overwritten or deleted. A read checks the memtable, then each level in turn, and would be slow if it had to open every run, so every run carries a Bloom filter, a tiny bitmap that says “definitely not here” for almost every key it does not contain.
Every write is an append into a small sorted memtable. When it fills, it is flushed as an immutable sorted run; when runs pile up, they are merged. Nothing is ever updated in place.
empty
empty
empty
A write never seeks: it lands in memory and later in one sequential run, which is why these stores absorb far more writes per second than a tree updated in place. The price is paid on reads, which may check several runs, and in compaction, which rewrites data in the background. Bloom filters make most of those checks free.
The costs do not vanish, they move. Each record is rewritten once per level during compaction, so a store with five levels writes every byte several times: write amplification. A key may exist in several runs until compaction catches up: space amplification. And a read may consult several runs: read amplification. Levelled and tiered compaction strategies are different points in that triangle, and tuning them is most of what operating an LSM store consists of.
| cost | B-tree (in place) | LSM-tree |
|---|---|---|
| write | a random page write per update | an append; sequential merges later |
| point read | one tree descent | memtable, then runs filtered by Bloom filters |
| range scan | leaves in order | merge across runs on the fly |
| space | pages half-empty after splits | stale versions until compaction |
What it changed
The paper waited a decade for its moment. Bigtable put an LSM-tree under Google’s storage in 2006; Google engineers extracted that engine as LevelDB in 2011; Facebook forked it into RocksDB, which now sits beneath CockroachDB, TiKV, MySQL’s MyRocks, Kafka Streams state stores and much of Meta. Cassandra, HBase, ScyllaDB and InfluxDB are LSM-trees with different compaction policies. Solid-state drives changed the arithmetic, since they have no arm to move, but they still prefer sequential writes and wear out faster under random ones, so the design kept winning.
Where you meet it today
- Almost every new storage engine since 2010: RocksDB, LevelDB, Pebble, Cassandra, HBase, ScyllaDB, Badger.
- Compaction stalls. The latency spike at 2 a.m. in a write-heavy service is often the LSM paying its deferred bill.
- Bloom filters appeared in production because of this structure and are now a standard tool anywhere a “definitely not” answer is cheap and useful.
- Deletes that do not free space. A delete in an LSM store is a tombstone record until compaction; this surprises everyone once.
The original. Read it after this page; the explainer above is a map, not a substitute.
A patient, diagram-heavy explanation of the structure and its trade-offs.
The production engine behind many databases, documenting the compaction strategies this page sketches.