LSM Tree Compaction Architecture in Depth

The merge every strategy shares

Strip away the strategy names and compaction is a k-way merge of sorted runs. Each input file is sorted by key, and within a key, versions are ordered newest first by a sequence number (RocksDB) or write timestamp (Cassandra). A min-heap holds the head of each input; popping the heap yields records in global key order, so the output is sorted without ever loading a whole file into memory. Memory use is one block buffer per input plus the heap, and the work is O(N log k) for N records and k inputs.

The interesting decisions happen when the same key appears more than once. The first version popped for a key is the newest, and every older version is shadowed, so it can be dropped. A delete is written as a tombstone, a record that says the key is gone. A tombstone cannot be dropped just because it is the newest version: an older value for the same key might still live in a file that is not part of this compaction, and dropping the tombstone would resurrect it. The sketch below shows the rule in its simplest form.

import heapq

PUT, DEL = 0, 1

def merge_runs(runs, oldest_live_snapshot, is_bottommost):
    """runs: iterables of (key, seqno, kind, value), sorted by key asc, seqno desc."""
    heap = []
    for i, run in enumerate(runs):
        it = iter(run)
        rec = next(it, None)
        if rec is not None:
            heapq.heappush(heap, (rec[0], -rec[1], i, rec, it))
    last_key = None
    while heap:
        key, _, i, rec, it = heapq.heappop(heap)
        nxt = next(it, None)
        if nxt is not None:
            heapq.heappush(heap, (nxt[0], -nxt[1], i, nxt, it))
        if key == last_key:
            continue                      # an older version, shadowed by one already emitted
        last_key = key
        _, seqno, kind, _ = rec
        if kind == DEL and is_bottommost and seqno < oldest_live_snapshot:
            continue                      # nothing older can exist below, and no reader needs it
        yield rec

Two conditions guard the tombstone. is_bottommost means no file outside this compaction could hold an older value for the key; the snapshot check means no open reader still needs the pre-delete state. Real engines keep one version per live snapshot and handle merge operands, and Cassandra adds a time rule covered below, but the skeleton is the same heap merge.

The merge every strategy shares

Strip away the strategy names and compaction is a k-way merge of sorted runs. Each input file is sorted by key, and within a key, versions are ordered newest first by a sequence number (RocksDB) or write timestamp (Cassandra). A min-heap holds the head of each input; popping the heap yields records in global key order, so the output is sorted without ever loading a whole file into memory. Memory use is one block buffer per input plus the heap, and the work is O(N log k) for N records and k inputs.

The interesting decisions happen when the same key appears more than once. The first version popped for a key is the newest, and every older version is shadowed, so it can be dropped. A delete is written as a tombstone, a record that says the key is gone. A tombstone cannot be dropped just because it is the newest version: an older value for the same key might still live in a file that is not part of this compaction, and dropping the tombstone would resurrect it. The sketch below shows the rule in its simplest form.

import heapq

PUT, DEL = 0, 1

def merge_runs(runs, oldest_live_snapshot, is_bottommost):
    """runs: iterables of (key, seqno, kind, value), sorted by key asc, seqno desc."""
    heap = []
    for i, run in enumerate(runs):
        it = iter(run)
        rec = next(it, None)
        if rec is not None:
            heapq.heappush(heap, (rec[0], -rec[1], i, rec, it))
    last_key = None
    while heap:
        key, _, i, rec, it = heapq.heappop(heap)
        nxt = next(it, None)
        if nxt is not None:
            heapq.heappush(heap, (nxt[0], -nxt[1], i, nxt, it))
        if key == last_key:
            continue                      # an older version, shadowed by one already emitted
        last_key = key
        _, seqno, kind, _ = rec
        if kind == DEL and is_bottommost and seqno < oldest_live_snapshot:
            continue                      # nothing older can exist below, and no reader needs it
        yield rec

Two conditions guard the tombstone. is_bottommost means no file outside this compaction could hold an older value for the key; the snapshot check means no open reader still needs the pre-delete state. Real engines keep one version per live snapshot and handle merge operands, and Cassandra adds a time rule covered below, but the skeleton is the same heap merge.

Write, read and space amplification

Three numbers describe what any compaction strategy costs, and you cannot minimise all three at once.

Leveled compaction keeps each level as one sorted run whose target size is a fixed multiple (the fanout, commonly 10) of the level above. Moving a file from level i to level i+1 means rewriting the overlapping part of level i+1, up to roughly fanout times the bytes moved, so a byte is rewritten on the order of fanout times per level. Real workloads land under that worst case, but leveled WA in the tens is normal. In return, each level below L0 contributes at most one file to a point lookup, and with about 90 percent of data in the last level, SA stays close to 1.1.

Tiered compaction merges several similar-sized runs into one larger run, so each byte is rewritten about once per tier and WA is low. The price is more overlapping runs per read and, while the largest tier merges, SA approaching 2. Bloom filters with about 10 bits per key reject about 99 percent of files that lack a key, hiding much of the point-read cost, but do nothing for range scans.

Leveled compaction

In RocksDB's default leveled style, L0 is special. Flushed memtables land there unmodified, so L0 files can overlap each other, and a read may have to check all of them. Compaction out of L0 is triggered by file count (level0_file_num_compaction_trigger, default 4), not by size. L1 has a target size set by max_bytes_for_level_base (256 MB by default), and each deeper level's target is max_bytes_for_level_multiplier (default 10) times the one above. With level_compaction_dynamic_level_bytes, which recent RocksDB releases enable by default, the targets are computed backwards from the actual size of the last level, which keeps the 10x ratio honest as data grows.

The scheduler computes a score for each level, file count over trigger for L0 and bytes over target for the rest, and compacts the level with the highest score above 1. Within a level it picks a file, finds the files in the next level whose key ranges overlap it, merges them, and writes new non-overlapping output files cut at a target file size.

def pick_compaction(levels, cfg):
    scores = []
    l0_files = len(levels[0])
    scores.append((l0_files / cfg.l0_trigger, 0))
    for n in range(1, len(levels) - 1):
        scores.append((size(levels[n]) / cfg.target_bytes(n), n))
    score, n = max(scores)
    if score < 1.0:
        return None                               # nothing is over budget
    inputs = levels[0] if n == 0 else [pick_file(levels[n])]   # e.g. round-robin by key
    lo, hi = key_range(inputs)
    overlap = [f for f in levels[n + 1] if f.hi >= lo and f.lo <= hi]
    return Compaction(inputs, overlap, output_level=n + 1)

Leveled suits read-heavy, update-heavy and range-scanning workloads: a scan merges at most the L0 files plus one run per level.

Size-tiered compaction

Cassandra's SizeTieredCompactionStrategy (STCS) groups SSTables into buckets of similar size, by default files within 0.5x to 1.5x of the bucket average, and compacts a bucket once it holds min_threshold files (default 4), merging at most max_threshold (default 32) at a time. RocksDB's universal compaction is a close relative that reasons about the ratio between adjacent sorted runs. Both are write optimised: a row is rewritten once per tier, and tiers grow by a factor of about 4 each time.

Its weaknesses: updates to one key scatter across many runs until the large tiers merge, and merging the largest tier temporarily doubles its footprint, which is why STCS operators traditionally keep about half the disk free.

Time-window compaction

TimeWindowCompactionStrategy (TWCS) is built for time-series data written roughly in time order and expired with a TTL. It groups SSTables by the time window their data falls in, configured with compaction_window_unit and compaction_window_size (one day by default), uses size-tiered merging inside the current window, and compacts each closed window down to a single file. When every cell in a file has expired, the whole file can be dropped without being rewritten, which is far cheaper than purging expired data cell by cell.

Out-of-order timestamps, explicit deletes and repairs of old data create SSTables that span windows and cannot be dropped. Aim for a few dozen windows over the TTL, and do not mix TTL'd and non-TTL'd data in one table.

Unified and hybrid strategies

The strategies above are points on one curve, and newer engines expose the curve directly. Cassandra 5.0 added the UnifiedCompactionStrategy (UCS), whose scaling_parameters option selects behaviour per level from strongly tiered (for example T4) to strongly leveled (for example L10). UCS also shards compaction by token range so that large nodes can run many independent compactions in parallel. Cassandra 5.0 keeps STCS as the default in cassandra.yaml; the optional cassandra_latest.yaml that ships with it sets UCS with T4 as the table default. Pick the point on the curve from your read/write ratio and disk headroom, not from a strategy's name.

Tombstones and the grace period

Deletes are where compaction most often surprises people. In Cassandra a tombstone can be purged only when two things are true. First, gc_grace_seconds (ten days by default) has passed since the delete, which gives repair a chance to copy the tombstone to every replica. If a tombstone is purged before a replica that missed the delete has been repaired, the old value comes back on the next read repair. Second, no SSTable outside the compaction may contain older data for the same partition, which Cassandra checks with bloom filters and per-file timestamp ranges. A major compaction does not delete all tombstones; it deletes the ones that satisfy both rules.

Delete-heavy workloads such as queues stored in a table accumulate tombstones faster than they can be purged, and Cassandra warns and eventually aborts queries that scan too many. The fix is usually a data model change, such as time-bucketed partitions, not a compaction setting.

Compaction debt, stalls and backpressure

If ingest outruns compaction, debt accumulates: L0 files pile up and reads slow down. Engines push back on writers, because the alternative is unbounded read amplification.

Cassandra has no write stop of this kind; instead it caps compaction with compaction_throughput and concurrent_compactors, and debt shows up as a rising pending-tasks count in nodetool compactionstats and growing SSTables-per-read in nodetool tablehistograms. Throttling compaction protects foreground latency today at the cost of read amplification tomorrow, so a throttle is only safe if average compaction throughput still exceeds average ingest times write amplification.

Worked example: sizing a write-heavy store

Suppose a RocksDB-backed service ingests 20 MB/s of user data, holds 1 TB live, and runs on a volume that sustains 600 MB/s of writes. With leveled compaction, a fanout of 10 and a 256 MB L1 base, dynamic level bytes gives a last level near 1 TB and levels above it of about 100 GB, 10 GB, 1 GB and 256 MB. Counting the WAL, the flush, the move out of L0 and roughly fanout-sized rewrites at each of the four lower levels gives a worst-case WA near 40; measured values for such trees are commonly half that. Even at WA 20, 20 MB/s of user writes becomes 400 MB/s of device writes, two thirds of the volume's budget, before any reads.

Switch the same data to a tiered layout with a factor of 4 and 64 MB flushes. There are about log4(1 TB / 64 MB), roughly 7, tiers, so WA is about 9 including the WAL and flush, or 180 MB/s. Writes now fit comfortably, at the cost of reserved space and more runs per read. If reads are latency sensitive and the volume can absorb the bandwidth, stay leveled; if ingest dominates, move toward tiered.

Confirm with measurement: RocksDB reports per-level bytes written through GetProperty("rocksdb.stats"), so actual WA is flush plus compaction writes divided by user bytes ingested over the same window.

Failure modes

• Compaction debt spiral. L0 grows, each L0 to L1 compaction gets larger and slower, and debt never shrinks. Alert on L0 files and pending bytes well before the slowdown trigger.
• Out of disk during a large merge. Tiered and major compactions need room for inputs and outputs at once. Keep headroom sized to the largest possible merge, not to average usage.
• Tombstone build-up. Queue-like delete patterns produce reads that scan thousands of dead rows. Remodel by time bucket, and never lower gc_grace_seconds below your repair interval.
• TWCS windows that never drop. Out-of-order writes or repairs mix timestamps into closed windows, so files never fully expire. Check the max and min timestamps per SSTable with sstablemetadata.

What to do next

1. Measure your real write amplification from engine statistics over a full day, and compare it to the device's sustained write bandwidth.
2. Classify each table by read/write ratio, update and delete pattern, and whether data expires by time.
3. Pick leveled for read-heavy or update-heavy tables, tiered for write-heavy append data, and TWCS only for TTL'd time-ordered data; on Cassandra 5.0 consider UCS with a scaling parameter that matches.
4. Alert on compaction debt: L0 file count, pending compaction bytes or pending tasks, and SSTables per read.
5. Reserve disk headroom for the largest merge your strategy can schedule.
6. Audit delete-heavy tables for tombstone scans and confirm repair runs within gc_grace_seconds.
7. Read on: how the LSM tree itself works, LSM trees versus B-trees, bloom filters, and Cassandra's compaction strategies in practice.