Skip to content

Multi-Paxos vs Raft log matching#

2024-06-30

A subtle difference between Multi-Paxos and Raft that trips people up: Raft's log matching property vs Multi-Paxos's more relaxed invariant.

Raft: strict prefix matching#

Raft guarantees that if two logs have an entry with the same index and term, then:

  1. They have the same command.
  2. All preceding entries are also identical.

This is enforced by the AppendEntries consistency check: the leader includes (prevLogIndex, prevLogTerm) and the follower rejects if it doesn't match. Mismatched suffixes get truncated.

Consequence: at any moment, the majority of servers agree on a common prefix. Reads from any follower with the leader's latest committed index are safe.

Multi-Paxos: per-slot agreement#

Multi-Paxos treats each log slot as an independent Paxos instance. The protocol only guarantees:

  1. Each slot has at most one committed value.
  2. The values across slots may commit in any order.

There is no cross-slot dependency at the protocol level. Slot 5 can commit before slot 3. The "log" is technically a partial function, not a sequence.

What Multi-Paxos does in practice#

Real implementations (Google Chubby, Multi-Paxos in Ceph) do enforce sequential commits at the application level — you can't apply slot 5 to the state machine until slot 4 is applied. But the underlying protocol lets slot 5 be decided first; it just waits in a buffer.

This is actually useful: under network partitions where slot 4 is stuck, other proposals can still make progress and be applied later when slot 4 recovers.

Why Raft's approach is simpler#

Raft chose strict log matching to make reasoning trivial: "the leader's log is the log." Multi-Paxos requires you to think about "decided but not yet applied" slots.

Both are correct; Raft is easier to explain.

Reference#

  • Ongaro's Raft dissertation, chapter 5 (log matching invariant).
  • van Renesse & Altinbuken, Paxos Made Moderately Complex.