Write amplification & compaction

The idea

Databases like RocksDB, LevelDB, and Cassandra use an LSM-tree (log-structured merge tree). To make writes fast, they never overwrite data in place. A new write lands in memory and an append-only log, then gets flushed to an immutable sorted file (an SSTable) at the top level.

The catch: those files pile up, so a background process called compaction keeps merging and rewriting them down through the levels. L0 into L1, L1 into L2, and so on. Every merge rewrites bytes that were already on disk. By the time a single 1 KB user write settles into the deepest level, the disk may have physically written it ten, twenty, even thirty times. That ratio, physical bytes written ÷ logical bytes written, is the write amplification factor (WAF).

How it works

Writes take a fast path into memory; the slow, expensive part is compaction running in the background. Each compaction rewrites data that is already durable on disk, which is exactly where the amplification comes from.

# LSM-tree write path (simplified)

def put(key, value):
    wal.append(key, value)        # 1 durable write (write-ahead log)
    memtable[key] = value         # in-memory only, no SSTable write yet
    if memtable.full():
        flush_to_L0(memtable)     # write a brand-new SSTable at level 0

def compact(level):
    # merge overlapping SSTables from `level` into `level + 1`
    inputs = tables_at[level] + overlapping(tables_at[level + 1])
    merged = merge_sorted(inputs)        # keep newest value per key, drop tombstones
    write_sstables(level + 1, merged)    # REWRITES data already on disk
    delete(inputs)                       # old files removed once the new ones are durable

# write amplification factor (WAF)
#   = total bytes written to disk  /  bytes the application wrote
#   = (WAL + flush + every compaction pass) / logical bytes

Cost

The core trade-off: an LSM-tree accepts high write amplification in exchange for fast sequential writes and strong compression. A B-tree does the opposite: lower write amplification, but it pays with random in-place I/O on every update.

Watch out for

• Leveled vs tiered compaction. Leveled compaction keeps space amplification low (~1.1×) but rewrites more often, raising write amplification. Tiered (size-tiered) compaction flips it: less rewriting, lower write-amp, but data sits duplicated across files, so space-amp balloons. Pick the one that matches your bottleneck.
• Write stalls. If ingest outruns compaction, L0 files stack up and the engine throttles or pauses writes until compaction catches up. A read-heavy benchmark can hide this; a sustained write burst exposes it.
• SSD wear. A WAF of 20× means the flash endurance budget drains 20× faster than the logical write rate suggests. Capacity-plan for physical writes, not logical ones.
• Latency spikes from big compactions. A large L0→L1 or deep-level merge moves a lot of data at once and competes with foreground reads for disk and CPU, showing up as tail-latency bumps.
• Measuring WAF wrong. True amplification counts the WAL plus the initial flush plus every compaction pass. Counting only one stage badly understates it.

Worked example

Follow one 1 KB key the application writes exactly once, and count the physical writes it triggers as it sinks through the tree:

The user wrote 1 KB; the disk wrote ~5 KB, so WAF ≈ 5× in this stripped-down trace. Real engines are worse: each compaction also re-reads and rewrites the overlapping data already living at the target level (the leveled fan-out, often ~10× per level), and keys get caught in several passes. That fan-out is why production write amplification commonly lands in the 10 to 30× range.

Check yourself