System Design HLD-08.08
Membership, gossip and failure detection
How clusters know who is alive: heartbeats and timeouts, phi accrual failure detectors, gossip that spreads news in log N rounds, and the SWIM protocol.
The big idea
Every cluster has to answer a deceptively simple question all the time: who is in the cluster, and who is still alive? A database needs it to route reads away from a dead replica, a cache ring needs it to move keys ( Consistent hashing ), and a leader election needs it to know when to start ( Quorums and leader election ). This shared view is called membershipThe list of nodes currently in a cluster and their status (alive, suspected, dead, left), as each node believes it to be..
You cannot know for certain that a remote node is dead; you can only notice that you have not heard from it. A failure detectorA component that decides, from missing or late messages, which nodes are probably down. turns that silence into a verdict, and every detector trades speed against false alarms. Then the verdict has to reach everyone, and with hundreds or thousands of nodes no single node should have to tell everybody.
Think of how news spreads through an office. Nobody sends an email to all 500 people; each person mentions it to a couple of colleagues at lunch, and they each mention it to a couple more. By the end of the day, everyone knows, and no one person did much work. That is gossip.
How it works
Step 1: Heartbeats and timeouts
The simplest detector: each node sends a small heartbeatA periodic 'I am alive' message sent by a node so others can notice when it stops. every second, and if you miss heartbeats for, say, 5 seconds, you declare the node dead.
The timeout is the whole game. Too short, and a garbage collection pause or a congested link gets a healthy node evicted, triggering pointless failovers and data movement. Too long, and requests keep going to a dead node for that whole window. And sending heartbeats from everyone to everyone does not scale: with 1,000 nodes that is 1,000 x 999, about a million messages every second, just to say "still here".
Step 2: Phi accrual: suspicion as a number
A fixed timeout ignores that networks differ. A node across an ocean with jittery latency needs a longer window than one in the same rack. The phi accrual failure detectorA failure detector that outputs a continuous suspicion level (phi) based on the observed distribution of heartbeat arrival times, instead of a yes/no timeout. learns from history. It records the gaps between recent heartbeats and, at any moment, asks: given those past gaps, how unlikely is it that the next heartbeat is still coming?
Here is the probability, from the learned distribution, that a heartbeat arrives even later than the time already waited. If heartbeats normally arrive every 1.0 s give or take 0.1 s, then 1.3 s of silence is already very unlikely and phi climbs fast. If they normally wobble between 0.5 s and 3 s, phi rises slowly. Phi of 1 means about a 10 percent chance you are wrong if you declare the node dead now, phi of 2 means 1 percent, phi of 3 means 0.1 percent. Each application picks a threshold, so one detector serves both "fail over fast" and "never evict by mistake" users. Cassandra and Akka use phi accrual detectors.
Step 3: Gossip dissemination
Once a node notices something (a new member joined, node 17 looks dead), the news has to spread. In a gossip protocolA protocol where each node periodically exchanges information with a few randomly chosen peers, so updates spread through the cluster like an epidemic., every node, once per round, picks a few random peers and exchanges what it knows. The number of peers is the fan-outHow many peers each node contacts per gossip round..
- Round 0 Only the center node knows the news (it noticed a node fail, or a new member joined).
- Round 1 It tells two peers chosen at random. Three nodes now know.
- Round 2 Each informed node tells two random peers. Seven nodes know; one more round reaches nearly everyone.
The arithmetic is why gossip is so popular. While few nodes know, the informed set multiplies every round: with fan-out 2, roughly 1, 3, 9, 27... So the number of rounds to reach everyone grows with the logarithm of the cluster size, not with the size itself. Going from 100 nodes to 10,000 adds only a handful of rounds. Each node does a constant amount of work per round no matter how big the cluster is, there is no central coordinator to fail, and because peers are random, a few lost messages or dead nodes barely slow it down.
The cost is that news is eventually everywhere, not instantly: membership is an eventually consistent view ( PACELC and consistency models ). Nodes may briefly disagree about who is alive. Systems handle this by versioning each node's state (a heartbeat counter or generation number) so newer information always wins when two views meet.
Step 4: SWIM, detection and dissemination together
SWIMScalable Weakly-consistent Infection-style process group Membership: a protocol that detects failures with direct and indirect pings and spreads membership changes by piggybacking them on those pings. combines a scalable detector with gossip:
- Ping: each period, a node pings one random member and waits for an ack.
- Indirect ping: if no ack arrives, it asks k other members to ping that node on its behalf (
ping-req). This tells "the target is down" apart from "the link between me and the target is flaky". - Suspect, then confirm: if no one gets an answer, the target is marked suspect rather than dead. If it is alive, it hears the suspicion through gossip and refutes it with a higher incarnation number. If not, after a timeout it is declared dead.
- Piggyback: membership updates ride along on the ping and ack messages already being sent, so dissemination costs no extra messages.
Each node sends a constant number of messages per period regardless of cluster size, unlike all-to-all heartbeats. HashiCorp's memberlist library, used by Consul and Serf, is based on SWIM with extensions.
Try it
Try this:
- Leave fan-out at 2 and press Play. Watch the S-shaped curve: slow at first, explosive in the middle, slow again at the end as informed nodes keep picking peers who already know.
- Set fan-out to 1 and play again. It still reaches everyone, just in more rounds. Compare the round count with log2(100), about 6.6.
- Set fan-out to 5. It finishes in fewer rounds, but count the cost: most of the extra messages in the last rounds go to nodes that already knew.
Going deeper
Why the tail is slow
Near the end, most random picks hit nodes that already know, so the last few stragglers take a while. Real protocols mix strategies: push (tell peers what you know) is fast early, pull (ask peers what they know) is fast late, and push-pull does both in one exchange. Many systems also gossip more often to a node that seems to be missing updates.
False positives cost more than slow detection
Declaring a live node dead is expensive: data gets re-replicated, leaders change, clients reconnect. That is why SWIM uses a suspect state and why phi thresholds are usually set conservatively. A node that keeps flapping between alive and dead can hurt a cluster more than one that is simply down.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| All-to-all heartbeats with fixed timeout | Small clusters (a handful of nodes) where simplicity matters most | Scale (messages grow with N squared) and links with variable latency |
| Phi accrual detector | Networks with uneven latency; tunable trade-off between speed and false alarms | Needs heartbeat history; a new or rarely heard node has little to learn from |
| Gossip dissemination | Large clusters with no central coordinator; robust to lost messages | News is eventually consistent and takes several rounds to spread |
| Central coordinator (etcd, ZooKeeper sessions) | A single authoritative membership view for leader election and locks | The coordinator becomes a dependency and a scaling limit |
Common mistakes
- Setting failure timeouts shorter than garbage collection pauses, so healthy nodes get evicted.
- Treating a gossip membership view as instantly consistent and acting on it as if every node agrees.
- Declaring a node dead from one missed ping instead of using indirect checks and a suspect state.
- Running all-to-all heartbeats on hundreds of nodes and wondering where the network bandwidth went.
- Using gossip membership alone for decisions that need exactly one owner; use consensus for those ( Consensus: Raft ).
In the wild
Cassandra nodes gossip their state with random peers every second and use a phi accrual detector to mark peers down. Consul and Serf build cluster membership on HashiCorp's memberlist, a SWIM-based library. Akka Cluster uses gossip for membership and phi accrual for failure detection, and Amazon's Dynamo paper described gossip-based membership and failure detection for its storage nodes.
Check yourself
-
Why can't a failure detector be both instant and never wrong?
Show answer
B. Because a slow node and a dead node look the same from outside, so faster verdicts mean more false alarms Silence is ambiguous. Waiting longer reduces mistakes but delays detection; every detector picks a point on that curve.
-
A phi accrual detector reports phi = 3 for a node. Roughly what does that mean?
Show answer
B. If you declare it dead now, there is about a 0.1 percent chance you are wrong Phi is minus log10 of the probability that a heartbeat still arrives later, so phi 3 means about 1 in 1,000.
-
A cluster grows from 100 to 10,000 nodes. Roughly how does the number of gossip rounds to spread news change?
Show answer
B. It roughly doubles, since rounds grow with log N log of 10,000 is twice the log of 100, so a few more rounds, while each node still sends a constant number of messages per round.
-
In SWIM, why ask other members to ping a node that did not answer?
Show answer
B. To tell a dead node apart from a broken link between the two nodes If others can reach it, the problem is the path, not the node, and it should not be declared dead.
Recap
- Membership is each node's view of who is in the cluster and alive.
- Failure detectors turn silence into a verdict and always trade detection speed against false alarms.
- Phi accrual detectors learn heartbeat timing and output a suspicion level you threshold.
- Gossip spreads news in a logarithmic number of rounds with constant work per node and no coordinator.
- SWIM combines random pings, indirect pings, a suspect state and piggybacked gossip.