Paxos vs Raft: Have we reached consensus on distributed consensus?

Replicated databases and coordination services keep several servers in agreement by replicating a log of operations: every server applies the same operations in the same order. Distributed consensus decides that order even when servers crash and messages are delayed. Two algorithms dominate production. Paxos, from Lamport, is famously subtle and is really a family described differently from paper to paper. Raft, from Ongaro and Ousterhout in 2014, was designed to be easier to understand and claimed to be as efficient.

Howard and Mortier rewrite Paxos, in the multi-decree form used in practice, using Raft's structure. Both algorithms then look the same in most respects. Servers are followers, candidates or leaders. Each server tracks a term number that only increases. A leader appends client operations to its log and sends them to followers with AppendEntries; once a majority acknowledges an entry, it is committed. When followers stop hearing from the leader, one becomes a candidate and asks for votes with RequestVote.

The differences are all in leader election. In Paxos, terms are divided among servers (server s may only run in terms where term mod n equals s), and any candidate can win; the votes it receives include the voters' log entries after its commit index, and the new leader adopts the entry with the highest term at each index, re-stamped with its own term. In Raft, any follower can run in any term, each server votes once per term, and a vote is granted only if the candidate's log is at least as up to date; no entries move during election, but a new leader cannot treat old-term entries as committed until it commits one from its own term.

The authors judge Raft slightly, not significantly, more understandable, and Raft's election surprisingly efficient because it sends no log entries. They expect Raft elections to be slower and more variable, because simultaneous candidates in the same term can split the vote, which Raft handles with randomized timeouts. Their conclusion: much of Raft's understandability comes from its clear presentation rather than from the algorithm.

Your customers' infrastructure runs on these. etcd (and so Kubernetes), Consul and CockroachDB use Raft; Chubby, Megastore, Borg, Azure Data Lake Store and WeChat's PaxosStore use Paxos, per the paper's citations. When a cluster misbehaves after a node failure, you are watching leader election.

A leader failure is a pause. Writes stop until a new leader is elected and has caught up. Our simulation puts that at roughly 160 to 190 ms with sensible timeouts and seconds when timeouts are configured too tightly. Know the election timeouts in the systems you deploy and how clients retry during elections.

Timeout tuning is a real lever. Raft relies on randomized timeouts to avoid split votes. In our model, a 5 ms spread caused 34 split rounds per election on average; a 50 to 150 ms spread fixed it. If a customer sees repeated elections under load, check timeouts, clock pauses (such as garbage collection) and network latency against them.

Use a proven implementation. The paper's point that the algorithms are subtle in small details, such as Raft's rule about committing old-term entries, is the reason not to build your own. Use etcd, ZooKeeper or a database's built-in replication.

Majorities set the failure budget. Both need a majority: three servers tolerate one failure, five tolerate two. Placing all of a majority in one zone defeats the point.