BOOK DEEP READ · Database Internals · Chapter 10
Database Internals · Ch 10 · Alex Petrov · 2019
If a team had to hold a full vote on every small decision, nothing would ever get done. So the group picks one person to call the shots — you bring things to them, and their word is final. Every time you transfer money, send a message or upload a photo, the few dozen machines behind it are doing exactly that: picking one machine to be in charge. Chapter 10 of Database Internals is about how that pick is made, and why it is far harder than it sounds.
The most common reason for replacing the boss is not that the machine actually broke. It is that its disk got busy and it answered half a second late. Nobody hears it speak up, everyone assumes it is gone, and a new election starts — while the machine itself, blissfully unaware, is still working normally. Replacing the boss is usually triggered by a misunderstanding, not by a failure.
With no boss, work stalls — but it fails loudly, and someone comes to fix it. The real disaster is two bosses at once: the old one never actually died, it just went unheard, and the new one has already taken office. Two people writing in the same ledger at the same time can bill your payment twice, and afterwards nobody can tell which ledger to believe — both are internally consistent. This is the accident the whole chapter is built to prevent.
The chapter lays out several classic approaches, each a step past the last:
But the thing most worth remembering is none of the above. It is the seal: give each boss an official stamp engraved with their term number, and rule that documents count only if they bear the newest term. Now it no longer matters if the old boss wakes up still issuing orders — the stamp in their hand is last term's, so everything they stamp is void.
The real trade-off is not "which picking method is cleverest." It is two things: do not keep swapping (every swap stops everyone while the handover happens), and once you swap, the old boss must truly lose power. The first comes from "don't move unless something actually broke"; the second comes from that term-numbered seal.
The honest cost: no picking method can guarantee there is only ever one boss — the best any of them promises is "eventually only one is left, after a messy stretch." The safety net was never in the picking. It is in the stamping.
Picking a boss is easy; voiding the previous one is the hard part. So stop expecting the election itself to be both fast and correct — stamp every term with a number and make everyone honour only the newest one. Then even when you get it wrong and briefly have two bosses, the ledger stays intact.
Want the actual algorithms, message costs and diagrams? → Switch to the deep read
You think leader election is about "picking the fittest machine." What this chapter is really about is that election itself cannot guarantee a single leader at any instant. Electing a leader is an instance of consensus, and every algorithm engineers actually use is weaker and cheaper than consensus — it only promises to converge on one leader. Which pushes the real safety boundary somewhere else entirely: into stability (don't re-elect unless something truly broke) and epoch numbers (make the previous leader's writes fail).
2f+1 nodes tolerate f failures, and a majority can only ever exist in one partition — that is the root defence against two leaders.Third chapter of Part II, "Distributed Systems." It follows Chapter 9 on failure detection — the trigger for an election is "we've decided the old leader is dead," so the detector's false-positive rate is your re-election rate — and sets up Chapter 11 on replication (a leader is what makes single-point ordering possible) and Chapter 14 on consensus, where Raft and Multi-Paxos fold election into the algorithm itself. Real-world counterparts: the ZooKeeper leader, etcd's Raft leader, Kafka's controller and per-partition leaders, Kubernetes controllers racing for a Lease, and automated MySQL failover.
First, why insist on a leader at all? Because "have n nodes negotiate every operation" and "have one node assign the order" differ by an order of magnitude in cost: in a leaderless design every write runs a round of voting and waits for a majority — two or three round trips even inside one datacenter — whereas with a leader the client gets an ordered result in a single round trip. Ordering, uniqueness and conflict resolution all degrade from "things to negotiate" into "look it up in the leader's log."
What happens if you don't solve it? The two directions fail very asymmetrically.
No leader: it fails loudly. A three-node strongly consistent cluster whose leader dies and cannot be replaced is simply not writable — not slow, fully stalled. That election gap is the most visible line on your availability bill: etcd's default election timeout is 1 second, so from "the leader is gone" to "the new leader can work" takes at least a few hundred milliseconds to a couple of seconds, during which every write queues or errors out.
Two leaders: it fails silently. The old leader was merely misjudged — one long GC pause, one bout of cross-rack jitter — and has no idea it was deposed, so it keeps accepting writes while the new leader does too. Two internally consistent histories, with no automatic way to decide which is right: that is not slow recovery, it is permanent data corruption, usually ending in a human reconciling ledgers by hand.
So the real question in this chapter is not "which algorithm elects fastest." It is: given that the signal triggering an election is itself unreliable (Chapter 9 proved "slow" and "dead" are indistinguishable), how can an election mechanism that will misfire avoid corrupting data?
Strictly speaking, "everyone agrees X is the leader" is a consensus decision: a set of nodes agreeing on a value in a way that cannot later be overturned. Consensus costs something: at least two rounds of messages, a majority, and durable state. Almost every classic algorithm in this chapter deliberately dodges that cost — no majority, just local rules like "whoever has the biggest id" — which means they only promise eventual convergence on one leader, never that two never coexist along the way. Hold onto that and the rest becomes easy to judge: these algorithms are not competing on correctness, but on how many messages, how fast the handover, and how bad the mess can get.
Bully is where every variant starts: each node has a globally comparable unique id (its rank), and the highest-ranked live node is leader. Whoever notices the leader is gone sends ELECTION to every node ranked above it; any reply means someone bigger is alive, so it drops out; silence means it broadcasts "I am the leader."
Why design it this way? Because it needs no shared state and no durability — ids you can compare and messages that arrive are enough. The price is three blind spots:
O(n²) messages. Fine at twenty nodes; at two hundred a single false positive can kick off tens of thousands of messages.Next-In-Line Failover: the leader piggybacks a priority-ordered list of alternates on its heartbeats. When it dies, the first name simply takes over and the entire election round disappears — handover time shrinks from "one election" to "one timeout." The cost is blunt: the list was written while the leader was alive and may be stale, so you must be able to walk down it, falling back to a full election only when it runs out.
Candidate / Ordinary: only candidates may become leader; ordinary nodes just notice trouble and notify a candidate. Messages drop from O(n²) across everyone to O(k²) among candidates — with 5 candidates in a 200-node cluster, an election costs two orders of magnitude less. The cost is that the candidate set becomes a new single point: lose all 5 and the remaining 195 healthy machines cannot elect anyone.
Ring: nodes form a logical ring where each knows only its successor. The election message travels around it, appending each live node's id as it passes; by the time it returns to the origin the roster is complete, and the highest id on it becomes leader. The appeal is linear message cost and needing only "know your successor" worth of topology.
Invitation is the one genuine change of mind in the chapter. The others all strain to guarantee a single global leader; this one simply admits that multiple groups may exist. Each process starts as leader of its own group of one, processes invite each other in, groups merge, and one of the original group leaders carries on. A network partition stops being an anomaly: both sides form groups, keep working, and merge once connectivity returns.
The cost is that the hard part moves from election to merging — two groups each hold an independently written history, so who arbitrates the conflict? Precisely what CRDTs and eventual consistency handle in Chapter 11. The trade-off in one line: either sacrifice availability to keep a single leader, or sacrifice the single leader to keep availability and settle the bill at merge time.
When the book judges each algorithm, it keeps returning to one question: does it cause frequent re-elections? That is an accounting question. Every re-election means stopping writes, waiting for the new leader to catch its log up, and waiting for clients to reconnect and retry — a few hundred milliseconds to several seconds each time. A detector that misfires once a minute leaves the cluster permanently half-dead. Hence the first engineering rule: if the incumbent is still working, never re-elect (a stable leader).
This is also why Bully's blind spot is lethal: its rule is that the highest rank must lead, so that flaky top-ranked machine forces a re-election on every recovery. Real systems invert it: the incumbent keeps the job as long as it can renew.
The other damping trick is randomised timeouts. If every node times out at the same instant and campaigns at once, the votes split, nobody reaches a majority, and the whole thing repeats — a livelock. Add a little jitter to each node's waiting period and "who goes first" separates naturally.
None of the algorithms above can rule out this scene: the old leader only appeared dead (a five-second full GC is plenty), the new leader has taken office, and the old one wakes up still believing it leads, and writes. If election cannot prevent it, defend elsewhere — give every leadership term a monotonically increasing epoch, carry it on every write down to the storage layer, and have storage accept only the highest epoch it has seen.
This step swaps an impossible requirement — guarantee two leaders never coexist — for an achievable one: allow two leaders, but let only one change data. The old leader's write comes back rejected, which is how it learns it was deposed and steps down. Election provides liveness; the epoch provides safety. The book's full treatment of epochs waits for Chapter 14 — Paxos ballot numbers and Raft terms are doing exactly this job.
Compare them across first. What actually separates these is whether a partition produces two leaders, not how fast they are.
Table 1 · What each election approach costs
| Mechanism | Messages | Handover speed | Two leaders under partition? | Cost / who it suits |
|---|---|---|---|---|
| Bully | O(n²) worst case | one full election round | Yes: each side elects its own maximum | Simplest, no shared state; but ignores fitness, and a flapping top rank causes livelock. Small clusters only |
| Next-In-Line | ~0 (list rides heartbeats) | Fastest: one timeout | Yes | The list goes stale; must be walkable downwards. Suits clear primary/standby pairs chasing low RTO |
| Candidate / Ordinary | O(k²) for k candidates | one round, candidates only | Yes | The candidate set becomes a new single point. Suits hundreds of nodes |
| Ring | O(n) per lap | one lap, linear in n | Yes: two rings, two leaders | The ring must self-repair; topology upkeep is extra work. Suits stable membership |
| Invitation | higher at merge time | no global convergence needed; the group works at once | Allowed on purpose | Moves the problem to merge conflicts. Suits availability-first, eventually consistent systems |
| Built into consensus (Raft / Zab) | one round of majority voting | election-timeout scale; etcd defaults to 1s | No: a majority exists in only one partition | The minority partition cannot write at all; needs 2f+1 machines and durable state. What almost every strongly consistent system actually uses |
In an actual architecture decision the question is usually not "which algorithm" but "which layer owns the leader" — most teams should not implement election at all.
Table 2 · Three engineering routes to "who elects"
| Route | How | What you get | What you pay |
|---|---|---|---|
| Roll your own | Bully / Ring style, on heartbeats plus ids | No external dependency, little code | Safety is entirely yours: you must build epochs and fencing, or one partition means corruption |
| External lease | Race for a TTL key in ZooKeeper / etcd / a Kubernetes Lease; the winner leads and keeps renewing | Tens of lines of code; uniqueness backed by the external cluster's consensus, and expiry is automatic — nobody declares anyone dead | One more dependency that must stay up; handover time is pinned to the lease length (typically 10–15s); you still need fencing |
| Consensus with built-in election | Use a Raft / Multi-Paxos / Zab library or product | Election and replication share one term number, so safety is provable; you can add constraints like "log must be current to win" | Highest implementation and operational complexity; writes must cross a majority, so cross-region latency shows |
One rule you can take away directly: every irreversible action must carry the epoch to its executor — shifting traffic, deleting data, charging a card. An election only tells you "I am probably the leader"; the epoch is what says "I am demonstrably the current one."
In any architecture review or interview question about high availability, the second cut lands here (the first is failure detection). Upgrade "if the leader dies we elect a new one" into "incumbent renewal first, randomised timeouts to avoid split votes, candidates must have current logs, and the executor fences on epoch" and the answer is in a different class.
Naming real systems: ZooKeeper uses Zab, relying on transaction ids so the new leader's history is no older than anyone's; etcd uses Raft with a 100ms default heartbeat and a 1000ms election timeout; Kafka's controller was once elected via ZooKeeper and since KRaft uses its own Raft implementation, with partition leadership additionally requiring the new leader to be in the ISR (in-sync replica set); Kubernetes runs multiple controller replicas that race for a Lease object.
100ms heartbeat interval." and "By default, etcd uses a 1000ms election timeout," with the heartbeat anchored to the network — "normally around 0.5-1.5x the round-trip time" — while for intercontinental deployments "The upper limit of election timeout is 50000ms (50s)." The election timeout is not a free knob: it is simultaneously your RTO floor and your false-positive ceiling.etcd Documentation · Tuning · tuning.mdwal_fsync_duration_seconds at a p99 under 10ms and note that "If monitoring of the machine's CPU usage shows heavy utilization, there may not be enough compute capacity for etcd." What really causes a leader change is often a shared SSD, not a crash.etcd Documentation · FAQ · faq.md1. The core claim: electing a leader is consensus (swapping "n nodes negotiate every operation" for "one node orders them"), yet every algorithm engineers use is weaker and cheaper — promising only eventual convergence on one leader, never that two never coexist.
2. The two failure modes are wildly asymmetric: no leader is a loud stall (recoverable); two leaders are a silent fork (usually not automatically recoverable).
3. Bully: highest live rank leads, no shared state needed; three blind spots — ignores fitness, a flapping top rank livelocks, and O(n²) messages.
4. Two cheap optimisations: successor lists (handover costs one timeout) and candidate sets (messages drop to O(k²), at the price of a new single point).
5. Ring collects the roster around a lap — linear messages, but the ring needs upkeep; Invitation simply allows coexisting groups and merges later, trading the single leader for availability and settling up at merge time.
6. Stability is the through-line: re-election costs stopped writes, log catch-up and reconnects, hundreds of milliseconds to seconds each. The rule is never re-elect while the incumbent can renew, plus randomised timeouts to avoid split votes.
7. The safety boundary is outside the election: give each term a monotonic epoch and fence at the storage layer, converting "there must never be two leaders" into "there may be two, but only one can write."
8. Real systems: etcd and Kafka KRaft use Raft (100ms heartbeat, 1s election timeout), ZooKeeper uses Zab, Kubernetes races for a Lease and says outright that it does not fence; in practice re-elections are triggered by slow disks and CPU contention far more often than by crashes.