Pointer Walk

Leader Election with Raft

Five servers and no boss. Timers run out, a candidate asks for votes, and a majority decides who leads.

Distributed SystemsAdvanced12 min read

Why have a leader at all

Important data is kept on several servers, so that losing one does not lose the data. That raises a hard problem: the copies must stay the same. If two servers accept different changes at the same moment, which one is right?

The simplest answer is to put one server in charge. Every change goes to that server, the leader, which decides the order and tells the others, the followers, to copy it. One decision-maker means no disagreements.

Then the leader crashes. Now what?

Someone must take over, and the servers must agree on who, with nobody outside telling them, over a network where messages get delayed and lost. This is leader election. The best-known method is part of an algorithm called Raft.

Three roles

At any moment each server is one of:

  • Follower. Does what the leader says. Every server starts here.
  • Candidate. Thinks there is no leader and is asking for votes.
  • Leader. Handles all changes and regularly reminds everyone that it is alive.

How an election happens

  1. The leader sends heartbeats

    A small "I am still here" message to every follower, many times a second.

  2. Each follower runs a countdown

    Every heartbeat resets it. As long as the leader is alive, no countdown ever reaches zero.

  3. A countdown runs out

    That follower has heard nothing for too long. It assumes the leader is gone, becomes a candidate, votes for itself and asks everyone else for their vote.

  4. The others vote

    A server gives its vote to the first candidate that asks, and votes only once per election.

  5. A majority wins

    A candidate that collects votes from more than half of all servers becomes the leader and starts sending heartbeats.

Leader electionInteractive
A

follower · term 0

B

follower · term 0

C

follower · term 0

D

follower · term 0

E

follower · term 0

  • follower (bar = countdown)
  • candidate
  • leader
  • crashed

Start. Five servers start as followers. There is no leader. Each has a countdown of a different length, and nobody tells them what to do.

Tick
0
Term
0
Leader
none

Watch it twice. First there is no leader, C's countdown is shortest, and C wins. Then C crashes. Nobody announces it. The heartbeats simply stop, another countdown runs out, and a new leader is chosen by the servers that are left.

Two details that make it work

Countdowns of different lengths. If every server waited exactly the same time, they would all become candidates in the same instant, all vote for themselves, and nobody would win. So each server picks its countdown at random within a range, and picks again each time. Usually one runs out clearly first, and that server wins before the others even stir.

If two do tie and split the vote, nobody reaches a majority. Both wait a new random time and try again. The tie breaks within a round or two.

Terms. Elections are numbered. Each new election starts a new term: 1, 2, 3. Every message carries its sender's term number.

Example

The old leader wakes up

C was leader in term 1. It froze for a few seconds and the others elected A in term 2. Now C wakes up, still believing it is in charge, and sends a heartbeat marked "term 1".

The others are on term 2. They reject it and reply with their term. C sees a higher number, realises it has been replaced, and steps down to follower. Nothing it tried to do as leader of term 1 is accepted.

Higher term always wins. That one rule clears up every "but I thought I was the leader" situation.

Why a majority

With five servers, a leader needs three votes. This number is not arbitrary. Two different candidates cannot both collect three votes out of five, because each server votes only once per term. So there can never be two leaders in the same term.

It also sets how much failure the group can survive:

ServersMajorityCan lose
321
532
743

As long as a majority is alive and can talk to each other, a leader can be elected. What happens to the minority when the network splits is the subject of Split Brain and Quorum.

Where you will meet it

Coordination services, distributed databases and the control plane of container orchestrators use Raft or a close relative to decide who is in charge and to keep their copies in agreement.

Key takeaways

  • A leader gives a group of servers one place where decisions are made.
  • Followers expect regular heartbeats. If they stop, a follower becomes a candidate and asks for votes.
  • A candidate needs votes from a majority of all servers to become leader.
  • Random countdown lengths prevent everyone from standing for election at once.
  • Numbered terms let servers recognise and reject an out-of-date leader.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress