LSM trees and compaction: an interactive storage engine simulator
A log-structured merge tree, or LSM tree, is the storage structure behind write-heavy databases such as Cassandra, RocksDB, LevelDB, ScyllaDB and HBase. Writes go to memory and are flushed to disk as sorted, immutable files; background compaction merges those files so reads stay fast and old versions are thrown away. How it compacts decides the trade-off between write, read and space amplification.
The playground writes 7,700 entries into an LSM tree, 100 at a time per flush. Choose leveled or size-tiered compaction, new keys or updates to the same keys, and play it through or drag to any moment.
7,700 writes of new keys, flushed 100 at a time. Leveled compaction writes each entry to disk 5.9 times on average, against 3.6 for size-tiered, and a lookup may have to check up to 6 sorted runs, against 9. A lookup for a missing key would read every run, but a 1% bloom filter per table rules most out: 0.04 disk reads on average right now.
How an LSM tree writes and reads
- Write: append the change to a write-ahead log for durability, then insert it into the memtable, a sorted structure in memory. Nothing on disk is updated in place.
- Flush: when the memtable is full, write it to disk as an SSTable, a sorted, immutable file, in one sequential write.
- Read: look in the memtable, then in the SSTables from newest to oldest, stopping at the first version of the key. A bloom filter per SSTable skips files that cannot hold it.
- Delete: write a tombstone, a marker that hides older versions until compaction removes them all.
- Compact: merge SSTables in the background, keeping only the newest version of each key.
Leveled vs size-tiered compaction
Leveled compaction keeps each level below L0 as one sorted run, each ten times larger than the one above, and merges a level into the next when it outgrows its target. A lookup checks at most one run per level, but each entry is rewritten every time it moves down. Size-tiered compaction lets tables of similar size accumulate and merges four of them into one bigger table, so entries are rewritten less often, but there are more tables to search and old versions linger longer.
In the playground, with new keys, leveled compaction writes each entry to disk 5.9 times on average and a lookup checks at most 6 sorted runs; size-tiered writes each entry 3.6 times, but a lookup may check 9. With updates to 600 keys, leveled storage peaks at about twice the live data, size-tiered at 4.7 times.
| Leveled | Size-tiered | |
|---|---|---|
| Write amplification | Higher: rewritten at every level | Lower |
| Read amplification | Lower: one run per level | Higher: many tables of each size |
| Space amplification | Lower: about 10% extra | Higher: duplicates, and room for big merges |
| Suits | Read-heavy data, updates | Write-heavy data, mostly new keys |
| Default in | RocksDB, LevelDB | Cassandra, long its default |
Time-series data has a third option: time-window compaction, as in Cassandra’s TimeWindowCompactionStrategy, merges only tables from the same time window and drops whole windows when they expire.
Why bloom filters matter
A read for a key that does not exist would have to check every sorted run, and a read for an old key checks most of them. A bloom filter per SSTable, kept in memory, answers “definitely not here” for almost every file that lacks the key. With a 1% false positive rate, a lookup that would check 9 runs reads on average 0.09 of them; without filters, it reads all 9.
LSM tree vs B-tree
| LSM tree | B-tree | |
|---|---|---|
| Writes | Sequential: memtable, then whole sorted files | In place: random page writes |
| Reads | May check several files; bloom filters help | One path from root to leaf |
| Background work | Compaction, which competes for disk | Little; pages split as they fill |
| Space | Compresses well; old versions until compaction | Pages left partly empty |
| Used by | Cassandra, RocksDB, ScyllaDB, HBase, Bigtable | PostgreSQL, MySQL InnoDB, SQL Server |
In a system design interview
Storage engines come up when a workload is very write-heavy: metrics, logs, chat messages, events. “We write 500,000 data points a second and read recent ranges, so we use an LSM-based store, Cassandra, with time-window compaction: writes are sequential, recent data stays in few files, and whole expired windows are dropped without rewriting anything.” Expect the follow-ups: compaction falling behind under load, the cost of tombstones, and why a read can be slower than in a B-tree.
Read the guide to storage engines or time-series data, or watch a strong candidate design a metrics monitoring system.
Questions people ask
What is an LSM tree?
A log-structured merge tree, a storage structure that buffers writes in a sorted in-memory table, flushes it to disk as an immutable sorted file (an SSTable) when full, and merges those files in the background. Every disk write is sequential, which makes LSM trees fast for write-heavy workloads.
What is compaction in an LSM tree?
Background merging of SSTables into larger ones, keeping only the newest version of each key and dropping deleted ones. Without it, the number of files a read must check would grow without limit and old versions would waste space. Compaction costs disk I/O and is the source of write amplification.
What is the difference between leveled and size-tiered compaction?
Leveled compaction keeps each level as one sorted run, each about ten times larger than the last, so reads check at most one file per level and little space is wasted, but data is rewritten at every level. Size-tiered compaction merges several similar-sized files at a time, which rewrites data less often but leaves more files to search and more duplicate versions.
What are read, write and space amplification?
Write amplification is how many bytes reach the disk for each byte the application writes, including compaction rewrites. Read amplification is how many files or pages a read touches. Space amplification is how much more disk is used than the live data needs. Compaction strategies trade these three against each other.
How do LSM trees use bloom filters?
Each SSTable has a bloom filter kept in memory. Before reading a file for a key, the database asks the filter, which can say the key is definitely absent. With a false positive rate around 1%, a lookup skips almost every file that does not hold the key, so reads, especially for missing keys, stay cheap despite many files.
What is the difference between an LSM tree and a B-tree?
A B-tree updates pages in place, so reads follow one root-to-leaf path but writes are random I/O. An LSM tree never updates in place: writes are sequential and fast, while reads may check several files and compaction runs in the background. B-trees power PostgreSQL and MySQL; LSM trees power Cassandra, RocksDB and HBase.
Which databases use LSM trees?
Cassandra, ScyllaDB, HBase and Google Bigtable, the embedded engines LevelDB and RocksDB, and the many systems built on RocksDB, such as CockroachDB’s earlier storage layer and Kafka Streams state stores. They suit workloads with heavy write traffic, like time series, logs, messaging and event data.