Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Leader Election

Let one of many identical instances run the work that must not run twice, and move that job when it fails: candidates racing for one lease, the gap with no leader and the TTL that sets it, what a new leader does first, and handing over on purpose.

A player in two matches

How does one player end up in two matches at the same time? In an online chess service the answer was a change made for availability. The matchmaking service went from one instance to three, and all three ran the matchmaking loop: every second it reads the players waiting in the queue, pairs them by rating and writes the matches. Three loops reading the same queue made overlapping pairings.

Going back to one instance would trade the bug for an outage on the day that instance dies. What the service wants is all three instances running and only one of them running the loop, with that job moving to another instance when the one doing it fails. That is Leader Election: identical instances choose one to do the work that must not run concurrently on several of them (a matchmaking loop here, elsewhere a job scheduler or the owner of a partition), and choose again when it is gone. The other two keep serving the API and stand by.

Racing for one key

The instances do not vote among themselves. They share a coordination service, such as etcd, ZooKeeper or Consul, which runs consensus internally so that it gives one answer even when some of its own nodes fail; how it does that belongs to Consensus. Leadership is a single key in it, matchmaker/leader, held under a lease: a claim that lapses on its own unless the holder renews it, here after 10 seconds. Every candidate tries the same atomic create-if-absent on that key, and the store lets exactly one succeed. The winner renews the lease every few seconds and runs the loop; the others watch the key and try again the moment it disappears.

One leader holds the lease

mm-2 runs no loop. It watches the key and races for it the moment the key is gone.

The key's value names the holder, so anything that must reach the leader, an admin tool cancelling a match for instance, reads or watches the key instead of a configured address. How often to renew, and why a leader must stop acting by its own deadline rather than wait to be told, are the lease's own rules, taught in Distributed locks & leader election.

The seconds with no matchmaker

Leadership changes hands only when the key does. If the operating system kills mm-1, nobody deletes its key: the lease runs out on its own, up to 10 seconds after the last renewal, and only then do the others race for it. Add the election and whatever the new leader does before it is useful, and that is how long players sit in the queue with nobody pairing them. Deciding from silence whether a process is dead or only slow is a problem of its own, which Gossip Protocol covers for clusters that detect failures among peers; here the lease settles it by expiring.

So the TTL (the lease's time to live) is a dial, and both ends hurt. Ten seconds means each crash can leave the queue unpaired for ten seconds before the race even starts. Two seconds shortens that, but now any stall longer than two seconds, a garbage-collection pause, a slow disk on the coordination service, a congested link, costs a healthy leader its leadership. Each false failover is a full takeover with its own cost, and when stalls are frequent, leadership flaps from instance to instance. Set the TTL from the gap the work can tolerate and the longest stall you have measured, not from the smallest number that sounds safe.

What the new leader does first

Winning the key gives mm-2 the right to run the loop, not the loop's state. Whatever mm-1 held only in memory died with it, so a leader keeps the state of its work where the next leader can read it: the queue and the matches live in the database, and the first thing a new leader does is load them before it acts.

Takeover can also repeat work. mm-1 may have written a match and asked a game server to open its game, then died before recording that the game was open; mm-2 finds the match still without a game and asks again. Any failover can repeat work, so every step a leader takes must be safe to perform twice: the match is written only if both players are still waiting, and the request to open a game carries the match's id, so mm-2's repeat sends the same id and gets back the game the first one opened. Idempotency & exactly-once illusions covers making steps safe to repeat.

Leaving without the wait

Every deploy restarts the leader at some point, and a leader that simply exits leaves its key behind for up to a full TTL. A leader shutting down should instead stop its loop, let the pairing in progress finish, and then delete the key only if it still holds it (a conditional delete, or revoking its own lease), which the watching candidates see at once, so the handover takes one race instead of one lease. In that order: releasing the key while the loop still runs gives the service two matchmakers for a moment.

When the old leader was only paused

All of this assumes the old leader is gone. A leader that is only paused, by a long garbage-collection stop or a partition from the coordination service, can wake after its lease expired and keep writing matches alongside the new one: two leaders at once, split-brain, which the election cannot see from the inside. What refuses the stale leader's writes is a fencing token, a number that grows with every new lease, checked where the matches are written: the database refuses any write whose token is lower than one it has already accepted, so a new leader records its token there as soon as it takes over; a stale write that lands before that still passes. Distributed locks & leader election explains it.

Between two leaders

In the Leader Election challenge, the interesting part of the drawing is the time between two leaders, so that is where the detail goes. Identical Service candidates race for a lease kept in a Data Store; the leader renews it on a Scheduler / Timer, with the TTL written on that edge; a lease that lapses unrenewed leads to a new election. Then the part that is easiest to leave out: the old leader waking up. Whether you use a fencing token checked where the matches are written or a Split-Brain Resolver with its rule spelled out, a reader should be able to see why a stale leader's write never takes effect.

Practice this