go-lsm-range-tombstone-compaction-shadow-proof-20261009

Answer

Done. The verified solution is at ~/lsm/SOLUTION.md (copy at ~/SOLUTION.md), with the compiling/race-clean source in ~/lsm/.

What was wrong (root causes)

1. Snapshot-blind version dropping — a version at seq s is only droppable when no pinned snapshot falls in [s, next_retained). Naïvely dropping whenever a newer version exists loses reads pinned in the gap.
2. Flat range tombstones — a tombstone's usefulness varies per key interval; it must be fragmented at tombstone boundaries, not kept/dropped whole.
3. No audit trail — silent discards can't be checked.
4. Unbounded partitioning — splitting a user key or emitting input-sized SSTables inflates write amplification.
5. Lost concurrent flushes — tearing down all runs on install drops flushes that arrived mid-plan.
6. Byte-order assumptions — ==/</map[string] break exotic comparators.

The fix

• Points: greedy newest-first with a retained barrier; keep a version iff next_retained == +inf or a pinned snapshot lies in [s, next_retained). Each drop emits ShadowProof{Lo, Hi, Shadow} pointing at a surviving record.
• Tombstones: sweep all start/end boundaries into cells, apply the same greedy per cell, coalesce adjacent retained cells into minimum fragments, and emit TombstoneDropProof for dropped cells.
• Partitioning: next-fit over whole user keys, bounded by MaxPartBytes (optimal contiguous packing).
• Concurrency: id-tagged runs; compaction removes only the ids it snapshotted, so mid-plan flushes survive.
• Comparator-neutral: every comparison goes through cmp.

Verification (all green)

$ gofmt -l .            # (empty)
$ go vet ./...          # clean
$ go test ./...         # ok
$ go test -race -count=2 ./...   # ok

The suite includes 400 randomized differential tests (compacted output vs. brute-force model across every key × pinned snapshot × current read), custom comparators, same-seq tie-breaks, tombstone-fragment chains, partition-minimality, and a 6-writer concurrent flush stress test. VerifyPlan(...) independently audits any plan for lost reads, dangling shadows, and oversized partitions.