Consensus: Paxos and Raft

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 3 — Reliability

Layer 3 · Post 20 of 21

← Previous: Split-Brain → Next: Fencing Tokens and Leases

Layer 3 — Reliability · Post 104 of 119

Paxos and Raft are the usual answers to "how do we pick one leader and one history?" in a crash-stop cluster.

What you'll learn

What "consensus" means for a replicated log
Raft as the explainable protocol (leader, terms, majority)
Why you use etcd/Consul/the database's Raft, not a weekend implementation

The idea in one minute

Consensus: a set of machines agrees on one value (or one sequence of values) despite crashes and delays — under crash-stop assumptions, not Byzantine.

Paxos (Lamport) is the classic: proposers, acceptors, learners; prepare/accept; majority. Correct, famously hard to implement from the paper.

Raft (Ongaro / Ousterhout) is the protocol most engineers can draw: elected leader, term numbers, replicated log, majority commit. It is designed to be understandable. Production etcd, Consul, Cockroach, TiKV, and many others speak Raft (or Multi-Paxos that looks similar).

Client --> Leader  --> append entry
             |         replicate to followers
             v
         majority ack --> committed --> apply FSM

Leader election (Post 36) + quorum (Post 37) are the pieces. This post names the log.

Why it matters

Anything that must not split-brain — Kubernetes config, a primary database, a metadata store — either uses one of these or pretends and hopes. Interviews: they will not ask you to prove Paxos. They will ask majority, terms, committed vs acknowledged, and why 3 or 5 nodes.

FLP (Post 101) says you need timeouts to elect. Raft's election timeout is that cheat. Safety is still "one committed log prefix."

How it works

Replicated state machine. If every node applies the same log in the same order, they end in the same state. Consensus is agreement on the log.

Raft, short:

Leader election. Timeouts; candidate increments term; majority of votes; votes remember the term (no two leaders in one term).
Log replication. Leader sends entries. A follower rejects if its log does not match (prev log term/index). Leader repairs.
Commit. Entry is committed when stored on a majority. Then the leader applies and tells followers. A minority partition cannot commit (CP).
New leader. Must have the longest / most up-to-date log among the majority that elected it (Raft's election restriction), so committed entries do not vanish.

Paxos, short: a value is chosen when a majority of acceptors accept it after a prepare that promises not to accept older proposals. Multi-Paxos keeps a stable leader to avoid a full prepare every time. Same majority idea.

What is not in the cartoon: disk, snapshots, configuration changes (membership), linearizable reads (often read index / heartbeat). Those are why you do not type Raft from memory into checkout.

2PC vs consensus. 2PC (Post 46) is atomic commit among participants who already have data. Paxos/Raft is agreeing the decision (or the log) among replicas. Spanner-like systems use consensus inside the commit.

A simple example

etcd, 3 nodes. Kubernetes stores a Deployment. The apiserver writes to etcd. etcd's Raft leader appends, waits for 2/3, then returns. A watcher on another node sees the same revision after commit. If one node is down, still a majority — writes work. If two are down, etcd stops writing. That is consensus doing its job, not an outage of "the algorithm failed."

Implementing this in Redis SET leader without terms is not Raft. That is how split-brain starts.

Common mistakes

Home-grown Paxos. Use etcd, ZooKeeper, Consul, or vendor HA.

Even cluster size (2, 4). Quorum math and ties. Use 3 or 5. (7 is slower elections, rarely worth it.)

"Raft is strongly consistent for my SQL replica." Raft in etcd does not make async Postgres linearizable. Know where the log lives.

Equating Raft with BFT. Crash model. Traitors are Post 100.

Ignoring disk. Consensus that only lives in RAM is a power-cord protocol.

How this shows up in real systems

etcd, Consul, ZooKeeper (Zab): control-plane consensus.
MongoDB replica sets, Cockroach, Yugabyte, TiKV, Redis Raft modules: data-plane cousins.
Kafka KRaft / old ZK: metadata consensus; partition data is still ISR replication (related, not identical).
Chubby / Spanner: Paxos lineage at Google.

Recap

Consensus = one log, majority, crash-stop.
Raft is the picture to draw; Paxos is the ancestor. Do not implement either for fun in prod.
Next: when the old leader was only slow — fencing tokens and leases.