Raft and Consensus

Because a number on its own cannot be checked, repaired or compared. If two machines hold the number 120 and 90, there is no way to work out which one is right. If they hold lists of commands, you can put the lists side by side and find the exact entry where they stopped agreeing.

A list of changes has another property that matters more here. Two machines that hold the same list and apply it in the same order must arrive at the same answer, every time, with no coordination at the moment of asking. So the whole problem of keeping many machines in agreement collapses into one question: can we keep their logs identical? Everything else follows from that.

They are the commands in this course's toy service, and they mean what they look like. Starting from 100, a log of +50 then -30 gives 120. An x2 doubles the balance, which is not something a real bank does, but it is here on purpose: doubling is the command that makes order matter.

Real clusters copy real commands, and this is the honest shape of it. The program behind a shop's website copies "set row 91 to this value". A service that stores files copies "put this piece of the file at this position". The machinery in this course does not care what the commands mean, only that everybody holds the same ones in the same order.

Two is the worst number. When two machines disagree, there is no way to break the tie, and if one goes quiet the other cannot tell whether it has crashed or whether the wire has broken. Everything in this course rests on being able to gather more than half, and more than half of two is two, so a two-machine cluster stops working the moment anything goes wrong.

Odd numbers are used for that reason, and small odd numbers because every machine has to be sent every entry. Three survives one failure and five survives two, which is why five is the usual answer. A hundred machines would survive forty-nine failures and would be slow at everything, because more than half of a hundred is fifty-one replies to wait for.

A term is just a number that each machine keeps and never lowers. It goes up in one situation: a machine gives up waiting to hear from a leader and decides to try to become leader itself. It adds one to its own term and asks for votes in that new term. So terms count leadership attempts, not seconds, and a term can last a millisecond or a month.

Two rules make the number useful. A machine that hears a term higher than its own adopts that number at once and drops back to being a follower, because a higher term means it has missed something. A machine that hears a term lower than its own refuses the message, because the sender is out of date and does not know it yet.

Because a clock is measured and a term is counted. Measuring involves error: a machine's clock runs slightly fast or slow, gets corrected by a jump, or was set wrong when it started. Two machines a metre apart can disagree by a whole second, and neither can tell which of them is the odd one.

Counting has no error. Nothing is being read off a dial. The number was 4 and somebody added one, so it is 5, and every machine that hears about term 5 knows term 4 is over. The cost is that a term number says nothing about how long anything took. It only puts events in order, and order is all these rules need.

Every message carries one, in both directions, and the reply is where a leader learns it has been replaced. Suppose a leader from term 4 sends an append to a follower that has moved on to term 7. The follower refuses, and its refusal is stamped term 7. The old leader reads that number, adopts it, and steps down to being a follower before it can do any damage.

So one number does two jobs. On the way out it lets the receiver check whether the sender is current. On the way back it lets the sender find out that it is not. Nobody has to be told in words, and no machine has to keep a list of who has been leader.

The cluster in these labs runs on ticks instead of seconds. A tick is one step of the simulation: first every message that is due gets delivered, then every machine's countdown goes down by one. A message takes a whole number of ticks to travel.

The point of ticks is that you can take one at a time and see the exact run that a fast animation would have blurred past. Nothing is waiting on a real clock, so nothing happens between your presses. In a real cluster a tick would be a few tens of milliseconds. The timeouts here of six to fourteen ticks would be a couple of hundred milliseconds of silence before somebody gets suspicious.

Because two groups that are each more than half of the same cluster cannot exist. Any two majorities have to share at least one machine, and that shared machine only gives one vote per term. So if a majority elected somebody in term 9, no second machine can also collect a majority in term 9. One term, at most one leader, guaranteed by arithmetic rather than by hoping.

Lower the threshold and the guarantee is gone. In a cluster of five, two groups of two fit comfortably side by side with nothing shared, so both could crown a leader. The lab below does that sum for you and then really runs the cluster to check the sum was right.

The leader keeps talking. Every few ticks it sends an append to every follower, and when there is nothing new to send it sends one anyway with no entries in it. That empty append is called a heartbeat, and its only job is to arrive. Receiving it resets the follower's countdown, so a follower that keeps hearing from a leader never times out.

You can watch this in Lab 5's row of messages, once somebody has won. An append that says "nothing new" is a heartbeat. It also means silence is the signal for everything: a follower does not need to be told the leader has died, and could not be, because a dead machine sends nothing. It only needs to notice that the heartbeats stopped.

Random means unpredictable to the machines themselves, not unrepeatable. Each cluster in these labs is built from a starting number called a seed, and the same seed produces the same sequence of "random" waits every time. That is why Start over gives a different run: it moves to the next seed.

Repeatable randomness is how anybody debugs a system like this. A failure that only appears once is almost impossible to study. A failure you can reproduce by naming a number can be watched as many times as you need. Real clusters use a real random source, and the property that matters is the same in both cases: machines that were identical stop being identical.

Each machine has one vote per term and may not change its mind. A candidate votes for itself the moment it becomes one, so a five-way split leaves five machines all holding a spent vote. Nobody can reach three, however long everybody waits, because there are no unspent votes left in that term.

The way out is a new term. The countdowns keep running, somebody times out again, adds one to its term, and now every machine has a fresh vote to give in a term it has not voted in. So a split vote costs a term and a round trip of messages, and that is all it costs. Nothing is corrupted by one.

Because the alternative is worse. Imagine a machine that held its vote back to see who else turned up. It would need a rule for how long to wait, and another for what to do if two candidates ask at once, and every such rule brings back the problem it was meant to solve. Voting for yourself needs no rule at all, and in a cluster of five it only costs you the election when at least three machines campaign at the same moment.

It also gives a small cluster something for nothing. A candidate in a three-machine cluster starts with one vote and needs only one more, so a single reply wins it. The split vote is the price, and Lab 8 measures the price as being close to nothing once the timeouts differ.

A message is a small bundle of named values, and each named value is a field. An append carries five of them. Three are straightforward: the leader's term, the new entries themselves, and how far the leader has committed. The other two describe the entry immediately before the new ones, and are called prevIndex and prevTerm.

Those last two are the interesting ones, and they are the subject of Step 6. They are not information the follower needs in order to write anything down. They are a claim about what the follower should already be holding and the follower checks the claim before it accepts a single entry.

Because there is no other order available. An entry can only be promised once a majority hold it, and they can only hold it if somebody sent it to them. So every entry spends a short time in a state where it exists, is written on disk in several places, and is still not something the client has been told about.

That in-between state is where nearly every interesting failure in this course lives. Step 8 crashes the leader in the middle of it. If you find yourself asking "but what if it dies right now", you are asking the right question, and the answer is a whole step.

Because a follower can be a long way behind, and one entry per message would take a long time to fix that. The leader sends everything from its guess for that follower onwards. A follower that missed ten entries can be handed all ten in one message, and is caught up after a single exchange.

This is also why the check in Step 6 is about the entry before the batch rather than about each entry in it. The batch is written or refused as one piece. A follower never ends up holding half of a message, which is one fewer state for anything to go wrong in.

Because the check was applied to every earlier entry too, so it reaches all the way back, one link at a time. A follower only ever accepted entry 40 after agreeing about entry 39, which it only accepted after agreeing about entry 38, and so on down to the empty log. So "we agree about entry 40" carries the whole of the history with it.

That is why one small comparison is enough, and why it has to be done before writing rather than afterwards. Accept an entry without the check and the chain is broken forever: from then on the two logs can differ anywhere below, and no later message would ever notice.

A function is a named piece of code that takes some values in and hands one value back. In the lab below, accepts is handed three things and must hand back either true or false. Those two words are the only answers a yes-or-no question has in code, and a follower's decision is exactly a yes-or-no question.

One of the three values handed in is a list: several values in order under one name, which programmers usually call an array. myTerms is the list of terms of the entries the follower already holds, so myTerms[0] is entry 1's term and myTerms[1] is entry 2's term. The number in the brackets is the index, counted from zero, which is why entry 5 lives at myTerms[4]. That off-by-one is a real nuisance and everybody meets it.

Four more pieces of writing and you have everything the lab needs. return x means "hand back x and stop". if (test) { … } means "do the part in the curly brackets only when the test holds". === asks "are these two exactly equal", and it is three equals signs because one equals sign means something else. And myTerms.length is how many entries the list holds, so a claim about an index bigger than that is a claim about an entry the follower does not have.

It can be. A follower that is a thousand entries out of step costs a thousand refusals, each one a round trip across the network, and Lab 11 lets you feel it at a small scale. The reason it is acceptable is that it is rare: this only happens after a leader change, and only for a follower that was away.

Real implementations speed it up without changing the idea. A refusing follower also reports the first index it holds from the term that clashed. That lets the leader skip a whole term's worth of guesses in one step instead of one entry at a time. The safety argument does not depend on the speed, so this is a speed-up rather than a different mechanism, and it is safe to leave out until the log gets long.

It promises the client that asked. Before an entry is committed, a client that asks "did my transfer happen" must be told no, or told nothing at all. After it is committed, the answer is yes, and no later event may turn that yes back into a no. Not a crash, not a network split, not an election.

That is why the count is a majority and why entries are on disk before they are counted. Any future majority must share at least one machine with this one, and that shared machine is holding the entry. So the entry cannot be lost by any group that is large enough to be allowed to decide anything.

You walk the list and count. For a given n, look at each machine's total in turn. Add one to a running count every time that total is n or more. Then compare the count with the majority you need. That is what a loop in the code lab below does: repeat the same small piece of work once per machine.

To find the highest such n, do that for n equal to 1, then 2, then 3, and remember the largest one that reached a majority. It is not the fastest way and it is the clearest, and the whole list is at most a few dozen entries, so clearest wins.

The lab writes that out with four more pieces of code. let best = 0 gives a name to a value that is going to change; const need = … gives a name to one that will not. for (let n = 1; n <= 40; n = n + 1) is the loop: run the part in the curly brackets with n as 1, then as 2, and so on up to 40. for (const s of stored) is the same idea over a list: run it once for each machine's total, calling that total s. And s >= n asks "is s at least n", while Math.floor rounds a number down to a whole one, which is how you halve five and get two.

Yes, and it must. The leader is one of the five machines and it is holding the entry on its own disk, so it is one of the copies. In a cluster of five, a leader plus two followers is three machines, which is the majority, so two replies are enough. That is why the count in Lab 13 starts at one before any follower is added.

Counting itself is not the same as trusting itself. It contributes one, exactly like everybody else, and one is never a majority of five. The rule is doing arithmetic over the whole cluster and the leader has no special weight in it beyond being the machine that does the sum.

A machine has two kinds of memory. Working memory is fast and forgets everything when the power goes. The disk is slower and keeps what it was given after a restart. Raft writes a log entry to disk before it answers for it, so a crashed machine comes back holding the same log and the same term it had when it fell over.

This is not a detail. The whole safety argument counts machines that hold an entry. A machine that forgets on restart would make the count meaningless, because an entry on three machines could be on zero after a power cut. The order matters too. Write first, answer second, because answering first and writing second is a promise that can evaporate.

Because a count taken now can be undone by a machine that is currently switched off. An entry from an older term can sit on a majority of the machines that happen to be up. A machine that is down may be holding a longer log from that same period, and when it comes back it is entitled to replace that entry. Committing it would be a promise that a later election could break.

So Raft adds one condition to Step 7's rule: a leader only commits by counting when the entry was created in its own current term. Old entries come along for free. The moment a new leader gets one entry of its own onto a majority, everything below it is committed too, because a log is only ever accepted whole. That is what the second button in the lab above demonstrates.

Because it has no idea how long it was gone. A machine that woke up still calling itself leader would start sending appends stamped with an old term, into a cluster that may have held three elections while it was down. Coming back as a follower costs nothing. If there is a current leader it will hear from it within a few ticks, and if there is not, its countdown runs out and it can campaign like anybody else.

The term and the log come back from disk, so it is not starting from nothing. It keeps everything it knew and gives up only the claim to be in charge, which is the one thing it knew that could have gone stale while it was away.

Ordinary things. The box that wires one row of machines to the next stops working. Somebody sets a rule meant to keep strangers out, and it keeps their own machines out instead. A cable is unplugged while somebody is tidying. The long link between two buildings gets so busy that nearly everything sent along it is dropped. From inside a machine, all four look identical to the other machines having died.

That indistinguishability is the point, and it is why "just check whether the other one is alive" never works. No message can tell you the difference, because the whole problem is that messages are not arriving. Raft never tries to tell the two apart, which is why it survives both.

Because nothing tells it. It sends appends into the silence and gets no replies, which is exactly what a busy or briefly congested network looks like. There is no message meaning "you were replaced", and there could not be one, since it would have to travel across the very link that is broken.

It finds out the moment the link comes back, and it finds out from one number. Any message it receives carrying a higher term makes it drop to being a follower at once. Until then it keeps trying, which is harmless, because trying is not the same as committing.

Because it cannot tell that it is the stranded side. From inside those two machines, the picture is identical to three machines having burned down, and in that situation trying to elect somebody is exactly the right response. A rule like "stop trying after five failures" would leave a cluster leaderless after a genuine outage, which is worse than a machine wasting messages.

The cost of trying is small and bounded: a term number that climbs and a few messages that go nowhere. The moment the link comes back, those higher term numbers are actually useful, because they push the cluster into a fresh election that everybody can take part in.

It would be, if any of them had been committed. They were not. The stranded leader could only reach one other machine, so nothing it wrote ever sat on three of the five, so no client was ever told that any of it had happened. Discarding an entry nobody was promised costs nobody anything.

The rule from Step 8 is what makes this safe rather than lucky. A machine only wins an election if its log is at least as up to date as a majority of the cluster, so the winner already holds every committed entry there is. Anything it does not hold was, by that argument, never committed. The overwrite can only ever destroy notes, never promises.

Two things, and both are engineering rather than new ideas. A log that only grows would eventually fill any disk, so real implementations take a snapshot of the state now and then and throw away the entries that led up to it. A machine that is far behind is then sent the snapshot instead of ten million entries.

The other is changing the membership: adding a machine or removing one without ever having two different majorities that do not overlap. Raft handles it by moving through a combined configuration where a decision needs a majority of both the old and the new set. Neither changes anything you have built here, and both are safe to leave until you need them.

The leader's log wins, always, and nobody decides anything at the moment of the merge. There is no comparison of the two histories, no rule about which looks better, and no vote about it. A follower's only move is to say yes or no to a claim, and once it says yes, everything after that point is replaced by whatever the leader sends.

All the judgement happened earlier, at the election. Choosing a leader whose log is at least as up to date as a majority is what makes "the leader's log wins" a safe rule instead of a reckless one. Get the election right and the merge needs no cleverness at all, which is the part of Raft worth copying into other designs.

It walks every machine's log and compares it against every other machine's, entry by entry, at each index they both reach. It also keeps a record of what was committed at each index the first time anything committed there, and compares every later commit against that record. The panel reports how many comparisons it just did, so you can see it is doing work rather than displaying a reassuring word.

Checking history as well as the present matters. A cluster that committed +50 at index 4 and then quietly replaced it with -30 would look perfectly consistent at any single moment, because all five machines would agree on the wrong thing. Only a check that remembers can catch it.

Because of two rules working together. A committed entry is on a majority of the machines. A machine can only be elected with votes from a majority, and no machine votes for a candidate whose log is behind its own. Any two majorities share at least one machine, and that machine is holding the entry, so it refuses anybody who does not have it.

So every leader that can ever exist already holds every committed entry, which means no leader can ever order that index overwritten. The argument uses no timing, no assumption about how fast messages travel, and no trust in any single machine. That is why it holds under any attack you can run in the panel above.

It does not promise the service keeps working. Crash three of the five machines in the panel above and the cluster stops accepting anything at all, correctly and on purpose, because no majority exists to promise with. Raft protects the truth of what it has already said, and it would rather stop than say something it might have to take back.

It does not promise speed either. Every command waits for a round trip to a majority, so a cluster spread across the world is slower than one in a single room, and no amount of tuning changes that. What you get in exchange is the one thing you cannot build afterwards: an answer of yes that stays true.

The storage layer must define when a completed write survives the failures in scope. A write accepted by an operating-system cache is not automatically safe from power loss.

A duplicate request must receive the same logical answer without running again. Remembering only that a number was seen prevents duplication but cannot reproduce the response.

A new leader first commits an entry from its own term before using the usual read-index reasoning. That establishes which prior entries are committed under Raft's current-term rule.

A Raft snapshot accelerates replica recovery and log compaction. It is not automatically an independent, historical or disaster-recovery backup; all replicas can faithfully agree on corrupted application state.

Some implementations preserve quorum overlap by allowing one voter change at a time and rejecting another while one is uncommitted. Follow the exact membership protocol your implementation proves, not a mixture of two designs.

It is a permission check for starting the real election. A successful pre-candidate still increments the term, requests actual votes and must win a majority under the normal rules.

Track leader changes, proposal and commit latency, applied lag, fsync latency, snapshot size and duration, peer progress, rejected proposals, quorum loss and configuration changes. Alert on user impact and endangered safety assumptions, not term changes alone.