LSM-Trees and SSTables

How a log-structured merge-tree turns random writes into sequential ones, what compaction costs, and how Bloom filters keep reads fast.

Overview

A log-structured merge-tree (LSM-tree) is a way to store sorted key-value data on disk that never updates a file in place. New writes collect in memory, get written out as a new sorted file, and background jobs later merge those files. RocksDB, LevelDB and Cassandra all store data this way, and so does Bigtable.

The idea comes from a 1996 paper by Patrick O'Neil and others. Their problem was a table that received inserts all day: keeping a B-tree index on it cost a random disk write per insert. The LSM-tree batches those changes in memory and pushes them to disk in large sorted runs, the way merge sort works. Google's Bigtable paper (2006) gave the parts the names used today: memtable, SSTable and compaction.

The write path

A write touches two places and nothing else. First it is appended to a write-ahead log (WAL), a file on disk that only grows at the end, so the write survives a crash. Then it is inserted into the memtable, a sorted structure in memory. RocksDB's default memtable is a skip list. The write is then done: no page on disk was read or rewritten.

When the memtable reaches its size limit (64 MB by default in RocksDB), it is frozen, a new empty memtable takes new writes, and a background thread writes the frozen one to disk as an SSTable (sorted string table). An SSTable is a file of key-value pairs sorted by key, with a small index of where each block starts. It is never changed after it is written. Once its data is in an SSTable, the matching part of the log can be deleted.

> [!WARNING] > 'Written to the log' does not always mean 'on the disk'. RocksDB's default write returns once the data is handed to the operating system. A process crash loses nothing, but a machine crash can lose the last few writes unless the write sets sync.

The read path

A key can live in several places at once: the memtable, and any number of SSTables, each holding an older or newer version. A read looks from newest to oldest and stops at the first hit.

The cost stays low for two reasons. Inside one SSTable, keys are sorted, so the in-memory block index finds the one block that could hold the key. Across SSTables, a Bloom filter per file answers 'definitely not here' or 'maybe here' from memory. RocksDB's usual setting spends about 10 bits per key for about a 1% false positive rate. Bigtable's paper notes the same benefit: most lookups for keys that do not exist never touch the disk.

Compaction

Flushing forever would leave thousands of small files, each holding old versions and deleted keys. Compaction is the background job that merges several SSTables into new ones. Because every input is sorted, the merge is a single sequential pass, like the merge step of merge sort. When a key appears in several inputs, only the newest version is kept.

A delete follows the same rule. A file cannot be edited, so a delete writes a tombstone, a marker that says the key is gone. Reads that meet the tombstone stop and return 'not found'. Compaction drops the older values it hides, and drops the tombstone itself once no older file can still hold the key.

The main strategies differ in when files are merged.

Size-tiered (Cassandra STCS, RocksDB universal) — Merges several files of similar size into one bigger file — Low write amplification — More files to check per read; needs spare disk during big merges
Leveled (LevelDB, RocksDB default, Cassandra LCS) — Levels of fixed target size, each level ten times the one before; files in a level do not overlap — Few files per read, little wasted space — Rewrites data again at each level, so more write amplification
Time window (Cassandra TWCS) — Groups files by the time their data was written — Time series that expire by TTL — Poor fit for data that is updated later

In leveled compaction, level 0 holds freshly flushed files that may overlap. Every level below is one sorted run split into non-overlapping files, so a read checks at most one file per level. Cassandra's default is still size-tiered; its docs point read-heavy or update-heavy tables to leveled and expiring time series to time window. Cassandra 5.0 added the unified compaction strategy (UCS), which its docs now recommend for most workloads.

The three costs

Every storage engine trades three kinds of overhead, and LSM-trees make the trade explicit.

Write amplification — Bytes written to disk per byte the application wrote — High: each byte is written to the log, flushed, then rewritten by compaction. RocksDB's tuning guide works an example of about 33 for leveled compaction
Read amplification — Disk reads per query — Moderate: one file per level, mostly avoided by Bloom filters and the block cache
Space amplification — Bytes on disk per byte of live data — Low for leveled, higher for size-tiered, which keeps old versions longer and needs room for merges

The RocksDB example assumes a 500 GB database with 10x level growth: 1 for the flush to level 0, 2 for level 0 into level 1, then about 10 for each deeper level, so 1 + 2 + 10 + 10 + 10 = 33. The log write comes on top of that. It is an example, not a constant, and real per-level costs are often below 10. It matters on SSDs, where every byte written wears the flash.

What you will be able to do

Walk through an LSM write and read, naming the memtable, WAL, SSTable and Bloom filter.
Explain compaction and tombstones, and why deletes do not free space at once.
Compare size-tiered and leveled compaction by their write, read and space costs.
Say when an LSM engine beats a B-tree, and when it does not.

Key concepts

LSM-tree: A storage design that buffers writes in memory, writes them out as sorted immutable files, and merges those files in the background.
Memtable: The sorted in-memory buffer that takes new writes. A skip list in RocksDB by default. Flushed to an SSTable when it reaches its size limit.
SSTable: A sorted string table: an immutable file of key-value pairs sorted by key, with a block index. Named in the Bigtable paper.
Write-ahead log (WAL): An append-only file written before the memtable so that unflushed writes can be replayed after a crash.
Compaction: The background merge of SSTables that keeps the newest version of each key and drops overwritten values and expired tombstones.
Tombstone: A marker written for a delete. It hides older values until compaction removes both.
Bloom filter: A compact bit array per SSTable that answers whether a key is definitely absent or maybe present, with no false negatives.
Write amplification: The ratio of bytes written to disk to bytes written by the application. Compaction is the main source in an LSM-tree.
Leveled compaction: Files are kept in levels of growing target size; every level below level 0 has non-overlapping files, so a read checks one file per level.
Size-tiered compaction: Files of similar size are merged together into a larger file. Fewer rewrites, but more files to check and more spare space needed.

When to use it

Explaining why Cassandra and RocksDB handle heavy write loads well
Comparing LSM-tree and B-tree engines when choosing a database
Discussing write amplification and SSD wear in a performance conversation
Explaining how Bloom filters cut read cost in a key-value store
Choosing a Cassandra compaction strategy for a workload

Interview questions

Walk me through a write and then a read in an LSM-tree.
Why can an LSM-tree take writes faster than a B-tree?
What is compaction, and how do size-tiered and leveled compaction differ?
How does a Bloom filter speed up reads, and what can go wrong?
When would you not choose an LSM-tree engine?