Raft: Consensus Explained by Getting It Wrong First

Five people are keeping a shared diary. Everyone must end up with exactly the same entries, in exactly the same order. People occasionally fall asleep mid-sentence, wake up hours later with no idea what they missed, or get locked in a room where they cannot hear anyone else.

Write down the rules that guarantee everybody still ends up with an identical diary.

That is consensus, and it is much harder than it sounds. It sits inside every system that promises your data is really saved — the coordination services behind Kubernetes, the databases that survive a machine dying, the systems that decide which server is in charge.

Paxos solved it correctly in 1989 and has been famously baffling ever since. Diego Ongaro and John Ousterhout at Stanford observed that a correct algorithm nobody can implement confidently is only half a solution — and designed for understandability as an explicit goal.

Their paper is called In Search of an Understandable Consensus Algorithm, from USENIX ATC 2014. The best way to see why Raft looks the way it does is to try designing it yourself and watch each obvious idea fail.

1. First try: tell everybody, wait for everybody

Send every diary entry to all five people. Wait for all five to confirm.

Correct, and useless. You have made things worse than one person keeping a diary — five people who must all respond fail more often than one, so you have added delay and subtracted reliability. Any single nap stops everything.

The fix is a majority. Require three of five to confirm, and the system survives two people being asleep.

Why a majority specifically? Because any two majorities of the same group must share at least one member. Three from five, and another three from five — they overlap. So a decision made by one majority cannot be forgotten by a later one, because somebody in the second group was also in the first and remembers.

Everything else in Raft is machinery for exploiting that overlap correctly.

2. Second try: anyone can write

Let any of the five accept an entry and pass it around.

This breaks immediately. Two people write different entries at the same time. Each convinces a different majority. Now there are two versions of the diary claiming to be the truth, and no way to reconcile them without throwing away somebody's confirmed work.

Raft's answer is decisive, and it is the single choice that makes the whole thing comprehensible: one leader at a time. All writes go through the leader. The leader decides the order. Everyone else copies.

This trades some theoretical elegance for an enormous simplification. There is exactly one place where order is decided, so conflicting orders cannot arise.

3. Third try: vote for a leader

Everyone votes. Most votes wins.

This fails on the case that matters. The network splits in two — three people in one room, two in another, neither able to hear the other. Each side elects its own leader. Each accepts entries. Now you have two diaries again, which is precisely the thing consensus exists to prevent. Engineers call it split brain.

Raft closes this with two mechanisms working together.

Numbered terms. Time is divided into numbered periods, each with at most one leader. Every message carries its sender's number. Anyone who sees a higher number than their own immediately steps down and updates.

This is elegant: an old leader who was cut off and comes back discovers they are stale on their very first exchange, and steps aside. No special reconciliation logic needed.

Majority votes. A candidate needs more than half the group, and each person votes at most once per period. Since two majorities must overlap, two candidates cannot both win the same period.

And the smaller side of a split can hold an election all it likes — it simply cannot reach a majority, so it elects nobody and correctly becomes unavailable rather than incorrectly available.

4. Fourth try: elections that never end

If everyone starts an election the moment they stop hearing from the leader, all five become candidates at once, split the vote evenly, and nobody wins. Then they all try again, simultaneously, forever.

Raft's answer is almost embarrassingly simple: wait a random amount of time first. Each server picks a random delay in a range — typically 150 to 300 milliseconds — before starting an election. One almost always wakes first, asks for votes, and wins before the others stir.

That is not a proof. It is a probability argument, and it works reliably in practice. It is also a good example of the paper's philosophy: a simple mechanism that is easy to reason about, chosen over a cleverer one that is not.

5. The three states

Every server is in exactly one of three states, and that is the whole state machine:

• Follower — passive. Answers the leader and any candidates. Everyone starts here.
• Candidate — has stopped hearing from a leader and is asking for votes.
• Leader — handles all requests and pushes entries to everyone else.

A follower who stops hearing heartbeats becomes a candidate. A candidate who wins becomes leader. Anyone who sees a higher term number drops back to follower. That is the entire lifecycle.

The paper splits the problem into three parts and handles them separately — leader election, log replication, and safety — and that decomposition is much of why it is followable.

6. Copying entries, and the trick that keeps them identical

Each diary entry records what happened, its position in the list, and which term it was created in. The leader writes it down, then sends it to everyone.

The mechanism that keeps every copy identical is a small check with a large consequence. Every message includes the position and term of the entry immediately before the new ones. A follower refuses the message unless their own diary has a matching entry at that position.

From that one rule follows the Log Matching Property: if two diaries agree on any single entry, they agree on everything before it too.

That is a lovely result. Checking one position proves agreement on the entire history, and it means the leader never has to compare whole diaries.

When a follower refuses, the leader steps its guess back one position and tries again, walking backwards until it finds the last point of agreement — then overwrites everything after. Followers do not negotiate. The leader's diary is authoritative.

An entry is committed once a majority have stored it. At that point it is permanent, and the leader mentions how far along it is in later messages so everyone else knows it is safe to act on.

7. The safety rule that is easy to miss

There is one more rule, and it is the one naive implementations get wrong.

Suppose the leader gets an entry onto a majority, so it is committed, and then crashes. Somebody who was not in that majority — and so does not have the entry — becomes a candidate. If they won, they would overwrite committed data.

Raft prevents it in the voting rule: refuse your vote to any candidate whose diary is less up to date than yours.

Now trace the logic. The committed entry is on a majority. A winning candidate needs a majority. Those two majorities must overlap. That overlapping person has the entry and will refuse to vote for a candidate missing it.

So a candidate missing committed data cannot win. The overlap property from step one, doing its job again.

8. The parts the summary skips

Snapshots. A diary that only grows eventually fills the disk and makes restarting take forever. So servers periodically save a summary of the current state and throw away the entries before it. A follower who is too far behind gets sent the summary rather than ten million entries.

Changing the group. Adding or removing a server changes what "a majority" means — and switching straight from one definition to the other risks a moment where two different majorities exist, which is the split-brain problem wearing a disguise. Raft handles it with a transitional period requiring majorities of both the old and new groups, or more commonly in practice by changing one server at a time, which cannot create two disjoint majorities.

Reading. Reads seem obviously safe from the leader — but a leader who has been cut off and does not yet know they have been replaced would hand you stale data. Real systems confirm they are still the leader before answering, and this is a routine source of bugs in reimplementations.

9. Why understandability was the right goal

Raft is not faster than Paxos. It does not survive more failures. It offers the same guarantees.

Its advantage is entirely that engineers can hold it in their heads — and that turned out to matter more than any performance property, because a consensus implementation whose maintainers do not fully understand it is a liability no matter how elegant.

The paper backed the claim with an unusual experiment: they taught both algorithms to students and tested them. Raft scored significantly higher.

Treating comprehensibility as a measurable design goal, rather than a matter of taste, is the most transferable thing about the work. It is also why essentially every system built since 2014 chose Raft. The correctness was available in 1989. The ability to implement it confidently was not.

Sources

• Ongaro, Ousterhout — In Search of an Understandable Consensus Algorithm, USENIX ATC 2014
• Ongaro — Consensus: Bridging Theory and Practice, Stanford PhD thesis, 2014
• Lamport — The Part-Time Parliament, ACM TOCS, 1998