system-design

Leader Election

Choosing one node to be in charge, and reliably choosing another when it dies. Simple to describe, and the place where split brain lives.

Prerequisites: Failure Modes, Coordination Services Time to read: ~20 minutes

The problem

Lots of things need exactly one node in charge:

A database primary accepting writes (two primaries = divergent data).
A scheduler running the nightly job (twenty schedulers = twenty invoices per customer).
A shard owner — exactly one node serves partition 7.
A coordinator managing cluster membership or rebalancing.

You need to elect one, and — the hard part — elect a new one when the current leader dies, without ever having two at once.

🚨 The difficulty follows directly from failure detection being impossible: you cannot distinguish “the leader is dead” from “the leader is slow” from “I can’t reach the leader.” Every leader election protocol is a way of making a safe decision despite that ambiguity.

Why not just… pick one?

“The node with the lowest IP is the leader.” Fine until it dies, and now nobody agrees on who’s next — because different nodes have different views of who’s alive.

“A human decides.” Works, but the recovery time is however long it takes to page someone. Your MTTR is now measured in tens of minutes.

“Everyone votes.” Better — this is the right shape. But two nodes on opposite sides of a network partition can each get votes from their side and both declare victory. Hence quorums.

Split brain: the failure you’re designing against

🚨 The thing that makes this hard.

5 nodes. Node 1 is leader. A network partition splits them 2 | 3.

Side A: nodes 1, 2       — node 1 still believes it is leader, keeps accepting writes
Side B: nodes 3, 4, 5    — can't reach node 1, elects node 3 as leader, accepts writes

Two leaders. Both accepting writes. The data diverges.
When the partition heals, which writes are real?

And it’s worse than it looks, because the old leader doesn’t know it’s been deposed. From its perspective, some peers stopped responding — a normal-looking condition.

Split brain has caused real, serious incidents, including GitHub’s 2018 outage where a 43-second partition caused divergence that took 24 hours to reconcile.

The defences

1. Quorum — only a majority can elect

The primary defence. A leader requires votes from a strict majority.

5 nodes, split 2 | 3:
  Side A (2 nodes): cannot reach 3 votes → NO leader → refuses writes
  Side B (3 nodes): reaches 3 votes → elects a leader → serves

📐 Because there can be only one majority in any partition, there can be only one leader. This is why quorum-based systems are safe, and why they’re CP — the minority side deliberately becomes unavailable rather than risk divergence.

🚨 This is also why cluster sizes are odd. 4 nodes need 3 for a majority — the same failure tolerance as 3 nodes, with more coordination overhead. Use 3 or 5.

2. Fencing tokens — assume the old leader will come back

Quorum stops a new leader emerging on the minority side. It doesn’t stop the old leader — which was partitioned, or paused by GC — from resuming and writing.

Node 1 is leader with epoch 5. It's partitioned.
Nodes 3,4,5 elect node 3 as leader with epoch 6.
Node 1's network recovers. It still thinks it's leader (epoch 5).
Node 1 writes to storage... which REJECTS it, because it has already seen epoch 6.

Every leadership term gets a monotonically increasing number (epoch, term, fence token, generation). Every write carries it. The resource being protected rejects anything with a stale number.

🚨 The critical detail: the protected resource must enforce the check. If storage happily accepts whatever it’s given, the token is decorative. This is the same problem as distributed locking, and it’s the most commonly missed part of both.

3. Leases — leadership expires

Leadership isn’t permanent; it’s a lease with a TTL that must be renewed.

Leader holds a lease for 10 seconds; renews every 3 seconds.
If it can't renew (partitioned, or dead), the lease expires and it MUST stop acting as leader.
Others wait for the full lease duration before electing a replacement.

✅ Self-healing: a dead leader’s lease expires without anyone intervening. 🚨 But leases depend on clocks, and clocks disagree (Time & Clocks). A leader whose clock runs slow may believe its lease is still valid after others have declared it expired. Leases reduce the split-brain window; they don’t eliminate it. You still need fencing.

4. STONITH

“Shoot The Other Node In The Head” — forcibly power off or isolate the old leader before promoting a new one, typically via out-of-band management (IPMI) or by revoking its storage access.

Blunt, effective, and used in traditional HA clusters. Requires infrastructure control you often don’t have in the cloud.

How it’s actually implemented

Using a coordination service (the usual answer)

Don’t implement consensus yourself. Use etcd, ZooKeeper, or Consul.

The ephemeral sequential node pattern:

/election/
  ├── node-0000000001   ← client A  (lowest = LEADER)
  ├── node-0000000002   ← client B  (watches node-1)
  └── node-0000000003   ← client C  (watches node-2)

Each candidate creates an ephemeral sequential node.
Lowest sequence number is leader.
Each other node watches its immediate predecessor — not the leader.
Leader dies → session expires → its node is auto-deleted → node-2 is notified → node-2 is now lowest → node-2 is leader.

🚨 Watching the predecessor rather than the leader is deliberate — it avoids the herd effect where all N-1 nodes wake simultaneously on a leadership change and stampede the coordination service. It’s a nice detail to mention.

With etcd it’s simpler, since it has leases and a campaign API built in:

session, _ := concurrency.NewSession(client, concurrency.WithTTL(10))
election := concurrency.NewElection(session, "/my-service/leader")
election.Campaign(ctx, myID)      // blocks until we become leader
// ... do leader work, checking session.Done() ...

On Kubernetes, use the built-in Lease object — the same mechanism Kubernetes’ own controllers use. 🎙️ “If we’re on Kubernetes I’d use a Lease rather than deploying ZooKeeper — leader election is already solved there.” That’s the answer most candidates miss.

The classic algorithms

Worth knowing by name:

Bully algorithm. The highest-ID reachable node wins. A node noticing the leader is gone challenges all higher IDs; if none respond, it declares itself leader. Simple, chatty, and prone to split brain because it has no quorum requirement.

Ring algorithm. Election messages circulate a logical ring, accumulating IDs; the highest wins. Fewer messages, but fragile to node failures during the election.

Raft’s election. The one used in practice: randomized election timeouts prevent nodes from campaigning simultaneously; a candidate needs a majority; terms (epochs) provide fencing. → Consensus

🚨 Bully and Ring are textbook algorithms, not production ones. If asked, note that they lack quorum requirements and are therefore unsafe under partition — that’s the insightful answer.

Designing with a leader

The leader is a bottleneck and a single point of failure. Every design with one should say how long a failover takes and what happens during it.

📐 The failover timeline, honestly:

Leader dies
  → 5–15 s   failure detection (lease expiry / missed heartbeats)
  → 1–5 s    election
  → 1–10 s   new leader warms up (cold caches, connection pools, state recovery)
  ─────────
  ~10–30 s of degraded or unavailable service

🚨 That warm-up phase is routinely forgotten and is often the largest component. A newly promoted database primary has an empty buffer pool and serves everything from disk for a while.

Shorten it with: pre-warmed standbys (a replica already caught up and holding a warm cache), and tuned but not-too-aggressive detection timeouts.

Clients must handle it: retry with backoff, re-resolve who the leader is (don’t cache it forever), and tolerate the window. A client that caches leader identity indefinitely keeps hammering a deposed node.

Avoiding leaders entirely

🚨 The best answer is often “don’t have one.” This is a strong thing to propose.

Partition the work instead. If each node owns a disjoint set of keys, no coordination is needed at all:

❌ One leader assigns work to 10 workers
✅ Worker N handles users where hash(user_id) % 10 == N

No election, no split brain, no failover window. Rebalancing on node failure is the only coordination needed, and consistent hashing handles it. → Consistent Hashing

Make operations idempotent so duplicate execution is harmless, removing the need for exactly-one semantics. → Idempotency

Use leaderless replication (Dynamo-style quorums) where any node accepts writes. → Quorums

Use a queue — many consumers, each message to one of them. The broker handles distribution; you need no leader.

🎙️ “Rather than electing a leader to distribute work, I’d partition by user ID so each worker owns a disjoint slice. That removes the election, the split-brain risk, and the failover window entirely — designing coordination away is more robust than implementing it correctly.”

⚖️ Trade-offs

Decision	Gain	Cost
Have a leader	Simple reasoning; a single ordering authority	Bottleneck, SPOF, failover window, split-brain risk
Quorum-based election	Provably at most one leader	Minority side unavailable; needs 3+ nodes
Fencing tokens	Old leader can’t corrupt data	The protected resource must enforce it
Leases	Self-healing; no manual intervention	Clock-dependent; reduces but doesn’t remove the window
Short detection timeout	Fast failover	False positives from GC pauses; disruptive churn
No leader (partitioned work)	No election, no split brain, no failover	Requires partitionable work; rebalancing complexity

In the real world

Kubernetes’ own controllers use leader election via Lease objects — kube-controller-manager and kube-scheduler run multiple replicas, only one active. It’s a good model to copy rather than reinvent.
GitHub’s 2018 incident is the canonical split-brain story: a 43-second network partition between datacenters triggered an automated failover, both sides accepted writes, and reconciling the divergence took 24 hours of degraded service. The partition lasted less than a minute; the consequences lasted a day — which is the argument for prioritizing failover correctness over failover speed.
Redis Sentinel provides leader election and automatic failover for Redis, and its documented caveats around split brain (and the min-replicas-to-write setting that mitigates it) are a good practical read on the topic.

🚨 Interview traps

Not mentioning split brain. It’s the central risk; raise it before the interviewer does.
Quorum without fencing. Quorum stops a new leader on the minority side; it doesn’t stop the old leader from resuming after a GC pause.
Even-numbered clusters. 4 nodes tolerate the same single failure as 3.
Ignoring the failover window, especially the warm-up portion.
Implementing consensus yourself. Use etcd/ZooKeeper/Raft library; say so.
Deploying ZooKeeper on Kubernetes when Lease objects already exist.
Not considering whether a leader is needed at all.

🎙️ Soundbites

“Election needs a quorum, so only a majority partition can elect — that’s what guarantees at most one leader. And fencing tokens, so the old leader can’t write after a GC pause when it comes back still believing it’s in charge.”
“Failover is roughly 10–30 seconds end to end, and the warm-up is usually the biggest part — a freshly promoted primary has a cold buffer pool. I’d keep a pre-warmed standby.”
“The fencing token only helps if the storage layer actually rejects stale epochs. If it accepts whatever it’s given, the token is decorative.”
“Three or five nodes, never four — four needs three for a majority, so it tolerates the same one failure as three but with more coordination.”
“I’d rather partition the work by key so each worker owns a disjoint slice. No election, no split brain, no failover window.”

🛠️ Try it

1. Build election with etcd. Three instances of a small program using etcd’s election API. Watch one become leader. Kill it. Time how long until another takes over — that number is your failover MTTR, and measuring it yourself is worth more than reading about it.

2. Cause split brain. Run a 3-node cluster in Docker. Use iptables (or docker network disconnect) to isolate the leader. Confirm the majority elects a new one. Then reconnect the old leader and observe what it does — does it step down cleanly, or does it try to act as leader?

3. Demonstrate the need for fencing. Have the leader hold a lease and write to a file. kill -STOP it for longer than the lease TTL, let another node take over, then kill -CONT it. The original writes with a stale epoch. Now add epoch checking on the file writer and watch the stale write get rejected.

4. Measure the warm-up cost. Promote a database replica to primary under load. Graph latency for the first two minutes. The recovery curve is the part people forget.

Check yourself

1. What is split brain and why does a quorum requirement prevent it?

Split brain is two nodes simultaneously believing they're the leader, both accepting writes, so the data diverges — typically after a network partition where the original leader can't be reached by the others but is still running. A quorum requirement prevents it because a leader must win votes from a strict majority, and **there can only be one majority in any partition of a set**. With 5 nodes split 2|3, the 2-node side cannot reach 3 votes, so it elects nobody and refuses writes; only the 3-node side has a leader. This is the CP choice — the minority side deliberately becomes unavailable rather than risk divergence.

2. Why aren't quorums alone sufficient? What else do you need?

Quorums prevent a *new* leader from being elected on the minority side, but they don't stop the *old* leader from continuing to act. A leader that was partitioned — or simply paused by a long GC — doesn't know it's been deposed; from its perspective some peers stopped responding, which looks normal. When it resumes, it writes as though still in charge. You need **fencing tokens**: each leadership term gets a monotonically increasing epoch number, every write carries it, and the protected resource rejects any write with an epoch lower than the highest it has seen. Critically, the *resource* must enforce this — if storage accepts whatever it's given, the token does nothing.

3. How long does leader failover actually take, and what dominates it?

Typically 10–30 seconds, in three phases: **failure detection** (5–15 s — waiting for a lease to expire or heartbeats to be missed, deliberately conservative to avoid false positives from GC pauses); **election** (1–5 s — a round of voting among a quorum); and **warm-up** (1–10 s or more — the new leader has cold caches, unwarmed connection pools, and may need to recover state). The warm-up is routinely forgotten and is often the largest component: a newly promoted database primary has an empty buffer pool and serves everything from disk until it fills. Mitigate with pre-warmed standbys that are already caught up and holding a warm cache.

4. Why do coordination clusters use odd numbers of nodes?

Because progress requires a strict majority, and adding an even-numbered member buys nothing. With 3 nodes you need 2 for a majority, tolerating 1 failure. With 4 you need 3 — still tolerating only 1 failure, but with an extra machine to run and one more node to convince on every write, making everything slower. With 5 you need 3, tolerating 2 failures. So the useful sizes are 3 and 5; beyond 5, write latency grows (more nodes must acknowledge) for negligible availability benefit.

5. When can you avoid leader election entirely, and why is that better?

When the work can be partitioned so each node owns a disjoint subset — worker N handles users where `hash(user_id) % N` matches, or each node owns specific shards. Then no node needs to coordinate with any other about who does what: there's no election, no split-brain risk, no failover window, and no coordination service dependency. Other leader-free approaches: making operations idempotent so duplicate execution is harmless; using a queue where the broker distributes messages to consumers; and leaderless quorum replication where any node accepts writes. It's better because eliminating a failure mode is more robust than handling it correctly — there's simply less that can go wrong.