LSM trees and compaction
Every write is fast because it only ever appends - and then the database spends the rest of its life rewriting that data over and over in the background, which is where all the real costs live.
B-trees update data in place, which means a random write to a random page, which on any storage medium is the expensive kind of write. LSM trees take the opposite position: never update anything, only append, and deal with the consequences later.
“Later” is compaction, and compaction is the entire subject.[1]paperThe Log-Structured Merge-Tree (LSM-Tree)
The write path
A write goes into an in-memory sorted structure - the memtable, often a skip list - and into a write-ahead log for durability. That is all. No seeking, no page splits, no random I/O.
When the memtable fills, it is flushed to disk as an immutable sorted string table. Now there are two places a key might live. Flush again and there are three. Left alone, a read would eventually have to search every file ever written.
So a background process merges them. That is compaction, and everything you care about follows from how it is organised.
Leveled versus tiered
Leveled keeps one sorted run per level, each level T times larger than the last. When
a level exceeds its budget, its overlapping data is merged into the next level down. Reads
touch at most one run per level. Writes pay for it: merging into an existing sorted run
means rewriting roughly T times as much data as you moved, at every level.
Tiered lets runs accumulate at each level and merges them wholesale when enough pile up.
Each byte is written roughly once per level rather than T times, so write amplification is
far lower - but a read may have to search several runs at every level.
Switch strategies in the widget and watch the two numbers move in opposite directions.
This is the RUM conjecture
Read amplification, update amplification, memory amplification: you can optimise for two, never all three.[2]paperDesigning Access Methods: The RUM Conjecture Leveled buys read and space efficiency with write amplification. Tiered buys write efficiency with read and space amplification. There is no setting that wins everywhere, because the conjecture says there cannot be.
Dayan and Idreos later showed the choice does not have to be uniform - the levels have very different cost profiles, so applying tiering to the shallow levels and leveling to the deepest one dominates either pure strategy.[3]paperDostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores
Write stalls
Compaction consumes exactly the disk bandwidth the write path wants. If writes arrive faster than compaction can drain them, L0 grows, and eventually the database has to stop accepting writes rather than let the backlog grow without bound.[4]docsRocksDB - Compaction and tuning guide
That is a write stall, and it is a deliberate design decision - the same backpressure argument as any other bounded queue. The alternative is unbounded memory growth and an out-of-memory kill.
Press Stall compaction in the widget. Levels back up, then the memtable fills, then writes stop. The safety property checked underneath confirms the memtable never exceeds its bound; the system pushes back rather than buffering.
Where the Bloom filters come in
A read that finds nothing still has to prove it, which means checking every run that could contain the key. This is why LSM engines put a Bloom filter in front of each SSTable: a negative answer skips the file without touching it.
It is a neat illustration of how these structures compose - the filter’s one-sided error is exactly the right shape, because a false positive costs one unnecessary read and a false negative would be a correctness bug.
Leveled or tiered - side by side
The choice is not a matter of taste. Drive both from the same write rate and the scoreboard tells you exactly what each one costs.
Leveled
RocksDB default: one sorted run per level, so a read touches few files.
Tiered
Cassandra style: several runs per level, so compaction rewrites far less.
| Measure | Leveled | Tiered | Gap |
|---|---|---|---|
| Write amplification | 4.90 | 1.98 | 2.5× |
| Sorted runs to search | 3.69 | 26.6 | 7.2× |
Each level holds T times the previous one. Bigger T means fewer levels but more rewriting.
The dial
The line - when someone asks
An LSM tree buffers writes in an in-memory table, flushes it to an immutable sorted file, and then merges those files in the background so reads do not have to search an unbounded number of them. Compaction is where the cost lands: leveled compaction rewrites data roughly T times per level to keep one sorted run per level, while tiered compaction rewrites far less but leaves more runs for reads to search. Which you want depends on whether you are bound by write throughput or read latency, and getting it wrong shows up as write stalls or as reads touching a dozen files.
Recall
Loading…
Where are you with this?
Saved on this device. Sign in to keep it across devices.
Sources
Primary
- [1]
- [2]
- [3]
Secondary
- [4]