Skip to content

Why I keep coming back to Paxos#

2024-05-04

Raft won the mindshare battle around 2014, and for good reason: it's easier to explain, easier to implement, easier to reason about. But every couple years I re-read the Paxos papers and find something new.

The thing Raft glosses over#

Raft's leader-election-plus-log-replication model is a specific choice. It enforces that log entries are committed in order and only by the leader. This is what makes Raft understandable, but it also means:

  • A follower with a longer log cannot be elected leader unless it has the highest-term entries.
  • The leader is a single point for all writes; no parallel-committing.
  • Log truncation happens when a new leader is elected with divergent entries.

Multi-Paxos doesn't have this structure. Each log slot is an independent Paxos instance, which means:

  • Different slots can be committed by different proposers in parallel.
  • There's no leader in the sense Raft means it; there's just a coordinator that proposes for the current view.
  • The "log" is more of a sparse mapping from slot → value.

Why this matters#

For most workloads Raft is fine. But for:

  • Wide-area replication where latency matters more than throughput — Multi-Paxos with a rotating leader (or Fast Paxos) can get you 1-RTT commits under low contention.
  • Sharded systems where you have a lot of slots and want per-slot liveness — Multi-Paxos handles slot-level failures more naturally.
  • Byzantine variants — most BFT protocols descend from Paxos, not Raft.

The papers to read#

  • Lamport, The Part-Time Parliament (1998) — the original, dense, but worth grinding through.
  • Lamport, Paxos Made Simple (2001) — the accessible version.
  • van Renesse & Altinbuken, Paxos Made Moderately Complex (CSUR 2015) — the "here's how you actually implement it" paper.
  • Chandra, Griesemer, Redstone, Paxos Made Live (PODC 2007) — Google's war stories.

Practical note#

If you're picking one to implement, pick Raft. If you're picking one to study, read Paxos. The gap between Paxos-the-idea and Paxos-you-can-ship is enormous, and closing it teaches you a lot about distributed systems.