Repository navigation
test: investigate deterministic simulation testing for concurrency #760
Description
Question
Would deterministic simulation testing (DST), especially controlled and replayable thread schedules, materially improve Minigraf's concurrency and durability coverage? Complete this investigation before the v3.0.0 release cut, on the v3 branch; this issue does not presume that a new framework should be adopted. Tracked by #383.
Context: bbtree's testing write-up uses Shuttle and ffs to exercise thousands of thread schedules and replay failures.
What Minigraf already covers
tests/concurrency_test.rsandtests/snapshot_atomicity_test.rsrace real threads and check transaction visibility, consistent query snapshots, and checkpoint interactions. The snapshot tests run for a fixed time, so the OS decides the interleavings.tests/property_test.rscompares generated histories and queries with a reference evaluator, including reopen behavior.src/storage/persistent_facts.rsusesFaultInjectingBackendto fail each page write and sync insave()and checks the reopened state at 47 failure points.tests/crash_kill_test.rsruns a seeded child workload, kills it during writes/checkpoints, and checks recovered data against a reference. It runs 5 rounds in the regular suite and 100 rounds per OS nightly. The seed reproduces the workload and chosen delay, but OS/process timing can still change the exact kill point.tests/soak_test.rsexercises longer histories, checkpoints, and reopens against a reference; its seed reproduces writes, while its time-based schedule varies.- Fuzzing and Kani proofs cover other correctness properties.
docs/TEST_COVERAGE.mdsummarizes the current test stack.
These give substantial fault, recovery, and concurrent-behavior coverage. I found no controlled scheduler (Shuttle, Loom, ffs, or equivalent) in the current test suite, so rare thread interleavings are neither systematically explored nor replayed by seed. A seeded workload alone is not DST in the sense used by the linked article.
Investigation scope
- Identify the highest-risk shared-state boundaries: transaction commit vs query snapshot, checkpoint vs query/reopen, and rule registration vs query. Check which are already serialized by locks and where schedule exploration could reveal a distinct failure mode.
- Compare a small test-only prototype using Shuttle, ffs, Loom, or explicit yield/barrier hooks. Record compatibility with Minigraf's
stdlocks, file I/O, subprocess crash tests, and native/WASM targets. Keep test dependencies out of the production binary. - Show whether the prototype can reproduce a known historical concurrency regression or a deliberately injected fault that existing stress tests do not reliably reproduce. Record the schedule/seed and the invariant checked.
- Estimate CI runtime and maintenance cost, then recommend a narrowly scoped suite, another targeted technique, or no DST adoption. Keep the existing real-OS and SIGKILL tests because a simulator cannot establish their platform behavior.
Release timing: v3.0.0
Bring the bounded investigation forward from v3.next to v3.0.0. #554 and #555 demonstrated partial-transaction visibility and inconsistent query snapshots on both release branches. The current v3 snapshot regression tests race real threads for three seconds, so passing them does not establish that a particular dangerous interleaving was exercised. v3's streaming query snapshots and copy-on-write checkpoint publication make this a useful reliability check before shipping the new engine and format.
Start with commit versus query snapshot and checkpoint publication versus an active reader/cursor. Use #554 or #555, or a deliberately injected equivalent fault, to demonstrate reproducible detection. #558 is useful historical context for checkpoint/read races, but its page-overwrite bug was v2.x-only; do not treat it as an existing v3 defect.
The pre-release deliverable is the existing bounded prototype and findings, including replay evidence, coverage gained, limitations, CI cost, and an explicit adopt/defer/reject recommendation. A documented negative result satisfies the investigation; broad framework adoption or a general simulation layer is not a release requirement. Fix any data-integrity regressions discovered before release, and assess larger implementation follow-ups separately. Keep dependencies test-only and retain real-OS concurrency and SIGKILL recovery tests.
Done when
Publish a short findings document or comment with the prototype result, reproducibility evidence, coverage gained, limitations, CI cost, and a concrete recommendation. File follow-up implementation issues only if the evidence warrants them.
Philosophy fit: a test-only, focused investigation supports PHILOSOPHY.md's reliability-first and small-runtime principles; avoid adding production dependencies or a general simulation layer without a demonstrated gap.
Activity
Merge pull request #786 from project-minigraf/test/760-deterministic-…
ci: schedule v3 storage interleaving checks from main (#760) (#787)