Leader election
Picking one machine to decide, and replacing it when it dies.
01The intuition
The problem it solves
A class is on a field trip with three teachers. Only one of them should count the students at each stop; if two count, they get different numbers and argue, and if none counts, a child is left behind. Before the trip they agree: Mr Rao counts. If Mr Rao is missing at a stop, the others need a rule to decide who takes over, and a way to make sure Mr Rao, when he reappears, does not start counting again at the same time.
Many systems have a job that exactly one machine should do: assign chunks to servers in a file system, hand out ranges in a sorted store, run the scheduler's poll loop, be the writer for a replicated database. Running it on two machines at once corrupts things; running it on none stops the system. Leader election is the rule for choosing the one machine, noticing when it dies, choosing another, and keeping the old one from interfering.
Build it one piece at a time
Step 1: a lock with a lease. Keep a small, highly available store (a consensus cell such as ZooKeeper, etcd or Chubby). Each candidate tries to create the key /leader with its own name. Exactly one create succeeds; that machine is leader. The key carries a lease: it disappears automatically unless the holder renews it every few seconds.
| Time | /leader key | Lease expires at | Leader |
|---|---|---|---|
| 0 s | A creates it | 10 s | A |
| 5 s | A renews | 15 s | A |
| 12 s | A crashed, no renewal | 15 s | A, as far as the store knows |
| 15 s | key expires; B creates it | 25 s | B |
Step 2: the gap, and why it exists. Between 12 s and 15 s nobody leads. Shortening the lease shortens the gap but makes a slow network look like a crash and causes needless failovers. Typical leases are 5 to 15 seconds; the gap is accepted.
Step 3: fence the old leader. At 14 s, A's machine recovers from a long pause (a garbage collection, a stalled disk) and continues as if it leads, writing to the shared data. Now A and B both act. The cure is a fencing token: every election increments a number stored with the key, and the leader includes it in every write to the resources it controls. A storage node that has seen token 8 from B rejects A's write carrying token 7. The old leader is not told to stop; it is made unable to do harm.
Step 4: watch rather than poll. Candidates do not hammer the store asking "is the key free". They register a watch on /leader and are notified when it vanishes. With a hundred candidates this turns a hundred polls a second into one notification per failover. To avoid a stampede when all hundred race to create the key, each creates a sequential node and the lowest number leads; the others watch only the node just below theirs.
Step 5: lead many things, not one. A sorted store has 10,000 tablets, each needing a leader. One global leader per tablet is too much coordination, so the design uses one elected master that assigns tablets to servers, and each assignment is itself a lease the server renews. The master's job is small and the data path does not touch it.
Why it works, with the numbers
The store's create-if-absent is atomic, so two candidates cannot both succeed; that is mutual exclusion. The lease bounds how long a dead leader blocks the system:
time without a leader ≤ lease length + election time ≈ 10 s + 1 s
and the fencing token makes the guarantee hold even when the old leader is alive but slow, which leases alone cannot do, because the old leader's clock may say the lease is still valid. The guarantee is: at most one leader is recognised by the resources at any time, and a new leader appears within the lease window of a failure. The failure modes are a leader that holds the lease but is not actually working (add health checks that make it step down), resources that do not check the token, and an unreachable store, which means no new leader can be elected while the current one may keep running on its lease.
The trade-off you must say out loud
Fast failover against false failovers, and the simplicity of one leader against its throughput limit. Say your lease length, that writes carry a fencing token, and what the system does during the leaderless gap (queue, reject, or serve reads only). The follow-up is "what if the election store itself is down", and the answer is that it is a consensus cell replicated across failure domains, and if it is unreachable the current leader keeps its lease until it expires and then everything pauses.
Where it shows up in the 100 Google problems
- Distributed file system: one master holds the namespace and chunk locations; its standby takes over through a lease, and chunk servers reject a stale master.
- Bigtable: a master elected through the lock service assigns tablets; tablet servers hold leases on their tablets.
- Distributed lock service: the service that everyone else uses to elect leaders, so it must be a consensus cell itself.