Compaction

Flush after flush, SSTables pile up. Every extra file adds a probe to the read path, dead versions and tombstones hog disk, and no amount of Bloom filtering fixes a thousand-file lookup. Compaction is the background job that merges SSTables, keeping only the newest version of each key and reclaiming everything else.

Two production strategies frame the design space:

• Size-tiered (Cassandra's default): when several similar-sized files accumulate, merge them into one bigger file; tiers grow roughly exponentially (4 MB → 16 MB → 64 MB…). Low write amplification, but reads probe more files, and a merge transiently needs ~2x disk.
• Leveled (LevelDB / RocksDB): L0 files may overlap; L1 and below are partitioned into disjoint key ranges, each level ~10x larger than the one above. A lookup touches at most one file per level — better read amplification, paid for by rewriting keys again and again as they cascade down levels.

When compaction cannot keep up with the write rate, L0 piles up and the engine throttles, then blocks, writers — a write stall, the classic LSM production incident (RocksDB slows at 20 L0 files and stops at 36 by default).

When may a tombstone be dropped?

The compaction invariant: a tombstone may be discarded only when no older version of its key can survive below the output. Drop it too early and an ancient value resurrects. Your exercise merges all files into one, so the output is always the bottom of the world — every tombstone can be dropped, taking the key it killed with it. Partial (leveled) compactions do not get that luxury; they must carry tombstones downward until the bottom level.

The merge, concretely

Emit one new sorted file containing the survivors, delete the old files, and give the new file the next unused id — file numbering never resets. Merge files 0, 1, 2 and the output is file 3.

Edge cases the tests actually exercise

• Every key tombstoned → the compacted file is still created, holding zero entries, and still appears in SSTABLES as SSTABLE 1: keys=0 first= last= — first= and last= печать with empty values, one space apart.
• COMPACT with zero SSTables still creates one empty output file: COMPACTED 0 -> 1 (0 entries).
• The count word is always entries, even for one: COMPACTED 1 -> 1 (1 entries).

Your exercise

Add COMPACT to the engine you have. The grader-caught mistakes, from the real tests: (1) newest-wins across three files — with a written as 1, 11, 111 into files 0/1/2, compaction keeps a=111, and GET a prints 111; (2) tombstone elimination — b, deleted in file 1, vanishes entirely: the visible test expects COMPACTED 3 -> 1 (3 entries) (a, c, d survive; b is gone) and GET b prints <nil>; (3) the empty edges — a bare COMPACT on a fresh store prints COMPACTED 0 -> 1 (0 entries) and SSTABLES then prints SSTABLE 0: keys=0 first= last=; skipping file creation when the input is empty fails the hidden test.