Consensus and leader election (Raft)

Consensus is getting several machines to agree on a value — such as who the leader is, or the order of operations — even when some of them fail.

Why it matters

Several machines need to agree, even when some crash or messages are delayed. If two of them both believe they're in charge, data gets corrupted.

The idea

Many systems need exactly one leader, or one agreed order of changes. Raft does this: nodes elect a leader by majority vote; the leader adds commands to its log and copies them to the others; an entry is committed once a majority has it. With 5 nodes, the cluster survives 2 failures. Tools like etcd and ZooKeeper give you this, so you don't build it yourself.

A committee that decides by majority vote. As long as most members are present, decisions stand, and two separate groups can never both be the majority.

A committee meets in one room. Machines talk over unreliable networks with delays, so Raft needs terms (numbered elections) and timeouts to stop two leaders acting at once.

How it works

  1. Every node starts as a follower. If a follower hears nothing from a leader for a random timeout (say 150–300 ms), it becomes a candidate.
  2. The candidate increases the term number and asks the others for their votes. Each node votes once per term.
  3. With votes from a majority, it becomes the leader and sends regular heartbeats.
  4. Clients send writes to the leader, which adds each one to its log and sends it to the followers.
  5. Once a majority have stored an entry, it's committed and applied, and the leader tells the followers.
  6. If the leader fails, the heartbeats stop, a new election begins, and the new leader's log becomes the reference.

Example

Kubernetes stores its cluster state in etcd, which uses Raft. A 3-node etcd cluster keeps working if 1 node fails.

Key points

Common mistakes

Not true: 4 nodes: one more failure survived than with 3 nodes.
In fact: A majority of 4 is 3, so 4 nodes survive only 1 failure, the same as 3 nodes. That is why clusters use odd sizes such as 3 or 5.

Not true: Partition: the smaller side keeps accepting writes.
In fact: Only the side with a majority can elect a leader and accept writes. That rule is what stops two leaders (split brain).

In the interview

Where we need a single leader or a distributed lock, I'd rely on a consensus system like etcd or ZooKeeper. It uses Raft or a similar protocol, so a majority must agree and the cluster survives the failure of a minority of nodes.

Part of Unit 4: Distributed systems and security in the free System Design course.