Storage engines II: LSM trees

A B+tree updates data in place. To change a row, it finds the page, modifies it, and eventually writes the page back. That is good for reads, but each small write can cost a random page write, and random writes are what storage hardware handles worst.

A log-structured merge tree (LSM tree) makes the opposite bet. It never modifies anything on disk. It buffers writes in memory, flushes them as sorted, immutable files, and merges those files in the background. Every disk write is a large sequential write.

That bet powers much of modern data infrastructure: RocksDB (inside MyRocks, TiKV, Kafka Streams, Flink and many more), Cassandra, ScyllaDB, HBase, Google's Bigtable and LevelDB, and CockroachDB's Pebble.

Concepts in this section

Read them in order. The first page explains the write path, and the rest build on it.

Comparing with a B-tree

LSMs suit high sustained write rates, such as event ingestion, metrics, logs, messaging and IoT. They also suit write-heavy key-value state, and data that is written once and expires by time. B-trees suit read-heavy OLTP with many secondary indexes and range queries, workloads that need steady tail latency, and teams that do not want to tune compaction.

Where LSMs show up

• RocksDB is a Meta fork of LevelDB, tuned for flash and many cores. Many systems embed it as a library.
• MyRocks runs RocksDB as a MySQL storage engine. Meta moved its main user database to it and roughly halved storage compared with compressed InnoDB.
• CockroachDB uses Pebble, a Go reimplementation of RocksDB's design, as its default engine since 2020.
• TiKV, YugabyteDB, Kafka Streams and Flink use RocksDB-based storage for node data or local state that outgrows memory.
• Cassandra and ScyllaDB have their own LSM implementations with pluggable compaction strategies. Bigtable and HBase were the original large-scale LSM deployments.

Common mistakes

• Choosing an LSM for read-heavy, range-heavy work. Scans must merge every level, which is its weak spot.
• Ignoring compaction capacity. If writes outpace compaction, reads slow down and the engine eventually stalls writes.
• Assuming an LSM is always cheaper on storage. Size-tiered compaction can need about twice the live data's disk space.

Key takeaways

• An LSM buffers writes in a memtable backed by a log, flushes immutable sorted files, and merges them in the background. All disk writes are sequential.
• Point reads check the memtable and then each level. Bloom filters and block indexes keep that close to one disk read.
• Compaction strategy is the main tuning choice, and it decides the trade-off between read cost, write cost and space.
• Deletes are tombstones. In replicated stores, purging them too early can bring back deleted data.

Further learning

ByteByteGo's short animated overview gives a good first pass over memtables, SSTables and compaction.

RocksDB wiki is the reference for the most widely used LSM engine. Designing Data-Intensive Applications (Kleppmann) covers both B-trees and LSMs in depth.