Under the Hood: Garbage Collection for Storage Engines
Because LSM-trees never overwrite data in place, updates and deletes create duplicate entries and tombstones that accumulate across SSTable files. Without maintenance, disk space would grow indefinitely and read performance would degrade catastrophically. Compaction is the background merge-sort process that reconciles versions, purges tombstones, and reorganizes data.
Size-Tiered Compaction (STCS) vs Leveled Compaction (LCS)
flowchart TD
subgraph STCS ["Size-Tiered Compaction (Cassandra Style)"]
T1["SSTable A (~100MB)"]
T2["SSTable B (~100MB)"]
T3["SSTable C (~100MB)"]
T4["SSTable D (~100MB)"]
T1 & T2 & T3 & T4 -->|"Merge Sort"| LargeT["New Single SSTable (~400MB)"]
end
subgraph LCS ["Leveled Compaction (RocksDB Style)"]
L0S["L0: Overlapping Files"] -->|"Compaction"| L1S["L1: 10MB Non-Overlapping Files (Total: 10MB)"]
L1S -->|"10x Growth"| L2S["L2: 10MB Non-Overlapping Files (Total: 100MB)"]
L2S -->|"10x Growth"| L3S["L3: 10MB Non-Overlapping Files (Total: 1GB)"]
end
Compaction Strategies Compared
| Metric | Size-Tiered Compaction (STCS) | Leveled Compaction (LCS) |
|---|---|---|
| Algorithm | Triggers when N SSTables of similar size accumulate in a tier. Merges them into one larger SSTable. | Each level L has a fixed capacity (10× Lprev). Merges an SSTable from L into overlapping SSTables in L+1. |
| Write Amplification | Low (~4x - 8x): Data is rewritten fewer times during its lifecycle. | High (~10x - 30x): Data is rewritten repeatedly at each level down to the base tier. |
| Space Amplification | High (Up to 100%): Requires 50% free disk headroom to perform merges of giant files. | Low (~10% - 20%): Non-overlapping levels guarantee minimal redundant versions. |
| Read Performance | Moderate: Point reads must probe multiple overlapping SSTables in each tier. | Exceptional: Non-overlapping files guarantee a key exists in at most ONE SSTable per level below L0 (L0 files overlap and may all need checking). |
Worked example: what amplification costs in hardware
A service ingests 50 MB/s of new data into a leveled LSM with a size ratio of 10 and 5 levels.
- Each level merge rewrites the incoming data plus the overlapping part of the next level, which with a ratio of 10 costs up to about 10 bytes written per byte moved down. Across levels, practical leveled write amplification is typically quoted around 10-30x.
- At 20x, the device absorbs 1 GB/s of writes, around 86 TB per day. A drive rated for 1 drive-write-per-day at 7.68 TB would wear out many times faster than rated, which is why write-heavy clusters use tiered or hybrid compaction, bigger memtables, or key-value separation (BlobDB, WiscKey).
- With size-tiered compaction at 4 files per tier, each byte is rewritten about once per tier, so perhaps 4-6x total, but a point read may probe several overlapping files per tier and space can temporarily double during large merges.
Strategy map
| Strategy | Write amp | Read cost | Space amp | Default in |
|---|---|---|---|---|
| Leveled | High | Low: at most one file per level below L0 | About 1.1x | RocksDB, ScyllaDB and Cassandra option LCS |
| Size-tiered | Low | Higher: several runs per tier | Up to 2x during merges | Cassandra (STCS) |
| Universal (RocksDB tiered) | Low to moderate | Moderate | Can reach 2x | RocksDB option |
| Time-window | Low for time series | Good for recent windows | Low if data expires by TTL | Cassandra TWCS for time series |
| Lazy leveling (Dostoevsky) | Tiered on upper levels | Leveled on last level | Low | Research, influenced hybrid designs |
Failure modes
- Write stalls: when L0 file counts or pending compaction bytes exceed limits, RocksDB slows and then stops writes.
- Compaction debt after bulk loads: read latency stays poor until the backlog clears; ingest pre-sorted files instead.
- Tombstone thresholds: Cassandra warns at 1,000 tombstones scanned per query and fails the query at 100,000 by default.