Checkpointing and Consistent Global State
Why this matters: 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.
Key takeaway
Checkpointing periodically saves the system's state to stable storage; on failure, the system recovers by reloading the last saved state. The hard part is not saving — it is ensuring the independently saved pieces form a consistent global state.
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.
| 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.
| 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.