Why Raft Won: Consensus Built for Humans

In 2013, consensus algorithms faced a curious paradox. Google’s Chubby lock service and Spanner database had been running Paxos for years—the same algorithm that won the Turing Award and had a correctness proof. At the same time, newer systems like etcd, Consul, and Kubernetes were standardizing on Raft, an algorithm that claimed no new theory, no performance advantage, and no novel guarantees. Both are consensus algorithms with identical safety properties in the same failure model. Neither is faster than the other in steady state. Yet Raft’s adoption accelerated while Paxos implementations stalled. The difference was not correctness—Paxos was and is proven safe—but comprehensibility. That difference, it turned out, was an engineering property worth more than theoretical elegance.

Left: Paxos as a symmetric swarm of proposers and acceptors with a large unspecified region. Right: Raft’s three explicit phases flowing top to bottom.

The Paxos Problem: Correct but Under-Specified

Leslie Lamport’s Paxos (1989, formalized in the famous “Paxos Made Simple” paper in 1998) solved one of distributed computing’s hardest problems: how do multiple independent systems agree on a single value, even if some fail? The algorithm is elegant and provably safe. At most one value is ever chosen. If one value is chosen, all non-failed processes eventually learn it. The proof is rigorous and stands to this day.

But there’s a gap between proof and practice.

The paper describes only the core two-phase voting protocol: prepare and accept. It is mathematically precise about voting logic and safety invariants. It is silent on everything else. The paper does not say:

• Which process should propose? In practice, real systems need a single leader to avoid dueling proposers (wasteful and slow). Paxos leaves leader election to “outside the algorithm”—a phrase that appears in the paper but is never formalized. What does “outside” mean? No two systems answered the same way.
• What if a leader crashes mid-round? How do you recover? Does the next leader re-run the prepare phase? What if it crashes? The gap here became a source of subtle bugs that bit implementations for years.
• How do you handle membership changes? What if you want to add or remove nodes dynamically? Paxos doesn’t address it directly. You could run Paxos separately for each membership epoch, but the paper provides no recipe.
• How do you structure a log? In production, you don’t just agree on a single value; you need a sequence of consensus values: entry 1, entry 2, entry 3, each agreed independently. Multi-Paxos extends the core idea to handle this, but the extension itself left critical details unspecified. How do you number entries? How do you handle gaps in the log? How do you know when an entry is truly committed?

Every major Paxos implementation—Google Chubby, Apache Zookeeper, Yahoo! Paxos, LinkedIn’s KaTeX Kafka—invented different answers to these questions. This wasn’t incompetence. It was necessity. The protocol was provably safe, but the paper was incomplete for production use. The implementations were correct in isolation, but they diverged enough that deep cross-system understanding became harder. An engineer who knew Chubby’s Paxos and tried to understand Zookeeper’s version found subtle differences in leader election, recovery strategy, and log structure. They were asking the same question—“How does Paxos work?”—and getting different answers.

This divergence had consequences. Bugs would hide in the gaps. A flaw in one system’s leader election strategy was “correct by Paxos” (because Paxos didn’t specify it) yet still wrong in practice. Security vulnerabilities appeared in implementations that were theoretically sound. And teaching Paxos became a nightmare: instructors would present the core algorithm, then have to explain that “in practice, you also need…” and fill in a dozen details the paper left blank.

Raft’s Insight: Make the Implicit Explicit

In 2014, Diego Ongaro and John Ousterhout at Stanford published “In Search of an Understandable Consensus Algorithm.” The paper’s title itself was a statement: consensus algorithms can be understandable. They didn’t invent a fundamentally new mathematical approach. Raft’s safety properties are equivalent to Paxos’s. They didn’t discover a new fault-tolerance model or bypass the Fischer-Lynch-Paterson impossibility result that bounds distributed consensus. Instead, they rebuilt Paxos from first principles, making an explicit design choice at each point where the Paxos paper had left a gap. The result: a specification that was complete enough for production systems without losing rigor.

Raft decomposes consensus into three orthogonal concerns, each with crystal-clear rules:

1. Leader Election

At any time, at most one node is leader for a given term (a monotonically increasing counter). Followers use randomized election timeouts (typically 150–300 ms). When a follower’s timeout fires, it increments its term, votes for itself, and sends RequestVote messages to all peers. A peer grants a vote if: the candidate’s term is at least as high as the peer’s, and either the peer hasn’t voted in this term or already voted for this candidate. The first candidate to win a majority of votes becomes leader for that term.

The key insight: term numbers enforce mutual exclusion. If two candidates somehow both claimed to be leader, they’d have different terms. Nodes only follow the highest term they’ve seen, so they’d eventually converge on one leader. No Byzantine logic, no complex recovery—just monotonic term numbers.

2. Log Replication

The leader receives client requests, appends them to its log as new entries, and replicates them to followers via AppendEntries messages. Each message includes: the leader’s term, the index and term of the previous log entry, the entries to replicate, and the leader’s commit index. A follower checks consistency: does my log have an entry at the previous index with the previous term? If yes, I append the new entries and reply success. If no, I reply failure (which tells the leader to backtrack). The leader waits for majority acknowledgment before committing.

Notably, there’s no ambiguity. The protocol is symmetric: all followers apply the same logic. If a follower crashes and restarts, it re-syncs with the leader deterministically. Log conflicts are resolved by the leader’s rule: “your log matches mine up to index X, so I’ll overwrite everything after.”

3. Safety

Raft adds one crucial constraint: a log entry is only “committed” (safe to apply to the state machine) once it’s replicated on a majority and the leader has committed an entry from its own term. This prevents an old leader from committing entries from a past term that might conflict with a newer leader’s view.

Why this matters: imagine Leader A replicates entry X to a majority, then crashes before committing it. Leader B is elected and overwrites A’s log with entry Y. Then A restarts and thinks X is committed. Disaster. Raft prevents this by requiring the leader to commit its own term’s entries before considering older entries safe.

Why This Works

The genius is not new mathematics—it’s ruthless compression. Every rule fits in a table or a short paragraph. A competent engineer can implement Raft in a weekend; the same engineer might spend months on Paxos and still miss edge cases. And because the rules are explicit, implementations converge: etcd, Consul, TiKV, Kubernetes, and dozens of smaller systems all run essentially the same Raft, with minor optimizations but identical semantics. You can read one implementation and understand another. Bugs in one system alert you to potential issues in others. Cross-system reasoning becomes tractable.

Mechanism: A Raft Replication Round Step by Step

Let’s trace a concrete scenario: a client sends a request to the Raft leader.

Step 1: Leader appends. The leader receives the request, creates a new log entry with the current term, appends it to its log in memory, and marks it as not yet committed.

Step 2: Leader replicates. The leader sends AppendEntries(term, prevLogIndex, prevLogTerm, entries[], leaderCommit) to all followers. The message includes:

• The leader’s current term.
• The index and term of the previous log entry (used for consistency checking).
• The new entries to replicate (typically 1 or more).
• The leader’s current commit index.

Step 3: Followers check consistency. Each follower receives the message and checks: “Do I have an entry at prevLogIndex with prevLogTerm?” This is the key safety check. If yes, the follower appends the new entries and replies success. If no (meaning my log diverged from the leader’s), the follower replies failure. The leader will then backtrack: it decrements prevLogIndex and retries until the follower acknowledges a matching point.

Step 4: Majority acknowledgment. The leader collects replies. Once a majority of followers (including itself) have acknowledged, the entry is now committed—safe to apply to the state machine. The leader applies the entry, executes the client’s request, and returns success.

Step 5: Propagate commit index. The leader includes the new commit index in the next batch of AppendEntries messages (or immediately if urgency demands). Followers see the leader’s commit index and advance their own, applying entries to their state machines.

Total messages in the fast path: 2 round-trips (append + reply, commit + reply). In a local network with fast consensus (e.g., 3 nodes, 2 required for majority), this is typically under 10 milliseconds. Multi-Paxos, in steady state, also requires roughly 2 round-trips (prepare if needed, accept + accepted, learn). The cost is equivalent; the clarity is night and day.

Handling Failures

When a node crashes or the network partitions:

• If the leader crashes, followers’ election timers fire, one wins an election, and becomes the new leader. The old leader’s uncommitted entries are discarded if they conflict.
• If a follower crashes, the leader keeps retrying until it rejoins. When it rejoins, the leader backfills its log.
• If a client doesn’t receive a reply, it retries. Raft is idempotent (applying the same entry twice is safe because each entry is tagged with a unique index), so retries are safe.

Each scenario is specified. There’s no gap between the paper and the implementation.

Where Raft and Paxos Converge: Identical Safety, Comparable Cost

It’s important to be precise: Raft and Paxos guarantee the same safety properties (in the same failure model, non-Byzantine):

• Agreement: No two processes ever choose and commit different values for the same index.
• Termination: If a quorum of processes is live and can communicate, they eventually commit entries and all non-failed processes learn them.
• Validity: Every committed value was proposed by some process.

These properties are not unique to either algorithm; they define the consensus problem itself. Both Paxos and Raft solve the same problem at the same level of abstraction.

On performance: In steady state (after leader election completes), both use O(N) messages per replication round, where N is the number of nodes. In a 5-node cluster with 3-node quorum, both send 4–5 messages per round (leader to followers, replies back). Neither has an asymptotic advantage. Raft may be slightly slower during leader election because it uses randomized timeouts (to avoid split votes), while Paxos can potentially recover faster with explicit leader recovery. However, in well-tuned production systems where leader elections are rare, this difference is negligible.

Latency-wise: both have 1-2 round-trip-times from client to committed state in the fast path. Measured wall-clock time will vary based on network, but the algorithmic complexity is the same.

The real gap is engineering. Paxos’s terseness means each implementer invents details. Those details, while locally correct, don’t align across systems. Raft’s explicitness means implementations converge. That convergence—being able to read etcd’s Raft and understand Consul’s, being able to port a fix from TiKV to another system, being able to teach the algorithm in a classroom and have students build working systems—that is worth far more than a hypothetical 10% latency gain.

When NOT to Use Raft (and When Paxos Might Still Win)

Raft’s design choices assume certain priorities: readability over flexibility, simplicity over optional optimizations, converged implementations over ad hoc variants. In most new systems, these are the right choices. But there are edge cases:

Inherited infrastructure

If your system already runs a battle-tested Paxos implementation (Google Chubby, Apache Spanner, Yahoo! systems that have run for 10+ years without major incidents), rewriting it for Raft is often not justified. The Paxos implementation has been debugged and hardened through years of production use. Its engineers understand all the quirks. Migration risk is real. The clarity gains, while nice, don’t outweigh the operational cost of a complete rewrite.

This is why Google still uses Paxos (via Chubby) for Spanner and other critical systems. Not because Paxos is “better,” but because it already works and Chubby is battle-tested.

Highly asymmetric or exotic topologies

Raft assumes a roughly symmetric cluster where nodes have similar roles and latencies. If your topology is exotic—say, one datacenter with fast nodes and another with slow nodes, or a wide-area network with unpredictable latency—you might need a custom consensus variant anyway. Paxos’s flexibility to handle leader changes and asymmetric quorums can be an advantage if you have the expertise to exploit it. But note: most production systems don’t actually need this flexibility. The cases where it matters are rare.

Byzantine or untrusted environments

Neither Paxos nor Raft tolerates Byzantine (arbitrary or malicious) node behavior. If nodes might be compromised or act adversarially, you need Byzantine Fault Tolerance (BFT) algorithms like PBFT, Tendermint, or Hotstuff. In that regime, Paxos and Raft are not competitors; neither applies.

Extremely latency-sensitive systems

If you’re building a system where every microsecond matters and you’ve profiled to find that consensus is the bottleneck, a highly optimized Paxos variant might win. But this is rare. Most systems are not consensus-bound; they’re bound by disk I/O, application logic, or network latency to users. Unless you’ve measured and proven consensus is the constraint, optimizing for consensus speed is premature.

In summary: Raft is the default choice for new consensus systems. Paxos is the answer to “We already have a Paxos system that works; should we migrate?” to which the answer is often no.

Why Comprehensibility Matters

This is the deeper lesson. Algorithms are not only about mathematics; they’re about engineering. A proof that an algorithm is safe is necessary but not sufficient. If engineers can’t implement it correctly, or can’t verify that a given implementation is correct, the proof is academic.

Raft’s win was not because it was smarter. It was because the gap between paper and production was smaller. Rules that are implicit in Paxos are explicit in Raft, so implementations don’t diverge. Code reviews become tractable. Security audits become feasible. New engineers can understand the system in weeks, not years.

This principle extends beyond consensus. In any complex distributed system, the cost of making implicit choices explicit—to make the rules readable and auditble—is often worth more than micro-optimizations. Raft proved it at scale: etcd (Kubernetes’s backing store), Consul (HashiCorp’s service mesh), and TiKV (PingCAP’s database) all use Raft, and all have thriving ecosystems. The clarity compounded.

Multi-Paxos requires 5 messages over 2 phases (prepare/promise/accept/accepted/learn). Raft requires 2-3 AppendEntries rounds, but the rules for when to send and what to do are explicit.

Takeaway

Raft didn’t win because it was faster or more correct. It won because its designers made a deliberate choice: trade some implementation flexibility for radical clarity. Every detail is specified. Every edge case is addressed. The algorithm fits in your head.

In a field obsessed with optimization, this felt like heresy. But engineering is not just about theory; it’s about building things that humans can understand, maintain, and debug. On that measure, Raft’s victory was decisive. And it’s a reminder that sometimes, the winning move is not to be smarter—it’s to be clearer.