BOOKS DEEP-READ · DATABASE INTERNALS · CH 9
Database Internals · Ch 9 · Alex Petrov · 2019
You message a colleague. Ten minutes, no reply. Are they in a meeting? Out of battery? In trouble? You can't tell. When a pile of machines works together, every machine spends every second answering that same question about the others: is that box dead, or just slow? Chapter 9 of Database Internals is about exactly that — how you decide a node has failed, and why you can never decide it correctly.
People don't publish their own obituary. A crashed machine doesn't send a farewell note either — it simply stops talking. So you have to reason backwards: it's been quiet this long, it's probably gone. But how long is "this long"? Nobody knows. That is the knot the whole chapter is tied around: silence can mean death, or it can mean traffic, and from the outside the two look identical.
The obvious fix is a stopwatch: no answer in 3 seconds, call it dead. Wait too little — the other side merely hit a network hiccup, or spent two seconds tidying up memory, and you have just pronounced a living machine dead. That's a false positive, and it's expensive: the system thinks the boss is gone, elects a new one, and now two bosses are giving orders; or it starts hauling hundreds of gigabytes to other machines and finishes off a network that was only wobbling — the detector has manufactured the very outage it was watching for. Wait too long and requests keep flowing to a genuinely dead box while users sit there for thirty seconds. Too short kills the living, too long is oblivious, and there is no "just right" number in between.
The most useful move in this chapter is to stop forcing the system to answer a yes/no question. Four ideas, each building on the last —
The real trade-off isn't "how do I judge more accurately" but "when I judge wrong, which direction hurts more": a bank transfer would rather be slow than kill a living node — two bosses will corrupt the ledger; a chat app's little green dot can be wrong all day as long as it's fast.
The honest cost: none of these methods is guaranteed correct. As long as messages can be arbitrarily late, "slow" and "dead" cannot be told apart, and every detector is just playing the odds.
You can never be sure whether another machine is dead or merely slow. So don't chase being right — replace the "dead / alive" yes/no question with a "how suspicious" score and let each action draw its own line according to what it costs. And accept it: sooner or later you will judge wrong, and the system has to survive that.
Want the actual algorithms, the thresholds and the diagrams? → switch to the deep read
You think failure detection is about deciding whether a machine is dead. Its real goal is keeping the cost of being wrong under control, given that you can never be right. The chapter first states the knot plainly — in an asynchronous network, "crashed" and "very slow" are indistinguishable from the outside — and then makes the move that matters in practice: stop having the detector emit a boolean, have it emit a tunable degree of suspicion, and hand the threshold to whoever consumes it.
Second chapter of Part II, "Distributed Systems". It follows Chapter 8, which filled in the assumption table — how reliable the link is, how trustworthy time is, how nodes fail — and it sets up Chapter 10, leader election: the first step of electing a leader is always deciding the old one is dead. Everything after that — replication, anti-entropy, consensus — treats failure detection as a pluggable component underneath. What does it map to in the wild? Cassandra deciding a node is up, ZooKeeper and etcd expiring sessions, Kubernetes marking a node NotReady, Kafka noticing a broker is gone.
Start with what happens if you don't solve it. Both directions are expensive.
The cost of missing a death: in a 3-node strongly consistent cluster, if the leader dies and nobody notices, the cluster cannot be written to at all — not slow, unwritable — until a human steps in. Failure detection sets "how long until the system starts saving itself", and that number is the floor on your RTO.
The cost of a false positive is subtler and bigger: a 200-node cluster that declares 5 healthy nodes dead immediately kicks off replica rebuilds and rebalancing — hundreds of gigabytes across racks, finishing off a network that had merely wobbled for 200 ms, so more nodes get declared dead, and it avalanches. Which is the mental model to install first: a failure detector is not a sensor, it is an actuator. The moment it speaks, the system fails over, reroutes and moves data — all expensive or irreversible. A wrong verdict is not "a bad reading", it is real destruction.
And getting it right is impossible in principle. A same-datacenter round trip is typically around 0.2 ms, with 5–20 ms spikes being common; one JVM full GC can freeze a process for 0.5 to 5 seconds; cross-region links jitter by hundreds of milliseconds routinely. Set the timeout to 1 second and a single GC pause is enough to kill a healthy node; set it to 30 seconds and users wait 30 seconds on a real failure. This is not a badly tuned parameter, it is a structural obstacle of the asynchronous model: with no bound on delay, "slow" and "dead" can never be separated. What the chapter answers is given that you can't be right, now what.
The book uses the classic Chandra–Toueg framing, scoring a detector on two properties:
In an asynchronous network the two are irreconcilable, and the tug-of-war is obvious: lengthen the timeout and accuracy rises while completeness slows; shorten it and the reverse. The book's handling is pragmatic — completeness is cheap (keep waiting long enough and you will eventually suspect it), accuracy is the hard part. So every real detector takes the same road: guarantee completeness, push false positives down as far as you can, and allow suspicion to be withdrawn — first mark a node suspected, and cancel it if the node speaks again; only before an irreversible action (evicting it from the cluster, say) escalate to convicted. That two-stage structure is the shared skeleton of every algorithm here.
There are exactly two postures. With a ping the monitor asks and waits for an answer; with a heartbeat the monitored side checks in on a schedule. Heartbeats halve the message count but need cooperation; pings also measure round-trip time for free. Their weak spot is identical: the only evidence is a timeout, and a timeout only says "I received nothing in this window".
The first idea that escapes timeouts (from Mostéfaoui, Mourgaya and Raynal): ignore clocks entirely, look only at relative order. Each process periodically broadcasts a round-numbered heartbeat to everyone; in each round a receiver waits only for the first n−f to arrive (n nodes, f the tolerated number of crashes), then moves on, marking whoever is persistently last as suspected.
The intuition: don't ask "how many milliseconds late is he", ask "is he always at the bottom of the pack". The payoff is elegant — when the whole datacenter slows down, everyone slows together, the ranking doesn't move, and you avoid the mass false positives that are exactly where fixed timeouts fall over. The price is two premises: at most f processes crash, and links are fair-loss (retransmit forever and it eventually gets through). Also, every round is an all-to-all broadcast, so traffic is O(n²) — double the nodes, quadruple the messages. Good for tens of nodes, not for thousands.
A cheap, effective trick: when A gets no answer from B, don't convict — ask k neighbours to probe B on your behalf, and withdraw the suspicion the moment any of them hears back. It separates two things routinely conflated: "the path from A to B is broken" and "B is actually broken". Most "that box mysteriously dropped out and came back" incidents are the former. The cost is one extra hop of latency and k times the probe traffic.
The design most worth taking away (Hayashibara et al., 2004). Three steps: keep a sliding window of the last few hundred to a thousand heartbeat inter-arrival times → fit a distribution to those samples → when the node has now been silent for t milliseconds, compute the probability that a normal heartbeat would arrive even later than t, and emit its negative logarithm: φ = -log₁₀ P(later than t).
In plain words, φ is the decibel scale of "how outrageous is this silence": φ=1 means convicting now has roughly a 10% chance of being wrong, φ=2 means 1%, φ=3 means 0.1% — every +1 divides the error probability by ten. You don't need to read the formula, only to remember that conversion.
The design intent most often missed: it hands the job of picking a threshold back to the consumer. From one suspicion level, the routing layer can drain new requests at φ=3 (reversible, cheap) while leader election waits until φ=8 to convict (irreversible, expensive) — one detector serving parties with wildly different costs, which a boolean cannot do. It is also adaptive: when the datacenter slows down, the distribution in the window shifts right and the time-to-convict stretches automatically without touching a single threshold. The costs: it needs a warm-up period to collect samples; it reacts to a step change (the network going from 1 ms to 1 s instantly) more slowly than a fixed timeout would; and the usual normal-distribution assumption does not always hold on a heavy-tailed real network.
Every approach so far implies a "who monitors whom" topology. Gossip-based detection (van Renesse et al., 1998) removes that layer too: each node keeps a table of the heartbeat counter it knows for every node. Each round it increments its own cell, picks a few random peers and exchanges the whole table, merging row by row, keeping the larger counter. If a row hasn't increased within T_fail, the node locally marks it suspected; only after a further T_cleanup is it dropped from the table — that buffer exists to stop one late, stale message from resurrecting it.
Three solid upsides: no single point; a fixed message volume per node per round, independent of cluster size (the number of rounds to reach everyone grows only with the logarithm of the node count — usually a handful for a few hundred nodes); and natural resistance to packet loss thanks to multiple retelling paths. The downside is equally concrete: your information is second-hand — you suspect B on the strength of what C said three seconds ago, so T_fail must leave room for propagation and convicting is necessarily slower. Gossip trades speed for cheapness and for not falling apart.
The chapter closes by reframing. Everything above answers "is B dead?"; FUSE (Dunagan et al., 2004) asks can this collaboration still continue? It binds a set of related processes into a failure group and promises exactly one thing — if anything anywhere in the group goes wrong (a process crashes, or the network cuts the group apart), every surviving member is notified within bounded time; any member can also trigger the notification deliberately.
The value of that swap: the layer above no longer maintains its own mutually contradictory guesses about who is alive, it receives one signal the whole group agrees on — "uncertain" becomes "everyone abandons and everyone retries". The cost is just as clear: the granularity coarsens from a node to a group, and one member's trouble takes the group down with it. This is shared fate by design, with a larger blast radius for a wrong verdict, so it only suits collaborations that already sink or swim together.
The soul of this chapter isn't "which algorithm wins" but which direction you'd rather be wrong in. First, across the mechanisms:
Table 1 · What each failure-detection approach costs
| Mechanism | Time to convict | False positives | Message cost | Fits |
|---|---|---|---|---|
| Fixed-timeout ping / heartbeat | Set directly by the timeout, seconds | High, and drifts with network jitter | 1–2 messages per pair per period | Small clusters, stable network, simplest to build |
| Timeout-free (relative order) | Adapts to network speed | Low; a general slowdown convicts nobody | O(n²), tens of nodes at most | Small/mid clusters afraid of jitter-driven avalanches |
| Outsourced heartbeats | One extra hop, slightly more | Low; separates a broken path from a broken node | k extra probes per suspicion | Cross-rack / cross-AZ, asymmetric links |
| Phi-accrual | Set by the consumer's threshold, tiered | Priceable: every +1 of φ divides it by ten | Same as heartbeats plus a little memory | When downstream actions differ wildly in cost |
| Gossip heartbeat table | Slow; must allow for propagation | Medium; the evidence is second-hand | Fixed per node, independent of size | Hundreds of nodes, no central referee |
Then vertically: given that you will be wrong, which way is more expensive? That is what decides where you lean.
Table 2 · Which direction of error hurts more
| Scenario | Cost of killing a live node | Cost of missing a dead one | Lean |
|---|---|---|---|
| Leader election / failover | Extreme: split-brain, two leaders taking writes, permanent divergence | High: cluster unwritable, but recoverable | Slow over wrong; add fencing |
| Replica rebuild / rebalance | Extreme: hundreds of GB moved for nothing, jitter becomes avalanche | Medium: temporarily under-replicated | Most conservative threshold, delay the trigger |
| Request routing | Low: you skip a healthy box and lose a little capacity | High: requests hit a black hole, users time out | Skip eagerly; it's reversible |
| Presence / membership display | Very low: the green dot flickers | Very low | Optimise for speed |
One rule you can apply directly: tier your actions by reversibility and give the irreversible ones higher thresholds. Draining traffic is reversible — act within seconds. Failing over and moving data are not — it is worth waiting another ten-plus seconds to buy accuracy. Phi-accrual won in industry precisely because it is the only output shape that supports that tiering natively.
Any architecture discussion or interview question about high availability lands here first — before you fail over, somebody has to decide the old leader is dead. Answering "how long should the timeout be" with "emit a continuous suspicion level, let each action pick a threshold matching its cost, and fence at the point of execution" is a different class of answer.
Some real names: Cassandra spreads heartbeats over gossip and convicts with a phi-accrual variant; Akka Cluster also uses phi-accrual; Consul / Serf run SWIM-style gossip with a "suspect" intermediate state; Kubernetes has the kubelet report status every 10 seconds and the control plane mark a node NotReady after a grace period of tens of seconds before evicting pods. etcd and ZooKeeper take a different road — the lease: nobody pronounces you dead, your lease simply expires. Its safety is easy to argue (as long as clock drift is bounded), at the cost of a floor on time-to-convict set by the lease length.
p99).1. The core claim: in an asynchronous network "crashed" and "very slow" are indistinguishable, so failure detection is inherently unreliable; the goal is not accuracy but a controllable cost of being wrong.
2. Two yardsticks: completeness (everything that should be caught eventually is — liveness) and accuracy (don't convict the innocent — safety) cannot both be had. Completeness is cheap; accuracy is the hard part.
3. Every algorithm shares a suspect → convict two-stage structure: suspicion is withdrawable, and only irreversible actions escalate to conviction.
4. Heartbeats and pings have only the timeout as evidence, hence the dilemma: short kills the living (one GC pause is enough), long is oblivious.
5. Four escapes: relative ordering (no clocks, just who is last; immune to general slowdown, costs O(n²)), outsourced heartbeats (ask via another path; separates a broken link from a broken node), phi-accrual (a continuous suspicion level; every +1 of φ divides the error rate by ten), and gossip (no centre, cost independent of size, but slower to convict).
6. FUSE inverts the question: instead of "who died", guarantee that every group member receives the failure notification — trading "uncertain" for "everyone retries", at the price of shared fate.
7. The real selection question is which direction of error costs more: failover and rebuilds should be slow rather than wrong, routing should skip eagerly; tier thresholds by reversibility.
8. In the wild: Cassandra and Akka use phi-accrual, Consul and Serf use SWIM, etcd and Kubernetes use leases and grace periods. The biggest trap is gray failure — detectors green, application down — which you must cover with business metrics and backstop with fencing.