Stage 4: Compaction

Objective:Merge accumulated segments, reclaim space from stale values and tombstones, and bound read amplification.

Flush enough and you drown in segments: every read scans more files, and deleted data still occupies space under tombstones. Compaction is the background job that merges segments -- keeping only each key's newest value and dropping tombstones once nothing older can resurrect the key. It's the "tree" in Log-Structured Merge-tree, and tuning it is half of operating RocksDB or Cassandra.

Implement store.compact():

• merge all segments into a single sorted segment (newest value per key wins)
• drop tombstones entirely -- after a full compaction nothing older exists, so the marker is no longer needed
• store.segments ends as [mergedSegment] (or [] if everything was deleted)
• reads must behave identically before and after

The write amplification trade-off: Compaction rewrites data. If a key is overwritten 10 times and compacted 5 times, it's been written to disk ~5 times even though the application only cared about the final value. This is "write amplification" -- the ratio of bytes written to disk vs bytes the application actually changed. RocksDB's default write amplification is 10-30x. It's the cost you pay for RAM-speed writes. Tuning compaction is tuning this multiplier.

Why tombstones can only be dropped at compaction time (not flush time): When you del("k") and flush, the tombstone must survive in the segment because there might be an older segment still holding the value of "k". Only when you compact everything together -- and no older segment can survive to hold an older value -- is it safe to drop the tombstone.

Why this matters in production

Without compaction, your Stage 3 engine slowly becomes unreadable. Every flush adds another segment; every read must scan all of them in the worst case. After 100 flushes you're scanning 100 segments per get(). Compaction is the background job that makes LSM engines practical: it merges segments, keeps only the newest value per key, and drops tombstones once no older segment can resurrect the key. This is why tuning "compaction strategy" is the first conversation in any RocksDB or Cassandra operations runbook. Level-based compaction, tiered compaction, TWCS -- these are all answers to the same question you're solving here: how many files should exist, and when do you merge them?