A log-structured merge tree makes a deliberate bargain. It turns random writes into sequential ones by buffering updates in memory, flushing them as immutable sorted runs, and putting off the expensive work of organization to a background process. That process is compaction. Nearly every performance property of an LSM-based store, including RocksDB, LevelDB, Cassandra, ScyllaDB and HBase, is determined by how compaction is designed.

Three quantities define the design space. Write amplification is the ratio of bytes written to storage to bytes written by the application. Read amplification is the number of sorted runs, or I/Os, that a lookup must consult. Space amplification is the ratio of physical storage consumed to the logical size of live data. The RUM conjecture, set out by Athanassoulis and colleagues, formalizes a familiar intuition: no access method can minimize read overhead, update overhead and space overhead at the same time. The compaction policy is where an LSM tree chooses its position among those three costs.

This article treats compaction as one family of policies with tunable parameters, not as a menu of unrelated named strategies. First, we derive the write amplification of leveled compaction as a function of its size ratio. Next, we contrast it with the read costs of tiered compaction as implemented in RocksDB's universal mode. Finally, we examine an operational problem that the asymptotics hide. Compaction is a workload that competes for finite I/O bandwidth, and when it falls behind, the entire system stalls.

Leveled compaction, popularized by LevelDB, organizes data into levels L0 through Ln. L0 holds freshly flushed files whose key ranges may overlap. Every other level holds exactly one sorted run, split into SSTables with non-overlapping key ranges. Each level's capacity is T times larger than the one above it, where T is the size ratio. Both LevelDB and RocksDB default to T = 10.

Merging maintains this structure. When level i exceeds its target size, the engine selects a file and merges it with every file in level i+1 whose key range overlaps it. Level i+1 is roughly T times larger, and its keys span the same key space. A single file from level i therefore overlaps approximately T files below it. As a result, moving one byte down a level rewrites about T bytes of the destination level.

The bound follows directly. Let N be the total data size and B the size of the memory buffer. The number of levels is L ≈ log_T(N/B). Each byte crosses every level once and causes up to T bytes of rewrite per crossing. Write amplification is therefore O(T · log_T(N/B)). For T = 10 and N/B = 10^4, that gives four levels and a worst case near 40. On top of that come the write-ahead log and the initial flush. Measured values in production are typically lower, often 10 to 30, because overlap is rarely total.

The size ratio has a non-obvious optimum. Treat T as continuous: write amplification is then proportional to T / ln T, which is minimized at T = e, about 2.7. A smaller ratio adds levels, while a larger ratio inflates the cost of each merge. Few deployments run near T = 3, however, because read and space costs push in the opposite direction. More levels mean more filters to probe on every lookup and more runs to merge in every range scan. Space amplification, meanwhile, approaches 1 + 1/T, which is about 1.11 at T = 10.

That space bound is leveled compaction's main strength. About 90 percent of the data sits in a single sorted run at the last level, so the number of obsolete versions is bounded and their space is reclaimed promptly. RocksDB's dynamic level sizing strengthens this guarantee by deriving level targets from the actual size of the last level rather than from fixed constants. This keeps the effective ratio accurate as datasets grow or shrink. The cost is paid entirely in write bandwidth and, on flash devices, in reduced endurance.

Takeaway

Leveled compaction buys bounded space and cheap reads by rewriting each byte roughly T times per level. The size ratio is the lever that trades write bandwidth against the depth of the tree.

Tiered compaction reverses the trade. Instead of keeping one sorted run per level, each level accumulates up to T runs of similar size. When the count reaches T, all of them are merged into a single run, which is promoted to the next level. Runs merge only with peers of similar size and never with a larger resident run. This one structural change rearranges every amplification factor.

Write amplification drops accordingly. Each byte is rewritten once per level, giving O(log_T(N/B)), a factor of T lower than leveling at the same size ratio. For this reason, tiered designs such as Cassandra's size-tiered strategy and RocksDB's universal compaction are preferred for ingest-heavy workloads. Typical examples include time-series data, event logs and write-dominated caches, where sustained throughput matters more than lookup latency.

Reads absorb the difference. A lookup may now need to consult up to T runs per level, so worst-case read amplification grows to O(T · log_T(N/B)) sorted runs. Bloom filters hide much of this cost for point queries. At roughly 10 bits per key, each filter has a false positive rate near 1 percent, and the expected wasted I/O for an absent key is the sum of those rates across all runs. Range scans get no such protection. Every run must be sought and merged through a heap, so short-scan latency degrades almost linearly with the number of runs.

RocksDB's universal compaction refines the basic scheme. Runs are ordered by age, and two conditions trigger a merge. The first is a size-ratio check, which merges consecutive runs of comparable size. The second is a space amplification check, governed by max_size_amplification_percent. It forces a full merge when the newer runs grow too large relative to the oldest one. This second check exists specifically to control the hidden cost of tiering.

That hidden cost is space. Obsolete versions of a key can persist across several runs until those runs finally meet in a merge. A full compaction also needs room for its inputs and its output at the same time, which can temporarily double the disk footprint. Hybrid designs address this. In the Dostoevsky work, Dayan and Idreos propose lazy leveling, which applies tiering to the upper levels and leveling only at the last. It keeps most of tiering's write savings while retaining leveling's space bound where most of the data actually lives.

Takeaway

Tiering is not a cheaper LSM tree; it moves the cost somewhere else. The write savings are paid for in extra runs, which Bloom filters hide from point lookups but never from range scans or disk usage.

Amplification bounds describe steady-state cost, but compaction is also a scheduling problem under contention. The core constraint is simple. If the application ingests data at rate R and the policy imposes write amplification W, the device must sustain R · W bytes per second of background writes, plus the matching reads. When R · W exceeds the available bandwidth, compaction debt accumulates without bound. No amount of tuning can repay debt that the hardware cannot service.

LSM engines respond with backpressure. RocksDB measures debt through the number of L0 files and the estimated bytes of pending compaction. When L0 reaches level0_slowdown_writes_trigger, 20 files by default, foreground writes are deliberately delayed. At level0_stop_writes_trigger, 36 files, they halt entirely. Similar soft and hard limits apply to pending compaction bytes and to the number of unflushed memtables. These write stalls are not failures. They are admission control: without them, read amplification in L0 would grow without limit.

The opposite risk is compaction starving the foreground. Background merges issue large sequential I/O, which lengthens queueing delays for latency-sensitive reads. Token-bucket rate limiters cap compaction throughput to prevent this. RocksDB's auto-tuned limiter goes further, adjusting its own rate based on how often requests are being throttled. The tension cannot be eliminated. Throttle too aggressively and debt builds until stalls arrive. Throttle too little and p99 read latency suffers all the time.

Prioritization decides which debt gets paid first. RocksDB gives each level a score: its size relative to its target, or, for L0, its file count relative to the compaction trigger. The level with the highest score is compacted next. Research systems go further. SILK, presented at USENIX ATC 2019, observed that latency spikes occur when flushes and L0-to-L1 compactions queue behind long-running merges at deeper levels. SILK gives priority to flushes and L0-to-L1 compactions and preempts deeper merges when needed. It also shifts bandwidth toward compaction when client load is low, which substantially reduces tail latency.

The broader lesson is that compaction must be scheduled against the shape of the load, not its average. In bLSM, Sears and Ramakrishnan introduced a spring-and-gear scheduler that paces merges at each level so progress stays proportional across the tree. This smooths latency instead of letting work arrive in bursts. In RocksDB, subcompactions split a single large merge into parallel pieces by key range, shortening the window during which a level is blocked. Each of these mechanisms gives up some peak efficiency in exchange for predictability.

Takeaway

Write amplification multiplied by the ingest rate is a bandwidth budget the device must honor. A write stall is what happens when a system enforces that budget late rather than early.

Compaction strategies are best understood as points in a continuous design space, not as separate alternatives. Leveling and tiering are the two extremes of a single parameter: how many runs a level may hold before it merges. The size ratio then scales the trade-off within each.

Three principles follow from this analysis. First, choose the policy from the workload's mix of writes, point reads and range scans, because Bloom filters offset tiering's cost for only one of these. Second, treat write amplification multiplied by the ingest rate as a hard bandwidth budget. Third, schedule compaction by urgency, paying the debt that blocks the foreground before the debt that merely accumulates.

Lamport's insistence on stating invariants precisely applies here as well. An LSM tree is correct by construction. It performs well only when its compaction invariant is maintained at a rate the hardware can sustain.