The
The escape is one sharp observation: almost everything a program does is deterministic. An add instruction, a memory read, a whole compiler pass — given the same starting state, they produce the same result, every time. Deterministic work doesn't need to be remembered, because it can always be recomputed. The only things that must be recorded are the events the program could not have computed for itself: the nondeterministic inputs. Everything else is regenerated on demand by simply running the program again. This is deterministic record & replay, and it is how reverse execution actually ships.
Perhaps the shortest important list in systems programming — record only:
read() returned, what the clock said,
what the network delivered;rdtsc, the x86
"read the CPU's cycle counter" instruction, whose result differs every run.Not recorded: results of arithmetic, values of local variables, the contents of memory — all of it deterministic, all of it recomputable. Replaying the log through a fresh execution of the same binary reproduces the original run bit for bit. Try the whole architecture in miniature:
Four log entries reproduce the entire run — however much deterministic computation happened between them. That ratio is why rr's log stays small and its recording overhead sits around 1.2–2× on a single core: the tracee mostly just runs, with the recorder intervening only at syscalls and signals.
Replay alone gives you time travel of a clumsy sort: to see step 89 of a billion-step run, replay
from the very beginning. So the tools add the second ingredient: periodic
checkpoints — full snapshots of the process, taken cheaply on Linux with
fork(), where the operating system's copy-on-write pages mean a "copy" of gigabytes
costs almost nothing until pages actually change. Now reverse-step from step
Read that again: the debugger never actually runs backwards. Every "reverse" command
is restore-plus-replay-forward, with the checkpoint spacing setting the price. Dense checkpoints:
fast reverse-steps, lots of memory. Sparse checkpoints: cheap recording, slow hops back. If that
trade sounds familiar, it should — it is exactly the checkpoint tradeoff from
fork() as the pebble:
rr was built at Mozilla in the early 2010s, born of Firefox-sized desperation: a
browser is millions of lines of C++ chewing on the wild-west input of the entire web, and its worst
bugs were intermittent — crashes that reproduced once per thousand test runs, evaporating the moment
a developer attached a debugger. Robert O'Callahan and colleagues reasoned that if a failing run
could be recorded cheaply enough to leave recording on in automated testing, then every
one-in-a-thousand failure would become permanently, deterministically replayable — and debuggable
backwards at leisure. The trick that made it practical was ruthless minimalism: no instruction
emulation, no code rewriting — run the real binary at nearly full speed on one core, log syscalls and
signals via ptrace, count hardware performance events to replay signal delivery at the
exact right instruction. rr escaped Mozilla to become a beloved everyday tool — and its authors' rule
of thumb became folklore: an intermittent bug you can record is just a deterministic bug you haven't
walked backwards through yet.
One core, one interleaving — rr's single-core scheduling makes multithreaded runs recordable, but it also makes them gentler than reality: many race conditions only bite under true parallelism. rr's answer is chaos mode, which deliberately randomises scheduling — starving threads, preempting at cruel moments — to coax rare interleavings into showing up while the tape is rolling. Once recorded, even a one-in-a-million race replays forever.
The same coin has a dark side: unrecorded nondeterminism breaks replay. If two threads race on shared memory across truly parallel cores, the winner of the race is decided by hardware timing that appears in no syscall and no log — a naive replayer cannot reproduce the outcome, and replay diverges from the recording. That is precisely why rr accepts the single-core cost, and why recording true parallelism faithfully (as some research systems attempt) requires logging memory ordering itself, at far greater expense. The log must contain every source of nondeterminism, or the whole edifice quietly collapses.
The classic misconception about record & replay — assumed by almost everyone meeting it for the first time — is that the tool saves the program's state after every step, like frames of a film. It does not, and could not: at gigabytes of overwritten state per second, the "film" would dwarf every disk you own. What is stored is inputs plus occasional checkpoints: kilobytes of syscall results and signal timings, plus a handful of copy-on-write snapshots. Every intermediate state you inspect in the debugger is recomputed on demand by deterministic replay from the nearest checkpoint. When the debugger shows you "the state at step 89", you are not reading a recording — you are watching a fresh execution that has been steered, by the log, into being indistinguishable from the original. Storage is traded for recomputation: the space–time tradeoff is not just an implementation detail of these tools; it is the whole design.