Reference: Anti-Entropy and Failure Detection

What it is

A cluster of hundreds of nodes has no central master to say who is alive or which replica is stale, so it has to work that out on its own. Two families of mechanism do this. Failure detection and membership (gossip) answers “who is in the cluster, and who is down?” Anti-entropy and repair (hinted handoff, read repair, Merkle trees) answers “which replicas have drifted, and how do they converge?” Together they make failure a steady state the system handles continuously instead of an event someone handles.

When you care

Any “what happens when a node dies?” follow-up on a replicated store lands here, and at hundreds of nodes failure is routine. The trap is presenting hinted handoff as the whole durability story. Interviewers want the tiers and the reason each exists.

Membership: gossip

Ring membership is not stored in a central master; that would reintroduce the single point of failure a leaderless design removed. Each node keeps its own view and reconciles it by gossip:

1. Every second, each node picks a few random peers and exchanges its ring state: node ids, token positions, heartbeat counters, status.
2. Information spreads like an epidemic: after about log₂ N rounds (roughly 7 in a 150-node cluster), every node has seen the update.
3. Each entry carries a generation (higher means the node restarted) and a version (higher means its state changed). The newer always wins.

A join or leave reaches the whole cluster in seconds. A node that suspects a peer is down starts routing around it, which is a local suspicion, not a quorum-agreed fact. That is right for this design: a false suspicion costs a few unnecessary hints, not a failover. Seed nodes (two or three well-known addresses per region) exist only so a new node can find its first peers.

Failure detection has a trade-off: a short timeout detects real failures fast but mislabels slow nodes (a garbage-collection pause) as dead; a long one is stable but slow to react. Many systems use an adaptive detector that scores each peer by how unusual its heartbeat gap is, rather than a fixed timeout.

The repair tiers

Hinted handoff. When a write’s replica is down, the coordinator writes that copy to the next healthy node, tagged with a hint. The stand-in keeps it in a separate buffer, not its main keyspace, with a time limit, and replays it on recovery.

Read repair. When a read finds a stale replica among its R responses, the coordinator sends the winning version back to it asynchronously. Hot keys are read constantly, so they are also repaired fastest, which is the right bias.

Merkle-tree anti-entropy. Each node keeps a Merkle tree per key range: a hash tree whose leaves hash slices of keys and whose parents hash their children. Two replicas compare roots first:

Compare root hashes -> match?  Done: the range is in sync (one message)
                    -> differ? Compare the children, recurse
                               -> find the differing leaf ranges
                               -> stream only those keys

Worked example. Comparing a multi-gigabyte range costs a few kilobytes of hashes when replicas are in sync, which is the common case, so the cluster can afford to run repair continuously. When they differ, only the divergent slices move, not the whole range. A single differing key costs a walk down the tree (about log₂ of the leaf count comparisons) plus one slice, not a full scan.

Deletes are writes

A delete cannot simply remove the record: a replica that missed it would resurrect the key during repair, because a missing key and a never-written key look the same. So a delete writes a tombstone, a versioned “this key is deleted” marker that propagates like any write and wins version comparisons. Tombstones are kept for a grace period longer than the maximum repair interval and then compacted away. If a replica stays down longer than that, bring it back by rebuilding it, not by letting it rejoin with old data, or the deleted keys return.

Tail latency: hedged reads

A related problem is the slow node that is not dead. With N=3, R=2, a read waits for the second-fastest response, but a garbage-collection pause or a compaction burst makes some responses take far longer. A hedged request sends the read to an extra replica if the expected responses have not arrived within a threshold (about the median latency), and uses whichever R responses come first. The slow replica is bypassed, not waited for.

Worked example. Without hedging, a read to A, B, and C returns when A (3 ms) and B (8 ms) answer; if B is stuck behind a 50 ms pause, the read takes 50 ms. With a 5 ms hedge threshold, a request to D fires at 5 ms, D answers at 6 ms, and the read returns at 6 ms. The cost is a small number of extra requests (only the slow few percent are hedged); the benefit is a p99 that moves toward the p50. Google reported cutting p99 by half or more with under 5% extra load.

When to pick what

Related

• Walkthrough: Designing a Distributed Key-Value Store — the store whose availability these repair tiers keep honest.
• Reference: Quorums, Versioning, and Conflict Resolution — the write side: how divergence is created and detected in the first place.
• Reference: Replication Strategies — leader-follower versus leaderless, the choice that makes these mechanisms necessary.