Failure Detection: Heartbeats and Gossip

1The core idea#

Failure detection is the mechanism a distributed system uses to form an opinion about which members are up. That word "opinion" is the whole point.

You cannot prove a node is dead, only suspect it.

• A node that stopped responding might be crashed.
• Or alive behind a congested switch.
• Or paused in a 4-second garbage collection.
• Or sitting on the far side of a network partition.
• From the outside, all four look identical: silence.

So failure detection is a bet. You watch for signs of life and, after enough silence, declare a node suspect or dead. Two numbers describe how good your bet is:

• Detection time. How long after a real crash before you notice. Lower is better for availability.
• False positive rate. How often you declare a healthy node dead. Lower is better for stability.

The mental model: a dial.

• Turn it one way and detection drops from 30 seconds to 3 seconds, but your false positive rate climbs to maybe one bad eviction per node per day once a GC pause slips past the window.
• Turn it the other way and the false positives vanish, but a crashed node keeps receiving traffic for half a minute.
• The craft is picking where on the dial you sit for this workload, then adding mechanisms that bend the curve so the choice hurts less.

The two building blocks to know cold:

• Heartbeats. How a node signals it is alive.
• Gossip. How that signal spreads across a cluster with no central bottleneck.

2How it works#

Heartbeats#

A heartbeat is a periodic "I'm still here" message. Two flavors:

• Push. Each node sends a beat every interval (say every 1 second) to whoever is watching. The watcher holds a timer. No beat inside the window, the node is marked suspect.
• Pull (probing). The watcher actively pings "are you there?" and expects a reply within a deadline. This is what a load balancer does when it hits GET healthz every few seconds.

Which to pick:

• Push scales better: each node emits one message regardless of how many watchers care.
• Pull gives the watcher control over timing, handy when the watcher is the one who needs a fresh answer right now.

The naive version uses a fixed timeout: miss N beats in a row, you are dead.

• Simple, and fine for a handful of nodes on a quiet network.
• It falls apart at scale because one timeout cannot fit every situation.
• The same 3-second threshold that is patient enough for a busy node is far too slow for a snappy one.

Gossip#

Heartbeats answer "how does one node prove it is alive." Gossip answers "how does the whole cluster agree on who is alive with no single coordinator." The trick is simple and a little viral.

How a round works:

• Each node keeps a local table: for every member, a heartbeat counter and the last time that counter changed.
• Every second, a node bumps its own counter and picks a few random peers to exchange tables with.
• Each side merges by keeping the higher counter per member.

Why it holds up:

• An update started at one node reaches the whole cluster in roughly log(N) rounds. For 1,000 nodes that is about 10 seconds at one round per second.
• It keeps working even when some nodes are down, because every node has many random paths to learn the news.
• No central watcher to overload, no single point of failure.

Phi-accrual: the upgrade that matters#

This is the idea that separates a senior answer from a junior one.

• Instead of a hard yes/no timeout, a phi-accrual detector outputs a suspicion level, phi, that rises continuously as silence grows.
• It learns the normal gap between heartbeats from recent history.
• If a node usually beats every 1s with a bit of jitter, a 1.2s gap barely moves phi.
• If that same node has been silent for 8s, phi spikes.

Why it is better than a fixed number:

• You act on a phi threshold instead of a wall-clock timeout.
• Phi adapts per node and per network condition.
• A node on a flaky cross-region link naturally shows more variance, so the detector tolerates longer gaps before it panics, with no per-link timeout to hand-tune.

3A worked example with real numbers#

Interviewers love it when you stop waving your hands and start computing. Say you run a 1,000-node Cassandra-style cluster.

The setup:

• Heartbeat interval: 1 second.
• Measure actual inter-arrival gaps over the last few minutes: roughly normal, mean 1,000ms, standard deviation 200ms. That is honest for a busy fleet with some GC jitter.

What phi means in practice. Phi is the negative base-10 log of the probability that you should still be waiting, given the time since the last beat:

• phi 1: about a 10 percent chance you are wrong to suspect.
• phi 2: 1 percent.
• phi 3: 0.1 percent.
• phi 8: 0.000001 percent (the Cassandra default).

What phi 8 buys you at this variance:

• With mean 1,000ms and deviation 200ms, phi 8 lands at roughly 4.5 seconds of silence.
• A healthy node that goes quiet for 1.5s during a minor GC pause sits at about phi 0.6, nowhere near the line. Nobody panics.
• A node that is genuinely gone crosses phi 8 at about 4.5s and gets marked suspect.
• A naive fixed timeout would hardcode 4.5s everywhere to get the same patience, including on snappy nodes (mean 1,000ms, 50ms deviation) that you could safely flag at 2 seconds. Phi gives each node its own threshold for free.

Now cost out the gossip traffic:

• Each node gossips to 3 random peers every second: 1,000 nodes times 3 equals 3,000 messages per second cluster-wide, and each node sends and receives only a handful.
• The full membership table for 1,000 members is maybe 40 bytes per entry, so 40KB, exchanged a few times a second per node: call it 120KB/s of background chatter per node.
• That is nothing on a 10Gbps NIC.

Convergence after a real death:

• The suspicion is local to whoever stops hearing beats.
• Gossip spreads the confirmed-dead status in about log base (fanout) of 1,000, roughly 6 to 7 rounds, under 10 seconds to tell the whole cluster.
• Total from crash to the last node knowing: about 4.5s to suspect plus under 10s to disseminate, call it 15 seconds worst case, and far less for the nodes nearest the dead one.

The four numbers to say out loud in a loop:

• Threshold phi 8.
• Roughly 4.5s to suspect at this variance.
• About 120KB/s background bandwidth per node.
• Under 10 seconds to converge across 1,000 nodes.

Specifics like that move you from "sounds senior" to "has actually shipped this."

4Trade-offs#

The real decisions, side by side:

What you give up each way:

• Fixed timeout. Dead simple, zero learning, but one number for the whole fleet. Tight and GC pauses evict healthy nodes. Loose and you serve errors from dead nodes for 30 seconds.
• Centralized detector (a coordinator pinging everyone, or everyone reporting to one place). Easy to reason about, fast and consistent decisions. But the coordinator is a bottleneck and a single point of failure: when it hiccups, the whole cluster looks dead at once. Fine at 50 nodes, painful at 5,000.
• Gossip. No bottleneck, survives partitions, scales beautifully. The cost is eventual consistency of membership: two nodes can briefly disagree on who is alive, and detection is slower because news spreads in rounds. You also burn steady background bandwidth, and a sloppy implementation can create gossip storms.
• Phi-accrual. Best false-positive behavior because it adapts, but it needs a warm-up window to learn each node's baseline, and a wildly bimodal heartbeat distribution confuses the model.

Gossip for who-is-alive, phi-accrual for is-this-one-dead. Pick the mechanism from the shape of the workload, not habit.

My honest default:

• Gossip for membership dissemination.
• Phi-accrual for the suspicion decision.
• That pairing is why it shows up in so many real systems, and it is exactly what the worked example priced out.

5Where it is used#

Cassandra and DynamoDB-style stores.

• Gossip tracks which nodes own which data ranges.
• A phi-accrual style detector keeps a single slow node from getting wrongly evicted and triggering a storm of data movement.
• Cassandra ships with a phi threshold default of 8, the exact number from the worked example.
• Evicting a node here is expensive: it kicks off rebalancing of terabytes.

Service meshes and Kubernetes.

• They lean on pull-based health checks.
• The kubelet probes your container with liveness and readiness checks on a fixed interval, and the control plane reacts.
• This is centralized-ish and simple on purpose, because the blast radius of one pod is small and operators want predictable behavior.

Consul and similar membership libraries (SWIM style).

• Nodes probe a random peer each interval.
• If that peer is quiet, they ask a few other nodes to probe it indirectly before declaring it dead.
• That indirect-probe step is a cheap, powerful false-positive killer: it separates "this node is dead" from "my path to this node is broken."

How to choose, in one line each:

• Reach for gossip when the cluster is large and membership changes often.
• Reach for centralized checks when the cluster is small, decisions must be fast and consistent, and you already have a control plane doing the watching.

6Common pitfalls and gotchas#

Timeout shorter than your GC pause.

• If a stop-the-world pause can last 3 seconds and your timeout is 2 seconds, you evict healthy nodes every time the collector runs.
• Size timeouts against your actual worst-case pause, not the average.
• This is the whole reason the worked example set phi 8 at 4.5 seconds rather than a tight 2.

The health check that lies.

• A healthz endpoint that returns 200 as long as the process is up tells you nothing about whether the service can do real work.
• If the database connection pool is exhausted, the process is "healthy" and completely useless.
• Make readiness checks exercise the real dependency path.
• Separate liveness (is the process wedged, restart it) from readiness (can it serve traffic right now).

Confusing node-down with partition.

• During a network split, each side thinks the other is dead.
• If both sides act on that belief, you get split-brain: two leaders, two sources of truth, data divergence.
• Failure detection alone cannot solve this. You need a quorum or fencing mechanism on top.
• An interviewer who hears you conflate the two will push hard.

Correlated failures breaking your assumptions.

• Heartbeat math assumes independent failures.
• A bad deploy, a config push, or an availability-zone outage takes down many nodes at once, and your detector lights up the whole fleet.
• Have a circuit breaker: if more than some fraction of the cluster looks dead at once, suspect the detector before suspecting the cluster.

7How it shows up in interviews#

Failure detection rarely gets its own question.

• It shows up as a follow-up inside a larger design: "you have a cluster of cache nodes, how does the client know one died?" or "your leader crashed, how does the system notice and fail over?"
• The interviewer is checking whether you understand that liveness is a guess, not a fact.

What they probe:

• Can you articulate the detection-time versus false-positive trade-off, with numbers?
• Do you know the difference between a node being dead and being partitioned or slow?
• Can you scale the mechanism? A fixed-timeout coordinator is a fine starting point, but can you evolve it to gossip when they say "now there are 10,000 nodes"?
• Do you connect detection to action? Detecting failure is useless unless something safe happens next.

Weak answer: "Each node sends a heartbeat every second. If we miss 3, the node is dead and we remove it."

Why it is weak:

• Not wrong, just incomplete. It ignores slow nodes, partitions, GC pauses, and scale.
• It is a 10-node answer given for a 10,000-node system.
• The moment the interviewer says "a node GCs for 3 seconds," it evicts a healthy node and the candidate has nothing left.
• No numbers, no sense that liveness is probabilistic, no connection to what happens after the node is marked dead.

Strong answer: "I'll start with heartbeats at a 1-second interval, but a fixed timeout evicts healthy nodes during GC pauses, so I'd use a phi-accrual detector that learns each node's normal cadence and outputs a suspicion score. Concretely, if a node's gaps are mean 1,000ms with 200ms deviation, a phi threshold of 8 flags it at about 4.5 seconds of silence, which clears our p99 GC pause, and a snappier node gets a tighter threshold for free. At 1,000 nodes I'd disseminate membership with gossip, 3 peers per second, around 120KB/s per node, converging across the fleet in under 10 seconds with no central bottleneck. I'd add an indirect-probe step, SWIM style, so a broken network path doesn't get mistaken for a dead node. Detection only marks a node suspect. Before we act, I want a quorum to agree, otherwise a partition gives us split-brain. And I'd add a safety valve: if more than 30 percent of the fleet looks dead at once, I trust the detector less and page a human instead of auto-evicting."

Why it is strong:

• Names the trade-off with real numbers.
• Handles the slow-versus-dead trap.
• Scales the mechanism from timeout to gossip on cue.
• Connects detection to a safe action through quorum.
• Defends against correlated failures.
• Every claim is backed by a figure the candidate can defend.

The one line I always want to hear: failure detection is probabilistic. Anyone who speaks in absolutes, "we know the node is dead," has not been burned yet. The engineers who have say "we suspect it is dead, so here is what we do that is safe even if we are wrong."

Next, try the System Design Question walkthrough on designing a highly available key-value store, where this exact detector feeds leader election and replica repair.