Consensus (Paxos and Raft)

01The intuition

The problem it solves

Five friends want to pick a restaurant by text message. Messages arrive late, some are lost, and one friend's phone dies halfway through. If each friend just goes where they think the majority said, two groups end up at two restaurants. What they need is a rule such that, whatever is lost and whoever drops out, everyone who does decide decides the same restaurant, and the group does decide as long as a majority is still texting.

Replace friends with five database replicas and the restaurant with "which write is next in the log". If replicas disagree about the order of writes, two of them can both believe they hold the latest balance of an account, and both are wrong. Consensus is the family of protocols, Paxos and Raft being the famous ones, that make a set of machines agree on one value, or one sequence of values, even when machines crash and messages are delayed, as long as a majority stays alive.

Build it one piece at a time

Step 1: majority, not unanimity. With 5 machines, require 3 to agree. Any two majorities share at least one machine, so two different values cannot both be chosen by a majority. This overlap is the whole secret, and it is why clusters have odd sizes: 3 survives 1 failure, 5 survives 2.

Step 2: a leader proposes. Rather than everyone proposing at once, elect one machine as leader for a term. The leader receives client writes, appends each to its log, and sends it to the others. A follower appends it and replies. When the leader hears from a majority (itself plus 2 of 4), the entry is committed: it will never be lost, because any future majority contains a machine that has it.

Step 3: elect a new leader safely. When followers stop hearing the leader's heartbeat, one starts an election for the next term and asks for votes. A machine votes only for a candidate whose log is at least as up to date as its own, and only once per term. A majority of votes makes a leader. Because the candidate needs a majority and committed entries live on a majority, the new leader always has every committed entry: in the table, C or D cannot win against A or B.

Step 4: terms stop the old leader. The crashed leader may come back and think it still leads. Every message carries the term number; a message from an old term is rejected, so a stale leader cannot commit anything. This is what makes split brain impossible.

Step 5: use it for the small things. Consensus costs a round trip to a majority for every write, so it is used for what must be exactly right and is not huge: the configuration of a cluster, who the leader of each shard is, locks, the metadata of a file system. Bulk data flows through simpler replication and relies on consensus only to decide who is in charge.

Why it works, with the numbers

A write is committed after one round trip from the leader to the nearest majority. Within a data center that is about 1 ms; across three continents it is the time to the second-closest region:

commit latency ≈ max over the fastest (N/2) followers of the round trip ≈ 1 ms local, 50–100 ms across regions

and throughput is limited by the leader's ability to send and receive, typically tens of thousands of entries a second, which is why entries are batched. The safety guarantee is unconditional: no two machines ever commit different values at the same log position, whatever the timing. The liveness guarantee is conditional: progress requires a majority alive and talking. The failure modes are losing a majority (the cluster stops writing rather than diverging, by design), repeated elections when heartbeats are too tight for the network, and the leader as a throughput bottleneck.

The trade-off you must say out loud

Correctness against latency and throughput. Say the cluster size and how many failures it survives, where the replicas are and therefore the commit latency, and what the system does when a majority is lost (it stops, and that is the right answer). The follow-up is "why not just use the database's replication", and the answer is that asynchronous replication can lose acknowledged writes on failover, and consensus is the price of not losing them.

Where it shows up in the 100 Google problems

• Globally consistent database: every shard is a Paxos group across regions; the commit latency is the geography.
• Distributed lock service: a five-replica consensus cell that stores locks and small files, as Chubby does.
• Configuration service: flag changes are committed through consensus so every server sees them in the same order.
• Managed pub/sub: which replica leads each partition is decided by consensus; the messages themselves are replicated more cheaply.

02Used in these problems

• Design a globally consistent, multi-region database (Spanner)
• Design a managed pub/sub or message queue with replay
• Design a distributed lock service (Chubby)
• Design a global configuration and feature-flag service