Paxos vs Raft: Differences Explained
On this page
Learning Objective
Compare what Paxos and Raft actually guarantee versus where they differ structurally, distinguish single-decree Paxos from Multi-Paxos and from variants including Flexible Paxos and EPaxos, and identify the areas where two implementations of the same algorithm legitimately diverge.
Concept Explanation
The first thing to establish is how much the two algorithms share, because the differences are often overstated. Both are crash-fault tolerant, both need 2f plus 1 nodes to tolerate f failures, both rely on majority quorum intersection as the mechanism that prevents divergence, both are safe under any network behaviour whatsoever, and both guarantee progress only under partial synchrony. Both are leader-driven in every serious deployment, and both commit a steady-state entry in one round trip from the leader to a majority. Anyone who has understood Raft has understood the substance of Multi-Paxos, because the safety arguments rest on the same quorum intersection property and the same idea of a value, once chosen, propagating forward through subsequent rounds.
The structural differences are real but narrower than the folklore suggests. The most consequential is where the burden of holding committed entries falls. Raft enforces leader completeness at election time through the up-to-date log restriction, so an elected leader is guaranteed to hold every committed entry and the log is always a contiguous prefix with no gaps. Paxos imposes no such restriction on who may become leader; instead a new leader discovers what was previously chosen by running phase one across log positions and adopting whatever values the promises report. Paxos therefore permits gaps, where later positions are decided while earlier ones are still unresolved, and requires the new leader to fill them before the log can be applied. Raft trades away that concurrency for a simpler invariant.
The second difference is in leadership handover. Because Raft restricts eligibility, leadership can only move to a node that is already fully caught up, which makes the handover simple and the invariant easy to state. Paxos allows any node to attempt leadership and makes it responsible for recovering the state it lacks, which is more flexible and considerably more intricate to implement correctly. The third difference is prescriptiveness rather than mechanics: Raft specifies elections, log structure, membership changes, snapshotting, and client interaction as one protocol, while Paxos specifies the agreement core precisely and leaves the rest to the implementer. That is why the phrase "we use Paxos" describes a family of related systems while "we use Raft" describes something much closer to a single protocol.
Several Paxos variants are worth recognising by name because they exploit degrees of freedom Raft deliberately gives up. Fast Paxos lets clients send values directly to acceptors, saving a message delay in the common case, at the cost of larger quorums and a recovery path when collisions occur. Flexible Paxos, from Howard, Malkhi, and Spiegelman in 2016, established a genuinely surprising result: the phase one and phase two quorums need only intersect with each other, not each be a majority. A five-node cluster can therefore use a phase two quorum of two if its phase one quorum is four, trading more expensive leader elections for cheaper steady-state commits, which is attractive when elections are rare. Egalitarian Paxos, or EPaxos, removes the leader entirely and commits commands that do not interfere with each other in a single round trip by tracking dependencies explicitly, which helps most in geo-distributed deployments where routing every write through one leader adds a cross-ocean round trip. Viewstamped Replication, published by Oki and Liskov in 1988, predates the publication of Paxos and is essentially equivalent, a reminder that this design space was explored more than once.
Finally, two implementations of the same algorithm legitimately diverge in areas the papers leave open, and knowing where to look saves real debugging time. Read handling is the biggest: a linearisable read can be served by committing a no-op through the log, by the cheaper ReadIndex approach where the leader confirms it still holds quorum and then serves from its state at the current commit index, or by a lease-based read that skips the confirmation and relies on a time-bounded leadership lease, which is fastest and introduces a clock assumption. Implementations also differ on whether PreVote and CheckQuorum are present, on batching and pipelining strategy, on whether entries are fsynced individually or in groups, on membership change style, and on how aggressively the AppendEntries rejection path is optimised. None of these changes the algorithm's guarantees, and all of them change its behaviour under load enough to matter operationally.
| Dimension | Multi-Paxos | Raft |
|---|---|---|
| Fault model and quorum | Crash faults, 2f + 1 nodes, majority quorums | Identical |
| Safety and liveness | Always safe; live under partial synchrony | Identical |
| Who may lead | Any node; it recovers missing state in phase one | Only a node whose log is at least as up to date as a majority |
| Log shape | May have gaps; positions can be decided out of order | Strictly contiguous prefix, no gaps |
| Specification scope | Agreement core specified; log, leader, membership left open | Elections, log, membership, snapshots, clients all specified |
| Practical consequence | A family of related, mutually incompatible implementations | Implementations that closely resemble each other and the paper |
Worked Example: Three Ways to Serve a Linearisable Read
Read handling is where implementations of the same algorithm diverge most visibly, and it is a decision with real consequences for latency and for what assumptions the system depends on.
# A client asks the leader for key "x". The leader has the value in
# memory. Why can it not simply answer?
# Because it may have been deposed seconds ago by a partition it has not
# noticed yet. Answering from local state could return a value a newer
# leader has already overwritten - a stale read, and a linearisability
# violation.
# --- OPTION 1: log read (simplest, slowest) ---
leader.propose({op: 'NOOP'}) # a full consensus round
wait_for_commit()
return state.get('x')
# Cost: one disk fsync on a majority + one network round trip.
# Every read becomes a write. Correct, and unacceptably expensive for
# a read-heavy workload.
# --- OPTION 2: ReadIndex (what etcd uses by default) ---
readIndex = leader.commitIndex
# Confirm leadership is still real, right now, by exchanging heartbeats:
if not leader.confirm_quorum_via_heartbeat():
raise NotLeaderError
wait_until(state.appliedIndex >= readIndex)
return state.get('x')
# Cost: one network round trip, NO disk write. Safe because a quorum
# just confirmed this node is leader, and any newer leader would have
# needed a quorum that overlaps this one.
# --- OPTION 3: lease read (fastest, adds a clock assumption) ---
# The leader holds a leadership lease valid until T_lease, granted when
# it last confirmed quorum. Followers promise not to elect a new leader
# before T_lease expires.
if now() < leader.lease_expiry - CLOCK_SKEW_BOUND:
return state.get('x') # ZERO network cost
else:
fall back to ReadIndex
# Cost: nothing. But correctness now depends on bounded clock drift
# between nodes. If one node's clock jumps forward, it may elect a new
# leader while the old leader still believes its lease is valid, and a
# stale read becomes possible.
# --- OPTION 4: follower read, explicitly NOT linearisable ---
return follower.state.get('x') # may be arbitrarily stale
# etcd calls this a serializable read (--consistency=s). Cheap and
# scalable, and correct only if the application tolerates staleness.
# ZooKeeper's equivalent barrier is the sync() call, which forces the
# follower to catch up to the leader before the read is served.
# The point: all four run the SAME consensus algorithm. The guarantees
# they give a client differ enormously, and the choice is made by the
# implementation and by the client's request flags, not by Raft.Real-World Examples
- etcd serves linearisable reads using the ReadIndex approach by default, confirming leadership with a heartbeat round before answering from local state, and also exposes an explicitly non-linearisable serializable read mode for clients that can tolerate staleness in exchange for avoiding the round trip entirely. Kubernetes relies on this distinction directly: the API server uses linearisable reads for operations that must observe the latest state and watches backed by the MVCC history for everything else.
- TiKV, the storage layer beneath TiDB, runs a Raft group per data region and implements lease-based reads as an optimisation over ReadIndex, explicitly documenting the clock assumption this introduces and bounding the lease to a fraction of the election timeout so that clock drift cannot outlast it. The same codebase supports both paths, which makes it a clear demonstration that read strategy is an implementation choice layered on top of Raft rather than part of Raft itself.
Review Questions & Answers
No. Both algorithms guarantee that a committed value is never lost; they place the work in different places. Raft enforces the property at election time through the up-to-date log restriction, so the leader is complete the moment it takes office. Paxos allows any node to lead and requires the new leader to run phase one across log positions, where quorum intersection forces it to discover and re-propose any value that may already have been chosen. Safety is equivalent because both rely on the same intersection argument; Raft simply front-loads the check, which makes the invariant easier to state and the implementation easier to verify.
Flexible Paxos showed that the phase one and phase two quorums need only intersect with each other, rather than each independently being a majority. In a five-node cluster, a phase two quorum of two is safe provided the phase one quorum is four, since any set of four and any set of two drawn from five must overlap. The trade is that steady-state commits become cheaper, needing acknowledgement from fewer nodes, while leader elections become more expensive, needing more. That is attractive when leadership is stable and elections are rare, because the common path is optimised at the expense of an uncommon one.
Because leadership is not self-evident. A leader may have been deposed by a partition it has not yet noticed, in which case a newer leader may already have committed a value that overwrites what the stale leader holds, and answering locally would return stale data and violate linearisability. ReadIndex closes the gap cheaply: the leader records its current commit index, exchanges heartbeats to confirm a majority still recognises it right now, waits for its own applied index to reach the recorded commit index, and then answers from local state. This costs one network round trip and no disk write, and it is safe because any newer leader would have needed a quorum overlapping the one that just confirmed this node.
A lease read assumes clock drift between nodes is bounded. The leader serves reads with no network confirmation at all while it believes its leadership lease is unexpired, and followers promise not to elect a new leader before that lease expires. If a follower's clock runs ahead, it may consider the lease expired and elect a new leader while the old leader still believes the lease is valid and continues serving reads from state the new leader has already superseded, producing a stale read that violates linearisability. ReadIndex avoids this entirely by confirming leadership through actual messages rather than through time, which is why implementations that offer leases bound them well inside the election timeout and document the clock assumption explicitly.
Lamport specified the agreement core precisely and left the log structure, leader election, membership changes, snapshotting, and client interaction unspecified, so each Paxos implementation invents those parts independently and they diverge in everything except the core. Raft specifies all of it as one prescriptive protocol, so independent implementations end up structurally similar and verifiable against the same specification and the same TLA+ model. The implication for anyone building a consensus layer is that Raft offers a far shorter path to a correct implementation, a reference implementation to compare against, and a shared vocabulary with operators, which is why nearly every consensus system built since 2014 chose it.