LSM compaction debt

What sustained write rate can an LSM store absorb, and what happens past it?

An LSM tree (log-structured merge tree) is a storage layout used by many key-value stores. Writes go first to an in-memory table (the memtable) and are flushed to sorted files on disk. Background compaction merges those files into larger sorted files at deeper levels. The trade is about time: accept writes at memory speed now, pay the merge cost later. (The files in the first on-disk level, L0, can have overlapping key ranges. Files in deeper levels do not overlap.)

Write amplification is how many bytes the disk writes for each logical byte the user writes. The sustainable logical write rate is

For leveled compaction with fanout T (each level is T times bigger than the one above) and L levels, write amplification is roughly T·L. For example 10 × 5 = 50.

Interest compounds

If writes exceed λ_max, unmerged files pile up in L0. Because L0 files overlap, a read must check all of them, and Bloom filters (small structures that say "this key is definitely not in this file") cannot skip files across them. Also, compacting overlapping files costs more than compacting disjoint ones, because more input must be read per unit of output. So debt raises read amplification and raises the cost of removing the debt. That superlinearity makes it a spiral rather than a queue.

The deliberate stall

The ending is a design choice, not a failure. When L0 reaches a file-count threshold, the engine stalls writes completely. Throughput goes from full speed to zero with nothing in between. This is bimodality created on purpose: the engine turns an unbounded latency-and-correctness problem into explicit backpressure. It chooses fail-fast over fail-degraded. It is the same move as the watchdog: destroy availability to keep state bounded and decidable. It is also metastable in the strict sense: after the write burst ends, the debt remains and the stalls continue, so the trigger and the sustaining effect are cleanly separate.

Escapes

All escapes are different positions inside the same triangle:

• Tiered compaction lowers write amplification and raises read and space amplification.
• Larger fanout reduces the number of levels but raises the cost of each compaction.
• Rate-limiting ingest below λ_max is admission control applied to writes.

Each is a position on the RUM trade-off (Read, Update, Memory amplification: improving one worsens another). This is the principle that costs are conserved (they move, they do not vanish), now with a named triangle.