Guide

Data structures and storage engines

Compaction strategies

Why LSM trees must merge their files, how leveled compaction keeps few sorted runs at high write cost, and how size-tiered compaction keeps writes cheap at the price of more files and more disk space.

98 of 143 · 3 min read

Without compaction, an LSM tree would pile up files forever. Reads would check more and more of them, and obsolete versions and tombstones would never be reclaimed. Compaction fixes that. It reads several SSTables, merge-sorts them, keeps only the newest version of each key, drops data that tombstones cover, and writes new SSTables. Then it deletes the inputs.

Concept

Before you start: a sorted run is a set of files whose key ranges do not overlap, so reading one key touches at most one file. The compaction strategy is the rule that decides which files merge together, and when.

The strategy decides most of an engine's performance. Two families cover most real systems.

Leveled compaction

Used by LevelDB and RocksDB (its default) and available in Cassandra as LCS.

  • Each level, L1, L2 and so on, is a single sorted run. Each one has a target size 10 times larger than the level above it.
  • RocksDB's defaults are max_bytes_for_level_base = 256 MB and a multiplier of 10. That gives L1 ≈ 256 MB, L2 ≈ 2.56 GB, L3 ≈ 25.6 GB, and so on.
  • When L0 reaches 4 files (level0_file_num_compaction_trigger), they merge into L1.
  • When a level exceeds its target, the engine picks one file from it and merges it with the overlapping files in the next level down. That next level is about 10 times larger, so one file overlaps roughly 10 files below it.

The result is few sorted runs, which is good for reads, and little stale data, about 10% extra space. The cost is that every byte gets rewritten many times as it moves down. That is expensive for writes.

Size-tiered compaction

Used by Cassandra's STCS, which was its long-time default, by ScyllaDB, and in spirit by RocksDB's "universal" compaction.

  • SSTables are grouped into tiers of similar size. When a tier has enough files (Cassandra's min_threshold is 4), they merge into one file of the next size up.
  • Each byte is rewritten only about once per tier, so writes are cheap.
  • But many overlapping files of each size can exist. A read may check more files, and old versions of a key may sit in several tiers until a large merge happens.
  • A big merge temporarily needs as much free space as its inputs. Size-tiered setups can briefly need about 2× the live data size on disk, so operators keep up to half the disk free.

Two more strategies

Time-window compaction (Cassandra's TWCS) groups data by write time and never merges across windows. For time-series data that expires, whole files can be dropped at once.

Cassandra 5.0's Unified Compaction Strategy can be tuned anywhere between tiered and leveled.

Walking through it: picking a strategy

Suppose a service ingests metrics continuously and deletes them after 30 days.

  • Size-tiered keeps writes cheap, but leaves more files for reads and needs spare disk for big merges.
  • Time-window fits better, because each window expires as a whole. No merge needs to cross the window boundary.
  • Leveled would rewrite each byte many times for data that is about to expire, which is wasted work.

The right answer depends on the read pattern, the write rate and the expiry. The next page works out the write cost for leveled compaction.

Common mistakes

  • Choosing leveled compaction for a write-heavy workload by default. Its write amplification may be the bottleneck.
  • Ignoring free disk space under size-tiered. Big merges need room to write new files before the old ones are deleted.
  • Using one strategy for every table. A time-series table and a frequently updated user table have different needs.

Check yourself

  • Why does leveled compaction give fewer sorted runs to read than size-tiered? Each level is a single sorted run, so a point read touches at most one file per level.
  • Why might size-tiered need twice the live data size in free disk space? A big merge writes new files while its input files still exist, so both copies sit on disk until the merge finishes.

Key takeaways

  • Compaction merges sorted files, keeps the newest version of each key, and drops covered tombstones.
  • Leveled compaction gives few sorted runs and little wasted space, at high write cost.
  • Size-tiered compaction gives cheap writes, at the price of more files to read and temporary disk space.
  • Time-window compaction suits time-series data that expires as a whole.

Further learning

Next, see how these choices show up as write amplification and what that costs the hardware, in write amplification.

RocksDB wiki: Leveled Compaction describes the level sizes and triggers in detail.

Write amplification

The read, write and space costs every storage engine trades off, a worked example of how leveled compaction multiplies one application write into about 43 device writes, and what that does to SSD endurance.

Reads, deletes and Bloom filters

How an LSM tree checks several places to find the newest value, how Bloom filters keep that close to one disk read, why range scans are the weak spot, and how tombstones make deletes hard, including Cassandra's zombie rows.

Storage engines II: LSM trees

Write-optimized storage built from memtables, sorted immutable files and background compaction. Covers how it reads, deletes and pays for its writes, and how it compares with a B-tree.