Anti-entropy, read repair and hinted handoff
Which replica repair actually converges?
Anti-entropy, read repair, hinted handoff
A quorum gives a guarantee about the quorum, not about every replica. A write at W=2 of N=3 leaves one replica stale by design, and a node that was temporarily unreachable accumulates divergence. So any system that accepts writes during partial failure must run a process that makes replicas converge again. The only choice is when to pay for the convergence.
Three placements of the same job
Read repair pays at read time. When a read finds replicas that disagree, it writes the newest value back to the stale ones. It is perfectly targeted, because it fixes data someone wanted. And it is useless for cold data: data that is never read is never repaired. The replicas most likely to be silently divergent are the ones nobody looks at. (Bit rot on disks is the same observation about storage media.) Read repair alone is not a convergence strategy. It is an opportunistic accelerator.
Hinted handoff pays at write time. A coordinator that cannot reach a replica stores the write locally as a hint and delivers it later. This buys write availability. The vendor description usually omits what it costs:
- A write acknowledged with hints did not reach W intended replicas. The quorum was satisfied by nodes that are not the true owners. So
R + W > Nno longer guarantees overlap, and a read can miss the write entirely. A sloppy quorum is not a quorum. It is a durability and consistency downgrade sold as availability. Use it only when you have deliberately chosen availability. - Hints pile up on the coordinator during exactly the outage that created them. A long outage produces a backlog of hints, and delivering them is a load spike aimed at the node that has just recovered.
Anti-entropy pays in the background, unconditionally. It is the only one of the three that actually guarantees convergence. Its cost is a comparison problem. Naively, comparing two replicas costs O(data), which is unaffordable at any useful frequency. A Merkle tree (a tree of hashes: each leaf hashes a range of keys, each parent hashes its children) reduces it. Two replicas exchange root hashes. If they match, they are identical. If not, they descend only into the subtrees whose hashes differ and transfer only the leaves that differ. The comparison takes about O(log n) hash exchanges for a small number of differences.
The key property: the cost scales with the divergence, not with the size of the dataset. The same shape appears in incremental view maintenance, delta-based change data capture and rsync's rolling checksum. Its failure mode is just as consistent: when divergence is large, the comparison degenerates toward a full scan, so the mechanism is slowest exactly when it is most needed. The granularity of a Merkle leaf is also a tuning knob: a leaf that is too coarse transfers unchanged data; one that is too fine costs tree metadata.
| Repair | Paid at | Strength | Weakness |
|---|---|---|---|
| Read repair | read time | targets wanted data | never repairs cold data |
| Hinted handoff | write time | write availability | weakens the quorum; hint backlog |
| Anti-entropy | background | guarantees convergence; cost ∝ divergence | slow when divergence is large |
The precondition under all three: a merge rule
Convergence requires deciding which version wins. Options:
- Last-write-wins (LWW) needs synchronized clocks, which do not exist, so LWW silently discards concurrent writes.
- Vector clocks (per-node counters that reveal whether two versions are ordered or concurrent) detect concurrency but push the resolution to the application.
- CRDTs (conflict-free replicated data types) make the merge operation associative, commutative and idempotent, so no decision is needed. This is again the right algebra removing the need to coordinate.
A repair mechanism cannot be judged without stating its merge rule. The transport is the easy half.