In Search of an Understandable Consensus Algorithm (Raft, 2014)
diego-ongaro and john-ousterhout, stanford-university. The extended tech-report version of the USENIX ATC 2014 paper, published 20 May 2014. T1 — the algorithm's own specification, read in full.
Two production systems in this spoke run Raft — yugabytedb per tablet, and the DCS layer patroni rents its consensus from — and until now nothing here explained it. podc-lecture-notes gave the spoke consensus and paxos; this is the algorithm most of the code actually uses.
The paper's goal is a claim about people, not about machines
The unusual thing is stated in the abstract and pursued as an experiment: the design target was understandability.
"our primary goal was understandability: could we define a consensus algorithm for practical systems and describe it in a way that is significantly easier to learn than Paxos?"
Two techniques serve it — decomposition (leader election, log replication and safety are separate problems) and state space reduction (fewer ways for servers to disagree than Paxos allows). That is a design methodology this corpus has not seen argued anywhere else: correctness and performance are treated as constraints, and the thing being optimised is what a reader can hold in their head.
The mechanism, in the order the paper separates it
- Strong leader. "log entries only flow from the leader to other servers." paxos lets any node propose; Raft forbids it, and buys the simplicity of a single writer per term.
- Leader election by randomized timers. Each follower waits a random timeout before becoming a candidate, so split votes resolve themselves instead of needing a tiebreak protocol.
- Membership changes by joint consensus — during a reconfiguration the majorities of the old and new configurations must overlap, so the cluster keeps serving while it changes shape. This is the operational problem reshaping a cluster runs into and neither Paxos paper in this spoke addresses.
Five properties are asserted to hold at all times (Figure 3). They are the vocabulary any replicated store in this spoke should be described in:
Election Safety: at most one leader can be elected in a given term. Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends. Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index. Leader Completeness: if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms. State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.
Safety does not depend on timing; availability does — and here is the inequality
The split consensus records from Lamport is stated by Raft as a design requirement and then given a usable form:
"safety must not depend on timing … However, availability … must inevitably depend on timing."
broadcastTime ≪ electionTimeout ≪ MTBF
Broadcast time is one round of parallel RPCs and replies; MTBF is the mean time between failures of a
single server. The paper asks for an order of magnitude on the left (so heartbeats reliably suppress
elections) and "a few orders of magnitude" on the right (so the cluster is not permanently electing).
That is the same rule patroni encodes as loop_wait + 2 * retry_timeout <= ttl — a production
system's version of this inequality, written down in this spoke six weeks before the algorithm behind
it was.
What was measured
Election, on five servers with a broadcast time of roughly 15 ms, leader crashed 1,000 times per configuration:
| Randomness in the election timeout | Result |
|---|---|
| none (150–150 ms) | elections "consistently took longer than 10 seconds" — split votes |
| 5 ms (150–155 ms) | median downtime 287 ms |
| 50 ms (150–200 ms) | worst case over 1,000 trials 513 ms |
| timeout lowered to 12–24 ms | 35 ms average, longest trial 152 ms |
Two things follow. Five milliseconds of randomness is the whole fix — the difference between ten seconds and 287 ms is not an algorithm change. And the floor is set by the timing inequality rather than by the protocol: below ~12 ms timeouts, heartbeats stop arriving in time and the cluster starts electing for no reason.
Throughput is one round trip from the leader to half the cluster in the steady state, which the paper calls the minimal number of messages, with batching and pipelining available on top.
The understandability claim is the one thing here with an experiment behind it, and it is thin
43 upper-level students at Stanford and U.C. Berkeley watched a lecture on each algorithm and took a quiz on each, in both orders.
- 33 of 43 scored higher on Raft. Means: Raft 25.7, Paxos 20.8, out of 60.
- A paired t-test puts the true difference at at least 2.5 points with 95% confidence.
- 33 of 41 said Raft would be easier to implement, and 33 of 41 easier to explain.
The authors list the ways the study favoured Paxos (15 participants had prior Paxos experience; the Paxos video was 14% longer) and the ways it might be biased for Raft (self-reported preference, students who knew the hypothesis). Worth holding at what it is: one course-sized sample, the authors' own materials, the authors' own grading rubric, measuring quiz scores rather than anyone's ability to build a correct system. It is more evidence than any competing design in this corpus offers, and it is not much.
Correctness is stronger where the claim is smaller: a TLA+ specification of about 400 lines, a mechanically checked proof of Log Completeness (resting on invariants that were not mechanically checked), and an informal but complete proof of State Machine Safety at about 3,500 words.
What this closes and what it does not
It closes growth edge 4 — the algorithm behind two of this spoke's production systems is now explained here rather than named. It does not supply an engine's account of running it: nothing here is a measurement from a database, and the election numbers come from the authors' own implementation on a five-node cluster of unstated hardware.
Related
consensus · paxos · part-time-parliament · paxos-made-simple · patroni · yugabytedb · chubby-lock-service · write-ahead-logging