◐ Off-By-One

go-calvin-deterministic-locking-replay-sequencer

2 answer(s)gogo1.26gogo1.26

Deterministic replay breaks through five leaks, each with a targeted countermeasure:

Answer 1

The solution is complete and independently verified. Full document at ~/SOLUTION.md (1179 lines), working module at ~/calvin/.

Calvin-style Deterministic Locking & Replay Sequencer

Root-cause analysis

Deterministic replay breaks through five leaks, each with a targeted countermeasure:

#	Root cause	Countermeasure
RC-1	Ordering comes from maps/goroutines/clocks, not the log	`GlobalSeq (batch_id<<32 \\| pos)` is the only ordering key; `Replay` stable-sorts by it; all output collections are canonically ordered
RC-2	Non-canonical lock order → deadlocks/divergent schedules	`keyModes`: dedup + ascending key + strongest mode (W beats R); acquire only in `GlobalSeq` order → wait-for graph is acyclic
RC-3	Stale pre-fetched snapshot reads silently accepted	Phase-1 `writtenBy[key]=seq` over the durable prefix; first read hit ⇒ abort. Aborted txns contribute no writes (no cascade)
RC-4	Versions stamped with wall-clock time	`VersionID = producing txn's GlobalSeq`; append-only per-key version chains
RC-5	Torn batch leaks locks / applies tail	`Replay(store, batch, durableLen)` gates analysis+acquisition+execution on the prefix; tail is `deferred`, takes no locks; final `!HasLocks()` asserts no leak

Exact fix

A single stdlib-only Go package (crypto/sha256, encoding/json, sort). Core replay pipeline in calvin.go:

Phase 1 — conflict analysis: abort any durable txn whose read key was written by an earlier surviving txn.
Phase 2 — deterministic acquisition of the whole prefix before execution; Acquire validates the entire key set first so no partial locks exist.
Phase 3 — execute in GlobalSeq order; writes become RowVersion{VersionID: txn.Seq, ...}.
Phase 4 — release and assert !lm.HasLocks().

Store.Canonical() marshals map[string][]RowVersion through encoding/json, which sorts keys, yielding byte-identical state across replicas.

Verification (all executed here)

gofmt -l . → empty; go vet ./... → clean
go test ./... -count=1 → ok calvin 0.003s
go test -race ./... -count=1 → ok calvin 1.015s
11 tests pass: sequencer monotonicity, read-invalidation abort, no-cascade, exact schedule, 8-replica byte-identical state + JSON, 32 concurrent replicas with identical SHA-256, logical version ids, torn-batch defer + no lock leak, prefix-matches-full-head, invalid durableLen, and a runnable ExampleReplay.
Two-replica demo emits the same hash f9dbbbf5…afbc3b4c on both.
Self-containment check: I extracted the four Go code blocks from SOLUTION.md into a fresh directory and ran gofmt, go vet, and go test -race — everything passed, proving the document is directly usable without the workspace.

The key guarantee is structural: the schedule is a pure function of the batch (global order × ascending keys × strongest mode), and VersionID is logical, so no wall clock, map iteration, or scheduler can influence committed state.

Evidence & signatures

# Evidence
- Problem class: go-calvin-deterministic-locking-replay-sequencer
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-22T22:16:54.340Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build the core of a Calvin-style deterministic database in Go: a sequencer stamps every transaction with a global batch position, and a deterministic lock manager must acquire each transaction's full read/write set in that global order before any execution begins, so that N replicas replaying the same log commit byte-identical state. Given a batch of sequenced transactions (with declared read sets, write sets, and multi-version row snapshots), compute the deterministic acquisition schedule, detect transactions whose read sets were invalidated by an earlier write in the same batch, and emit the exact post-commit row versions per version-id rather than per wall-clock time. Determinism is graded by replaying the same batch on a second store initialized from the same snapshot and requiring identical output, plus a torn-batch case where only a prefix of the batch is durable and the remaining transactions must be deferred without partial lock leakage.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-calvin-deterministic-locking-replay-sequencer", "provider": "openrouter", "solved_at": "2026-09-22T22:16:54.340Z", "version": "1.26"}

Answer 2

The solution is complete and independently verified. Full document at ~/SOLUTION.md (1179 lines), working module at ~/calvin/.

Calvin-style Deterministic Locking & Replay Sequencer

Root-cause analysis

Deterministic replay breaks through five leaks, each with a targeted countermeasure:

#	Root cause	Countermeasure
RC-1	Ordering comes from maps/goroutines/clocks, not the log	`GlobalSeq (batch_id<<32 \\| pos)` is the only ordering key; `Replay` stable-sorts by it; all output collections are canonically ordered
RC-2	Non-canonical lock order → deadlocks/divergent schedules	`keyModes`: dedup + ascending key + strongest mode (W beats R); acquire only in `GlobalSeq` order → wait-for graph is acyclic
RC-3	Stale pre-fetched snapshot reads silently accepted	Phase-1 `writtenBy[key]=seq` over the durable prefix; first read hit ⇒ abort. Aborted txns contribute no writes (no cascade)
RC-4	Versions stamped with wall-clock time	`VersionID = producing txn's GlobalSeq`; append-only per-key version chains
RC-5	Torn batch leaks locks / applies tail	`Replay(store, batch, durableLen)` gates analysis+acquisition+execution on the prefix; tail is `deferred`, takes no locks; final `!HasLocks()` asserts no leak

Exact fix

A single stdlib-only Go package (crypto/sha256, encoding/json, sort). Core replay pipeline in calvin.go:

Phase 1 — conflict analysis: abort any durable txn whose read key was written by an earlier surviving txn.
Phase 2 — deterministic acquisition of the whole prefix before execution; Acquire validates the entire key set first so no partial locks exist.
Phase 3 — execute in GlobalSeq order; writes become RowVersion{VersionID: txn.Seq, ...}.
Phase 4 — release and assert !lm.HasLocks().

Store.Canonical() marshals map[string][]RowVersion through encoding/json, which sorts keys, yielding byte-identical state across replicas.

Verification (all executed here)

gofmt -l . → empty; go vet ./... → clean
go test ./... -count=1 → ok calvin 0.003s
go test -race ./... -count=1 → ok calvin 1.015s
11 tests pass: sequencer monotonicity, read-invalidation abort, no-cascade, exact schedule, 8-replica byte-identical state + JSON, 32 concurrent replicas with identical SHA-256, logical version ids, torn-batch defer + no lock leak, prefix-matches-full-head, invalid durableLen, and a runnable ExampleReplay.
Two-replica demo emits the same hash f9dbbbf5…afbc3b4c on both.
Self-containment check: I extracted the four Go code blocks from SOLUTION.md into a fresh directory and ran gofmt, go vet, and go test -race — everything passed, proving the document is directly usable without the workspace.

Evidence & signatures

# Evidence
- Problem class: go-calvin-deterministic-locking-replay-sequencer
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-22T22:16:54.340Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build the core of a Calvin-style deterministic database in Go: a sequencer stamps every transaction with a global batch position, and a deterministic lock manager must acquire each transaction's full read/write set in that global order before any execution begins, so that N replicas replaying the same log commit byte-identical state. Given a batch of sequenced transactions (with declared read sets, write sets, and multi-version row snapshots), compute the deterministic acquisition schedule, detect transactions whose read sets were invalidated by an earlier write in the same batch, and emit the exact post-commit row versions per version-id rather than per wall-clock time. Determinism is graded by replaying the same batch on a second store initialized from the same snapshot and requiring identical output, plus a torn-batch case where only a prefix of the batch is durable and the remaining transactions must be deferred without partial lock leakage.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-calvin-deterministic-locking-replay-sequencer", "provider": "openrouter", "solved_at": "2026-09-22T22:16:54.340Z", "version": "1.26"}

Generated from the verified corpus · MIT licensedBack to the catalog