Failure Detection: Heartbeats and Phi Accrual
On this page
The failure detection trade-off
A node stops responding. Is it dead, or slow (Day 1)? A failure detector must decide when to give up waiting:
- Short timeout: fast failover, but slow-but-alive nodes get declared dead. That triggers needless failovers, data movement, and sometimes two active leaders.
- Long timeout: fewer false alarms, but real failures take longer to handle, and users wait.
You can't have both perfectly; FLP (Day 14) says so. Good detectors make the trade-off adaptive.
Heartbeats with a fixed timeout
Each node sends a heartbeat every second; if none arrives for, say, 5 seconds, it's suspected dead. Simple, used everywhere (Raft's election timeout, Kubernetes node heartbeats). The weakness: a fixed timeout ignores how the network really behaves. On a quiet LAN, 5 seconds is very slow; during a busy period with garbage collection pauses, 5 seconds might cause false alarms.
Phi-accrual: suspicion as a number
The phi-accrual failure detector (Hayashibara and colleagues, 2004) learns the normal distribution of heartbeat intervals and outputs a continuous suspicion level φ instead of a yes/no answer. φ = −log10(probability that a heartbeat would arrive this late if the node were alive). φ = 1 means about a 10 percent chance it's still alive; φ = 3, about 0.1 percent; φ = 8, about one in a hundred million.
# phi.py: a phi-accrual failure detector (normal approximation of heartbeat intervals)
import math, random, statistics
class PhiAccrual:
def __init__(self, window=200):
self.intervals, self.last, self.window = [], None, window
def heartbeat(self, now):
if self.last is not None:
self.intervals = (self.intervals + [now - self.last])[-self.window:]
self.last = now
def phi(self, now):
mean = statistics.mean(self.intervals)
std = max(statistics.stdev(self.intervals), 0.1 * mean) # avoid a zero spread
elapsed = now - self.last
p_later = 0.5 * math.erfc((elapsed - mean) / (std * math.sqrt(2))) # P(next beat later than this)
return -math.log10(max(p_later, 1e-300))With heartbeats arriving about every second (±0.1 s):
0.5 s since last heartbeat -> phi 0.00
1.0 s since last heartbeat -> phi 0.32
1.3 s since last heartbeat -> phi 2.99
1.5 s since last heartbeat -> phi 6.76
2.0 s since last heartbeat -> phi 23.69The application chooses a threshold, for example 8, and the detector adapts: on a jittery network the learned spread is wider, so suspicion rises more slowly; on a steady one, it rises fast. Cassandra (phi_convict_threshold, default 8) and Akka use phi-accrual detectors. Real implementations fit the distribution more carefully, but the idea is the same.
Gossip and SWIM in large clusters
With thousands of nodes, everyone heartbeating everyone is too much traffic. Gossip protocols spread membership and liveness: each node periodically exchanges state with a few random peers, and information spreads epidemically, reaching all nodes in roughly logarithmic rounds. SWIM (used by HashiCorp's Serf, Consul and memberlist) adds indirect probing: if A can't reach B, it asks a few other nodes to ping B before suspecting it, which separates "B is dead" from "the link between A and B is bad". Suspicion periods let a falsely suspected node refute it.
Designing around imperfect detection
- Assume the detector will be wrong sometimes and make it safe: fencing tokens (Day 18), majorities, idempotent retries.
- Tune per environment: measure normal heartbeat jitter, garbage collection pauses and network latency before choosing timeouts.
- Distinguish reachability from health: a process can answer heartbeats while its disk is full; add application-level health checks.
- Add hysteresis: require several missed heartbeats, and several successes before readmitting, so nodes don't flap.
Check yourself
Shorter timeouts detect real failures faster but produce more false suspicions of slow nodes; longer timeouts do the opposite.
It learns the spread of heartbeat intervals; with more variation, the same silence produces lower suspicion, so it waits longer before declaring failure.
A failed node from a broken link between two particular nodes. When a direct ping goes unanswered, the node asks a few other members to ping the suspect; if any of them succeed, the suspect is alive and only that link is bad.
All-to-all heartbeats grow with the square of the cluster size. Gossip spreads membership information with a fixed number of messages per node, scaling to thousands of nodes.
Treat it as a suspicion: fail over in a way that's safe even if the node is alive, using fencing and idempotent operations, rather than assuming it's gone.