Replay from log and the catch-up condition

When does replaying a log rebuild the same state, and how much headroom does catching up need?

What it is. State can be written as a fold over the log: state = fold(f, initial, log), meaning: start from an initial state and apply the function f to every log record in order. If the log is complete and ordered, any state you can reach by processing the log you can reach again by processing it again from a known offset. Replay does not need to know what the failure was, which makes it the cheapest mechanism to have. Its steady-state cost is a log you were already keeping.

Determinism is the precondition, and nobody checks it

Replay gives the same state only if f is a real function (same input, same output) and the log is its only input. The ways to break this are ordinary:

• reading the clock: now(),
• unseeded random numbers,
• enrichment lookups against a table that has changed since,
• summing floating-point numbers in a different partition order (floating-point addition is not associative: (a + b) + c can differ slightly from a + (b + c)),
• hash iteration order,
• and the subtle one: any dependence on the arrival order of events when that order is not itself recorded in the log.

The worst feature of this failure is that replay produces a different but plausible answer, silently, and only on the recovery path. The difference may surface weeks later as a reconciliation break. This is the clearest example here of a mechanism that assumes purity, cannot check purity, and lets the data pay without anyone filing a ticket. It is the third symptom: Wanjiru's code read now() and a lookup table that changed.

The catch-up condition

During an outage, new work keeps arriving. Recovery time is:

If the replay throughput does not exceed the arrival rate, recovery never ends.

To recover in T/k you need the drain rate to be k times the arrival rate: M − a = k·a, so M = (k + 1)·a. To recover in a third of the outage (k = 3) you need maximum throughput four times the arrival rate, which means running at 25% utilization.

The consequence is important: the utilization target of a system that recovers by replay is set by its recovery budget, not by its latency budget. This is a different and usually stricter limit than the queueing argument (which says that latency grows quickly as utilization approaches 100%). It is also why Wanjiru's backlog barely shrank: results-intake ran at 90% of its maximum, so its drain rate was only 10% of maximum throughput (about 1/9 of the arrival rate). (The case where catch-up load breaks the system again is a replay storm.)

What bounds replay

The retention window: you can replay exactly as far back as someone decided to keep the log. So the retention policy is silently a recovery-capability policy, usually owned by a different team on cost grounds.