Distributed Systems Core · lesson 4 of 11 · about 28 min
How a machine knows another has died, and why it can never be sure: the timeout trade-off measured as false alarms against detection time, an adaptive phi accrual detector, failures that answer pings but fail real work, what monitoring topologies cost, and what a long pause does to a leader holding a lease. Tap any for a plain-language card.
The timeout dial
This is the problem, and it has no perfect solution in an asynchronous network. The simulation sends 40,000 heartbeats with log-normal delay, random loss and occasional congestion stalls (released all at once, as real queues do), and counts false alarms per hour and the time to notice a real crash, for different numbers of allowed missed beats.
With 1-second beats and 2.5 s stalls, 2 allowed misses gives dozens of false alarms an hour; 6 gives none but takes 5 seconds to notice a crash.
Declaring death after 3 missed beats (3.0 s) raises 7.5 false alarms an hour and notices a real crash in 2.44 s on average. Each bar shows another choice: more misses allowed means calmer but slower. There is no setting that is both instant and never wrong.
Seeded simulation: 40,000 heartbeats, 20 ms median delay (log-normal), your loss and stall settings. A false alarm is a gap between arrivals longer than the timeout.
Phi accrual
That fixes the main weakness of a fixed timeout: in a calm network a 3-second timeout is far too slow (heartbeats arrive within 60 ms of schedule), and in a noisy one it is too short. The graph shows phi growing as a beat is late for a calm window (mean 1 s, deviation 60 ms); the table runs both detectors through a calm and then a noisy regime.
Compare detection time in the calm regime, then raise the stall length and the threshold.
| Regime | Fixed: false alarms/h | Fixed detects in | Phi: false alarms/h | Phi detects in |
|---|---|---|---|---|
| Calm network | 0.0 | 3.0 s | 0.0 | 1.11 s |
| Noisy network | 7.2 | 3.0 s | 15.1 | 2.46 s |
In the calm regime phi (threshold 8) notices a crash in about 1.11 s against 3.0 s for the fixed timeout, because it learned that beats are very regular. In the noisy regime it widens by itself to 2.46 s. Its false alarms (15 an hour) depend on the threshold: raise it to trade speed for calm. Cassandra's default is 8.
Phi uses the last 500 gaps, assumed normally distributed. Heavy-tailed stalls are harder than normal jitter, which is why a high threshold matters.
Gray failure
The fix is the deep health check: instead of “is the port open”, perform a small real operation (touch the database, read a key) and require a few failures in a row before acting. Below, a node fails a fraction of real requests. A shallow ping never notices; a deep check finds it after k consecutive failed checks. Compare the requests lost.
Set 30% failures with a deep check needing 3 in a row: found in seconds. The shallow ping would run for an hour.
A node failing 30% of 200 requests a second keeps answering pings, so a shallow check leaves it in service and 216,000 requests fail in an hour. A deep check needing 3 failures in a row (every 2 s) removes it after about 40 s with 2,400 requests lost. Raising N reduces false alarms but delays removal: the timeout dial again.
Each check fails with the node's failure probability; the node is removed after N consecutive failed checks. Seeded.
Who watches whom
The other cost is disagreement. Failure detection is local opinion. If a partition splits the cluster into a group of 150 and a group of 350, each side concludes that the other side is dead. A central monitor on one side calls the other side dead too. That is exactly the situation consensus protocols and fencing exist to handle safely: never act on a single node's opinion alone.
Set 500 nodes at 1-second beats and compare all-to-all with a ring.
All-to-all monitoring at 500 nodes sends 250K messages a second; a ring needs 1K. After a partition of 150 | 350, the 150 nodes believe 350 nodes are dead and the 350 believe 150 are dead: both sides are sure, both are partly wrong. A central monitor on the larger side would also declare 150 dead.
Arithmetic: all-to-all N(N−1) per interval, ring 2N, central N, gossip with 3 peers 3N. Responses not counted.
Pick the setting
Choose the failure detection that fits what a false alarm and a late alarm cost. Each answer is worth 20 XP.
Ask: what does a false alarm cost? and what does a late detection cost?
A cache cluster in one data centre where removing a healthy node only costs some cache misses.
Tip: press 1 to 3 to answer, Enter for the next one.
Who lives by this
Four real systems and the failure-detection numbers they document.
phi accrual failure detector
The phi accrual paper proposed outputting a continuous suspicion level, phi, computed from the distribution of recent heartbeat arrival times, instead of a boolean, and letting each application choose its own threshold. It showed good trade-offs between detection time and mistakes under varying network conditions.
gossip heartbeats → phi accrual → convict at 8
Cassandra uses a phi accrual detector over its gossip heartbeats, with phi_convict_threshold defaulting to 8, and documents raising it (for example to 12) in cloud environments with noisy networks to avoid marking nodes down by mistake.
kubelet → Lease every 10 s → controller grace period 40 s
Each Kubernetes node renews a Lease object about every 10 seconds, and the node controller marks a node unhealthy only after the node-monitor-grace-period, 40 seconds by default, passes without an update. The grace period is the timeout dial set to four missed beats.
interval 30 s · unhealthy after 2 failures
AWS documents health checks on load balancer target groups with a configurable interval (30 seconds by default), and thresholds for how many consecutive failures mark a target unhealthy and how many successes bring it back. The defaults mean roughly a minute to react: a deliberate bias toward calm over speed.
Interview angle
Six questions, each worth 20 XP. “How do you detect a failed node?” is a standard probe of distributed-systems depth.
Name the trade-off (false alarms vs detection time), say how you would pick the timeout, and mention deep health checks.
Why can a failure detector never be perfect in an asynchronous network?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Pauses are usually milliseconds, but real systems have a long tail (Martin Kleppmann's well-known critique of lock services describes exactly this). A longer lease makes it rarer but slows failover, since nobody can take over until the lease expires. The robust fix is not a better timeout but a : every grant gets an increasing number, and storage rejects writes carrying an older one, so the revived old leader's writes are refused. The next-but-three lesson builds on this.
With a 10-second lease and a 2-in-1,000 chance of a 15-second pause, a few overlaps a day. Then switch fencing on.
With a 10 s lease, 0.195% of leases are outlasted by a pause: about 16.8 episodes a day (one renewal every 10 s), each leaving two leaders for roughly 6.1 s. A longer lease shrinks that, and makes failover slower by the same amount.
100,000 seeded leases; pause = log-normal body plus an occasional long stall. One renewal every 10 seconds assumed for the per-day figure.