~ $ cd teaching/raft && cat README.md

Raft, and a recipe for concurrency

In the autumn of 2013 the distributed systems laboratory at the UOC set its students a consensus algorithm to implement: Raft, which was then a draft going round, a year away from being presented. I worked on that laboratory, and my implementation is public: one Java class over the course's skeleton, dated October 2013.

Raft was designed to be understandable, and it is. The hard part of the assignment is somewhere else. A server is doing four things at once — timing out, asking for votes, answering other servers' requests, replicating its log — every one of them reads and writes the same few fields, and between any two lines the network may hand it a message that makes it a different kind of server. That is a lot to ask of someone writing their first concurrent program.

The recipe

So the implementation follows a recipe simple enough to be followed by someone who cannot yet reason about interleavings, and still concurrent:

1. One guard for all the state. Not a lock per field: one. Take it, check that you are still what you think you are — only leaders send heartbeats — and copy everything you are about to need into local variables that nothing else can touch.
2. Let go before doing anything slow. Never hold the guard across the network. The remote call runs with the copies, on another thread, for as long as it takes, and the server goes on answering everyone else.
3. Take the guard again, and trust nothing. The answer arrives in a world that has moved. Am I still the leader? Is it still the same term? Is this follower's index still where I left it? If any answer is no, drop the result and return. There is nothing to undo, because nothing was written.

That is the whole of it, and the code says so in its own comments: gather common info (from iteration to iteration may become rotten) going in, and execute inside the guard, any sent data could be changed and must be reevaluated coming back.

Why it works

It removes the two things a beginner gets wrong. There is one lock, so there is no order of locks to get wrong and no deadlock. And no lock is held while waiting, so nothing stalls behind a slow server. What is left is the one real difficulty, stale data, and the recipe turns it from something to reason about into something to check: a list of ifs at the top of step three.

It costs something. Work is sometimes thrown away, and it leans on Raft being built the same way — terms and indices are exactly the version numbers step three needs. But that is not a coincidence to apologise for. Optimistic concurrency, compare-and-swap, a database's UPDATE … WHERE version = ?: read, work outside, write only if nothing moved. It is the pattern most concurrent code that works turns out to have.

Making parallel machines usable by people who are not parallel programmers was what my PhD was about. This was the same problem, with students in place of scientists.