Raft vs Multi-Paxos: Consistent Replicas Explained

Raft and Multi-Paxos are consensus algorithms that let a group of servers behave as a single, highly available state machine by replicating a log of commands in the same order on every server. Both deliver the same core guarantee: if a majority of servers are alive and can communicate, the system continues to operate, and every surviving server that applies the log ends up in exactly the same state, even if some servers crash or messages are lost or delayed. The key difference is how they achieve this: Multi-Paxos is a more modular but famously hard-to-implement protocol, while Raft is a more structured design that was created specifically to be easier to understand and build correctly.

Formula

The core arithmetic behind both algorithms is the quorum rule: to commit an entry, a leader must get a majority of votes or acknowledgments. The quorum size is calculated as:

Q = ⌊N/2⌋ + 1

• N = total number of servers in the cluster
• Q = minimum number of servers that must agree on a value for it to be committed

The maximum number of server failures that can be tolerated is F = ⌊N/2⌋. For example, with 5 servers, Q = 3 and F = 2. With 3 servers, Q = 2 and F = 1.

Worked Example

Suppose you have a cluster of 5 servers (N = 5). The quorum size is Q = ⌊5/2⌋ + 1 = 2 + 1 = 3. This means any decision (like electing a leader or committing a log entry) requires at least 3 servers to agree.

If the leader sends a new log entry to all 5 servers, it waits for acknowledgments. Once 3 servers (including the leader itself) have durably stored the entry, the leader considers it committed and tells the others to apply it. The system can afford to lose up to 2 servers and still make progress. If 3 servers fail, the remaining 2 cannot form a quorum, so the cluster stops accepting new writes to avoid split-brain scenarios.

Background: The Consensus Problem

Distributed systems often need to keep multiple copies of data in sync. If one server fails, another should take over seamlessly. But simply copying data from a primary to backups can lead to inconsistencies: the primary might crash after sending a write to some backups but before sending it to others, leaving the backups with different states. Consensus algorithms solve this by ensuring that every server applies the same sequence of operations, even when failures occur. The classic result in this field is the Paxos algorithm, published by Leslie Lamport in 1998. Paxos is elegant and theoretically sound, but its original description was abstract and hard to translate into production code. Multi-Paxos is a practical optimization that reuses a single leader to handle many log entries, but it still leaves many implementation details unspecified, leading to subtle bugs. Raft, introduced by Diego Ongaro and John Ousterhout in 2014, was designed as a more comprehensible alternative that explicitly decomposes the problem into leader election, log replication, and safety.

How Raft Works

Raft organizes time into terms. Each term begins with an election. Servers are in one of three states: leader, follower, or candidate. The leader is responsible for receiving client requests and replicating them as log entries. Followers simply respond to the leader’s requests. If a follower doesn’t hear from a leader within a randomized timeout (typically 150–300 ms), it becomes a candidate and starts a new election by requesting votes from other servers. A candidate wins if it gets a majority of votes. The elected leader then sends periodic heartbeats to maintain its authority. Log entries flow from the leader to followers in order. The leader appends a new entry to its local log, then sends AppendEntries RPCs to followers. When a majority of servers have acknowledged the entry, the leader commits it and applies it to its state machine. Followers apply the entry when the leader tells them it is committed. Raft’s safety is based on two properties: the Election Safety property (at most one leader per term) and the Log Matching property (if two logs contain an entry with the same index and term, they are identical from the beginning to that index). These rules prevent a stale leader from overwriting committed entries.

How Multi-Paxos Works

Multi-Paxos is an optimization of the original Paxos algorithm. Instead of running a full Paxos round (prepare/accept) for every log entry, it elects a distinguished leader once, and then the leader can propose entries without re-running the prepare phase for each one. The leader assigns a monotonically increasing log index to each client request. It sends the entry to all acceptors (servers). An acceptor accepts the entry if it hasn’t already promised to accept a higher-numbered proposal. Once a majority of acceptors accept the entry, it is committed. The leader can then send a message to learners (which may be the acceptors themselves) to inform them of the committed value. Multi-Paxos is more flexible than Raft in terms of how the log is managed — it doesn’t require contiguous log entries, and it can handle out-of-order commits. However, this flexibility comes at a cost: implementers must handle many edge cases, such as gaps in the log, duplicate proposals, and ensuring that a newly elected leader has all committed entries. These details are not fully specified in the original papers, leading to subtle bugs in many implementations.

Raft vs Multi-Paxos: Key Differences

• Leader election: Raft uses randomized timeouts and a term-based voting system, making it easy to reason about. Multi-Paxos does not specify a leader election algorithm; it assumes one exists, and the leader can be any server that has the highest proposal number.
• Log management: Raft enforces a contiguous log with no gaps. Multi-Paxos allows gaps, which can improve efficiency but complicates implementation.
• Commitment: In Raft, an entry is committed when it is replicated on a majority of servers and the leader has committed it. In Multi-Paxos, an entry is committed when a majority of acceptors have accepted it, and the leader can then inform learners.
• Understandability: Raft was designed for teachability and is widely used in education and industry (e.g., etcd, Consul). Multi-Paxos is more abstract and has fewer complete implementations, but it is used in systems like Google’s Spanner and Chubby.
• Failure handling: Raft has explicit rules for handling leader failures, including the restriction that a candidate must have all committed entries to become leader. Multi-Paxos relies on the underlying leader election to handle failures, which can be more complex.

Choosing Between Raft and Multi-Paxos

For most new systems, Raft is the recommended choice due to its clarity and the availability of mature libraries. It is easier to implement correctly, debug, and explain to other engineers. If you need to integrate with an existing Paxos-based system or require the flexibility of non-contiguous logs for performance reasons, Multi-Paxos might be worth considering, but be prepared for a steep learning curve. In practice, many production systems that claim to use Paxos actually use a variant that resembles Raft. The choice often comes down to the team’s familiarity with the algorithms and the specific requirements of the system, such as the need to handle out-of-order commits or to minimize the number of messages per entry.

Common Problems and Misconceptions

One common misconception is that Raft and Paxos are fundamentally different in terms of safety. In fact, both guarantee the same safety properties: agreement, validity, and termination. The difference is in the approach and the ease of implementation. Another misconception is that a majority quorum means you need more than half of the servers, which is true, but it’s also important to remember that the quorum must be a majority of all servers, not just the active ones. A common bug in Raft implementations is not handling the case where a leader receives a request for a term higher than its own; it must step down immediately. In Multi-Paxos, a common issue is the lack of a clear leader election protocol, leading to split-brain scenarios if two leaders are elected simultaneously. To avoid these issues, it’s crucial to follow the algorithm specifications precisely and to test thoroughly with fault injection.

Costs and Trade-offs

Both algorithms require a majority of servers to be available, which means you need at least 3 servers to tolerate 1 failure, 5 servers to tolerate 2, and so on. This increases infrastructure costs. The performance overhead is also non-trivial: each log entry requires a round trip to a majority of servers, which adds latency. However, both algorithms can be optimized with batching, pipelining, and using a more efficient transport. The biggest cost is often the engineering effort to implement and maintain the consensus layer. Raft’s simplicity reduces this cost, but it can still be significant. For systems that don’t require strong consistency, a simpler replication strategy like primary-backup with synchronous replication might be sufficient and cheaper.

Alternatives to Raft and Multi-Paxos

There are other consensus algorithms and approaches that might be more suitable for specific use cases. For example, ZAB (ZooKeeper Atomic Broadcast) is used by Apache ZooKeeper and is similar to Raft but with a different leader election mechanism. Viewstamped Replication is another classic algorithm that predates Raft and is used in some systems. For systems that can tolerate weaker consistency, such as eventual consistency, you might not need consensus at all. For example, CRDTs (Conflict-free Replicated Data Types) allow replicas to diverge and then converge without coordination. If you need high throughput and can accept occasional conflicts, a leaderless approach like Dynamo-style quorum might be more appropriate. However, for linearizable reads and writes, Raft and Multi-Paxos remain the standard choices.

Frequently Asked Questions

What is the difference between Paxos and Multi-Paxos?

Paxos is a single-decree consensus protocol that decides on one value. Multi-Paxos is an extension that uses a stable leader to decide on a sequence of values (a log) efficiently. It avoids the prepare phase for every entry, making it practical for state machine replication.

Why is Raft considered easier than Paxos?

Raft is easier because it decomposes the problem into smaller, more intuitive parts: leader election, log replication, and safety. It uses randomized timeouts and explicit terms, which are easier to reason about. Paxos is more abstract and leaves many implementation details unspecified, leading to subtle bugs.

Can Raft and Multi-Paxos be used for non-replicated systems?

No, they are specifically designed for replicating state across a cluster. They ensure that all servers agree on the same sequence of operations, which is essential for fault tolerance and consistency. If you only need a single server, you don’t need consensus.

What happens if a leader in Raft is partitioned from the rest?

If the leader is partitioned, it will not be able to communicate with a majority of servers, so it cannot commit new entries. The other servers will eventually time out and elect a new leader. The old leader, when it reconnects, will discover a higher term and step down, reverting to follower.

How many servers do I need for a fault-tolerant cluster?

To tolerate F failures, you need at least 2F+1 servers. For example, to tolerate 1 failure, you need 3 servers; to tolerate 2 failures, you need 5 servers. This is because you need a majority to make progress, and with 2F+1 servers, a majority can still be formed even if F servers fail.

Are there any open-source implementations of Raft and Multi-Paxos?

Yes, there are many. For Raft, popular implementations include etcd (Go), Consul (Go), and HashiCorp’s Raft library. For Multi-Paxos, implementations are less common, but you can find them in academic projects and some production systems like Google’s Chubby (though it’s not open source). Open-source examples include the LogCabin project (Raft) and various Paxos libraries on GitHub.

Related

• Long File Names: Limits and What Counts
• Time Management: Evidence & Real-Life Tips
• Apple Watch Series 10 vs Series 9: Full Comparison

in t | Number of servers | servers | 5 | 3
in f | Faults tolerated | servers | 2 | 0
out quorum | Quorum size | servers | floor(t/2) + 1 | 0
out majority | Majority | % | (floor(t/2)+1)/t*100 | 1