Consensus with Raft

A bank keeps your balance on five servers, so that losing one machine loses nothing. Now two requests arrive at once: "withdraw 80" and "withdraw 50", with 100 in the account. If two servers each accept a different one first, the copies disagree, and when one of them crashes, which balance was the real one?

Keeping copies is easy. Keeping them in agreement while machines crash, restart and lose touch with each other is the hard part, and it has a name: consensus. The usual trick is a replicated state machine. Every server holds the same log of commands and applies them in the same order, so they all compute the same state. Consensus is agreeing on that log, one entry at a time.

Raft (Ongaro and Ousterhout, 2014) is the consensus algorithm behind etcd, Consul, CockroachDB and many others. It was designed to be understood: one leader takes all the writes, and a simple majority rule makes sure nothing it has promised is ever lost.

leader, follower, candidate

The three roles. One leader takes client writes and sends them to the followers; a follower that stops hearing from a leader becomes a candidate and asks for votes.

term

A numbered period with at most one leader. Every message carries the sender's term, and a server that sees a higher term moves up to it.

election timeout

How long a follower waits without hearing from a leader before it starts an election. Each server picks its own at random, typically 150 to 300 ms.

log entry

One command, stored with the term in which a leader received it. Shown here as term:value, so 2:x is x, written in term 2.

majority

More than half of all the servers: 3 of 5, 2 of 3. Raft needs one to elect a leader and one to commit an entry.

committed

Safe for ever: stored on a majority under the rules below, so every future leader will have it. Only then is it applied and answered.

Raft divides time into terms, numbered 1, 2, 3, and so on. Each term starts with an election, and at most one leader can win it. Terms work like the Lamport clocks from the logical-clocks lesson: every request and reply carries the sender's term, and a server that sees a larger one adopts it. A leader that learns of a newer term knows it is out of date and steps down at once.

A leader sends AppendEntries messages, empty ones as heartbeats, often enough that no follower's election timer runs out. When one does, that follower becomes a candidate: it starts a new term, votes for itself and sends RequestVote to every other server. A server grants at most one vote per term, so two candidates can never both reach a majority in the same term. Because each server draws its timeout at random, one usually times out well before the rest and wins before anyone else starts.

That overlap is also why the cluster survives failures. With $2f + 1$ servers, any $f$ can crash and the other $f + 1$ are still a majority, able to elect a leader and commit. Three servers survive one failure, five survive two.

Start a fresh five-server cluster and press Next event one event at a time. Before each one, say whose election timer runs out first, whether each server grants its vote, and which vote makes the candidate leader.

Once elected, the leader takes every client write. It appends the command to its own log with its current term, then sends it to every follower in an AppendEntries message. Each message also names the entry just before the new ones, by index and term. A follower accepts only if its own log has that same entry there. That one check keeps the logs in step: if two logs hold an entry with the same index and term, they are identical up to that point.

When the check fails, the follower refuses, and the leader backs up: it moves its nextIndex for that follower one entry earlier and tries again, until it finds the last entry they agree on. From there it sends everything the follower is missing, and the follower deletes any of its own entries that conflict.

Votes have a second rule, and it is what keeps committed entries safe. A server refuses a candidate whose log is less up to date than its own: compare the terms of the last entries, and if those are equal, the longer log wins. A candidate missing a committed entry can't collect a majority, because a majority holds that entry.

Now break the network. A partition splits the servers into groups that can't reach each other. Raft promises nothing to the side without a majority; it only promises that that side can't do damage.

There is one more subtlety, and it is the one most explanations get wrong. A leader counts how many servers store each entry and marks it committed once a majority do, but only for entries from its own current term. An entry left by an earlier leader is not committed just because it reaches a majority. The paper's Figure 8 shows why. A leader of term 2 gets an entry onto two of five servers and crashes. Another server is elected in term 3 and takes a different entry at that index, then crashes in turn. The first server comes back, wins term 4 and copies its term 2 entry onto a third server, a majority. If it counted that as committed and then crashed, the term 3 server could still win an election, because its last entry, from term 3, is newer than theirs, and it would overwrite the "committed" entry. So older entries commit only indirectly: once an entry from the leader's current term is on a majority, everything before it in the log is committed too. Real implementations append an empty no-op entry at the start of each term to get there quickly.

Raft has limits worth knowing. It assumes servers crash or fall silent but never lie: a server that sends wrong messages on purpose, a Byzantine fault, needs heavier protocols. And when no majority can talk to each other, Raft stops taking writes rather than risk two answers. That is the consistency side of the CAP trade-off: during a partition it gives up availability on the minority side to stay correct.

• Consensus means agreeing on one log; replicated state machines apply it in the same order on every server.
• Raft elects one leader per term with randomised timeouts and one vote per term; higher terms always win, so stale leaders step down.
• The leader replicates its log with AppendEntries, which checks the previous entry's index and term; on a mismatch it backs up nextIndex until the logs agree.
• Voters refuse candidates with less up-to-date logs, so every leader already holds every committed entry.
• An entry commits once the leader has it on a majority and it is from the leader's own term; older entries commit along with it.
• With $2f + 1$ servers Raft survives $f$ failures; a side without a majority stops rather than disagree.