Checkpointing and Consistent Global State
In one line: backward error recovery needs a saved state to return to. Saving that state across several machines at once is far subtler than it looks — do it naively and you will restore your system into a state that never actually happened.
Why checkpoint at all
Two reasons, both about not repeating work:
- Long computations. A job that has run for six hours should not restart from zero because one worker died.
- Recovery speed. Replaying an entire event log from the beginning is slow. A checkpoint plus a short replay is fast — which is MTTR, which is availability.
This is backward error recovery made concrete: you do not need to understand what went wrong, only to have a known-good state to return to.
The two classes of global state
Checkpoints are classified by the consistency of the resulting global state:
- Consistent state: all processes share a coherent view of events. Completed updates are saved, in-progress updates are rolled back, and no messages are in transit.
- Inconsistent state: checkpoints across processes are uncoordinated, leading to discrepancies.
Consider three processes — i, j, and k — exchanging messages m1 and m2. Each saves a snapshot: C1,i, C1,j, C1,k.
The consistent case
Message m1 is both sent and received after the checkpoints are taken. No message crosses the cut, so the recovered state is coherent: the snapshot describes a moment that genuinely existed.
The inconsistent case
Here the processes exchanged messages during checkpointing. Process i records having received m1, but process j has not recorded sending it. Restore both snapshots and you get a system where a message exists at its destination and was never sent — a state that never occurred in the real execution.
The orphan message
This is called an orphan message, and it is the defining symptom of an inconsistent cut. It is genuinely dangerous because it is not detected as an error — the system happily resumes from a fabricated history. If m1 was "transfer 100 units," the recovered system has credited a transfer that was never debited.
The mirror case is benign by comparison: a message recorded as sent but not yet received is simply in transit. That state is consistent, provided the recovery mechanism replays or re-delivers it.
| Situation at the cut | Sender recorded send? | Receiver recorded receipt? | Verdict |
|---|---|---|---|
| Message entirely before the cut | Consistent | ||
| Message entirely after the cut | Consistent | ||
| In transit across the cut | Consistent — replay it | ||
| Orphan message | INCONSISTENT — impossible state |
The rule that falls out: a cut is consistent if and only if it contains no orphan messages. Every received message must have a recorded sender.
The domino effect
If processes checkpoint independently, recovery does not stop where you want it to.
Process i fails and rolls back to C1,i. But i had already sent a message to j after that checkpoint — so from j's perspective, j now holds an orphan. j must roll back too. That rollback orphans a message j sent to k, so k rolls back. And so on.
This is the domino effect: a single failure cascades rollbacks backwards through the system, potentially discarding all progress despite every process having saved checkpoints diligently. The set of checkpoints you can actually recover to is called the recovery line, and with uncoordinated checkpointing it can sit arbitrarily far in the past.
Going deeper (Staff+)
The standard fix is coordinated checkpointing: processes agree on a cut rather than choosing independently, guaranteeing consistency and eliminating the domino effect at the cost of coordination. The classic algorithm is the Chandy-Lamport distributed snapshot, which uses marker messages to record a consistent cut without pausing the system — and it is the direct ancestor of the exactly-once checkpointing in modern stream processors like Apache Flink.
The alternative is communication-induced or message-logging checkpointing: log messages alongside independent checkpoints so orphans can be reconstructed by replay instead of prevented.
| Strategy | How it works | Pro | Con |
|---|---|---|---|
| Uncoordinated | Each process checkpoints whenever it likes | No coordination cost; simple | Domino effect; recovery line may be useless |
| Coordinated | Processes agree on a global cut | Always consistent; recovery line is the last checkpoint | Coordination overhead; some synchronization |
| Message logging | Independent checkpoints plus a log of messages | Fast recovery; no domino | Log storage and replay complexity |
Where you meet this in practice
The vocabulary is academic; the mechanism is everywhere:
| System | Its checkpoint | What it recovers |
|---|---|---|
| Relational database | WAL checkpoint / snapshot | Replay the log from the last checkpoint after a crash |
| Apache Flink | Distributed barrier snapshot | Exactly-once stream processing across operators |
| Redis | RDB snapshot / AOF rewrite | In-memory state after restart |
| VM / container | Memory + disk snapshot | Live migration and rollback |
| ML training | Periodic model weight dump | Resume a multi-day run after a node dies |
Key takeaway
Saving state on one machine is trivial. Saving it across many at once requires a consistent cut — one with no orphan messages — or you will faithfully restore a history that never happened.
Interview signal by level
| Level | What a strong answer sounds like |
|---|---|
| L4 | "We'd periodically save state so we can restore after a crash." |
| L5 | Knows the hazard: "snapshots have to be coordinated across nodes, otherwise the combined state can be inconsistent." |
| Staff+ | Names the mechanism: "a cut is consistent iff there are no orphan messages — received but not recorded as sent. Uncoordinated checkpointing risks the domino effect, so I'd use coordinated snapshots à la Chandy-Lamport, and size the interval from how much recomputation we can afford." |
Next: the NFR with the most techniques attached to it, and the one people understand least precisely.