Raft: consensus you can actually understand

I’ve tried to learn Paxos three times. The first time I read Lamport’s “Paxos Made Simple”, whose abstract is one sentence long, “The Paxos algorithm, when presented in plain English, is very simple.” I got through it, understood each step, and couldn’t have told you afterwards why it worked. The second time I read Google’s “Paxos Made Live” paper about building Chubby, which is mostly a list of all the ways real systems differ from the algorithm, and which made me feel better about not understanding it. The third time I gave up and just used ZooKeeper.

So when Diego Ongaro and John Ousterhout’s Raft paper, “In Search of an Understandable Consensus Algorithm”, won best paper at USENIX ATC in Philadelphia last month, I sat down with it over a weekend. It’s the first consensus paper I’ve read where I could close it and explain the algorithm to someone else, which I suppose is the point. Its stated goal is understandability. They even ran a user study: 43 students at Stanford and Berkeley learned both Raft and Paxos, and 33 of them did better on the Raft quiz.

This is my attempt at explaining it, mostly so I can check I really did understand it.

What problem this solves

You have some state you care about, say a key-value store, and you want it on several machines so that losing one doesn’t lose the data or take you offline. The classic way to do this is a replicated state machine: every server keeps a log of commands, and if every server applies the same commands in the same order, they all end up with the same state. The hard part is getting the servers to agree on the log when machines crash, restart, get slow, and networks drop or delay messages. That’s consensus.

I care about this more than I used to. Two years ago an EC2 outage took us down for most of an afternoon, and failing the database over to a healthy zone was us, by hand, editing config files over SSH. Systems like etcd and Consul, both built on Raft, are basically “do that failover correctly, automatically”, and I’d like to understand what I’m trusting before I trust it.

Raft splits the problem into three parts, which is the main reason it’s easier to follow: leader election, log replication and safety. (Membership changes are a fourth, and I’m skipping them here.)

Terms and roles

Every server is in one of three states: follower, candidate or leader. In normal operation there’s exactly one leader and everyone else is a follower. Followers are passive. They only respond to requests from the leader and from candidates.

Time is divided into terms, numbered with consecutive integers. Each term starts with an election, and at most one leader can win it. Every message carries the sender’s term, and if a server ever sees a term higher than its own, it updates to that term and steps down to follower immediately. That one rule clears up most of the confusion you’d otherwise get from stale leaders coming back from the dead. A leader that was cut off for a minute comes back, sees everyone else is two terms ahead, and quietly becomes a follower.

Leader election

The leader sends regular heartbeats (empty AppendEntries messages) to every follower. If a follower hears nothing for its election timeout, it assumes the leader is dead. It increments its term, becomes a candidate, votes for itself and sends RequestVote to everyone else.

Each server votes for at most one candidate per term, first come first served (with one restriction I’ll get to below). A candidate that collects votes from a majority of the cluster becomes leader and starts sending heartbeats, which stops anyone else from starting an election. If it hears from a legitimate leader with a term at least as high as its own, it backs down. If nobody wins, because the vote split, everyone times out and tries again in a new term.

The split vote is where a naive design would livelock, everyone timing out together, all becoming candidates, all voting for themselves, forever. Raft’s answer is almost comically simple: each server picks its election timeout at random from a range, and the paper suggests 150–300ms. Usually one server times out first, wins before anyone else wakes up, and that’s that. Their measurements show this converging quickly, and also show what happens if the range is too narrow: with no randomness at all, elections can take a very long time. There’s something I love about a correctness argument in a distributed systems paper leaning on “pick a random number”, it’s the kind of thing a math professor would have marked me down for.

Log replication

Once there’s a leader, clients send it commands. The leader appends each command to its own log as a new entry, tagged with the current term, and sends it to the followers in AppendEntries. When a majority of servers have stored the entry, the leader considers it committed, applies it to its state machine and replies to the client. Followers learn the commit point from later messages and apply entries up to it.

The clever part is how the leader keeps followers consistent without a lot of bookkeeping. Every AppendEntries includes the index and term of the entry just before the new ones. A follower only accepts the new entries if its own log has an entry at that index with that term. If it doesn’t, it says no, and the leader steps back one entry and tries again, until it finds the point where the two logs agree. From there, the follower throws away anything after that point that conflicts and takes the leader’s entries. Logs only ever flow from leader to follower, and a leader never overwrites its own log.

The paper proves what they call the Log Matching Property from this: if two logs have an entry with the same index and term, they’re identical up to that point. That one consistency check, applied inductively, does all the work. The first time I read it I went back and looked for the rest of the mechanism, and there isn’t any.

The subtle part

So far you could build all this yourself in an afternoon and get it wrong. The two rules that make it safe are in section 5.4, and the second one took me a couple of reads.

The first is the election restriction. A server won’t vote for a candidate whose log is less up-to-date than its own. “Up-to-date” means: compare the term of the last entry, and the higher term wins; if the terms are equal, the longer log wins. Since a committed entry is on a majority, and a winning candidate needs votes from a majority, at least one voter has every committed entry, and it will refuse to vote for anyone missing one. So a new leader always has every committed entry. That’s what lets Raft get away with logs only flowing one way.

The second is about entries from earlier terms. You’d think that if the new leader sees an old entry sitting on a majority of servers, it’s committed. It isn’t, necessarily. The paper’s Figure 8 walks through a sequence of crashes where an entry from term 2 ends up on a majority, and is still overwritten by a later leader carrying an entry from term 3. The fix is a rule: a leader only counts replicas for entries from its own term. Once one of those is on a majority, everything before it is committed too, by the Log Matching Property. Old entries get committed indirectly, by riding along with a new one.

I’d never have found that case myself. I’m also not sure I’d have caught it in a code review of someone else’s implementation, which is exactly why I’d rather use one of the existing ones than write my own. The paper says there are about 25 open source implementations floating around, at various levels of maturity, and Ousterhout’s group runs theirs (LogCabin) for RAMCloud’s configuration.

Should you use it?

You probably shouldn’t implement Raft yourself, for the same reason you shouldn’t write your own crypto. But you should understand it if you run anything built on it, because when your three-node etcd cluster loses two nodes and stops accepting writes, that’s the algorithm doing its job and not a bug. A majority is a majority. Three nodes tolerate one failure, five tolerate two, and four tolerate one, which surprises people.

What I’ll be doing is going back over our own failover setup with this in my head, because I’m now fairly sure it has a split-brain case we’ve just never hit.