Certainty in uncertainty: how randomness makes Raft reliable

We left off with three machines that need to agree on one leader and one order of writes, while any of them might die at any second, and none of them can tell "dead" from "busy" from "I can't reach you right now".

That's the consensus problem. Raft is one way out of it. No paper jargon here, I'll introduce the words as we hit them, in the order I actually understood them, which was nothing like the order the paper presents them.

Three friends and one notebook

Picture three friends who have to keep identical notebooks. Not similar. Identical. Same entries, same order, page for page.

That's all Raft is trying to do. It gives you a log every node agrees on, and that sounds underwhelming until you notice what falls out of it: if everyone starts blank and applies the same commands in the same order, everyone ends up in the same state. Pour that log into a hashmap and you've got a replicated key-value store. Apply the same log to a different state machine and you replicate that system's state instead. BeeDB pours it into a memcached-style cache.

So: how do three friends keep identical notebooks when any of them can walk out of the room?

The first idea, and why it breaks

Everyone lands on the same first idea. One friend writes, the others copy. Fine.

But when does the writer get to say "it's safely written"?

Maybe when everyone has confirmed. Except now you're as slow as the slowest friend. And if that friend has gone home, you're not slow, you're stopped: one person on holiday and the whole system stops accepting writes.

And there's a trickier version. The friend is sitting right there, perfectly fine, writing everything down, but their replies never reach you. From where you're sitting, that looks exactly like a friend who has left the room. You cannot tell "gone" from "can't hear me", and that ambiguity is most of what makes this hard.

Then the real question: what if the writer dies? Who notices, who takes over, and how do you know the new writer isn't missing pages the old one already promised were safe?

Raft answers all of that with one idea.

Majority

Don't wait for everyone. Wait for a majority.

A majority is floor(n/2) + 1, which is what integer division gives you anyway: three of five, four of six, four of seven. Watch the even case, because six nodes needs four votes, not three.

So the leader sends the write to everybody and waits for the fastest majority to answer. The slowest node never holds anything up. One dead node out of three changes nothing at all. A cluster of n survives (n-1)/2 failures: three tolerate one, five tolerate two.

Lose more than that and writes stop. That's not a bug, that's the promise. BeeDB would rather refuse your write than accept one it can't stand behind.

And once a majority of the nodes have it on disk, the write is committed. That word carries all the weight in this post. A write that hasn't reached a majority can still vanish, and that's allowed, because nobody was promised anything yet.

One refinement, because this is the sentence people repeat loosely. A leader commits an entry this way only when the entry belongs to its own term. Entries left over from an earlier term are not committed just by counting copies; they become committed along with the first current-term entry that commits. Raft is strict about this, and Figure 8 of the Raft paper shows what goes wrong otherwise.

A committed write cannot be lost. Not "probably not lost": the voting rule below is what turns that into a guarantee.

Why a committed write survives the leader dying

Three nodes: the leader L, and followers F1 and F2.

A write reaches L and F1. That's two out of three, so it's committed, so the client is told STORED. Then L dies.

F2 never saw that write. Can F2 take over and wipe it out?

No, and the rule that saves you is small: a node only votes for a candidate whose log is at least as up to date as its own.

"Up to date" has a precise meaning here, and it is not "longer". Compare the last entry in each log: the one with the higher term is more up to date, and only when those terms are equal does the longer log win. A log with more entries in it can still be behind, if its last entry came from an older term.

F2 asks F1 for a vote. F1 is holding an entry F2 has never heard of, so F1 says no. F2 needs two votes out of three, and the dead leader isn't voting, so F2 is stuck. F1 becomes leader instead, and F1 has the write.

That isn't luck, it's arithmetic. A committed write sits on a majority. A winner needs votes from a majority. Any two majorities share at least one node. That shared node has the write, and it won't vote for anyone who's missing it.

Now flip it. Five nodes, and a write reaches the leader and F1 only, two out of five, not a majority, not committed. The leader dies, and F2, F3 and F4 elect one of themselves without ever asking F1. In that election the write is gone: the winner never had it, and its own entries take that slot. A different election could have gone the other way, with F1 winning and the entry surviving. Uncommitted means undetermined. Either way it is allowed, because nobody was ever told it was safe.

Terms: elections have numbers

Think about an election in a democracy. The old leader's time is up, candidates file their papers, somebody wins, and that's a new term with a number on it.

Same word, same idea. A term is one round of "who's in charge", the numbers only ever go up, and there's at most one leader per term. No double-engine sarkaar.

At most one, mind you, not exactly one. Sometimes a term produces no leader at all and everyone tries again with the next number.

Those numbers do more work than they look like they do. Every message carries one. A node sitting in term 4 that hears term 7 knows immediately that it's been asleep: it jumps to 7, forgets the old leader, and follows the new reality. And when an old leader comes back from the dead still convinced it's in charge, the first reply it gets tells it the term is 7 now, and it steps down on the spot. One number, and stale leaders can't do any damage.

That's also why every node writes down its current term and its vote before replying. Restart without that and a node could vote twice in one election, and two leaders is exactly the disaster we're trying to avoid.

And now the dice

One thing is still missing. If the leader goes quiet, who decides it's time for an election?

Nobody decides. Every follower runs a timer, and every heartbeat from the leader resets it. If the timer ever runs out, that node stops waiting, bumps the term, and starts asking for votes.

Now imagine all three timers are the same length. All three fire together, all three campaign, all three split the vote, nobody wins. Then they do it again. And again.

So the timer is random. In BeeDB it's a fresh random value between a minimum and a maximum, picked every single time the timer resets, not once at startup. Someone wakes up first and usually wins before the others stir, and on the rare split vote everybody re-rolls and tries again.

Which is my favourite thing about this algorithm. The way you get three notebooks that match exactly, page for page, is by having each node roll dice. Said plainly: because every node picks its own timeout independently, they rarely campaign at the same instant, and one of them gets far enough ahead to win. Randomness is what makes them converge.

Next: what actually happens to one write, from your keyboard to the disk.