LSM Compaction: Size-Tiered and Leveled Strategies Compared

A B-tree modifies a page in place, which means every update to a leaf costs at least one random write and, once the log is counted, two. On a device where a random 4 KiB write costs far more than a sequential one, that is the dominant cost of the engine. The log-structured merge tree takes the opposite position: never modify anything in place. Writes are appended to an in-memory structure that is flushed sequentially to disk when it fills, and the resulting immutable files are merged in the background. Random writes become sequential ones, and the price is paid later, in the merges.

The structure and its three costs

An LSM tree holds data in a sequence of immutable sorted runs. The newest data lives in a memtable, an in-memory sorted structure — a skip list or a red-black tree — backed by a write-ahead log so that it survives a crash. When the memtable reaches a size threshold, it is frozen, written out as a sorted file, and replaced by an empty one. Files accumulate, and a background process merges them.

Every read must consult the memtable and then the runs, newest first, because a key may exist in several runs at different versions and the newest wins. That is read amplification: the number of files that must be consulted to answer one lookup. Because runs are sorted and each carries a compact index of its block boundaries, a lookup within a run is a binary search over the index followed by one block read; but the number of runs is what multiplies.

Write amplification is the ratio of bytes written to the device to bytes written by the user. Every flush writes the memtable once; every compaction rewrites the runs it merges. A key that is overwritten repeatedly is rewritten each time it participates in a merge.

Space amplification is the ratio of bytes stored to bytes of live data. It comes from obsolete versions still present in older runs, from tombstones that have not yet been dropped, and from the free space that a merge needs to write its output while its inputs still exist.

The three are coupled. Merging more aggressively reduces read and space amplification and increases write amplification. The strategies below are different points on that surface.

Size-tiered compaction

The simplest policy merges runs of similar size. When a level of the hierarchy accumulates enough runs of comparable size, they are merged into one run of the next size up. The invariant is that there are at most a bounded number of runs per size tier, so the number of runs a read must consult grows logarithmically with data size.

Size-tiered compaction has the lowest write amplification of the common strategies, because each byte participates in a merge only when its run is merged with runs of similar size — roughly once per tier it passes through. A run that reaches the top tier is written O(log N) times over its lifetime, where N is the number of tiers. The cost is read amplification: a read may have to consult several runs within each tier, since runs at the same tier are not disjoint in key range, and space amplification is worse because old versions can persist in a large run for a long time.

It also produces the characteristic write stall. Merges are triggered when a tier overflows, so the work arrives in bursts, and if the flush rate outpaces the merge rate the memtable fills, writes block, and latency spikes. The usual mitigation is to throttle incoming writes once the number of pending flushes crosses a threshold, which converts a latency spike into reduced throughput.

Leveled compaction

Leveled compaction, as implemented in LevelDB and its descendants, imposes a stronger invariant. The tree is divided into levels with a size ratio, typically ten: level 1 holds up to some tens of megabytes, each subsequent level holds ten times the previous. Within a level, runs are disjoint in key range — no key appears in two runs of the same level — so a lookup consults at most one run per level.

Compaction moves a run from level i into level i+1 by merging it with the overlapping range of level i+1. Because the ranges are disjoint, only a small slice of the destination level participates, typically around one run’s worth. That is what keeps write amplification bounded at roughly the level ratio times the number of levels: each byte is rewritten once per level it descends through, so with a ratio of ten and four levels the amplification is on the order of ten to twenty, plus the initial flush.

The benefit is read amplification: one run per level plus the memtable, so a lookup touches a handful of files regardless of data size. Space amplification is also low, because each level holds at most one version of each key and obsolete versions are dropped as soon as their range is compacted. The cost is that compaction rewrites a large slice of the destination level for every run that arrives, which is exactly the write amplification the size-tiered policy avoids.

# Which slice of the destination level a compaction must rewrite.
def overlap(level_runs, lo, hi):
    """level_runs is sorted by (smallest_key, largest_key)."""
    hits = [r for r in level_runs if r.largest >= lo and r.smallest <= hi]
    if not hits:
        return None
    # Expand to the full extent covered by the overlapping runs, so that the
    # output can replace them without leaving a gap in key space.
    return (min(r.smallest for r in hits), max(r.largest for r in hits))

The detail that matters in practice is the boundary expansion in that fragment. Because runs are disjoint but not adjacent, the input run’s key range may overlap several destination runs plus the gaps between them. The compaction must rewrite the entire covered span, gaps included, or the destination level would acquire a range that no run covers and the disjointness invariant would break. The size of the rewrite therefore depends on how fragmented the destination level’s runs are, which is why a level whose runs are large and contiguous compacts far more cheaply than one fragmented by many small runs.

Hybrid and tiered variants

RocksDB exposes both policies and a hybrid: the newest levels use leveled compaction, where read amplification matters most because the data is hot, and the oldest levels use tiered compaction, where the data is cold and read amplification is amortized over large scans. The hybrid is a deliberate concession that the three amplifications are not equally important at every depth.

A second variant defers the merge of the topmost runs, on the theory that the newest data is the most likely to be overwritten again, so merging it now is wasted work. This is the tiered or stacking idea and it trades a higher read amplification on recent keys for a lower write amplification on update-heavy workloads.

Tombstones and the deletion problem

A delete cannot remove a key from an older run without rewriting that run, so it writes a tombstone: a marker recording that the key is deleted as of this sequence number. The tombstone shadows older versions, and a read that finds the tombstone stops. Only when a compaction merges the tombstone with the run containing the last live version may both be dropped.

The consequence is that a range delete over a large key space produces a proportional number of tombstones, all of which must be carried through every level before they disappear. A workload that inserts and deletes the same keys in a loop accumulates tombstones at the rate of the writes and can show space amplification well above the live data size until compaction catches up. Some engines special-case range tombstones — a single record covering a key interval — precisely to avoid writing one marker per key.

Tombstones also interact with snapshots. A tombstone cannot be dropped while a snapshot exists that predates it, because that snapshot must still see the older version. Long-lived read snapshots therefore pin obsolete data in place and inflate space amplification for as long as they are held.

Where the log fits

The memtable is backed by a write-ahead log so that a crash does not lose the unflushed portion. Each write is appended to the log and inserted into the memtable; the log is flushed only at points where the memtable is known to be durable, which is when its sorted file has been written. Group commit works the same way as in a page-oriented engine: one flush covers every write that arrived before it. The log’s own write amplification is one sequential write per user write, which is the floor that no strategy can go below — the same floor described in write-ahead log record ordering.

Recovery replays the log into a fresh memtable. Because the log is append-only and the memtable is a sorted structure, replay is a sequence of insertions, and the log may contain the same key many times; the final state is determined by the last occurrence, so replay is idempotent in effect even though it is not idempotent per record.

Choosing between them

The decision reduces to which amplification the workload can least afford. A write-heavy ingestion workload with rare reads prefers size-tiered or tiered compaction: the write amplification of leveled compaction, on the order of ten to twenty times the user bytes, is paid on every byte ingested, while the extra read amplification is paid only on the occasional query. A read-heavy workload with steady updates prefers leveled compaction: the read path’s predictability matters more than the background write cost, and the low space amplification keeps the working set closer to cache.

A mixed workload usually ends up with leveled compaction in the hot levels and tiered in the cold ones, plus a throttle that keeps compaction from falling behind. The metric that predicts trouble is not the amplification ratios but the ratio of compaction debt to compaction throughput: once the merge rate cannot keep up with the flush rate, every strategy converges on the same behaviour, which is to stop accepting writes. The full accounting, from the memtable flush through the device’s own garbage collection, is in write amplification across the storage stack, and the page-oriented alternative whose costs it avoids is described in B-tree page splits.