Topic 13B.6
Gossip, Failure Detection & Merkle Trees
In one line
Large clusters can't have every node ping every other node. Gossip spreads membership and state epidemically, phi-accrual detectors decide who's dead, and Merkle trees let replicas find differences by comparing a few hashes.
Think of it like this
News in a village. Nobody announces it to everyone; each person tells a few others each hour, and within a short time the whole village knows. That's GOSSIP. To check whether two libraries have the same books, they compare one summary per shelf first and only inspect shelves whose summaries differ: that's a MERKLE TREE.
Key ideas
- 01
GOSSIP PROTOCOLS: every second, each node exchanges state (membership, heartbeats, versions) with a few random peers. Information reaches all N nodes in O(log N) rounds, with no central coordinator and graceful handling of failures. Used by Cassandra, Consul/Serf (SWIM), Redis Cluster, and many service meshes.
- 02
FAILURE DETECTION: a missed heartbeat might be a dead node, a slow network, or a GC pause. Fixed timeouts are either too slow (long outage) or too jumpy (false alarms, needless failovers). PHI-ACCRUAL detectors (Cassandra, Akka) output a suspicion level based on the history of heartbeat intervals; SWIM adds indirect probes ('can YOU reach node X?') before declaring death.
- 03
MERKLE TREES: hash each data range, then hash pairs of hashes up to a single root. Two replicas compare roots; if equal, they're identical; if not, they descend only into subtrees whose hashes differ, finding the exact out-of-sync ranges with a handful of comparisons. Used for ANTI-ENTROPY repair (Cassandra, DynamoDB-style stores), Git, blockchains, and file sync (Dropbox, rsync-like tools).
- 04
Together these make LEADERLESS, highly available stores work: gossip for membership, consistent hashing for placement (Phase 8), quorums for reads/writes (Phase 13), hinted handoff for temporarily down nodes, and Merkle-tree repair to converge eventually.
Code & diagrams
Explain without notes
Why is gossip more scalable than all-to-all heartbeats?
Practice
Two replicas of a 1 TB key-value store may have diverged after a network partition. How do you find and fix the differences without comparing all data?
Trade-offs
- ↔
Gossip is scalable and robust but eventually consistent (state spreads over seconds); aggressive failure detection speeds failover but risks false positives and flapping.
Run it in production
You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:
Completion checklist
I can explain gossip convergence and phi-accrual detection
I can describe Merkle-tree anti-entropy repair