go-lsm-compaction-split-atomic-publish
Done. Here's the summary of the diagnosis and the verified solution.
~/go-lsm-compaction-split-atomic-publish/ — a complete Go 1.26 module (zero external deps):
| File | Purpose |
|---|---|
SOLUTION.md |
Self-contained solution: title, root-cause analysis, exact fix (code), verification with real output |
lsm.go |
SSTable, versioned MVCC Manifest, Compactor (atomic + naive paths), proving Reader, invariants |
lsm_test.go |
5 tests including concurrent -race stress tests |
main.go |
Runnable before/after demonstration (go run .) |
An LSM compactor splits one L-run into many L+1 SSTables. Readers only see the versioned manifest, and if each output table is published in a separate manifest commit, snapshots exist where L+1 is partial (gap → missed keys) and where adjacent L+1 tables share a boundary key (overlap → double-seen keys). It's an atomicity bug in the manifest interface, not a sizing bug.
Atomic publish — remove the L inputs and add all L+1 outputs inside one Manifest.Install (one version = one linearization point; no intermediate version exists), plus InstallChecked (validateVersion) that refuses to publish any version with a per-level overlap or an uncovered key, and a proving reader that runs a full-universe scan on every snapshot it pins.
go vet / go build cleango test -v ./... — all 5 pass: naive publisher → reader sees 5500 gapped keys + 8 overlaps; atomic publisher → 1 commit, 0 gaps, 0 overlaps; guard refuses bad publishesgo test -race ./... and -count=2 — clean (no data races), concurrent atomic scenario: 0 violations across thousands of validated snapshotsgo run . — printed before/after timeline showing the exact intermediate versions a naive publisher exposes vs. the single-version atomic swap# Evidence - Problem class: go-lsm-compaction-split-atomic-publish - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-29T10:38:52.129Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "An LSM key-value store splits a level-L run into multiple output SSTables during compaction into level L+1, while concurrent readers traverse versioned snapshots. Publishing each output table in a separate manifest commit lets readers observe overlapping or gapped key ranges across the level and miss or double-see keys. Implement the split so all output tables are published atomically in a single versioned manifest commit, and add a reader that provably never observes range gaps or overlaps during compaction.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lsm-compaction-split-atomic-publish", "provider": "openrouter", "solved_at": "2026-08-29T10:38:52.130Z", "version": "1.26"}Done. Here's the summary of the diagnosis and the verified solution.
~/go-lsm-compaction-split-atomic-publish/ — a complete Go 1.26 module (zero external deps):
| File | Purpose |
|---|---|
SOLUTION.md |
Self-contained solution: title, root-cause analysis, exact fix (code), verification with real output |
lsm.go |
SSTable, versioned MVCC Manifest, Compactor (atomic + naive paths), proving Reader, invariants |
lsm_test.go |
5 tests including concurrent -race stress tests |
main.go |
Runnable before/after demonstration (go run .) |
An LSM compactor splits one L-run into many L+1 SSTables. Readers only see the versioned manifest, and if each output table is published in a separate manifest commit, snapshots exist where L+1 is partial (gap → missed keys) and where adjacent L+1 tables share a boundary key (overlap → double-seen keys). It's an atomicity bug in the manifest interface, not a sizing bug.
Atomic publish — remove the L inputs and add all L+1 outputs inside one Manifest.Install (one version = one linearization point; no intermediate version exists), plus InstallChecked (validateVersion) that refuses to publish any version with a per-level overlap or an uncovered key, and a proving reader that runs a full-universe scan on every snapshot it pins.
go vet / go build cleango test -v ./... — all 5 pass: naive publisher → reader sees 5500 gapped keys + 8 overlaps; atomic publisher → 1 commit, 0 gaps, 0 overlaps; guard refuses bad publishesgo test -race ./... and -count=2 — clean (no data races), concurrent atomic scenario: 0 violations across thousands of validated snapshotsgo run . — printed before/after timeline showing the exact intermediate versions a naive publisher exposes vs. the single-version atomic swap# Evidence - Problem class: go-lsm-compaction-split-atomic-publish - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-29T10:38:52.129Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "An LSM key-value store splits a level-L run into multiple output SSTables during compaction into level L+1, while concurrent readers traverse versioned snapshots. Publishing each output table in a separate manifest commit lets readers observe overlapping or gapped key ranges across the level and miss or double-see keys. Implement the split so all output tables are published atomically in a single versioned manifest commit, and add a reader that provably never observes range gaps or overlaps during compaction.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lsm-compaction-split-atomic-publish", "provider": "openrouter", "solved_at": "2026-08-29T10:38:52.130Z", "version": "1.26"}