Raft consensus algorithm: interactive leader election

Raft is a consensus algorithm that keeps a log identical on a cluster of servers, usually three or five, for as long as a majority of them is up. One server is elected leader. It takes every write, appends it to its log and copies it to the others, and the write is committed once a majority has it. When the leader fails, the others notice the missing heartbeats, and the first whose randomized election timer runs out asks for votes and becomes leader for a higher term.

The playground is a five-server cluster running ten times slower than real Raft. Watch the first election, send a write, then stop the leader and watch a new one take over. Stop three servers and see what stops working.

How Raft leader election works

1. Every server starts as a follower with a random election timeout, 150 to 300 ms in the Raft paper.
2. The leader sends heartbeats (empty AppendEntries messages) every 50 ms or so. Each one resets a follower’s timer.
3. When a follower’s timer runs out without hearing from a leader, it becomes a candidate: it increments its term, votes for itself and sends RequestVote to every other server.
4. Each server votes once per term, for the first candidate that asks, and only if the candidate’s log is at least as up to date as its own.
5. A candidate with votes from a majority becomes leader and starts sending heartbeats at once, which stops everyone else’s timers. If no one wins, the timers run out again and a new term begins.

The timeouts are random so that one server almost always times out first and wins before anyone else starts campaigning. When two do start together and split the vote, both time out again at different random moments, and the next term usually settles it.

Terms: Raft’s clock

A term is a number that goes up with every election, and each term has at most one leader. Every message carries the sender’s term. A server that sees a higher term than its own adopts it and becomes a follower, which is how a stale leader that was cut off finds out it has been replaced: its next message is answered with a newer term and it steps down. A message with an older term is ignored.

How Raft commits a write

The leader appends the write to its log and sends it to every follower in its next AppendEntries. Once a majority of servers, the leader included, has the entry, the leader marks it committed, applies it, and answers the client; the followers learn the new commit point from the next heartbeat. An entry on a majority survives any later election, because a candidate needs a majority of votes and only gets votes from servers whose logs are no newer than its own, so whoever wins already has every committed entry.

One subtle rule: a new leader never commits an entry from an earlier term just by counting copies. It commits a new entry from its own term, and the older ones before it commit with it. In the playground, stop the leader right after a write that has not reached a majority, restart everyone, and send another write to see it.

Why a majority, and how many servers

Any two majorities share at least one server, and that shared server is what stops two leaders being elected in the same term or a committed entry being lost. It is also why the minority side of a network partition can do nothing: it can neither elect a leader nor commit a write, while the majority side carries on. Writes cost one round trip to the fastest majority, so the servers usually sit in different zones of one region.

Where Raft is used

Raft and Paxos solve the same problem with the same guarantees. Raft was designed to be easier to understand and to implement, with one strong leader and leader election spelled out; Multi-Paxos is more flexible and the literature around it is older. ZooKeeper uses its own protocol, ZAB, which is similar in spirit.

Raft’s vote, in code

def on_request_vote(term, candidate, last_log_index, last_log_term):
    if term > self.current_term:              # a newer term: whatever we were, we follow now
        self.current_term, self.voted_for = term, None
        self.role = "follower"

    my_last_term = self.log[-1].term if self.log else 0
    up_to_date = (last_log_term, last_log_index) >= (my_last_term, len(self.log))

    if term == self.current_term and self.voted_for in (None, candidate) and up_to_date:
        self.voted_for = candidate            # written to disk before replying
        self.reset_election_timer()
        return (self.current_term, True)
    return (self.current_term, False)

The term and the vote must be written to disk before the reply is sent. Otherwise a server that crashes and restarts could vote twice in one term, and two leaders could be elected.

In a system design interview

Raft comes up wherever something must agree: a leader, a lock, configuration, or a strongly consistent store. Say it with the numbers: “Five replicas running Raft, as etcd does, spread over three zones; it survives two failures, a write commits after one round trip to a majority, and failover takes an election timeout plus a round trip, well under a second.” Expect the follow-ups: what the minority side of a partition can do (nothing), how reads stay correct (go through the leader, or confirm it is still leader before answering), and why not seven replicas (slower writes for little gain).

Read the how Raft works guide for log matching and snapshots, or watch a strong candidate design a key-value store.

Questions people ask