python-sstable-overlap-tombstone-compaction-proof

Answer

The solution is complete, saved at ~/compaction/SOLUTION.md, and independently verified by extracting its code blocks into a clean directory and re-running the full test suite.

Summary

Root causes found (all reproduced by the tests):

1. Tombstone elision resurrects sibling L0 data — a compaction may read a tombstone + a lower-level value while leaving an overlapping sibling table that holds an older value. The bottommost test must scan every level, not just deeper ones.
2. Bottommost must use the full expanded output range — a next-level table pulled in can widen the key range into a sibling source-level table. Testing only the original source window wrongly elides a needed tombstone.
3. Snapshot pinning — the minimal safe retention set is {newest} plus {newest version ≤ S for each pinned snapshot S}.
4. Crash mid-step — a step must commit atomically only after all output files are durable; partial outputs are orphans and recovery discards them.

The fix (in planner.py): - retained_versions: exact snapshot retention + guarded tombstone elision. - _bottommost: checks all levels over the full expanded input range. - generate_candidates: iteratively expands next-level overlaps to a fixed point; feasibility is fan_in·read_buffer + write_buffer ≤ memory_cap. - Greedy selection by minimum output_bytes / input_bytes (write amplification). - Step carries per-output SHA-256 checksums; apply_plan re-derives and verifies them; simulate_crash_recovery proves recovery at every output-file boundary.

Verification results:

PASS tombstone_no_resurrect
PASS bottommost_tombstone_drop
PASS snapshot_needs_old_version
PASS memory_cap_tradeoff steps_low=2 wa_low=0.400 steps_high=1 wa_high=0.250
PASS output_range_widening_regression
PASS crash_at_every_boundary checks=9 steps=2
PASS large_random_fuzz trials=200
ALL CHECKS PASSED

Plus ad-hoc stress runs: 6000 randomized differential trials across 20 seeds and 4019 randomized crash-boundary recoveries over 400 plans — all preserved the MVCC view exactly.

Files: - ~/compaction/SOLUTION.md — full write-up (title, root-cause analysis, complete code, verification) - ~/compaction/planner.py — implementation - ~/compaction/test_planner.py — proof harness

Run it with:

cd ~/compaction && python3 test_planner.py

The markdown is self-contained: extracting its two python code blocks into a fresh directory and running the harness reproduces ALL CHECKS PASSED.