Deterministic Replay: Recording a Thread Schedule and Playing It Back

A bug that appears once in a thousand runs is not a debugging problem in the usual sense. There is no failure to inspect, only a probability. The conventional response is to add logging, rerun, and wait, which converts a nondeterministic failure into a large volume of data that may not contain the failing run. The alternative is to make the run repeatable: record enough of the execution that it can be replayed exactly, and debug the replay as often as needed.

Recording the thread schedule is the obvious half of that. It is also the easy half, and a tool that records only the schedule will fail to reproduce the bug. What must be captured is every source of nondeterminism that can affect the program’s observable behaviour, and the list of those sources is longer than it first appears.

The sources of nondeterminism

The schedule is the first and largest. Which thread runs at each point determines which reads see which writes, which locks are contended, and which code paths are taken. The order of context switches is not the same as the order of thread creation or the order of wakeups, so a recording must capture the actual sequence of scheduling decisions: at each point where the program could have switched, which thread the kernel chose.

The second source is time. A program that reads a clock, sets a timer, or measures elapsed time observes values that differ on every run. The differences propagate into behaviour whenever a timeout fires or a duration is compared against a threshold. Recording the return values of clock reads, and replaying them, makes the observable time deterministic, even though the replay does not run at the original speed.

The third is input from outside the process: file contents, network responses, device state, signals. Some of these can be captured by recording the results of the system calls that fetched them. Others cannot be captured at that level, because the kernel’s behaviour depends on state the recorder does not control, so the boundary must be drawn at the syscall and the recorded result substituted on replay.

The fourth, and the one most often forgotten, is the order of asynchronous events the program itself generates: signal delivery, SIGCHLD, completion of asynchronous I/O, and callbacks from a runtime’s thread pool. These are scheduling decisions too, and they must be recorded in the same sequence as the thread switches.

The fifth is memory layout. Address-space randomisation, allocator decisions, and hash functions seeded from a random value all change the addresses and iteration orders the program observes. A program that iterates a hash table and takes a different path depending on the order of its elements will not replay from a schedule alone.

A recorder’s design is largely a statement about which of these it captures and which it declares out of scope.

Recording as a trace of decisions

The naive approach is to log every scheduling event with a timestamp, which produces a trace whose size grows with the number of context switches. For a program that makes many short syscalls, that is a large volume, and the volume is what makes the approach impractical for long runs.

The refinement is to record decisions only at points where the outcome is not determined by the program’s own state. If a single thread is runnable, the scheduler’s choice is forced and need not be recorded. If several are runnable, the choice is recorded as a small integer — the index of the chosen thread. The trace therefore contains an entry only at contention points, and the replay reconstructs the forced choices from the program’s own execution.

This works because the program’s state at a given point is a function of the recorded decisions and the inputs, provided everything else is deterministic. The property that makes the trace small is the same property that makes replay possible: determinism of the deterministic parts.

The mechanism used by the rr debugger is a refinement of this idea. It counts the execution’s progress in terms of events — syscalls, signals, and the transitions between them — rather than in time. Each thread is assigned events in a total order, and the recording stores, for each event, which thread ran it. Replay then runs threads one at a time and uses hardware performance counters to stop each thread after exactly one event has retired. The hardware feature that makes this work is the ability to count retired conditional branches and deliver a signal after a specified number, which gives a per-thread event counter with low overhead.

The consequence is that a recorded trace is proportional to the number of events, not to the duration. A program that sleeps for an hour without doing anything records almost nothing, and replay of that hour takes no time at all because the sleep is emulated rather than performed.

rr record ./server --config ./conf
rr replay                      # opens a gdb session on the recording
# inside the replay:
#   reverse-continue           run backwards to the previous breakpoint
#   reverse-step               step backwards one source line
#   watch -l counter           hardware watchpoint, replayed in reverse

Reverse execution is the property that makes replay worth its cost. Because the recording determines every step, the debugger can reconstruct any earlier state, so a watchpoint on a variable that is corrupted at an unknown point can be run backwards to find the write that changed it. Without replay, the same investigation requires either a conditional watchpoint and a rerun, or a search through logs.

What replay must reproduce besides the schedule

A schedule trace alone is insufficient for the reasons listed above, and each additional source needs its own treatment.

Clock reads are intercepted and answered from a recorded sequence. The values are recorded in order and replayed in order, so a program that calls the clock twice gets the same two values both times, and the interval between them is the recorded interval rather than the replay’s actual interval. This is what makes timeouts deterministic: a timer that fired at the recorded moment fires at the same logical moment on replay, even if the replay takes a different wall-clock time to get there.

System calls are the natural boundary for external input. A recorder can intercept at the syscall entry and exit and record the arguments, the return value, and the bytes written into output buffers. On replay, the call is not performed; the recorded result is placed in the buffer and the recorded return value is returned. The kernel’s actual state is therefore irrelevant to the replay, which is both the strength and the limitation: a replay does not need the original files to exist, but it also cannot reveal a bug caused by a syscall behaving differently on a second call.

Randomness needs the same treatment. A program’s calls to a random number generator, and the runtime’s own seeding, must be recorded and substituted. A hash table whose iteration order depends on a random seed is a common source of unreproducible behaviour, and recording the seed is enough to make its order stable.

Memory layout is the hardest to reproduce exactly, because it is determined by the allocator and the loader rather than by anything the program recorded. Recorders handle it by fixing the layout: disabling address randomisation for the process, using a deterministic allocator, and replaying the recorded virtual addresses. When the layout cannot be fixed, a bug that depends on it is out of scope, and a replay tool should say so rather than produce a replay that diverges silently.

The divergence problem

A replay that diverges from the recording is worse than no replay, because it produces a confident wrong answer. Divergence occurs when the replay’s state differs from the recorded state at some point, and the usual causes are an input the recorder did not intercept, a nondeterministic instruction the recorder did not model, or a race inside the recorder itself.

Detecting divergence requires the recorder to have recorded something that can be compared. The standard technique is to record a checksum of the program’s output — writes to file descriptors, exit codes — and to compare on replay. A stronger technique is to record the results of a sample of computations, or to record the event count and verify that the replay retires the same number of events per thread. Without such a check, a replay that takes a different path looks exactly like a replay that found a different bug.

The check is not free, and it is the reason replay tools are usually restricted to a single machine and a single kernel version. A kernel that changes the layout of a structure passed to a syscall changes the bytes the recorder captured, and the replay must be run against the same interface. Container images and pinned kernels exist in practice for this reason.

Where replay fits against observation

Replay is not a substitute for the tools that observe a single run. A race detector such as the one described in ThreadSanitizer vector clocks reports a race that may never produce a visible failure, and replay reproduces a failure that already occurred. The first is a static-ish analysis over one execution’s ordering; the second is a recording of one execution that can be examined repeatedly.

The combination is what matters operationally. A race report identifies the two accesses and the missing ordering; a replay recording of the failing run shows the sequence that made the race observable. The same pairing applies to memory errors: the shadow-memory checks described in AddressSanitizer shadow memory catch the access at the moment it happens, and the replay lets the state before the access be inspected as many times as needed.

The cost is the constant factor. Recording intercepts every syscall and every scheduling decision, so a recorded run is slower and larger than an unrecorded one, and the trace must be stored and moved to the machine where it will be replayed. The trade is deliberate: a run that can be repeated is worth several runs that cannot, and the debugging session on a replay is bounded by the recording’s content rather than by luck.

One final limitation deserves emphasis. Replay reproduces the program’s execution, not the environment’s. A bug caused by a hardware fault, a kernel bug, or a device returning inconsistent data is captured only to the extent that the recorder intercepted the resulting syscall results. A replay of such a run shows what the program did with the data it received, which is usually the part that matters, and never shows why the data arrived that way.