Size-Tiered Compaction (Cassandra)

Size-Tiered Compaction (Cassandra)

Size-tiered compaction (STCS) is the simplest compaction strategy an LSM tree can implement, and it's the default strategy in Cassandra (and an option in ScyllaDB and RocksDB). The idea: don't reorganize data by key range at all — just group SSTables of roughly the same size together and merge them when there are enough of them.

The core rule

Maintain the invariant: compact when you have at least MIN (typically 4) SSTables of similar size. "Similar size" is defined by a ratio bucket — two files are in the same bucket if neither is more than some factor (commonly 2x) larger than the other. When a memtable flush produces a new small SSTable, it starts in the smallest bucket. Once four small files pile up, they merge into one file that's roughly 4x bigger — which then becomes the seed of the next size tier. Repeat, and you get exponentially growing tiers: a handful of tiny files, fewer medium files, even fewer large files.

bucket(s) = every file f such that s/2 <= f <= 2*s

This is why it's called "tiered" — files naturally sort themselves into geometrically-spaced size classes without you ever telling the system what the tiers should be.

Why this trade-off

• Write amplification is low. Each byte gets rewritten only O(log n) times as it graduates tier to tier, and STCS never has to touch files outside the bucket being merged.
• Read amplification and space amplification are high. Because merges are triggered by size, not key range, a single key can be scattered across one file per tier — a point read may need to probe every tier (Bloom filters help, but don't eliminate the cost). Worse, because compaction only happens when 4 similar-sized files accumulate, a table with mostly-static data can sit with 2-3 stale, overlapping files indefinitely, each still holding tombstones and overwritten versions — driving space amplification up. This is the classic Cassandra "too many sstables" pain point under low-throughput workloads.

Implementation shape

Simulating STCS means, after every flush:

1. Build "buckets" — for every candidate file size (checked largest-first, per your spec), collect all files within the 2x ratio window of it.
2. If any bucket has >= MIN files, compact all of them (not just 4) into a single new file whose size is their sum.
3. Repeat, since a newly created (larger) file might now complete a different bucket, and it's possible for multiple rounds of compaction to cascade from a single flush.

A subtlety worth internalizing: because compaction is triggered by count, not just presence-of-overlap, a bucket with only 2 or 3 similar-sized files stays untouched — this is intentional (Cassandra doesn't want to compact 2 huge files together just because they happen to be near in size; the cost/benefit only pays off once enough redundant files accumulate). Also note the largest-first policy in the exercise: when multiple buckets are eligible after a flush, you compact the largest one first, since letting large tiers back up is the more damaging failure mode (they represent the most bytes of amplified reads/space).

Building this simulator gives you the exact bucketing and cascading logic a size-tiered compactor runs on every flush — the same logic, just without the disk I/O.