Notesstorage🌱 seedling

Compaction

Also: LSM Compaction · Leveled Compaction · Size-Tiered Compaction · Universal Compaction

The background process in an [[LSM-Tree]] that merge-sorts [[SSTable]]s into new ones, keeping only the newest version of each key and dropping tombstones. The strategy for which files to merge sets the balance between write, read and space amplification.

Why it exists

Without it, files pile up: reads check ever more of them, and overwritten or deleted values waste disk forever.

How it works

  • Merging sorted files is a streaming merge, like the merge step of merge sort: sequential reads in, sequential writes out.
  • Leveled: L0 holds fresh, overlapping flushes; each lower level is one sorted run of non-overlapping files, about 10× the size of the level above. A level over its target merges a file into the overlapping range of the next.
  • Size-tiered (universal): wait for several files of similar size, merge them into one bigger file.
  • A tombstone can only be dropped once no older file below could still hold the key.

Trade-offs

Leveled Size-tiered
Write Amplification high (often over 10×) low
Read amplification ≈ one file per level many overlapping files
Space amplification ≈ 10–14% up to 2× during big merges

In practice

  • RocksDB defaults to leveled, and since 8.4 sizes levels from the bottom up so about 90% of data sits in the last level.
  • Cassandra defaults to size-tiered; 5.0 added a Unified Compaction Strategy, now recommended, that can behave like either.

Pitfalls

  • Compaction debt: if writes outpace compaction, L0 grows, reads slow and the engine stalls writes on purpose. Monitor pending-compaction bytes.
  • Size-tiered needs free disk headroom for the largest merge.
  • Not the same as Kafka's Log Compaction, which keeps the latest value per key in a log but has no levels.

Recall

These cards are also in your review deck, scheduled with spaced repetition.