python-mvcc-temporal-index-online-vacuum
Done. The verified solution is at ~/mvcc/SOLUTION.md, with runnable artifacts alongside it.
Root causes diagnosed
1. Snapshot visibility keyed on commit time instead of an interval → long readers see later writes.
2. Vacuum driven by commit order instead of the set of active snapshots → reclaims versions a still-open old transaction needs (out-of-order completion).
3. Conflict detection limited to primary keys → phantoms/write-skew survive.
4. No snapshot-aware GC → hot-key version chains grow with update count.
5. Applying deletes-before-puts reverses intra-transaction put/delete order (a real bug the differential oracle caught).
The fix
- Every version stores [begin, end); visible iff begin <= S < end, end = ∞ = live.
- Online vacuum retention rule: keep v ⟺ v.end == ∞ or ∃ active snapshot s: v.begin <= s < v.end. Safe under out-of-order completion because it uses snapshot set, not commit order.
- Serializable OCC backward validation over point reads, scanned ranges (predicate locks), and write sets.
- Apply transaction ops in logical order.
- Result: hot-key chains bounded by |active snapshots| + 1, independent of update count.
Verification
- python3 -m unittest discover -v → 12 tests, OK.
- 11 deterministic tests cover snapshot reads, range scans, phantom aborts, vacuum watermarks, out-of-order pinning, and the skew bound (500 updates + 3 readers → ≤4 versions).
- 30 randomized trials × 300 ops compared against a brute-force oracle after interleaved commits/aborts/vacuum.
- I also extracted the code block from the markdown, compiled it, and ran a smoke test against the embedded copy — it passes, so the document is directly usable.
# Evidence - Problem class: python-mvcc-temporal-index-online-vacuum - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-04T10:06:54.055Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement an MVCC secondary index for a temporal database that supports snapshot reads, range scans, concurrent writes, and online vacuum while transactions may retain old snapshots. The design must reclaim versions safely under out-of-order transaction completion, preserve serializable range-conflict detection, and bound write amplification under skewed keys; provide invariants and complexity analysis.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-mvcc-temporal-index-online-vacuum", "provider": "openrouter", "solved_at": "2026-10-04T10:06:54.055Z", "version": "3.11"}