Read Repair and Hinted Handoff on the Write Path

A leaderless store acknowledges a write once W replicas have it. The remaining replicas are not written at all, or are written by a background process that may be arbitrarily far behind. The system therefore has to answer something a single-leader log answers implicitly: how a replica that missed a write learns about it, and how the system establishes that it has caught up.

Two mechanisms handle the common cases, and a third handles the residue. Read repair fixes replicas that a read happens to touch. Hinted handoff holds writes for a temporarily unavailable replica and delivers them when it returns. Anti-entropy compares whole datasets to find divergence that neither of the first two noticed. Each has a distinct failure mode, and the interesting engineering is in the boundary between them.

The read path as a repair opportunity

A read in a leaderless store contacts R replicas and merges their responses. Merging already requires comparing versions, so the coordinator knows which replicas returned the winning value and which returned something older. The older ones are candidates for repair, and repairing them costs one extra write per stale replica, issued before the read returns or queued after it.

The common form is a blocking read repair: the coordinator writes the winning value back to every replica that returned a dominated version, waits for those writes, then returns. Waiting makes the read linearizable in the sense that a subsequent read from any of those replicas sees the newer value, at the cost of turning a read into a write for the stale replicas.

The alternative is an asynchronous read repair, where the write-back is queued and the read returns immediately. This is cheaper under load and leaves a window in which a second read of the same key, aimed at the same stale replica, returns the old value again. The window is bounded by the queue drain time, which is not bounded at all when the cluster is saturated.

Read repair only repairs what is read. A key that is never read after a replica misses a write stays divergent indefinitely. For a workload with a long tail of cold keys, that means most of the dataset is never repaired by this mechanism. The fraction that is repaired is the fraction that is read, weighted by read frequency, and the cold tail is exactly the part that anti-entropy exists to cover.

Detecting a stale response

The comparison that drives repair is the same partial order used for conflict detection. A replica returns a value with a version vector; the coordinator keeps the values whose vectors are not dominated by another value’s vector. If exactly one value survives, the read is unambiguous and every replica that returned a dominated version is behind. If several survive, they are concurrent and repair must not overwrite any of them.

That last clause is where read repair can destroy data. A coordinator that picks “the latest” by a scalar timestamp and overwrites the rest will erase a concurrent sibling, and the merge function that was supposed to see both never runs. The repair path must distinguish “this replica is behind” from “this replica holds a value that is incomparable”, and only the first is repairable by overwriting. The details of the comparison are in version vectors and conflict detection.

Hinted handoff is a queue, not a fix

When a write’s target replica is unreachable, the coordinator can store the write locally along with a note saying which replica it was meant for. That note is the hint. When the target comes back, the coordinator replays the hinted writes.

The mechanism converts an immediate failure into a deferred delivery, which is what keeps W achievable when fewer than W of the intended replicas are up. A write quorum of two over three replicas can still succeed with one replica down, because the coordinator substitutes itself as the second acknowledgement. The data is durable on the coordinator, which is a real node with real storage, so this is not a fiction.

What hinted handoff does not do is repair a replica that was down for a long time. Hints accumulate on the coordinator while the target is absent, and the coordinator’s local storage is finite. Implementations bound the hint window, commonly on the order of hours, and discard hints older than the bound. After that the divergence must be found by anti-entropy, which is a much more expensive operation.

Hints also fail when the coordinator itself fails. A hint stored on a node that dies before delivering it is lost, and the write it represented exists only on the replicas that acknowledged it. This is not a correctness violation if W was met by other replicas, but it widens the divergence that anti-entropy must later reconcile.

The three mechanisms cover different populations

The populations are worth separating because each mechanism’s guarantee is stated over a different set:

Mechanism	Repairs	Trigger	Bound on completeness
Blocking read repair	replicas touched by a read	every read	only read keys
Async read repair	replicas touched by a read	every read, delayed	only read keys, delay unbounded
Hinted handoff	replicas temporarily down	write to an unreachable replica	hint retention window
Anti-entropy	anything divergent	periodic scan	scan interval and cost

A key that is written once, read never, and whose replica was down beyond the hint window is repaired only by anti-entropy. A key that is read constantly is repaired within one read. A key whose replica was down for minutes is repaired by hints, usually before any read occurs. The design is sound precisely because the mechanisms overlap in the middle and the overlap is cheap.

Ordering hazards during replay

Replaying hinted writes out of order produces a replica that holds a newer value before it holds the older one it was derived from. For a register that is harmless — the newer value simply wins. For a data structure where the later write depends on the earlier one, it is not: applying an increment before the base value exists yields a wrong total.

Two practices avoid this. The first is to replay hints for a given key in the order the coordinator issued them, which requires the hint store to preserve per-key order. The second is to make the replay idempotent and order-insensitive by replaying values rather than operations — shipping the merged value with its version rather than the delta that produced it. Value-based replay is the safer default and the reason many systems store the full record in the hint rather than a compact operation.

There is also the interaction with deletes. A delete that is represented as a tombstone must be hinted like any other write, or the replica that missed it will keep serving a value that the rest of the cluster has removed. Tombstones have their own lifetime problem: they must be retained longer than the maximum divergence window, or a replica that missed the delete will resurrect the value during anti-entropy. The retention period is therefore coupled to the hint window and the repair interval, and shortening either without shortening the tombstone lifetime reintroduces deleted data.

Sizing the window

The parameters that matter are the hint retention window, the anti-entropy interval, and the tombstone lifetime. They are not independent. The invariant that holds a leaderless store together is:

tombstone lifetime > max(hint window, anti-entropy interval) + expected repair duration

Violating it does not produce an error. It produces a value that reappears after being deleted, at a time far from the delete, which is among the hardest classes of bug to attribute. The safe configuration makes the tombstone lifetime the largest of the three by a comfortable margin, and treats any proposal to shorten it as a change to the durability of deletes rather than a storage optimisation.

The cost of that margin is storage: tombstones for every deleted key, retained for the longest window in the system. For a workload with a high delete rate this is a substantial fraction of the dataset, which is why implementations expose tombstone counts and why compaction interacts with replication settings. The alternative to tombstones — comparing full dataset hashes to find divergence — moves the cost from per-key metadata to periodic scan work, which is what Merkle tree anti-entropy is designed to reduce.