Last month, I took Dave Beazley’s week-long course on The Structure and Interpretation of Computer Programs.
This month, I’m taking Rafting Trip, in which we attempt to implement the Raft algorithm from this paper. In this series, I’ll share memorable insights from the course (here’s where you can see all the posts so far).
The Raft algorithm is a distributed system consensus algorithm designed (and heavily marketed by its designers) to be easier to understand and implement than its predecessor, the Paxos algorithm.
What? Don’t worry about it. Here’s the key question:
When we build software, can we achieve a single source of truth without a single point of failure?
- single point of failure: If this one service/database goes down, our entire system is inoperable. We might try to prevent this by making copies of that thing.
- single source of truth: Problem being, if we make a bunch of copies, how do we update them in such a way that they always have the same data?
Before signing up for this course, I hadn’t dug into the details of either Raft or Paxos. I have spent most of my career thus far focused on building legible, maintainable client applications. In the last year, I have started digging deeper into the stack. I’d like to understand the libraries that we use to build client applications. How are those libraries built?
It’s not uncommon to use some sort of resilient distributed data store in client applications: think Redis or memcache. Those libraries would be implemented with something like Raft.
So in trying that myself, I’m hoping to gain a deeper understanding of the problems that these libraries attempt to solve—and more broadly, the techniques that library and framework designers use to get from the problem they’re solving to a solution that should work in a wide variety of client applications. This could be, I think, a very different set of techniques than the ones I use to implement a client application with the needs of a particular product owner in mind.
As a bonus, we’ll get hands on with a set of programming problems that I just haven’t seen in my career so far.
So how does Raft work?
- Multiple copies of the state (data) are kept on multiple servers.
- If a majority (say, 3 out of 5) of the servers are up, the system is operational.
- Commands to these servers are kept in an ordered log. In order to catch the system up so the data is at the most updated state, a server can replay this log much the way that a client app replays a collection of database migrations in order to reach the most updated database schema.
- If the majority (3 out of 5, say), of the servers agree on the current, updated state of the system, that is considered “the answer.”
- So how do we get other servers back up to speed after they go down? Actions are coordinated by one server, called the leader. The leader might change over time (leadership is divided into ‘terms’). The leader has two jobs:
- Accept all client requests.
- Get all the other servers caught up to the most updated state of the system.
- What if the leader goes down? The remaining servers will elect a new leader. A subtlety of the Raft algorithm: servers will never elect a server that doesn’t have the complete log as the leader.
And then, when one of the servers goes down, the whole system heals itself.
How?
We’ll get there over the course of this series. We’ll start, though, by setting up:
- The servers we’ll coordinate with raft
- The data that we want all those servers to access and modify with consistent results
That’s our topic for the next post. In the meantime, I also found this 18 minute explanation of the algorithm that will give you a broad-strokes idea of what we’re about to do, before we get into the nitty-gritty.
If you liked this piece, you might also like:
The SICP series (with insights from a course by the same instructor)
The time I drew pictures for you (and cussed on live stream) while talkin’ ’bout refactoring
The Leveling Up Series (an all-time favorite of gearheads who read my stuff)