The question this answers
Can I capture a failing interleaving well enough to run it again on demand?
A checkout handler that intermittently double-charges: roughly one request in forty thousand, only in production, never under test.
The order record and its charged flag, read and written by concurrent retries of the same checkout; plus everything the runtime treats as an input — the scheduler's decisions, lock grant order, clock reads and network responses.
An order is charged exactly once, and a replayed execution produces the same sequence of observable operations as the recorded one.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
What has to be recorded for a replay to be faithful
A program is a deterministic function of its inputs — as long as you count *all* of them. In a concurrent program the inputs include things nobody usually thinks of as input: the order in which the scheduler ran runnable threads, which waiter a lock granted ownership to, the value returned by every clock read, the interleaving of I/O completions, the addresses returned by the allocator, the seed of every random number generator, and the responses that came back over the network.
Record those and replay becomes possible: rerun the program, and whenever it asks for one of those inputs, hand it the recorded answer instead of the real one. The program then follows the same path it followed originally, including the same disastrous interleaving. This is the Determinism: Same Input, Same Output? idea applied as a debugging tool rather than as a design property.
The table below is the checklist. Anything missing from it is a source of divergence, and divergence in a replay is not a small error — the executions separate at the first differing decision and everything after it is a different program run.
| Source | What is recorded | If omitted |
|---|---|---|
| Thread scheduling | Which runnable thread ran at each scheduling point, and for how long | The interleaving differs and the bug does not reproduce — the whole point is lost |
| Lock grant order | Which waiter received ownership at each release | A different thread wins the race; the failing schedule is unreachable |
| Clock reads | The value returned by every time query | Timeout paths and cache expiries take different branches |
| Random sources | Seeds and every drawn value | Sharding, jitter and retry backoff all diverge |
| I/O completions | Order and content of every read, response and callback | The program takes a different branch on the first differing byte |
| Atomic and CAS outcomes | Success or failure of each compare-and-swap | A retry loop iterates a different number of times, changing everything downstream |
| Memory addresses / allocation order | Addresses handed out, where behaviour depends on them | Usually harmless; occasionally decisive for hash iteration order |
The recorded failure, replayed
The schedule below is the double-charge, as recovered from a recording. Two retries of the same checkout both read charged = false, both pass the guard, and both charge. It is the classic check-then-act shape — The Atomicity Illusion — and once the recording exists it is not mysterious at all. The value of replay is entirely in getting from "one in forty thousand, in production only" to this diagram.
What replay buys beyond reproduction is *stability under observation*. Because every nondeterministic input is now supplied from the recording, adding a log line does not change the schedule: the scheduler decisions are replayed from the file, not made afresh. This directly defeats the Heisenbugs: The Bug That Leaves When You Look at It problem, and it is the single strongest reason to want this capability. You can set a breakpoint, step, inspect, and rerun the identical execution as many times as you like.
Many implementations add reverse execution on top: because the recording holds the full sequence, the debugger can step backwards from the failure to the cause. That inverts the usual search — instead of guessing where to break and running forward repeatedly, you start at the symptom and walk back.
| # | Retry 1 (worker-4) | Retry 2 (worker-11) | Payment provider | State |
|---|---|---|---|---|
| 1 | SELECT charged FROM orders WHERE id=88213 -> false | · | · | charged=false charges=0 |
| 2 | guard passes: proceed to charge | · | · | charged=false charges=0 |
| 3 | · | SELECT charged -> false | · | charged=false charges=0 |
| 4 | · | guard passes: proceed to charge | · | charged=false charges=0 |
| 5 | POST /charge (idempotency key absent) -> ok | · | · | charged=false charges=1 |
| 6 | · | · | captures 49.00 | charged=false charges=1 |
| 7 | · | POST /charge -> ok | · | charged=false charges=2 ✕ Charged exactly once. The customer has been charged twice and no error was raised anywhere. |
| 8 | UPDATE orders SET charged=true | · | · | charged=true charges=2 |
| 9 | · | UPDATE orders SET charged=true | · | charged=true charges=2 |
What it costs, and where it stops being practical
Replay is not free, and the costs are structural rather than incidental. Recording every scheduling decision means intercepting the scheduler, which typically means serializing execution onto one core or inserting a control point at every preemption — and that alone can be a large slowdown. Recording every I/O byte means storage proportional to traffic. Recording memory nondeterminism may mean instrumenting shared accesses, at which point you are paying race-detector-scale overhead as well.
The read-out below lays out the tiers honestly, because "record and replay" describes several very different things at very different prices. Application-level input recording is cheap and catches a lot; full scheduler-faithful replay is expensive and catches everything; hardware-assisted approaches sit in between and carry platform restrictions.
And there is a hard limitation worth stating plainly: recording that forces sequential execution can prevent the bug from ever occurring, because a bug that requires genuine parallelism on two cores may be unreachable in a run that interleaves on one. That is the same perturbation problem from Heisenbugs: The Bug That Leaves When You Look at It, arriving in a more expensive form. Replay is superb once you have captured the failure; it is not a guarantee that you will capture it.
TIER 1 -- INPUT REPLAY (application level) records request payloads, clock reads, RNG seeds, downstream responses misses thread scheduling, lock grant order cost a few percent; storage proportional to request volume catches logic bugs, retry bugs, anything driven by external input MISSES the interleaving. Most concurrency bugs are not reproduced. TIER 2 -- SCHEDULE REPLAY (runtime level) records every scheduling decision, lock grant, channel send/recv order misses memory-level races the runtime does not mediate cost 2x - 20x runtime; often forces single-core interleaving catches the great majority of race conditions and lost updates CAVEAT forcing one core can make true-parallel bugs unreachable TIER 3 -- FULL EXECUTION REPLAY (system level) records syscalls, signals, scheduling, and enough CPU state to re-run misses little, within its supported platform cost often 1.2x - 5x with hardware assist; large recording files catches essentially everything, including reverse stepping to the cause CAVEAT platform-restricted, and shared-memory parallelism is the hard case WHERE IT PAYS reproduction rate below ~1 in 10,000 and cost of the bug is high (money moved, data corrupted, customer-visible duplicate action) WHERE IT DOES NOT a bug that reproduces in 1 run in 20 under an existing stress harness. Just use the stress harness.
Key points
- A concurrent program is deterministic given all its inputs — including scheduling decisions, lock grants, clock reads and I/O order, which nobody normally counts as input.
- Replay converts a one-in-forty-thousand production bug into a file you can run on demand, which is the difference between weeks and an afternoon.
- Its unique property is stability under observation: log lines and breakpoints no longer move the schedule, because the schedule comes from the recording.
- Reverse execution falls out of a recording, letting you start at the symptom and walk backwards to the cause.
- It exists in tiers with wildly different costs — input replay is cheap and misses interleavings; full execution replay is expensive and catches nearly everything.
- Recording can prevent the bug: forcing interleaving onto one core makes genuinely-parallel failures unreachable. Capture is not guaranteed.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Intercept every nondeterministic source — scheduler, lock grants, clock, RNG, syscalls, I/O completions — and write the outcome of each to a log during the recorded run.
- • On replay, run the same binary with the interceptors in playback mode: each request for a nondeterministic value is answered from the log instead of from the real source.
- • Serialize scheduling decisions so the recorded order of thread execution is reimposed, which is what makes the interleaving reproduce.
- • Detect divergence by checking a running signature of executed operations against the log; a mismatch means a source was missed and the replay is no longer faithful.
- • Optionally checkpoint periodically so replay can start near the failure rather than from process start, which is what makes reverse stepping practical.
- • The recorded failure: R1 reads charged=false, R2 reads charged=false, R1 charges, R2 charges, both update. Replayed, this occurs on run one and every subsequent run.
- • The same code under normal execution: on 39,999 out of 40,000 runs R1 completes its update before R2 reads, the guard rejects, and everything is correct. That is why the test suite has never caught it.
- • Under a recorder that forces single-core interleaving: a bug requiring both threads to be *simultaneously* inside a non-atomic 128-bit read never occurs, because the two halves are never truly concurrent. The recording is faithful to what it captured and captured nothing.
- • A missed source — an unrecorded clock read used for a cache expiry — causes replay to take the non-expired branch. From that step onward, the replayed execution is a different program and the divergence check fires.
- • Replay guarantees that the recorded execution is reproduced, for exactly the set of nondeterminism sources the recorder captured. Anything outside that set is a divergence risk.
- • It guarantees stability under observation *within* the replay: probes no longer alter the schedule, because the schedule is data.
- • It does not guarantee you will capture the failing run. Recording overhead changes timing, and the bug may become rarer or unreachable while recording.
- • It does not find bugs. It reproduces them. Discovery still needs stress testing, a detector, or production.
- • A faithful replay says nothing about whether *other* schedules are also broken — it shows one, precisely.
- • Serializing scheduling decisions is itself a global synchronization point, which is why the slowdown can be severe on highly parallel workloads.
- • The recording log is written from every thread and is a shared resource; a naive implementation makes it the new bottleneck.
- • Checkpointing pauses execution to snapshot state, adding periodic latency spikes to an already-slowed run.
- • Silent divergence: a nondeterminism source was missed, replay drifts, and the developer debugs a run that never happened.
- • Recording overhead suppresses the bug, so weeks of recording produce no failing capture and the effort is written off.
- • Recording files grow to a size nobody can store or move, especially when the bug appears once a day and requires continuous capture.
- • Recordings contain full I/O payloads — credentials, personal data, card numbers — creating a serious handling problem. See What You Just Wrote Into a Log Half the Company Can Read.
- • Single-core replay hides genuinely parallel bugs, and the team concludes the code is correct because it replays cleanly.
- • Rare, expensive, production-only bugs — the double-charge, the corrupted record, the duplicated side effect. High cost per occurrence justifies high tooling cost.
- • Bugs that vanish under instrumentation, where replay is the only way to observe without perturbing.
- • Post-mortem analysis where the failing run has already happened and you need to walk backwards from the symptom.
- • Making a flaky concurrency test deterministic in CI, so it either passes or fails the same way every time.
- • When a stress harness already reproduces the bug in one run in twenty. Replay is far more machinery than the situation needs — see Stress Testing: A Test That Passed Once Proves Nothing.
- • On throughput-critical production paths, where even a modest slowdown is not acceptable and continuous recording is therefore not an option.
- • When the interleaving is not actually the issue and the bug is ordinary logic, which replay reproduces faithfully and expensively.
- • Where recording payloads would put regulated data into a debugging artefact that then circulates by email.
- • Divergence rate during replay — anything above zero means a source is unrecorded and every conclusion is suspect.
- • Reproduction rate under recording compared to without it: a large drop means recording is suppressing the bug.
- • Recording throughput and storage per hour, against how long you expect to wait for a capture.
- • Time-to-first-reproduction before and after adopting replay, which is the only number that justifies the investment.
- • A recording infrastructure to build or adopt, with playback, divergence detection and checkpointing — this is a substantial system, not a flag.
- • Every nondeterministic source in the codebase must route through an interceptable seam; a direct clock read anywhere is a hole.
- • Recordings are sensitive artefacts with a retention, access-control and redaction policy attached.
- • Platform coupling: the strongest tiers are tied to specific architectures and operating systems, which constrains where the bug can be reproduced.
- • Stress testing with randomized scheduling, which raises the reproduction rate instead of capturing one occurrence — cheaper and usually the right first move. See Stress Testing: A Test That Passed Once Proves Nothing.
- • A race detector, which finds unordered accesses without needing reproduction at all — Race Detectors: What They Find, and What They Structurally Cannot.
- • Cheap per-thread trace buffers dumped on failure, which give the interleaving after the fact without replay machinery — Heisenbugs: The Bug That Leaves When You Look at It.
- • Designing the nondeterminism out: an idempotency key or a conditional update makes the double-charge impossible, which is better than reproducing it — Optimistic Concurrency Control.
- • Model checking a small critical section exhaustively, when the state space is genuinely tiny.
What people believe, and what is true
Record and replay means recording the inputs.
Application inputs are the easy part and the part that misses concurrency bugs. The scheduling decisions and lock grants are the inputs that matter here.
If it replays cleanly, the code is correct.
It reproduces one execution. A single-core replay in particular can be perfectly faithful to a run in which the parallel bug could not occur.
Replay finds concurrency bugs.
It reproduces them. Finding still requires a detector, a stress harness, or production traffic — replay is what you reach for after something has already failed once.