Distributed consensus

Getting a group of machines to agree on one value, while some are crashed and messages are being dropped, is the hardest problem in distributed systems. It underpins leader election, distributed locks, and every strongly consistent database, and it is the most expensive thing you can put on a request path, so the judgment is mostly about where not to use it.

Leader election in Raft after the leader fails100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

What agreement has to survive

Nodes crash mid-operation, messages arrive late or out of order, and no global clock exists to order two events. What makes it hard is that a crashed node and a slow node look identical from outside: a short timeout declares healthy nodes dead, a long one stalls the cluster.

Consensus is agreement on an ordered sequence of operations even when a bounded number of participants fail. That sequence is a replicated log: feed replicas the same operations in the same order and their states stay identical. Leader election reduces to it, the primitive underneath distributed locking, and so does atomic commit, where replicating the coordinator's decision stops two-phase commit blocking when that coordinator dies.

Why a majority

Progress requires acknowledgement from a quorum, more than half of an agreed membership list. One property does all the work: any two majorities of the same set overlap in at least one node, so a new majority always contains a member that saw what the previous one committed.

3 nodes -> majority 2 -> survives 1 failure
4 nodes -> majority 3 -> survives 1 failure
5 nodes -> majority 3 -> survives 2 failures

Four nodes tolerate exactly what three do while adding a machine that can fail and an ack every commit waits on, so even sizes are strictly worse than the odd size below. Placement matters as much as count: with three nodes in two zones, losing the zone holding two leaves one of three, below majority, and writes stop. Five across three zones (2+2+1) survives any single zone — the redundancy rule applied to a quorum, since copies that fail together are one copy.

What a commit costs

Every committed entry costs one round trip from the leader to a majority, plus a durable write on each node that acks. In the 2+2+1 layout no majority fits inside one zone, so that round trip crosses a zone boundary: call it ~1 ms, twice the 0.5 ms in-datacenter hop on the latency ladder. The ladder has no entry for a durable write, only an SSD random read at 100 µs; an fsync must reach stable storage, so assume ~1 ms on commodity SSD.

round trip to a follower in another zone   ~1 ms
that follower's fsync before it acks       ~1 ms
                                           ------
commit latency floor                       ~2 ms   per entry

The leader's own fsync overlaps that round trip, so there is no third term. What the floor is not is a throughput ceiling. A Raft leader pipelines, sending the next AppendEntries before the previous entry commits, so Little's Law applies: throughput = entries in flight ÷ latency. Twenty proposals in flight at a 2 ms floor is 10,000 commits/s; only a client holding one request outstanding sees 1 ÷ latency.

What caps a single group is the leader: one process appends, fsyncs, ships every entry to both followers, tracks their match indexes, and applies the result, all on one disk. Group commit amortises the fsync across batched entries, so batching fifty entries per round trip raises the ceiling and not only the entry count. A tuned group manages tens of thousands of small entries a second, bought not for throughput but for a log a majority cannot lose.

Across regions the cost stops being a rounding error. With the leader in Mumbai and enough voters in US East that a majority needs a remote ack, the ~200 ms round trip floors every write; at 500 write QPS that is 500 × 0.2 s = 100 writes in flight, a pool-sizing problem before it is a latency one.

Reads are not free either: a leader paused on garbage collection still answers from local state, so a strongly consistent read needs a lease or read-index check, another majority round trip. On a partition the minority side refuses writes rather than diverge, the CP choice, and with no partition the group still pays that round trip rather than answering locally, so under PACELC it is PC/EC. Consistency models covers the rest of that dial.

Paxos and Raft

Paxos (Leslie Lamport) came first and is notoriously hard to implement without subtle bugs; Raft (Diego Ongaro and John Ousterhout) targets the same safety while being understandable, splitting the problem into leader election plus log replication. Two rules carry that safety. Terms are a logical clock: a node votes at most once per term, so two leaders can never win one, and any node seeing a higher term steps down — how a returning leader learns it was replaced. The election restriction: a voter refuses a candidate whose log is behind its own, so by majority intersection the winner already holds every committed entry.

You consume these rather than build them: etcd and Consul (Raft) and ZooKeeper (ZAB) supply leader election, configuration and locks, and Kubernetes stores its cluster state in etcd. Spanner (Paxos), CockroachDB and TiDB (Raft) run one group per key range — thousands of groups, each with its own leader and disk, which is how they clear the single-leader ceiling.

When not to reach for it

The alternative you are rejecting is a single leader with asynchronous followers. It commits on its own fsync with no majority wait, ~1 ms rather than ~2 ms, and never waits on the slowest node of a quorum or a cross-region link. The price is the un-replicated tail: on failover, acknowledged writes the leader had not shipped are gone. Choose on RPO — if the last few hundred milliseconds are survivable, replication is cheaper. The usual shape is both: consensus on the control plane, where the rate is tiny and correctness absolute, and asynchronous replication on the data plane, where the volume is.

In an interview

What is tested is whether you recognise which problems need agreement, reach for an existing coordination service rather than writing one, and — the part that separates candidates — can price it.

Say it with the numbers attached: "Leader election goes through etcd, which is Raft internally. Five nodes across three availability zones, so losing a zone still leaves a majority. Each committed entry costs a cross-zone round trip plus a follower fsync, about 2 ms, so the group stays in one region and cross-region replication is asynchronous. That is CP at partition time, PC/EC under PACELC."

The mistake that loses points is calling a consensus-backed store the highly available option. It is the opposite: it stops serving the minority side of a partition on purpose, and that refusal is the feature. A close second is routing every user write through one group without pricing the ~2 ms floor per commit or the single leader and disk carrying the entire write path.

Check yourself

1. Five etcd nodes sit 2+2+1 across three zones and the zone holding two fails. Are writes still accepted, and how much headroom is left?

Three of five survive, a majority, so writes continue, with no headroom: one more failure leaves two and the cluster goes read-only. Compare the sizing someone will propose instead. Three across two zones survives losing the single-node zone, since two of three is still a majority, but stops when the two-node zone goes. Surviving any one zone is what the extra pair buys.

2. Your p99 write budget is 150 ms and someone proposes five voters, leader in Mumbai, three in US East. Does it fit?

No. With three of five voters remote, no majority forms in-region, so every commit waits the ~200 ms round trip, over budget before any application work. Put three of the five in-region and a majority commits in ~2 ms, the remote nodes trailing as extra copies. A majority genuinely spanning both regions cannot fit under the ladder's ~200 ms at all; add the fsync and the request's own work and the budget starts near 250 ms.

3. The write path is 40,000 QPS. Does it go through one Raft group?

Not on its own, though not because the floor forbids it: 2 ms is a latency, not a ceiling, and Little's Law gives 40,000 × 0.002 s = 80 entries in flight, which a pipelining leader can hold. The problem is where they land — one process doing 40,000 appends and group-committed fsyncs a second, 80,000 outbound AppendEntries and 40,000 applies, all on one disk. That is the top of what a tuned group manages, with nothing spare for the 2–5× peak over average, and one failover stops the whole write path. Shard into independent groups, as CockroachDB and TiDB do per key range, or keep consensus off the data path.