IT PAPER DEEP-READ · PAPER 50
Diego Ongaro & John Ousterhout · Stanford · USENIX ATC 2014
In 2014, two Stanford researchers (Diego Ongaro and John Ousterhout) introduced Raft—a set of rules that lets a group of computers "agree on the same thing, and never take it back." Many of the big systems you use every day (Kubernetes, the database CockroachDB, service registries like etcd / Consul) have a small cluster of machines quietly backing each other up and watching one another, so that "even if a few die, the survivors remember exactly the same record and never disagree." Raft is that agreement rulebook. Its most unusual feature isn't being faster or stronger—it was deliberately designed to be readable and to be implemented correctly.
Picture a team where everyone holds an identical notebook listing, in order, "the operations we've performed." The rule: every notebook must stay line-for-line identical forever; once a line is "locked in," it can never be changed or dropped—not even if someone dozes off or a passed note gets lost. Getting a group of drowsy members over an unreliable channel to keep their notebooks perfectly matched has a proper name: consensus.
Consensus already had a canonical answer, called Paxos, proposed in 1990 (its author won a Turing Award). The trouble: it's notoriously hard to understand. Textbooks couldn't make it click, engineers couldn't fully grasp it, and anyone building a working system on it had to bolt on their own unproven patches. An algorithm where "one small mistake causes disaster," yet almost nobody truly understands it, is itself a serious hazard. Raft's authors simply made "being understandable" the number-one design goal and let everything else fall in line behind it.
Three moves, all humble.
First, elect a single captain (leader): at any moment only the captain may write new lines; everyone else just copies the captain's notebook. Information always flows from the captain to the members—unlike the old approach where anyone could propose and things turned to chaos.
Second, elect the captain with random timers: each person holds a little countdown timer set to a random length; if they hear nothing from a captain for a while, whoever's timer rings first stands up and asks "vote me captain?" Because the lengths are random, two people rarely stand at once; if they tie, each re-rolls a new random time and the deadlock quickly breaks.
Third, only a majority counts: after the captain writes a line, it counts as "locked in" only once more than half the team has copied it. The beauty is that any two "more-than-half" groups must overlap, so the next captain is guaranteed to carry every locked-in line—locked-in content can never be lost. One more rule: only someone whose notebook is current enough is eligible to be elected, which slams the door on "a member missing pages becoming captain and leading everyone astray."
Raft turned consensus from black magic only a few experts dared touch into something an ordinary engineer can implement after reading one paper. Countless pieces of infrastructure today—etcd, Consul, TiKV, CockroachDB, Kafka's newer coordination layer—run on Raft or a variant. In a real sense, it made "reliable distributed systems" something anyone can build.
One honest caveat: every write has to pass through the single captain, so the captain is a throughput ceiling; and when the captain drops off, the whole team pauses briefly to elect a new one before continuing. It also guards only against "crashing," not "lying"—it assumes no member is malicious.
Elect one captain to keep the ledger while everyone copies it, use random timers to pick the captain and "a majority-has-copied-it before it counts" to make locked-in entries un-loseable—Raft rewrote a consensus algorithm no one had understood for thirty years into rules you can actually read and implement correctly, becoming the consistency core of countless modern distributed systems.
Want the role state machine, the replicated-log diagram, and the numbers? → Switch to the deep read
Raft is a replicated consensus algorithm: it lets a group of servers that can crash and communicate only over an unreliable network agree, irrevocably, on the order of a sequence of commands (a replicated log). Its fault tolerance and performance match Paxos, but it makes understandability the primary design goal—via a "strong leader + randomized elections + decomposition into leader election / log replication / safety"—so that consensus became, for the first time, teachable, graspable, and implementable correctly. Today it is the consensus core of etcd, Consul, TiKV, CockroachDB, and many more.
RequestVote and AppendEntries (replication / heartbeat).The authors are Diego Ongaro and John Ousterhout of Stanford; the paper appeared at USENIX ATC 2014 (a fuller version is Ongaro's PhD dissertation). It follows Lamport's Paxos (the 2001 "made simple" version) and Multi-Paxos—the reigning consensus classics for three decades—and precedes nearly every new-generation coordination system in industry. Less an invention of a new principle than a re-shaping of existing principles into a form a human head can actually hold.
The reliability of many critical systems reduces to one thing: getting multiple machines to agree on "which operations happened, and in what order." The mechanism is the replicated state machine—each machine stores an identical command log and executes it in order, so states stay identical everywhere; lose a few machines and, as long as a majority lives, service continues. Google's Chubby, Yahoo's ZooKeeper, and GFS's master election all rest on such a "consensus engine."
And the de facto standard for consensus had long been Lamport's Paxos. Correct and classic—but saddled with two flaws that vexed practitioners for years.
First, too hard to understand. The authors say so bluntly: Paxos is famously opaque, and few grasp it without serious effort—they themselves only felt confident after a long struggle and several secondary explanations. An algorithm whose correctness is critical, yet which most of its users understand only half-way, is dangerous.
Second, hard to build on. Paxos originally describes agreeing on one value (single-decree), but real systems need to agree on a whole sequence of values (a log). The step from single-decree to Multi-Paxos is left vague, so every implementation improvises, adding its own patches; the results diverge and are hard to prove correct. As the Chubby team famously put it, real systems bear little resemblance to textbook Paxos.
So Ongaro and Ousterhout changed the starting point: design a new algorithm with "understandability" as the first-class goal—whenever a trade-off makes it easier to learn or harder to get wrong, take it. Two techniques carried the day: problem decomposition (splitting consensus into a few relatively independent, separately explainable sub-problems) and shrinking the state space (minimizing the states the system can be in, and the amount of nondeterminism, so the reader has fewer cases to consider). Raft grew out of that.
Raft's first design decision is to split consensus into three separately-understandable sub-problems: ① leader election (how to elect a unique leader and replace one that dies), ② log replication (how the leader safely lays client commands out across all machines), and ③ safety (the rules that guarantee "no one ever executes contradictory commands"). Explain each on its own; together they are all of Raft.
The decision that runs through all three is the strong leader: at most one leader per cluster at any time, and the log flows only one way, from leader to followers. That single cut removes much of Paxos's complexity—the "anyone can propose, conflicts must be reconciled" mess—because in normal times a client talks only to the leader while the rest passively copy.
Raft slices time into successively numbered terms, each beginning with an election. The term number is a global logical clock: every message carries the sender's term, and whoever sees a term larger than its own immediately concedes it is stale, reverts to follower, and updates its term; whoever receives a smaller term simply rejects it. This one rule automatically neutralizes "stale leaders" and spares countless special cases.
A server transitions only among three roles: a follower passively answers RPCs from leaders and candidates; a candidate is running for office; a leader handles all client requests. The leader periodically sends empty AppendEntries as heartbeats declaring "I'm still here." If a follower hears no heartbeat within an election timeout, it assumes the leader is gone: it increments its term, becomes a candidate, votes for itself, and sends RequestVote to everyone. A majority of votes wins, and the winner starts sending heartbeats to hold the floor.
The catch in elections is the split vote: several followers time out at once, all campaign, the votes fracture, no one reaches a majority, and everyone times out to try again—possibly stalling repeatedly. Raft's fix is elegantly simple: pick each election timeout at random (say, uniformly in 150–300 ms). Then one server usually times out first and grabs a majority before the rest; if they collide, each one's next timeout is a fresh random value, so they soon spread out. A single random number turns the old scourge of split votes into a low-probability, fast-healing event.
Client commands go only to the leader. The leader appends the command as a new entry to the end of its own log (each entry holds command, term, index), then replicates it to all followers in parallel with AppendEntries. Once the entry is stored on a majority, the leader marks it "committed," executes it, returns the result to the client, and later piggybacks "how far we've committed" on heartbeats so followers execute it too.
How is the alignment guaranteed? By a Log Matching property: if an entry in two logs has the same index and term, then the two logs are identical in every entry up through that point. The implementation needs just one trick—every AppendEntries carries "the index and term of the preceding entry," and a follower whose slot doesn't match simply rejects it. On a rejection the leader steps the position back one and retries, until it finds a point where the two agree, then overwrites everything after that point in the follower's log with its own entries. So the leader never modifies its own log; it merely forces followers to look like it.
The above isn't enough on its own: if a follower missing committed entries became the new leader, its overwriting could erase content that was already committed and already reported to clients—which must never happen. Raft slams the door with an election restriction: when voting, a candidate must include the term and index of its last log entry in RequestVote, and a follower grants its vote only if the candidate's log is at least as up-to-date as its own (comparison rule: compare the last entry's term first, higher term wins; on a tie, the longer log wins).
Combine that with "any two majorities intersect" and you get Raft's key guarantee—Leader Completeness: any committed entry is present in the log of every leader thereafter. The reasoning: an entry is committed = it lives on some majority; a new leader is elected = it won the votes of another majority; the two majorities must intersect, and the machine in the intersection both holds that committed entry and voted for the new leader—yet it votes only for someone whose log is "no older than its own," so the new leader must also hold that entry. Committed content is thereby never lost.
There's a famous subtlety here (the paper's Figure 8): a leader cannot conclude that an entry from a previous term is committed merely because it now sits on a majority—because a later leader could still overwrite it. Raft's rule is that a leader advances the commit point only by replicating a new entry from its own current term; once a current-term entry is committed, the Log Matching property makes those earlier previous-term entries committed indirectly. This counterintuitive rule is the easiest place to get a Raft implementation wrong.
Raft also supplies two engineering necessities: cluster membership changes use a two-phase "joint consensus" transition, guaranteeing that during a config switch no two disjoint majorities can arise and elect two leaders; and log compaction uses snapshots—each server independently snapshots its committed prefix and discards it, keeping the log from growing without bound.
Raft's central claim is "easier to understand," so the paper does something rare—it measures understandability as a metric: the authors recruited 43 students at Stanford and Berkeley, had each watch one lecture video on Paxos and one on Raft, then take a matching quiz. Raft's average quiz score came out about 4.9 points higher than Paxos (out of 60), and 33 of the 43 scored higher on Raft; in a survey, most participants judged Raft easier to implement and easier to explain to others.
On correctness, the authors give a formal specification of Raft and prove its safety (centered on Leader Completeness above). On performance, they measure leader election: with randomized timeouts the cluster elects a new leader in well under a second—often within a few hundred milliseconds—across most configurations; shrink the randomization range and split votes stretch election time markedly, which conversely confirms the value of the randomized-timeout trick. For steady-state throughput and latency, Raft is in the same class as Multi-Paxos.
Raft's influence lies more in engineering and education than in theoretical breakthrough. After publication, dozens of open-source implementations quickly appeared, and it rapidly became the industry's de facto standard: Kubernetes's metadata store etcd, HashiCorp's Consul, TiDB's TiKV, CockroachDB, RethinkDB, and even Kafka's KRaft that replaced ZooKeeper—their consensus cores are Raft or a variant. It lowered the bar for "build a strongly consistent distributed system" from "you must be a consensus expert" to "you can read one paper."
At a deeper level, Raft showed that "understandability" can itself be a first-class research goal: the same fault-tolerance guarantees, told a different way with a different abstraction, can benefit an entire industry. It duly became the go-to teaching material for consensus in nearly every distributed-systems course.
① In one line: Raft is a replicated consensus algorithm that lets crashable machines agree irrevocably on "a replicated log"; its headline selling point is being designed for understandability.
② The pain: Paxos is correct but extremely hard to understand, and its path from single-decree to a "log" is vague—everyone improvises and correctness suffers; a correctness-critical algorithm that almost no one truly reads.
③ Decomposition: split consensus into leader election / log replication / safety and explain each; the through-line is the strong leader—the log flows only from leader to followers.
④ Election: use terms as a logical clock and step down on any higher term; use randomized election timeouts to make split votes rare and fast-healing; a majority of votes wins.
⑤ Replication: a command is appended by the leader, laid out to all via AppendEntries, and committed once a majority replicates it; a "preceding index + term" consistency check forcibly aligns follower logs.
⑥ Safety: only a "sufficiently up-to-date" candidate can be elected (election restriction) + any two majorities intersect ⇒ Leader Completeness: a committed entry lives in every later leader and is never lost.
⑦ The subtlety: a leader advances commit only by replicating a current-term entry; earlier-term entries are committed indirectly (Figure 8)—the single easiest thing to implement wrong.
⑧ Results & impact: it beat Paxos measurably in an understandability user study; it spawned etcd, Consul, TiKV, CockroachDB, KRaft, and more, becoming the de facto standard and the default teaching choice for consensus.
⑨ Limits: single-leader bottleneck + an election unavailability window; no gain over Paxos in fault tolerance / performance; no Byzantine tolerance; a membership-change pitfall was found; timeouts need tuning.