Overview
Consensus is getting multiple nodes to agree on a single value or a sequence of values, even when some nodes crash or messages are delayed. It is the foundation for leader election, replicated logs, distributed locks, and configuration stores. Paxos and Raft are the most famous algorithms; Raft was designed to be easier to understand.
Raft elects a leader using majority votes; the leader appends client commands to its log and replicates them to followers; an entry is committed once a majority has stored it. Because any two majorities overlap, committed entries survive leader changes. A cluster of 2f + 1 nodes tolerates f failures, which is why clusters are usually 3 or 5 nodes.
A verdict needs a majority. Even if some jurors are absent, a majority decision stands, and because any two majorities share at least one juror, the jury can never later record two contradictory verdicts.
When to use it
- Leader election and cluster membership.
- Strongly consistent metadata and configuration.
- Distributed locks with fencing.
- Replicated state machines (etcd, CockroachDB ranges).
Where it shows up in interviews
Recognize it when: strongly consistent config, locks, or leader.
- Design a distributed lock service
- Design a service discovery system
Recognize it when: every replica must apply the same operations in order.
- Design a distributed key-value store with strong consistency
- Design a replicated job queue
Where it is used in real software
Stores all Kubernetes cluster state; the API server depends on it for consistency.
Coordination for Kafka (older versions), HBase, and Hadoop.
Each data range is a Raft group, providing strongly consistent distributed SQL.
Key terms
- Term
- Raft's logical epoch; increases with each election.
- Log replication
- Leader sends entries; followers append in order.
- Commit
- An entry stored on a majority; safe to apply.
- Election timeout
- Randomized wait before a follower becomes a candidate.
- Safety vs liveness
- Never disagree vs eventually make progress.
How it works, step by step
- 1Followers wait for heartbeats
Randomized election timeouts (for example 150-300 ms).
- 2Candidate requests votes
Increments the term; wins with a majority.
- 3Leader appends client commands
Sends AppendEntries to followers.
- 4Commit on majority
Once a majority stores an entry, it is committed and applied.
- 5Handle failures
New elections on leader failure; logs are repaired to match the leader.
STEP 1The client sends SET x = 7. The leader appends it to its log at index 12 (uncommitted).
Cluster size and fault tolerance
Majority = floor(n / 2) + 1
| Nodes | Majority | Failures tolerated | Note |
|---|---|---|---|
| 1 | 1 | 0 | No fault tolerance |
| 3 | 2 | 1 | Common minimum |
| 4 | 3 | 1 | No better than 3, more cost |
| 5 | 3 | 2 | Common for production |
| 7 | 4 | 3 | Slower writes |
NOWNodes: 1 | Majority: 1 | Failures tolerated: 0 | Note: No fault tolerance
Use odd cluster sizes. More nodes increase fault tolerance but every write must wait for more acknowledgments.
Implementation
// Core Raft voting rule (simplified)type VoteRequest = { term: number; candidateId: string; lastLogIndex: number; lastLogTerm: number }; class RaftNode { currentTerm = 0; votedFor: string | null = null; log: { term: number; command: string }[] = []; handleRequestVote(req: VoteRequest): { term: number; granted: boolean } { if (req.term < this.currentTerm) return { term: this.currentTerm, granted: false }; if (req.term > this.currentTerm) { this.currentTerm = req.term; this.votedFor = null; } const myLastTerm = this.log.at(-1)?.term ?? 0; const candidateUpToDate = req.lastLogTerm > myLastTerm || (req.lastLogTerm === myLastTerm && req.lastLogIndex >= this.log.length); const granted = (this.votedFor === null || this.votedFor === req.candidateId) && candidateUpToDate; if (granted) this.votedFor = req.candidateId; // persisted to disk in a real implementation return { term: this.currentTerm, granted }; }}Complexity and performance
Crash faults.
Milliseconds in one region.
Trade-offs
Consensus is slower than asynchronous replication and cannot make progress without a majority.
Larger clusters tolerate more failures but have slower writes.
Variants and related techniques
Paxos with a stable leader; used in Spanner and Chubby.
Many Raft groups, one per data range, for horizontal scaling.
Tolerates malicious nodes; used in blockchains.
Common mistakes
- Running consensus clusters across high-latency links casually.
Fix: Every write waits for a majority; place nodes to balance latency and fault tolerance.
- Using consensus stores for large data.
Fix: etcd and ZooKeeper are for small metadata, not bulk storage.
Interview questions
How does Raft guarantee committed entries are never lost?
An entry is committed only after a majority stores it, and a candidate can win an election only if its log is at least as up-to-date as a majority's. Since majorities overlap, any new leader must already have every committed entry.
Why use 5 nodes instead of 4?
Both need a majority of 3 for progress, but 5 nodes tolerate 2 failures while 4 tolerate only 1. Even sizes add cost without improving fault tolerance.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Trace a Raft election with a network delay | Medium | Terms and votes. |
| Design a configuration service on Raft | Hard | Replicated state machine. |