Copy, log or recipe: the nine ways to recover

From what can interrupted state be rebuilt, and which failure model do all nine recovery mechanisms assume?

There are exactly three artifacts from which interrupted state can be rebuilt:

1. a copy of it,
2. a log of the changes that produced it, or
3. the recipe that produced it.

There is no fourth. Every mechanism in this article is a choice of which artifact you paid for in advance, plus a policy for when to use it.

The choice is forced, because two costs are linked in opposite directions. Let D be the recovery distance: the gap between the last trustworthy point and the failure. Let C be the steady-state price of maintaining that trustworthy point.

• Retry sits at C = 0, and D is the whole request: you redo everything.
• A hot standby (a second machine that already holds the current state) sits at C = a full duplicate, and D ≈ 0.
• Logs and checkpoints lie in between, on the same curve (the product C × D is roughly fixed).

You cannot reduce both. You choose which one you pay and how often. This is the old trade-off between precomputing and recomputing, applied to state: a checkpoint is precomputation, lineage is recomputation, and a log is the raw material both are made from.

The failure model, stated once

All nine mechanisms assume crash-recovery with fail-stop semantics: a node stops, it stops cleanly, and its stable storage survives. Two violations of this model break all nine, and this article cannot repair them:

• A node that fails slow instead of stopping defeats every failure detector these mechanisms depend on. (A slow node looks, for a long time, like a healthy node.)
• A node that returns wrong answers instead of no answers defeats the reconstruction itself. Data systems handle that only at the edges, with checksums (a small number computed from data that changes if the data is damaged), not with protocols.

When someone says that a mechanism is "fault tolerant", the useful question is: which failure model did they mean?

Overview table