Raft leader election
On the roadmap:Advanced · step 4: Distributed systems
Nodes elect a leader by majority vote with random timers. A crashed leader is replaced, and without a majority nobody can lead.
In plain words
A group of servers needs exactly one leader. Each waits a random time without hearing from a leader, then asks the others to vote for it. Whoever gets more than half of all the votes leads, and keeps the rest calm by sending regular heartbeats. If the leader disappears, the first timer to run out starts a new election.
Why it matters
Many systems need one machine to decide: who owns a job, who takes the writes. Choosing by majority vote means the cluster always agrees on one leader, survives the loss of a minority of machines, and cannot split into two leaders that both think they are in charge.
Where you meet it
- etcd, the store behind Kubernetes, which runs Raft
- Consul servers, which use Raft to elect a leader and agree on changes
- Replicated databases and coordination services that need one agreed leader
You will be able to
- Explain terms, votes and why a majority is required
- See why random timers usually avoid two candidates at the same moment
- Say why five nodes survive two failures but not three
In interviews
Leader election and consensus come up in 'design a distributed lock', 'design a key-value store' and replication questions.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Nodes with a role (follower, candidate, leader), a term and a random election timer
- A leader's heartbeat that resets everyone's timer
- A timeout that makes a node a candidate for a new term and ask for votes
- A leader only when more than half of all the nodes vote for it
export type Role = "follower" | "candidate" | "leader";
export type Node = { id: number; role: Role; term: number; votedFor: number | null; timer: number; alive: boolean };
/** A small seeded random generator, so every run is the same. */
export function rng(seed: number) {
return () => {
seed = (seed + 0x6d2b79f5) | 0;
let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
/** Leader election in the style of Raft, without the log. Messages arrive instantly, so one tick is one moment of time. */
export class RaftCluster {
nodes: Node[];
private rand: () => number;
constructor(size = 5, seed = 1, private minTimer = 5, private maxTimer = 10) {
this.rand = rng(seed);
this.nodes = Array.from({ length: size }, (_, id) => ({ id, role: "follower", term: 0, votedFor: null, timer: this.pick(), alive: true }));
}
/** Each node waits a different, random time, so usually one of them asks for votes first. */
private pick(): number { return this.minTimer + Math.floor(this.rand() * (this.maxTimer - this.minTimer + 1)); }
leader(): Node | null {
const ls = this.nodes.filter((n) => n.alive && n.role === "leader");
return ls.sort((a, b) => b.term - a.term)[0] ?? null;
}
crash(id: number): void { this.nodes[id].alive = false; }
restart(id: number): void { const n = this.nodes[id]; n.alive = true; n.role = "follower"; n.timer = this.pick(); }
tick(): void {
const up = this.nodes.filter((n) => n.alive);
// a leader's heartbeat tells everyone with an older term to follow it, and resets their timers
for (const l of up.filter((n) => n.role === "leader")) {
for (const p of up) {
if (p === l) continue;
if (p.term > l.term) { l.role = "follower"; l.term = p.term; l.votedFor = null; break; } // someone is further ahead: step down
if (p.term < l.term) { p.term = l.term; p.votedFor = null; }
p.role = "follower"; p.timer = this.pick();
}
}
// everyone else counts down, and a timer that runs out starts an election
for (const n of up) {
if (n.role === "leader") continue;
if (--n.timer <= 0) this.elect(n);
}
}
private elect(c: Node): void {
c.role = "candidate"; c.term++; c.votedFor = c.id; c.timer = this.pick();
let votes = 1;
for (const p of this.nodes.filter((n) => n.alive && n !== c)) {
if (p.term < c.term) { p.term = c.term; p.votedFor = c.id; p.role = "follower"; p.timer = this.pick(); votes++; } // a newer term: vote for the first candidate who asks
}
if (votes > this.nodes.length / 2) c.role = "leader"; // needs more than half of ALL nodes, alive or not
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints raft-leader-election ok when everything passes. You need Node.js installed.
mkdir raft-leader-election && cd raft-leader-election
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Real Raft adds a log. A candidate can win only if its log is at least as up to date as its voters', so a decision that was committed is never lost in an election.
- Messages take time and can be lost, so two candidates can split the vote. Random timers make a repeat unlikely, and a new term starts when it happens.
- Timers are chosen to be much longer than a network round trip, a few hundred milliseconds in typical settings, and heartbeats are far more frequent.
- Clusters usually have three or five nodes: a majority of 3 is 2 and a majority of 5 is 3, and an odd size gives the same fault tolerance with fewer machines.
Ways to choose a leader
| How it decides | Survives a minority failing? | Main risk | Pick it when | |
|---|---|---|---|---|
| Raft election | A majority vote in numbered terms | Yes | More nodes and messages | You need one trusted leader |
| Highest id wins (bully) | The highest id that is alive | Often, but a split network can create two leaders | Two leaders at once | The network is small and reliable |
| Lease from a coordination service | Whoever holds a time-limited lease | Yes, if the service does | The service becomes the dependency | You already run etcd or ZooKeeper |
| Fixed leader | A person or a setting picks it | No automatic failover | Downtime until someone acts | A tiny system |
What it cannot do
It needs a majority
With five nodes, three must be reachable. If two are cut off from the other three, only the three can elect a leader.
Elections pause the service
While nodes wait for timers and vote, there is no leader and writes stop for a moment.
It depends on timing
Timers that are too short cause needless elections. Too long makes failover slow.
This lab has no log
It shows only the election. Agreeing on what was decided is the log replication half of Raft.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add message delays so two candidates can split the vote and a new election has to start
- Vote only for a candidate whose log is at least as up to date as yours
- Add log replication so the leader's decisions are copied to the followers