Consensus and Cluster Coordination: Raft, Paxos, Quorum (N/R/W), Gossip Protocol
How several servers agree on the same thing (who the leader is, what the latest value is) when some servers are down or the network breaks.
54.1 Why is it used?
- A distributed system needs exactly one leader; if two leaders appear (split brain) the data can get corrupted.
- Critical data such as config, service discovery and distributed locks must be the same on all nodes.
- The system should keep running even when some nodes fail: decisions are taken by majority (quorum).
- Quorum N/R/W lets you balance consistency and availability (Cassandra, DynamoDB).
- Gossip spreads the health/membership of thousands of nodes to everyone without a central server.
54.2 How it works
- Raft: one leader is elected (term + votes, randomized election timeout); all writes go to the leader, log entries are replicated to followers, and committed after a majority acknowledges.
- Paxos: Proposer, Acceptor and Learner roles; a majority agrees on one value through prepare/promise and accept phases; correct but hard to understand/implement.
- Majority quorum: 2f+1 nodes tolerate f failures: 1 failure with 3 nodes, 2 with 5 nodes; that is why clusters have an odd number (3/5) of nodes.
- Quorum N/R/W: N = copies, W = how many nodes must acknowledge a write, R = how many nodes a read goes to; if R + W > N the read sees the latest write.
- Example N=3: W=2, R=2 gives strong-ish consistency; W=1, R=1 is fast but a stale read is possible.
- Gossip Protocol: every node tells a few random nodes its info (heartbeat, membership) every second; like an epidemic it reaches everyone in O(log N) rounds.
- Failure detection: along with gossip, phi-accrual (Cassandra) or SWIM (Consul/Serf) detects a dead node.
- Fencing token / lease: the leader gets a time-limited lease and an increasing token; if an old leader comes back its writes are rejected.
- 1.kubectl apply -> API server -> 1 write goes to the etcd LEADER (term 4, all writes)
- 2.2 send log entry -> Follower 1 and Follower 2 (etcd)
- 3.3 ack -> Leader + 1 follower = 2 of 3 majority
- 4.4 COMMIT, OK to the client
Raft states: Leader, Follower, Candidate (random election timeout). The 2f+1 rule, keep it odd: 3 nodes tolerate 1 failure, 5 nodes tolerate 2, 4 nodes only 1 (a waste), 2 nodes 0 (no use). Majority = N/2 + 1.
- 1.Follower crash: 2 of 3 alive = majority, the cluster keeps running
- 2.Leader crash: timeout -> Candidate: term 5, votes -> new Leader within seconds
- 3.Network partition: the lone node has no majority, rejects writes, no split brain
- 1.Write v2 with W = 2: A: v2, B: v2, C: v1
- 2.Read R = 2: R + W = 2 + 2 > 3, B is common, so the latest v2 is returned; W=1, R=1 = fast but a stale read
- 3.Gossip (membership & health): round 1 n1 tells 2 random nodes
- 4.Round 2: they pass it on; everyone is reached in O(log N) rounds; a dead node is caught by phi-accrual / SWIM
54.3 Tools
| Tool | Type | How it is used |
|---|---|---|
| etcd | Raft based KV store | All of Kubernetes' cluster state lives in etcd; used for leader election, watches and distributed locks. |
| Apache ZooKeeper | Coordination service (ZAB) | The Paxos-like ZAB protocol; leader election and locks via ephemeral znodes; used in older Kafka, HBase, Hadoop. |
| HashiCorp Consul | Service discovery + KV | A consistent catalog/KV via Raft among servers; membership and health via gossip (Serf/SWIM) among agents. |
| Apache Cassandra | Leaderless wide-column DB | Cluster membership via gossip; N/R/W control via tunable consistency (ONE, QUORUM, ALL). |
| Kafka KRaft | Raft inside Kafka | Newer Kafka versions drop ZooKeeper and use a built-in Raft controller quorum for metadata. |
| Amazon DynamoDB | Managed NoSQL | Manages replication/quorum internally; offers an eventually consistent or strongly consistent read option. |
54.4 Comparison: etcd vs ZooKeeper vs Consul vs Cassandra
| Point | etcd | ZooKeeper | Consul | Cassandra |
|---|---|---|---|---|
| Protocol | Raft | ZAB (Paxos-like) | Raft (servers) + Gossip (agents) | Gossip + quorum (leaderless) |
| Consistency | Strong (linearizable) | Strong writes, reads can be slightly stale | Strong for KV/catalog (default mode) | Tunable: from ONE to ALL |
| Leader | Yes, one leader | Yes, one leader | Yes (in the server cluster) | No, any node can be the coordinator |
| Data size | Small metadata (MBs-GBs) | Small metadata | Small KV + service catalog | Large data (TBs-PBs) |
| Typical cluster | 3 or 5 nodes | 3 or 5 nodes | 3-5 servers + thousands of agents | Dozens to hundreds of nodes |
| API / ease | gRPC/HTTP, simple | Java client, older style | HTTP, DNS, UI: easy | CQL (SQL-like) |
| Best for | Kubernetes, config, leader election | Legacy Hadoop/Kafka ecosystem | Service discovery + health checks | High write throughput data storage |
54.5 When to choose which
- etcd: config, leader election and locks in Kubernetes or a cloud-native app.
- ZooKeeper: when you are already in the Hadoop/HBase/older Kafka ecosystem; chosen less in new projects.
- Consul: multi-datacenter service discovery, health checks and DNS-based lookup.
- Cassandra (quorum + gossip): very large data, high writes, and availability > strict consistency.
- Do not implement Raft/Paxos yourself: use a tested library/tool.
54.6 Real-world example
etcd in the Kubernetes control plane (an illustrative setup).
- A production Kubernetes cluster has 3 or 5 etcd nodes; they hold all of the cluster's state (pods, deployments, secrets).
- Raft elects one etcd leader; every kubectl apply write reaches the leader through the API server.
- The leader sends the entry to followers; it commits once 2 of 3 (a majority) acknowledge.
- One etcd node crashes: the other 2 are a majority, so the cluster keeps running.
- The leader crashes: the followers' election timeout expires, a new term, votes, and a new leader within seconds.
- Network partition: 1 node is cut off, cannot get a majority, so it accepts no writes; no split brain.
- Alongside, in a data store like Cassandra, N=3, R=QUORUM, W=QUORUM (2+2>3) means reads return the latest data.
54.7 Interview tips
- Explain the R + W > N formula and the 2f+1 rule with an example; remember Raft's 3 states (Leader, Follower, Candidate).
- Common mistake: running an even number of nodes (2 or 4); 4 nodes also tolerate only 1 failure, same as 3; keep it odd.
- Using etcd/ZooKeeper as a general database to store large data; they are meant for metadata.
- Spreading a consensus cluster across high-latency regions: every write waits for a majority, so latency rises. Number to quote: 3 nodes = 1 failure, 5 nodes = 2 failures.