Consensus Algorithms: Raft and Paxos

Consensus is the problem of getting several machines to agree on a value, or a sequence of values, even when some of them crash or messages are delayed. It's the foundation of anything that needs one source of truth across machines: leader election, configuration stores, distributed locks, and strongly consistent replicated databases. Raft and Paxos are the two best-known algorithms.

What consensus guarantees

• Agreement: all non-faulty nodes decide the same value.
• Validity: the decided value was proposed by some node.
• Termination: eventually a decision is reached, as long as a majority of nodes are up and can talk to each other.

Majorities are the trick. Any two majorities of the same cluster overlap in at least one node, so two conflicting decisions can never both win. A cluster of 2f + 1 nodes tolerates f failures: 3 nodes survive 1 failure, 5 survive 2. That's why consensus clusters have odd sizes; a 4th node adds cost without extra fault tolerance.

Raft in three parts

Raft was designed to be understandable. Each node is a follower, candidate or leader, and time is divided into numbered terms.

1. Leader election

• Followers expect regular heartbeats from the leader. If one hears nothing for a randomised election timeout (for example 150–300 ms), it becomes a candidate, increments the term, votes for itself and asks others for votes.
• A node votes for at most one candidate per term, and only for a candidate whose log is at least as up to date as its own.
• A candidate with votes from a majority becomes leader. Randomised timeouts make split votes rare.

2. Log replication

Every node applies committed log entries, in order, to its own state machine (a key-value map, say). Since all logs are identical up to the commit point, all state machines end up identical. This is state machine replication.

3. Safety

Raft guarantees a committed entry is never lost: a new leader must have every committed entry (enforced by the voting rule), and leaders never overwrite their own log. Followers with conflicting uncommitted entries are brought back in line by the leader.

Paxos

Paxos (Leslie Lamport) solves the same problem with proposers, acceptors and learners in two phases: proposers obtain promises from a majority of acceptors for a numbered proposal, then ask them to accept a value. Multi-Paxos elects a stable leader to skip the first phase for each value, which makes it behave much like Raft. Paxos is proven and flexible but notoriously hard to implement correctly, which is why Raft became popular.

Costs and limits

• Latency: every write needs a round trip to a majority; across regions that means tens to hundreds of milliseconds per commit.
• Throughput is bounded by the leader; scale by partitioning data into many independent consensus groups (as CockroachDB, TiKV and Spanner do).
• Availability: a minority partition can't make progress, which is the CP choice in the CAP theorem.
• Crash failures only: Raft and Paxos assume nodes don't lie. Tolerating malicious nodes needs Byzantine fault-tolerant protocols, as in blockchains.

Use it, don't build it

Implementing consensus correctly is very hard. Systems almost always use an existing consensus service or library: etcd (Raft), ZooKeeper (ZAB, a Paxos-like protocol), Consul (Raft), or a database that embeds Raft or Paxos. Typical uses: storing cluster membership and configuration, leader election, distributed locks, and strongly consistent metadata.