Distributed systems · 14 min

Raft consensus

Five servers hold copies of the same settings. Raft’s four rules stop them from ever disagreeing, even when the network splits them in two.

A noodle chain runs 300 shops. Every morning, each shop’s till reads a few settings from a small config store: today’s menu, today’s drink, today’s dessert. If the store says menu = ramen, the kitchens make ramen.

One server would be a single point of failure, so the store keeps a copy on five servers, named tokyo, osaka, kyoto, nagoya and sapporo. Any of them can answer a till. Any of them can take a change from a manager.

That works fine for months. Then one morning a network cable fails.

Two managers, two menus

The failed cable cuts the five servers into two groups that can’t reach each other: kyoto and nagoya on one side, tokyo, osaka and sapporo on the other. Every server is still running. Each just thinks the others went quiet.

1. At 9:00 a manager connected to kyoto sets menu = sushi. kyoto saves it, copies it to nagoya, and replies “saved”.
2. At 9:05 another manager connected to tokyo sets menu = udon. tokyo saves it, copies it to osaka and sapporo, and replies “saved”.
3. For the next hour, shops that ask kyoto or nagoya buy fish. Shops that ask the other three make udon.
4. At 10:00 the cable is fixed. The servers compare notes and find two different menus. Whichever one they keep, a manager who was told “saved” has just lost their change.

This is split brain: one system has split into two halves, each sure it is the real one, each accepting changes the other never sees. Swap “menu” for “bank balance” and the same story makes money appear or vanish.

Raft is a set of four rules that makes this impossible. Each rule closes one hole. We will add them one at a time, then watch them work in the demo.

Rule 1: only one server takes writes

The first problem was that two servers both accepted changes. So pick one server to be the leader. Every write goes to the leader, which saves it and passes it on. The other servers are followers: they copy whatever the leader sends and never take writes themselves.

The leader passes writes on in a message called AppendEntries: “add these entries to your log”. It also sends one every 50 ms when there is nothing new, as a heartbeat that means “I’m still here”. Each follower runs a timer, set to a random length between 150 and 300 ms, that restarts whenever a heartbeat arrives.

If a follower’s timer runs out, it assumes the leader is gone. It becomes a candidate: it votes for itself and asks everyone else to vote for it.

The timers are random so that one follower usually runs out first and asks before anyone else wakes up. If every timer were exactly 200 ms, all the followers would become candidates at once and split the votes. Then no one wins; each waits for a new random timer and tries again in the next term.

Rule 2: a leader needs 3 votes out of 5

Rule 1 alone doesn’t help. In the split story, kyoto’s side and tokyo’s side would each elect a leader, and we are back to two menus.

So a candidate only becomes leader if a majority votes for it: more than half, which for 5 servers means 3. Each server gets one vote per term and gives it to the first candidate that asks. A candidate spends its vote on itself, so it can’t vote for anyone else in that term.

Why does that stop two leaders? Pick any two groups of 3 from the 5 servers. Take tokyo, osaka, kyoto and kyoto, nagoya, sapporo: kyoto is in both. Two groups of 3 need 6 places, and there are only 5 servers, so at least one server is always in both. The demo’s “See all the majorities” button lists all 10 possible groups if you want to check.

That shared server votes once per term. It can’t help two candidates win the same term, so there is at most one leader per term.

Now replay the split. kyoto and nagoya are only 2. They can never collect 3 votes, so their side can’t elect a new leader. tokyo, osaka and sapporo are 3, so their side can.

Rule 3: a write counts only when 3 servers have it

There is still a gap. Suppose kyoto was already the leader when the cable failed. It notices that tokyo, osaka and sapporo stopped replying, but a slow network and a dead server look exactly the same from where kyoto sits. So it carries on as leader and keeps taking writes.

Rule 3 fixes that. When the leader gets a write, it adds the entry to its log and sends it to the followers. The entry is committed only once 3 of the 5 logs hold it, counting the leader’s own. Only then does the leader tell the client, the manager who sent the write, “saved”.

kyoto can reach only nagoya, so a write sent to kyoto reaches 2 logs and stops there. It is never committed, and the manager never hears “saved”. The request hangs until it times out, instead of quietly succeeding on half the system. First, see rules 1 to 3 in action. The demo calls each server a node.

Look at column #2 in the log table. kyoto and nagoya hold “sushi” (SET menu = sushi), tagged t1. The other three hold “matcha” (SET drink = matcha), tagged t2. For a moment there really are two leaders, but only one of them can commit anything.

Now press Heal the network, then Next until every log matches. This is the opening story with an honest ending: the sushi manager got a timeout instead of a false “saved”, and every shop reads the same settings.

Rule 4: a server that missed a write can’t become leader

Look at the small t1 and t2 tags in the log table. Every entry is stamped with the term in which its leader wrote it. ramen is t1; matcha is t2. That stamp never changes, even when the server’s own term moves on.

Now the last hole. Carry on from the healed demo: every log is #1 ramen (t1), #2 matcha (t2), and tokyo leads term 2. A manager sets dessert = mochi. tokyo writes it as #3 (t2) and it reaches osaka and sapporo: 3 of 5, so it is committed. kyoto and nagoya haven’t got it yet. Then tokyo crashes.

If nagoya won the next election, it would lead with a log that has no #3. It would tell the followers to make their logs match its own, and a committed write would disappear.

So a server only votes for a candidate whose log is at least as up to date as its own. Compare the stamp on each log’s last entry: the higher term wins. If the stamps are equal, the longer log wins.

nagoya gets 2 votes and needs 3. It loses. Entry #3 lives on 3 servers, and any 3 voters include at least one of them, so a candidate without #3 always meets someone who refuses.

The four rules in a few lines

Notice that “3 of 5” appears twice: once to win a vote, once to commit a write.

on any message with a higher term than mine:
    adopt that term; become a follower

on my election timer running out:
    term += 1; become candidate; vote for myself
    ask every other server for a vote

on a vote request from candidate c:
    yes only if I haven't voted this term
        and c's log is at least as up to date as mine

on 3 of 5 votes:   become leader; heartbeat every 50 ms

on a client write, as leader:
    add it to my log; send AppendEntries
    once 3 of 5 logs hold it: committed, reply "saved"

What the rules cost you

In a split, the small side stops taking writes; kyoto’s sushi write just hung. Raft would rather say nothing than say something wrong. It keeps working as long as a majority is up and connected:

Where Raft runs

• etcd, the settings store every Kubernetes cluster keeps its state in.
• HashiCorp Consul, a service registry and settings store, uses it among its servers.
• Kafka, the message queue, uses it in KRaft mode to agree on which brokers own which data.
• CockroachDB, a distributed SQL database, runs a separate Raft group for each range of keys, so different ranges have different leaders.

Reach for it when copies must never disagree: settings, locks, or a database that promises a write is safe once acknowledged. If two halves briefly disagreeing is fine, as with view counts or a cache, waiting for a majority buys you nothing.