torn-segment-journal-recovery-20261006

Answer

Done. The verified, self-contained solution is at ~/SOLUTION.md, with runnable artifacts journal_recovery.py and test_journal_recovery.py. I extracted the code back out of the markdown into a clean directory and re-ran it — 12/12 tests pass, proving the document is self-contained.

Summary

Root cause. The failure modes (torn writes, truncation, duplicates, concurrent reordering, causally-impossible-but-checksum-valid histories, unbounded growth) need orthogonal defenses. The key insight is that byte validity ≠ causal validity: a CRC-perfect record can still describe an impossible history, so you must never let a checksum decide what to apply.

The fix

1. Framed, self-validating records — magic | seq(u64) | txn(u64) | idx(u32) | flags(u32) | len(u32) | payload | crc32, with a MAX_PAYLOAD cap so a torn length field can't drive allocation.
2. Longest valid prefix per segment — a streaming scanner yields records until the first TornRecord/CorruptRecord, then stops. No speculative resync.
3. Global slot dedup on (txn, idx): identical duplicates collapse; conflicting duplicates poison the transaction.
4. Causal validation per txn: indices contiguous 0..n-1, BEGIN only at 0, strictly increasing seq, unique COMMIT as the final record — otherwise reject, never apply.
5. Exactly-once via checkpoint watermark: skip seq <= watermark; apply eligible commits deterministically by (commit_seq, txn_id).
6. Bounded memory: stream segments, buffer only post-checkpoint txns, evict lowest txn_id on overflow and purge it from the dedup index — memory is O(post-checkpoint window), independent of journal length.

Verification highlights (see §4 of the doc): torn-tail prefix recovery, exactly-once under duplicates and checkpoint replay, rejection of COMMIT-without-BEGIN and index gaps, conflicting-duplicate poisoning, 100 uncommitted txns held in ≤10 slots, independent segment tails, compaction roundtrip, streaming file input, and a 50-history randomized differential test against an oracle.

If you want the inline markdown pasted here in full (~660 lines) rather than as a file, say so and I'll print it.