Checkpoints and lineage: save the state or the recipe
When does recomputing from lineage pay?
Checkpoint and snapshot recovery
What it is. Replay cost grows without limit as the system runs longer. A checkpoint cuts it: it turns an unbounded recovery distance into a bounded one, paid for as a steady-state write cost.
The interval, and what C really is
The best interval was derived in Why failure recovery is a different kind of problem: I* = √(2·C·MTBF), a forgiving square root. One boundary: the I/2 term assumes failures arrive without memory (any moment is equally likely). When the checkpoint itself stalls the system and triggers a failure detector, the failure is correlated with the checkpoint and the expectation is wrong. And C is a stall or a debt, not a volume: a sharp checkpoint pauses, a fuzzy one leaves consistency debt for the log to repair at recovery (Checkpointing: sharp, fuzzy, incremental). The same two currencies as everywhere: pause, or reconcile later.
What makes a checkpoint recoverable
It must be a consistent cut: it must never record that a message was received without recording that it was sent. And it must be paired with the input position it corresponds to. The pair (state, offset) must become durable atomically. If it cannot, the order you choose is the failure you choose:
- save state first, then offset: a crash in between gives duplicates (state already contains the effect, but the offset says "not yet processed"),
- save offset first, then state: a crash in between gives loss.
There is no third order. This is the "designate one write" principle: make the pair become durable through one single write. (The algorithm that produces a consistent cut belongs to distributed-systems topics; the consumer-offset version of the ordering is in Making a repeat harmless.)
Incremental checkpoints
An incremental checkpoint saves only what changed since the last one. It is cheaper to take but more expensive to restore (a chain of deltas), and it needs a garbage collector for the old ones. Every storage design that never overwrites ends up with an indirection layer and a garbage collector. An incremental state backend is another instance of the pattern.
Where the interval stops mattering
Once the state is large, recovery time is dominated by moving the state. 1 TB at 1 GB/s takes 1,000 s, about 17 minutes, before any computation happens. Past that point the checkpoint interval no longer affects RTO. Only restore bandwidth does. This is why systems try to restart a task on the node that holds a local copy, and why "we checkpoint every 30 seconds" tells you nothing about how fast the system comes back.
Lineage-based recomputation
What it is. If a computation is deterministic and its inputs are immutable and still present, its output is redundant information: you can compute it again. So you store the recipe (a DAG of steps, a few kilobytes) instead of the result (terabytes). Recording lineage costs almost nothing. Using it is expensive.
The cost is the fan-in, not the data lost
- With narrow dependencies (each output piece depends on one input piece), losing one partition needs one upstream partition per level. Recovery is O(depth), and cheap.
- With a wide dependency (a shuffle, where each output piece depends on every upstream piece), losing one partition means re-running the entire upstream stage.
The recovery unit (a partition) is finer than the dependency unit (all partitions). The amplification equals the fan-in. This is the general rule that a mismatch between the size of what you lose and the size of what you must redo causes amplification.
This forces the design everyone actually ships, and it corrects a piece of folklore: "lineage-based" systems are checkpoint-based across shuffle boundaries and lineage-based within them. Materialized shuffle files are a checkpoint placed at exactly the point where recomputation would otherwise become total. The lineage story is true for narrow stages and quietly false for wide ones.
It degrades with history length
An iterative job's lineage chain grows with the number of iterations, so recovering iteration 100 costs about 100 times recovering iteration 1. A fixed recovery budget meets linear growth. So iterative workloads use explicit checkpoints, which is the mechanism admitting its own limit.
Two preconditions, both unverified
- Determinism, as with replay.
- Input immutability. Recomputing against a source that has changed produces a different answer than its sibling partitions, giving a dataset that is internally inconsistent in a way no schema check catches. A task retry that re-reads a live JDBC table (a database table read through a standard Java connector) is this bug, and it is common. Lineage needs the source to be a snapshot. If it is not, lineage is not a recovery mechanism.
Boundary. Lineage recovers intermediate state only. It says nothing about output that has already been emitted.