Compaction: Merging SSTables

Topic Overview

Merge SSTables to Reclaim Space

Repeated flushes create overlapping SSTables. Compaction merges sorted runs, dropping tombstoned keys and reducing read amplification. Size-tiered compaction merges files of similar size; leveled compaction organizes into levels with non-overlap invariants.

Two-Way Merge

Open iterators on two sorted SSTables, compare keys, emit smaller, handle duplicates by keeping newest.

cCopy
Loading…

• Compaction IO dominates LSM write amplification
• Tombstones must survive until no older version exists
• Background threads compact while serving reads from old files
• Monitor pending compaction bytes in production systems

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will merge two SSTable files into one sorted output, resolving duplicate keys. This exercise requires keeping the newest value for colliding keys.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Write a C program that compacts one SSTable run: every input row is (key, value, seqno, tombstone), already grouped by key, and multiple rows may share a key (older versions from previous flushes).

Input (stdin):

• First line: n, the number of rows
• Next n lines: "key value seqno tomb" (tomb=1 means this row is a tombstone; rows may arrive in any order)
• Last line: dropTombstones (1 = this compaction targets the bottommost level, 0 = it does not)

Compaction rules:

• Group rows by key. For each key, only the row with the highest seqno survives (highest seqno = newest version).
• If the surviving row is a tombstone and dropTombstones=1, the key is dropped entirely, with nothing older beneath it, the delete is now complete.
• If dropTombstones=0, a surviving tombstone is kept: this compaction cannot prove no older SSTable holds the key.
• Rows are emitted in ascending key order.

Output:

• One line per surviving key: "KEEP key value seq=S" or "TOMBSTONE key" (surviving tombstone)
• One line per key fully erased: "DROP key"
• "INPUT_BYTES b" (each input row costs 16 bytes)
• "OUTPUT_BYTES b" (each surviving row costs 16 bytes)
• "RECLAIMED b" (INPUT_BYTES - OUTPUT_BYTES)
• "SURVIVED k" (number of surviving keys)