Scheduler 04: Leader Election

From Scratch · Distributed Scheduler. Follows Scheduler 03: Heap and Timing Wheel, which made “what fires next” cheap, and hands off to Scheduler 05: Dispatch Queue.

Before you start. This series builds a small copy of a job scheduler: a program whose whole purpose is to fire other programs at the right moment, the way a phone alarm goes off at 7am with nobody watching the clock by hand. So far, that scheduler runs on one machine, a single computer, and it can already hold thousands of pending jobs while always knowing which one fires next without checking every one of them. This lesson is about what happens the moment you stop trusting that one machine to stay up, and run three of it instead.

The idea in 30 seconds

A single scheduler is a single point of failure. Running three of them naively just makes every job fire three times instead of once.
Leader election picks one of the three to be in charge, and re-picks automatically the moment that one disappears.
The mechanism is a lease: a claim on being leader that expires unless you keep renewing it, so silence, not a health check, is what tells the room a leader is gone.
A lease cannot stop two machines from both believing they are in charge at once. A frozen machine can wake up long after its lease expired and still think it is holding the stick.
That situation is split-brain, and it cannot be prevented, only survived.
Fencing is how you survive it: every new lease comes with a rising token, and the room refuses any action carrying an old one, so only the current leader’s actions are ever obeyed.

Read the story · Skip to the numbers