Heartbeat, gossip and failure detection

In a cluster, machines fail silently. A crashed node does not announce it. Others must notice, because requests sent to it are lost and its work must be reassigned. But the network can be slow and a busy node can pause, so a node that is merely slow looks identical to one that is dead. Failure detection is therefore a matter of suspicion, never of certainty.

A heartbeat is a small message sent regularly to say "I am alive". The receiver records when it last heard one. If none arrives within a timeout, the sender is declared failed.

The timeout is a tradeoff.

• Too short: a brief network hiccup or a pause for garbage collection causes a false alarm, triggering needless failover and data movement.
• Too long: a real failure goes unnoticed, and requests keep failing.

Who sends heartbeats to whom matters. A single monitor collecting them from everyone becomes a bottleneck and a single point of failure. All to all heartbeats cost N squared messages, which is impractical beyond small groups. Large clusters use gossip.

In gossip, also called epidemic protocols, each node periodically, say once a second, picks a few random peers and exchanges what it knows: the list of nodes and, for each, a heartbeat counter or version. Each side merges the newer information into its own view.

Like a rumor, a fact spreads exponentially. After each round the number of informed nodes roughly doubles, so news reaches all N nodes in about log2 N rounds. For 1,000 nodes that is about 10 rounds, 10 seconds at one round a second. Each node sends only a constant number of messages per round, regardless of cluster size.

Variants: push (send what I know), pull (ask for what you know) and push-pull (both), which converges fastest.

Strengths: no central point, tolerates failures and lost messages, and scales gently. Weaknesses: information is eventually consistent, so views can differ briefly, and there is some redundant traffic. Dynamo and Cassandra use gossip for membership and health.

Each node keeps, for every peer, the latest heartbeat counter it has seen and when. A peer whose counter has not advanced for longer than a threshold is suspected, and once most views agree, it is marked down. No single node has to decide for everyone.

A fixed timeout treats a network with steady 100 ms delivery the same as one with erratic 2 second delays. The phi accrual detector, used by Cassandra and Akka, replaces the yes or no verdict with a suspicion level.

It records the intervals between recent heartbeats from each peer and learns their typical distribution. When a heartbeat is late, it asks how unlikely that lateness is, given the history, and reports phi, which is roughly the negative base 10 logarithm of that probability.

• A phi of 1 means about a 10 percent chance the delay is normal.
• A phi of 2 means about 1 percent, and so on.
• The application chooses a threshold, commonly around 8, above which the node is treated as failed.

Because the estimate adapts to measured behavior, a jittery link gets a more forgiving cutoff and a steady link gets a stricter one. This gives fewer false alarms and faster detection without hand tuning the timeout for every environment.

• Treat temporary failure differently from permanent. Cassandra marks a node down and uses hints, but only removes it from the ring on explicit command.
• Confirm before acting: several peers must agree, or a second probe goes through a different route.
• Add jitter and back off, so a recovering cluster is not flooded.
• Remember the limit: a detector can be wrong, so systems that rely on exclusivity need leases and fencing, covered next.

• Heartbeat: the basic signal of life. Tune the timeout carefully.
• Gossip: spreads that signal across a large cluster in logarithmic time, with no central watcher.
• Phi accrual: turns heartbeat timing into an adaptive suspicion score instead of a fixed cutoff.