Leveled Compaction (LevelDB / RocksDB)

Leveled compaction is the strategy LevelDB introduced and RocksDB inherited. It maintains a tower of levels L0, L1, L2, ... where each level (below L0) is exactly non-overlapping and roughly 10x the total size of the level above.

The Layout

L0:  [a..z] [a..z] [a..z]      <- overlapping (from memtable flushes); up to ~4 files
L1:  [a..g][h..p][q..z]        <- non-overlapping; ~10 MB total
L2:  [a..b][c..d]...[y..z]     <- non-overlapping; ~100 MB total
L3:  ...                       <- 1 GB total
L4:  ...                       <- 10 GB total
L5:  ...                       <- 100 GB total
L6:  ...                       <- 1 TB total  (LevelDB stops here)

Each level has a target size. When a level exceeds its target, compaction picks one file from that level and merges it into the overlapping files in the next level. Result: the next level grows; some bytes from the input level vanish.

The Algorithm

The merged output is split into multiple files (to stay around target file size, ~64 MB). The new files are spliced into the next level, preserving non-overlap.

Properties

• Predictable, bounded read amplification. From L1 down, at most one SSTable per level can contain a given key. With L0 = ~4 files and 6 deeper levels, worst case is 10 SSTable checks. Bloom filters knock this to ~1 disk read for misses.
• Low space amplification. A key only exists in at most 2 levels (during compaction). Steady state ~1.1x.
• Higher write amplification. With a 10x level ratio, a byte is rewritten log_10(total/L0) times. For 100 GB and L0=10MB, that's 4 levels of compaction. Plus the WAL: WA ≈ 5-10x typically.
• Smooth, fine-grained compaction. Each compaction job touches one file from level L and a few files from level L+1. No 10 GB merge storms.

L0 → L1 Special

L0 has overlapping key ranges (each file is a separate memtable flush). So L0 → L1 compaction takes ALL L0 files plus their overlapping L1 files. After this, L1+ is guaranteed non-overlapping.

L0 has its own trigger (default RocksDB: compact when 4 L0 files exist) separate from the size-based triggers for deeper levels.

Why Levels Are 10x Apart

The 10x ratio is empirical. It makes:

• Each level's total size is 10x the previous → 7 levels → 10^7 = 10 TB max.
• Write amp per level is ~10 (one file from L0 gets merged with ~10 overlapping L1 files → 11x rewrite of those bytes).
• Total write amp = ~10 levels × that ratio = ~30x worst case. RocksDB's "dynamic levels" tune this down.

You can change it (RocksDB: max_bytes_for_level_multiplier). Smaller ratio = lower WA but more levels = higher RA.

Compaction Priorities

When multiple levels are over target, pick the worst:

score(L) = current_size(L) / target_size(L)
compact the level with the highest score

This naturally balances: levels that grow faster get compacted more often.