Heartbeats and failure detection: an interactive timeout simulator

Distributed systems detect failed nodes from heartbeats: each node sends a small message every second, and if none arrives for a timeout, it is declared dead. The catch is that a dead node and a slow one look the same from outside. A short timeout notices crashes quickly but also declares healthy nodes dead whenever they pause or the network hiccups; a long one rarely errs but leaves a real failure unnoticed for longer. There is no timeout that is both fast and never wrong.

The playground simulates a day of heartbeats from a node that never fails. Change the conditions and the timeout, and count how often it is wrongly declared dead, against how long a real crash would take to notice.

Why healthy nodes go quiet

• Lost or delayed packets: one lost heartbeat makes a two-second silence. In the flaky preset, with 2% of heartbeats lost, a 2 second timeout raises 1,061 false alarms in a day; a 1.5 second timeout, 2,088.
• Stop-the-world pauses: a garbage collector, a paused virtual machine or heavy swapping stops the node, heartbeats included, for seconds. The node is fine and will carry on as if nothing happened.
• Overload: a node too busy to send heartbeats on time looks dead, and failing it over moves its load onto the others, which can then look dead too.

The cost of each kind of mistake

A false alarm is not harmless. Declaring a node dead typically starts a failover, a leader election, a rebalance of partitions or the rescheduling of its work, each of which costs time and load, and the “dead” node may still be acting on its own, which is why leases and fencing tokens exist. A slow detection costs availability: requests keep going to a dead node, or nothing takes over its work, for the whole timeout. With a timeout of T and a heartbeat every second, a crash is noticed after about T minus half a second on average.

Detecting better than a fixed timeout

• Phi accrual: instead of a yes-or-no timeout, compute a suspicion level from how unusual the current silence is given the history of heartbeat intervals, and act when it crosses a threshold. Cassandra and Akka use it; the threshold adapts to how noisy each link really is.
• Ask others before deciding: SWIM-style membership, used by Consul and Serf, has other nodes probe a suspect indirectly before it is declared dead, so one bad link does not condemn a healthy node.
• Suspect first, then confirm: mark a silent node suspect, stop sending it new work, and only declare it dead after a longer timeout. Kubernetes waits a configurable time before evicting pods from an unreachable node.
• Use a lease: a node holds a lease it must renew, and gives up its role on its own when it cannot, so the rest of the system can safely take over once the lease has expired.

A phi accrual detector in code

import math, statistics, time

class PhiAccrualDetector:
    """Suspicion that grows with silence, scaled to how regular heartbeats have been."""
    def __init__(self, window=100):
        self.intervals, self.window, self.last = [], window, None

    def heartbeat(self, now=None):
        now = now or time.monotonic()
        if self.last is not None:
            self.intervals = (self.intervals + [now - self.last])[-self.window:]
        self.last = now

    def phi(self, now=None):
        now = now or time.monotonic()
        mean = statistics.mean(self.intervals)
        std = max(statistics.pstdev(self.intervals), 0.1 * mean)
        # chance a heartbeat this late would still arrive, under a normal approximation
        p_later = 0.5 * math.erfc((now - self.last - mean) / (std * math.sqrt(2)))
        return -math.log10(max(p_later, 1e-300))

# declare the node dead once phi passes 8: about a 1 in 100 million chance it was just late

In a system design interview

When a design relies on noticing failures, give the numbers and the trade-off: “Nodes heartbeat every second; a node silent for 5 seconds is marked suspect and stops getting new work, and after 15 seconds its partitions are reassigned. Shorter would fail over on every long GC pause; longer would leave partitions unserved.” Expect the follow-ups: what the old node does if it was only paused, how you avoid split brain, and how detection interacts with leader election.

Read the guide to gossip and failure detection, see gossip for how membership spreads and Raft for election timeouts in practice, or watch a strong candidate design a job scheduler.

Questions people ask