LSM trees

In 1996, three researchers — Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil — published a paper titled "The Log-Structured Merge-Tree." They were looking at the same problem as Bayer & McCreight had 26 years earlier, but from the opposite angle: instead of optimizing reads, what if you optimized writes?

Their insight was elegant: never update disk data in place. All writes go to an in-memory buffer (the MemTable). When it fills up, dump it to disk as a sorted, immutable file (an SSTable — Sorted String Table). Never touch that file again — just create new ones as more data comes in. Reads have to check multiple files, but every write is a fast sequential append.

For a decade the paper was ignored. Then in 2006, Google published the BigTable paper. Then Amazon published Dynamo (2007), Facebook released Cassandra (2008), Google open-sourced LevelDB (2011), and Facebook released RocksDB (2013). Every one uses LSM-trees. Today, LSM-trees are the storage engine inside Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, TiKV, InfluxDB, ClickHouse (partially), and the write layers of CockroachDB, TiDB, YugabyteDB, and MongoDB WiredTiger's LSM mode.

The core idea — never write in place

A B-tree write updates a page in place: read the page into memory, modify it, write it back to the same disk location. This random write is the expensive part. LSM-trees never do it. Every write is a sequential append — first to the WAL (for durability), then into the in-memory MemTable. When the MemTable fills (typical 64 MB), it's flushed to disk as an SSTable — another sequential write. SSTables are immutable once written.

Sequential writes are ~100× faster than random writes on both SSDs (avoiding write amplification) and traditional HDDs (avoiding seek time). LSM-trees exploit this ruthlessly. A Cassandra node can ingest hundreds of thousands of writes per second per node because every write is a sequential append.

The three-part architecture — MemTable + WAL + SSTables

MemTable is a sorted in-memory data structure — usually a skip list. Reads check it first. Writes go into it. When it fills, it's flushed to disk. WAL (Write-Ahead Log) is a sequential log of every write, appended before the write hits the MemTable. On crash, the WAL replays to reconstruct the MemTable. SSTables are the immutable on-disk files — sorted key-value pairs with an index at the end. Once written, never modified. Only deleted (during compaction).

Compaction — the maintenance ritual

If you never rewrite, you accumulate SSTables forever. Reads would have to check all of them (bad), and space would grow (worse — updates and deletes leave "shadow" entries). The solution: compaction. Periodically, the engine merges multiple SSTables into one — dropping deleted keys and keeping only the latest value for each key.

Compaction is the single biggest tuning knob in LSM systems. More aggressive compaction = fewer SSTables to check = faster reads, but higher write amplification and disk I/O. Less aggressive = faster writes but slower reads. RocksDB has tiered, leveled, and hybrid compaction strategies — each a different point in the trade-off. Cassandra's SizeTiered vs LeveledCompactionStrategy is the same choice.

Reads — the hard part

Reads must check every place the key could be: MemTable first (newest), then SSTables from newest to oldest. Naïve implementation would read every SSTable on every miss. Two techniques make it fast:

• Bloom filters — each SSTable has a bloom filter for its keys. Before reading the SSTable, check the bloom filter. If it says "definitely not here," skip the SSTable entirely. Typical: 1% false-positive rate at 10 bits per key.
• Sparse indexes — each SSTable's footer has an index of one key per block (usually 4 KB). Binary-search the index to find the right block, then linear-scan.

With bloom filters and sparse indexes, a well-tuned LSM typically needs 1-2 SSTable reads on average per point lookup. Range scans are more expensive — they must merge across all SSTables — which is why Cassandra range queries are often constrained to a single partition.

Compaction strategies — tiered vs leveled

The write-amplification trade-off

Every LSM has a cost: write amplification. A single byte written by the application ends up being written to disk multiple times as it moves through compaction levels. Typical: 10-30x write amplification. This is why LSM-based databases wear out SSDs faster than B-tree databases. RocksDB engineers have spent enormous effort minimizing this (see Facebook papers on tuning).

The trade-off table:

• LSM: high write throughput, low read latency on point lookups (with bloom filters), high write amplification, disk-hungry compaction.
• B+tree: high read throughput, fast range scans, low write amplification, but writes are slower under concurrency.

Applied in real systems

Key takeaways

• LSM = MemTable + WAL + SSTables + compaction. Writes append; SSTables are immutable; compaction merges them.
• Writes are sequential — 100× faster than random writes on both HDD and SSD. This is the LSM win.
• Reads check multiple SSTables. Bloom filters skip irrelevant ones (~1% false-positive rate). Sparse indexes find the right block within an SSTable.
• Compaction merges SSTables, drops deletes, and reclaims space. Tiered = faster writes; leveled = faster reads. Every LSM database has this tuning knob.
• Write amplification is the cost — typically 10-30×. LSMs wear out SSDs faster than B-trees.
• RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, TiKV, Pebble, InfluxDB IOx — every write-heavy modern storage engine uses LSM. Learn one and you can read the source of the others.
• The BigTable/Dynamo/Cassandra papers together made LSM the default write-heavy storage engine for the modern distributed data world.

References

• O'Neil et al. (1996) — The Log-Structured Merge-Tree. Acta Informatica.
• Chang et al. (2006) — Bigtable. OSDI.
• Lakshman & Malik (2010) — Cassandra.
• Dong et al. (2017) — Optimizing Space Amplification in RocksDB. Facebook.
• Kleppmann (2017) — Designing Data-Intensive Applications, Chapter 3.
• Petrov (2019) — Database Internals, Chapter 3 has the modern treatment.