Quorum and leader election

When data is copied across machines, which copy is right? When one machine must make decisions, which one is it? Both questions are about agreement in a system where machines fail and messages are lost. Two patterns answer them: the quorum and the leader and follower arrangement with elections.

A quorum is the minimum number of nodes that must take part for an operation to count. The usual rule is a majority: more than half, which is floor(N / 2) + 1.

The reason is simple geometry. Any two majorities of the same group must overlap in at least one node. So if a write was acknowledged by a majority, and a later read asks a majority, the read is guaranteed to meet at least one node that saw the write.

• N = 3 needs 2 and tolerates 1 failure.
• N = 5 needs 3 and tolerates 2 failures.
• N = 4 needs 3 and still tolerates only 1, so an even number buys nothing. Clusters use odd sizes.

For replicated data you can also pick separate counts, W for writes and R for reads, with the rule R + W > N. Raising W makes reads cheaper and writes slower, and the reverse. A quorum also protects against a partition: only the side holding a majority can proceed, so two sides never both act.

Coordinating every node on every operation is slow and complicated. A simpler arrangement picks one node as the leader. The leader receives all writes, decides their order, and sends them to the followers, which apply them in the same order. Reads may go to the leader, or to followers if slightly old data is acceptable.

This gives a single, clear order of events, which is what keeps replicas identical. The price is that the leader is a bottleneck and a point of failure, so if it dies, the group must quickly elect a new one.

Consensus protocols such as Raft make election safe. A simplified view of Raft:

1. Time is divided into terms, numbered upward. Each term has at most one leader.
2. Every follower expects regular heartbeats from the leader. If one arrives too late, a follower waits a randomized timeout, so nodes rarely start together, then becomes a candidate, increases its term, votes for itself and asks the others for votes.
3. Each node votes for at most one candidate per term. A candidate that gets a majority becomes the leader and starts sending heartbeats.
4. If no one wins, because votes split, the timeouts expire again and a new term begins. Randomization makes this resolve quickly.
5. A candidate whose log is less up to date than a voter's does not get that vote, so a new leader always has every committed entry.

The leader appends a write to its log and sends it to followers. Once a majority have stored it, the entry is committed, and the leader applies it and replies to the client. If the leader crashes afterwards, any new leader, chosen by a majority, must have the entry, because the majorities overlap.

• Leader fails: the cluster has no leader for a short election, typically under a second or so, then continues. Writes pause during this window.
• Minority partition: a group that cannot reach a majority cannot elect a leader and cannot commit writes. This is the consistency-over-availability choice from CAP.
• Old leader returns: it sees a higher term, steps down, and catches up from the new leader.

etcd, ZooKeeper, Consul, and the metadata layer of Kafka use majority-based leader election. Chubby uses Paxos for the same purpose. Databases use a leader per shard, with the quorum guarding the failover.

• Benefit: simple reasoning, a single ordering of writes, and automatic recovery.
• Cost: the leader limits write throughput, a short unavailability during elections, and more replicas mean more messages per write. Keep consensus groups small, 3 or 5, and use them for coordination data, not for bulk data.