System Design HLD-08.05
Quorums and leader election
Why majorities always overlap, how a majority vote elects exactly one leader per term, leases, and election as a service from ZooKeeper and etcd.
The big idea
Many systems need exactly one node in charge: one database leader taking writes, one scheduler assigning jobs, one primary per shard. Choosing it is easy when everything works. It is hard when the network splits and nodes cannot tell whether the current leader is dead or just unreachable. If each side of a partition picks its own leader, you get split brain and conflicting writes.
The core trick is the majority quorumAny group containing more than half of the nodes in a cluster.. Any two groups that each contain more than half of the nodes must share at least one node. So if becoming leader requires votes from a majority, and each node votes at most once per election round, two leaders can never be elected in the same round. A minority, cut off by a partition, can never elect one at all.
Think of a club of five members electing a president. Winning needs three votes, and everyone votes once. Two candidates cannot both get three votes, because there are only five votes to go around.
How it works
Step 1: Majorities overlap
from itertools import combinations
nodes = range(1, 6) # a 5-node cluster
majorities = [set(c) for k in (3, 4, 5) for c in combinations(nodes, k)]
pairs = [(a, b) for a in majorities for b in majorities]
always_overlap = all(a & b for a, b in pairs)
print(f"{len(majorities)} possible majorities, {len(pairs)} pairs checked")
print("every two majorities share at least one node:", always_overlap)
# Why that matters: a node votes once per term, so two candidates can never both win.
votes_a, votes_b = {1, 2, 3}, {3, 4, 5}
print("candidate A's voters", votes_a, "and B's", votes_b, "overlap in", votes_a & votes_b,
"-> node 3 would have to vote twice in one term, which Raft forbids")
# Fault tolerance: how many nodes can fail and still leave a majority?
for n in (3, 4, 5, 6, 7):
print(f"{n} nodes: majority {n // 2 + 1}, tolerates {n - (n // 2 + 1)} failure(s)")Output
16 possible majorities, 256 pairs checked
every two majorities share at least one node: True
candidate A's voters {1, 2, 3} and B's {3, 4, 5} overlap in {3} -> node 3 would have to vote twice in one term, which Raft forbids
3 nodes: majority 2, tolerates 1 failure(s)
4 nodes: majority 3, tolerates 1 failure(s)
5 nodes: majority 3, tolerates 2 failure(s)
6 nodes: majority 4, tolerates 2 failure(s)
7 nodes: majority 4, tolerates 3 failure(s) Every pair among the 16 possible majorities of a five-node cluster overlaps. That overlap node is the referee: it can only vote for one candidate per term. The table also shows why clusters have odd sizes. Four nodes tolerate one failure, the same as three, while costing more; five tolerate two.
Step 2: Terms and votes
Elections are numbered by a monotonically increasing termAn election epoch: a number that increases with every election; messages from older terms are ignored, so stale leaders are recognized and rejected. (also called epoch or generation). A node that notices the leader is silent starts a new term and asks for votes. A node votes for at most one candidate per term. Any node that sees a higher term immediately accepts it and steps down if it was leader. So an old leader returning from a partition learns it has been replaced the moment it talks to anyone in the new term.
Step 3: Leases
Even with one elected leader, an old leader that was paused or partitioned may still believe it leads for a while. A leaseA time-limited grant of leadership or ownership that must be renewed before it expires. bounds that: the leader is only allowed to act for a fixed time (say 10 seconds) unless it renews its lease with a majority. Followers promise not to elect anyone new until the lease could have expired. Leases depend on clocks advancing at roughly the same rate, so they are combined with fencing ( Distributed locks and fencing tokens ) for safety.
Step 4: Do not build it yourself
Correct election is subtle, so most systems use a coordination service: ZooKeeper or etcd (which runs Raft, Consensus: Raft ). An application creates an ephemeral key or node tied to its session; whoever holds it is leader, and if its session dies, the key disappears and others are notified to take over. Kubernetes controllers use leader election leases stored in etcd in exactly this way.
Going deeper
Election timeouts and flapping
Candidates use randomized timeouts so they rarely start elections at the same moment and split the vote. Timeouts must be well above normal network and pause times; otherwise a busy leader is repeatedly voted out, and the cluster spends its time electing instead of working.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Majority election (3 or 5 nodes) | Exactly one leader per term, safe under partitions | The minority side cannot elect or serve; needs an odd-sized cluster |
| Coordination service (etcd, ZooKeeper) | Proven election and leases as a building block | Another critical system to operate |
| Manual failover | Very simple setups where minutes of downtime are acceptable | Speed of recovery and human error at 3 a.m. |
Common mistakes
- Running an even number of nodes and expecting better fault tolerance.
- Letting any node become leader when it cannot see the old one, causing split brain.
- Election timeouts shorter than garbage collection pauses.
- Implementing your own election instead of using a proven library or service.
Check yourself
-
Why can't two leaders be elected in the same term with majority voting?
Show answer
B. Any two majorities share a node, and each node votes once per term The shared node would have to vote for both candidates, which it may not.
-
How many failures does a 5-node majority-based cluster tolerate?
Show answer
B. 2 A majority is 3, so 2 nodes can fail and 3 remain.
-
A partitioned old leader rejoins. How does it learn it has been replaced?
Show answer
B. It sees a higher term from other nodes and steps down Higher terms always win; seeing one makes it a follower.
-
What does a leader lease bound?
Show answer
B. How long a leader may act without renewing with a majority After the lease, it must renew or stop acting as leader.
Recap
- Leadership needs exactly one leader, even during partitions.
- Any two majorities overlap, so majority voting elects at most one leader per term.
- Terms increase with every election; higher terms always win.
- Leases bound how long a leader may act without renewing.
- Use etcd, ZooKeeper or a Raft library rather than writing election yourself.