LESSON 26.2
LSM trees
Log-structured merge trees turn every write into a sequential append. Memtables, SSTables, compaction strategies and Bloom filters, plus the read, write and space amplification trade-off against B-trees.
7 min read
B-trees update pages in place, which means random writes. Log-structured merge trees (LSM trees) never modify data on disk. They buffer writes in memory, write them out as sorted immutable files, and merge those files in the background. That makes writes very fast, at the price of more work on reads and in the background. Cassandra, ScyllaDB, RocksDB, LevelDB, HBase, Bigtable and many time-series databases are built this way.
The write path
- Append the write to a commit log for durability.
- Insert it into the memtable, a sorted in-memory structure such as a skip list.
- When the memtable reaches a size limit (tens to hundreds of MB), write it to disk as a sorted string table (SSTable) in one sequential pass, then start a fresh memtable.
- Updates and deletes are just new writes. A delete writes a tombstone.
The read path
- Check the memtable.
- Check SSTables from newest to oldest. The first match wins, since newer values shadow older ones.
- Skip most files using each SSTable's Bloom filter and its sparse index of key ranges.
- Use a block cache for hot data.
Compaction
Without compaction, files would pile up and reads would check more and more of them. Compaction merges SSTables, keeping only the newest value for each key and dropping tombstoned data once it's safe.
Size-tiered
- Low write amplification
- Good for write-heavy loads
- A key may exist in many files, so reads check more
- Needs lots of free disk temporarily
Pick it when: Write-heavy workloads, append-mostly data (Cassandra's default).
Leveled
- Each level's files don't overlap, so reads touch about one file per level
- Less wasted space
- Higher write amplification
Pick it when: Read-heavy or update-heavy workloads (RocksDB's default).
Time-window
- Old windows are compacted once and then left alone
- Whole windows expire cheaply
- Only for time-ordered data
Pick it when: Metrics, logs and other time series with TTLs.
Amplification: the core trade-off
Every storage engine balances three costs, and improving one usually worsens another:
- Write amplificationLSM leveled ~10–30×; B-tree pages also high for small rows
- bytes written to disk per byte of user data
- Read amplificationB-tree ~1–2 disk reads; LSM more, reduced by Bloom filters
- files or pages touched per lookup
- Space amplificationLSM keeps old versions until compaction; B-trees waste space in half-full pages
- disk used per byte of live data
B-tree
- Predictable reads
- Good range scans
- Natural fit for transactions and locks
- Random writes
- Slower for write-heavy loads
Pick it when: OLTP with mixed reads and writes: Postgres, MySQL.
LSM tree
- Very high write throughput
- Sequential I/O
- Better compression
- Compaction uses I/O and CPU in the background
- Reads and deletes need care
Pick it when: Write-heavy: events, time series, messaging, large key-value stores.
Where LSM trees bite
- Tombstone build-up: queue-like patterns (insert then delete) leave piles of tombstones that every read scans until compaction removes them.
- Latency spikes when compaction competes with foreground reads; rate-limit compaction.
- Point reads of missing keys depend on Bloom filters fitting in memory.
Pause compaction during a write burst, then resume it and compare the number of runs a read must probe.
Try it
Metrics Ingestion HLD
Store a firehose of metrics points efficiently.