Paxos and Raft Overview for System Design
On this page
Agreeing without a referee
Three servers hold the configuration for your system. A client sets max_connections = 500. One server is slow, one crashes mid-update. Afterwards, the three must still agree on the current value, and on the order of every change before it. With no shared memory, an unreliable network and machines that fail, how do they agree?
That's consensus: getting several nodes to agree on a single value, or a single ordered log of operations, while tolerating some node failures. It's the foundation under leader election, distributed locks, configuration stores and strongly consistent replicated databases.
What are Paxos and Raft?
Paxos, by Leslie Lamport (published 1998), was the first widely studied consensus algorithm with a correctness proof. It's notoriously hard to understand and to implement correctly from the paper.
Raft, by Diego Ongaro and John Ousterhout (2014), solves the same problem and was designed to be understandable. Most modern systems use Raft: etcd (which stores Kubernetes' state), Consul, CockroachDB, TiKV, RabbitMQ quorum queues and Kafka's KRaft mode.
How Raft works, in three ideas
1. One leader at a time. Nodes are followers, candidates or the leader. The leader handles all writes. If followers stop hearing its heartbeats, one becomes a candidate and asks for votes; whoever gets a majority becomes leader for a new term (Day 63).
2. A replicated log. The leader appends each write to its log and sends it to followers. An entry is committed once a majority of nodes have stored it. Only then does the leader apply it and reply success. Committed entries are never lost, because any future leader must have them: a candidate without the latest committed entries can't win a majority vote.
3. Majorities overlap. Any two majorities of the same cluster share at least one node. That's why two leaders can't both commit conflicting entries for the same term, and why a minority side of a network partition can't make progress.
Why consensus clusters use 3 or 5 nodes
A cluster of N nodes needs a majority, more than N/2, to make progress. So it tolerates the failure of the rest:
| Nodes | Majority | Failures tolerated |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
Four nodes tolerate no more failures than three and add latency, so clusters use odd numbers. More nodes also mean more replication per write, so 3 or 5 is typical.
Where consensus is used: etcd, ZooKeeper and Kafka
You'll rarely implement consensus yourself, and you shouldn't. You'll use systems built on it:
- etcd, ZooKeeper, Consul for configuration, service discovery, leader election and locks.
- Distributed SQL databases (CockroachDB, Spanner, YugabyteDB) that replicate each data range with consensus.
- Kafka for cluster metadata, and RabbitMQ quorum queues.
The trade-off is the CAP one (Day 5): consensus systems are CP. A minority partition stops accepting writes rather than risk disagreement, and every write waits for a majority, adding latency, especially across regions.
What consensus costs per write
Each committed write needs a round trip from the leader to a majority, plus a durable write to disk on each of them. Inside one data center that's typically a few milliseconds. Spread a 5-node cluster across three regions, and every write waits for a cross-region round trip, often tens of milliseconds or more. Consensus stores are built for small, important data, not bulk data.
That's also why etcd sets a storage quota, 2 GB by default, and the Kubernetes docs warn against large etcd databases. Store configuration, leases and locks in it; keep your orders and logs elsewhere.
Reads have a subtlety too. A follower may be slightly behind the leader, so a read from a follower can be stale. Systems that promise up-to-date reads route them through the leader, which first confirms it's still leader with a majority. etcd's default reads do this; its "serializable" read option trades freshness for speed.
To go further, with leader election and log replication step by step, see the consensus course.
Check yourself
When the leader has replicated it to a majority of the cluster, counting itself. Only then does the leader apply it to its state machine and acknowledge the client. A majority guarantees that any future leader, which also needs a majority to win, will already have the entry.
Both need a majority of 3 or more; 4 nodes tolerate only one failure, the same as 3, while 5 tolerate two.
etcd is for small coordination data. Every write pays a majority round trip and the store has a size quota. Keep orders in a database built for volume.
The group of 3, because it holds a majority of the 5 nodes, so it can elect a leader and commit writes. The group of 2 can't reach a majority, so it stops accepting writes rather than risk two sides diverging. When the partition heals, the 2 nodes catch up from the majority's log.
The leader must send the entry to followers and wait for a majority to store it, so each write includes at least one network round trip and disk syncs on several machines. That's why consensus stores like etcd hold small, critical coordination data, not high-volume application data.