go-btree-latch-crabbing-concurrent-scan-consistency
Done. The verified, self-contained solution is written to ~/btree/SOLUTION.md (37 KB), with the runnable code in btree.go and btree_test.go.
cur then next can duplicate a key (split inserts a node it later visits) or miss one (next is left-merged behind it). "Release-then-lock" is not enough — a borrow can steal the next leaf's min into an already-visited leaf.t.root lets a reader grab the old root and descend into a stale subtree.maxKeys=7, minKeys=3 (2*minKeys+1 == maxKeys), no operation ever revisits an ancestor.next read latch before releasing cur. Since splits/left-merges need cur write, and right-merges keep next alive, a key present for the whole scan is reported exactly once and keys arrive strictly increasing.go test -race)--- PASS: TestBasicSequential (invariant after every op, full drain)
--- PASS: TestRandomizedModel (60k ops, tiny+large keyspace)
--- PASS: TestScanOrderAndBounds
--- PASS: TestConcurrentStress (300 rounds, mutators + scanners, invariants each round)
--- PASS: TestConcurrentScanNoMiss (8 scanners x 800 scans vs boundary churn)
--- PASS: TestChurnSmallKeyspace (constant merges + root collapse under 20k scans)
ok btree 8.189s
Also passes -count=3 and GOMAXPROCS=1,2,4,8. The invariant checker validates sorted keys, occupancy bounds, equal leaf depth, children==keys+1, separator routing, and that the physical next chain matches the in-order leaf traversal. No races, deadlocks, missed keys, or duplicates.
# Evidence - Problem class: go-btree-latch-crabbing-concurrent-scan-consistency - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-16T10:28:18.934Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Build a concurrent B+tree index in Go that uses latch crabbing (coupling) for point reads, inserts, and deletes, with correct deadlock avoidance when a node must be split or merged with a sibling reachable only through the parent. Concurrent range scans must observe a consistent key ordering: a scanner may not miss a key that was present for the entire scan nor return a key twice, even while other goroutines split and merge nodes mid-scan. The implementation must pass a race-detector stress test that interleaves thousands of inserts, deletes, and full-range scans while verifying the tree invariants and a monotonic scan output after every batch.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-btree-latch-crabbing-concurrent-scan-consistency", "provider": "openrouter", "solved_at": "2026-09-16T10:28:18.934Z", "version": "1.26"}Done. The verified, self-contained solution is written to ~/btree/SOLUTION.md (37 KB), with the runnable code in btree.go and btree_test.go.
cur then next can duplicate a key (split inserts a node it later visits) or miss one (next is left-merged behind it). "Release-then-lock" is not enough — a borrow can steal the next leaf's min into an already-visited leaf.t.root lets a reader grab the old root and descend into a stale subtree.maxKeys=7, minKeys=3 (2*minKeys+1 == maxKeys), no operation ever revisits an ancestor.next read latch before releasing cur. Since splits/left-merges need cur write, and right-merges keep next alive, a key present for the whole scan is reported exactly once and keys arrive strictly increasing.go test -race)--- PASS: TestBasicSequential (invariant after every op, full drain)
--- PASS: TestRandomizedModel (60k ops, tiny+large keyspace)
--- PASS: TestScanOrderAndBounds
--- PASS: TestConcurrentStress (300 rounds, mutators + scanners, invariants each round)
--- PASS: TestConcurrentScanNoMiss (8 scanners x 800 scans vs boundary churn)
--- PASS: TestChurnSmallKeyspace (constant merges + root collapse under 20k scans)
ok btree 8.189s
Also passes -count=3 and GOMAXPROCS=1,2,4,8. The invariant checker validates sorted keys, occupancy bounds, equal leaf depth, children==keys+1, separator routing, and that the physical next chain matches the in-order leaf traversal. No races, deadlocks, missed keys, or duplicates.
# Evidence - Problem class: go-btree-latch-crabbing-concurrent-scan-consistency - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-16T10:28:18.934Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Build a concurrent B+tree index in Go that uses latch crabbing (coupling) for point reads, inserts, and deletes, with correct deadlock avoidance when a node must be split or merged with a sibling reachable only through the parent. Concurrent range scans must observe a consistent key ordering: a scanner may not miss a key that was present for the entire scan nor return a key twice, even while other goroutines split and merge nodes mid-scan. The implementation must pass a race-detector stress test that interleaves thousands of inserts, deletes, and full-range scans while verifying the tree invariants and a monotonic scan output after every batch.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-btree-latch-crabbing-concurrent-scan-consistency", "provider": "openrouter", "solved_at": "2026-09-16T10:28:18.934Z", "version": "1.26"}