go-btree-page-split-merge-undo
Done. The solution is delivered at ~/SOLUTION.md (self-contained), with the verified implementation in ~/btree/ and the full test suite passing.
Root cause: A B+ tree mutation spans many 4 KiB pages (splits, merges, redistributes, root-pointer changes, bitmap allocations), and none of those in-place writes is atomic. A torn page or a crash between any two page writes leaves a mixed, unrecoverable state. Guided by Verify(), a strict invariant checker, my own implementation exposed two additional subtle bug classes beyond the crash protocol itself:
keys[i] (min of right subtree) stale → tree ordered but internally inconsistent.seq=0; the monotonic-seq validation then rejected the in-flight undo record and skipped its rollback (silent corruption).The fix: a write-ahead undo log of full pre-mutation page images with commit records: - every mutation captures pre-images of all pages it will touch, fsyncs the undo record, writes pages, fsyncs data, then fsyncs a commit record; - recovery validates each record (length, CRC-32, monotonic seq, page bounds), rolls back uncommitted mutations newest-first by whole-page overwrite (idempotent — a torn page or interrupted recovery converges on re-run), fsyncs, then truncates the log to a bare header; - plus root-split growth, underflow merge/redistribute/root-shrink, and separator repair on delete.
Verification: 12 tests all pass (go test -v), also under -race -count=2, including a 500-mutation random crash loop (2/3 crash probability at each protocol step), torn writes to superblock/bitmap/leaf/log, torn commit vs undo records, interrupted-recovery idempotence, corrupt-log-tail truncation, root-split growth to height ≥ 2, and full shrink-to-empty via merges. As a final check, I extracted the code embedded in SOLUTION.md into a clean directory — it builds and passes on its own, so the document is directly usable.
# Evidence - Problem class: go-btree-page-split-merge-undo - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-30T23:23:07.701Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an on-disk B+tree with fixed 4KB pages whose split and merge operations are made crash-consistent with an undo log of pre-mutation page images, so a crash or torn write between two mutations is recoverable to the last consistent state. Include root-split tree growth, underflow merge/redistribute, and a recovery pass that validates undo records and rolls back torn mutations idempotently; keys and values are 8-byte integers.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-btree-page-split-merge-undo", "provider": "openrouter", "solved_at": "2026-08-30T23:23:07.701Z", "version": "1.26"}Done. The solution is delivered at ~/SOLUTION.md (self-contained), with the verified implementation in ~/btree/ and the full test suite passing.
Root cause: A B+ tree mutation spans many 4 KiB pages (splits, merges, redistributes, root-pointer changes, bitmap allocations), and none of those in-place writes is atomic. A torn page or a crash between any two page writes leaves a mixed, unrecoverable state. Guided by Verify(), a strict invariant checker, my own implementation exposed two additional subtle bug classes beyond the crash protocol itself:
keys[i] (min of right subtree) stale → tree ordered but internally inconsistent.seq=0; the monotonic-seq validation then rejected the in-flight undo record and skipped its rollback (silent corruption).The fix: a write-ahead undo log of full pre-mutation page images with commit records: - every mutation captures pre-images of all pages it will touch, fsyncs the undo record, writes pages, fsyncs data, then fsyncs a commit record; - recovery validates each record (length, CRC-32, monotonic seq, page bounds), rolls back uncommitted mutations newest-first by whole-page overwrite (idempotent — a torn page or interrupted recovery converges on re-run), fsyncs, then truncates the log to a bare header; - plus root-split growth, underflow merge/redistribute/root-shrink, and separator repair on delete.
Verification: 12 tests all pass (go test -v), also under -race -count=2, including a 500-mutation random crash loop (2/3 crash probability at each protocol step), torn writes to superblock/bitmap/leaf/log, torn commit vs undo records, interrupted-recovery idempotence, corrupt-log-tail truncation, root-split growth to height ≥ 2, and full shrink-to-empty via merges. As a final check, I extracted the code embedded in SOLUTION.md into a clean directory — it builds and passes on its own, so the document is directly usable.
# Evidence - Problem class: go-btree-page-split-merge-undo - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-30T23:23:07.701Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an on-disk B+tree with fixed 4KB pages whose split and merge operations are made crash-consistent with an undo log of pre-mutation page images, so a crash or torn write between two mutations is recoverable to the last consistent state. Include root-split tree growth, underflow merge/redistribute, and a recovery pass that validates undo records and rolls back torn mutations idempotently; keys and values are 8-byte integers.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-btree-page-split-merge-undo", "provider": "openrouter", "solved_at": "2026-08-30T23:23:07.701Z", "version": "1.26"}