Back to System design

Consensus: Raft and Paxos in Plain English

hard
Scale: Write latency = 1 RTT to majority; reads = leader RTT or lease-fast Storage: Log + snapshot per node; logs truncated after snapshots Google, CoreOS/etcd, Cockroach
FundamentalsConsensusDistributed Systems

Consensus is the problem of getting distributed nodes to agree on a value (or sequence of values) despite some failing or being temporarily unreachable. It's the foundation of every strongly consistent distributed system: etcd, ZooKeeper, Spanner, CockroachDB, Kafka KRaft.

ScaleWrite latency = 1 RTT to majority; reads = leader RTT or lease-fast
StorageLog + snapshot per node; logs truncated after snapshots

Key Concepts

1
1. Raft in three sub-problems. Leader election: followers timeout → candidate, request votes, majority wins for the term. Log replication: leader appends to local log → sends AppendEntries → commits once a majority acks. Safety: only nodes whose log contains all committed entries from prior terms can be elected leader (leader completeness).
1. Raft in three sub-problems.AppendEntries
2
2. Why odd-numbered clusters. Tolerate (N-1)/2 failures and avoid split votes. 3 nodes tolerate 1 failure (need 2 to write); 5 tolerate 2 (need 3). Going to 7+ increases latency without increasing fault tolerance for typical single-failure-at-a-time scenarios. Even numbers (4, 6) are bad — same fault tolerance as 3, 5 but higher split-vote risk.
2. Why odd-numbered clusters.(N-1)/2
3
3. Paxos preceded Raft. Same guarantees; famously harder to understand. Multi-Paxos (stable leader for many instances) ≈ Raft. Spanner uses Paxos per group ('Paxos groups'); Google's Chubby uses Paxos. New systems generally pick Raft for the implementation ecosystem (etcd/io Raft, HashiCorp Raft).
3. Paxos preceded Raft.
4
4. Read scaling is the achilles heel. Every linearizable read traditionally goes to the leader (or does a ReadIndex / quorum read). Adding nodes does not scale reads under strong consistency. Workarounds: lease reads (leader serves reads locally during a lease window), follower reads with read indexes that confirm the follower is up-to-date, or stale reads that explicitly relax consistency.
4. Read scaling is the achilles heel.
5
5. Production essentials. Snapshot periodically so the log doesn't grow forever; truncate up to the snapshot. Membership changes use joint consensus (Cold ∪ Cnew) or single-node-at-a-time — naive replacement can create two majorities. Never roll your own: use etcd, ZooKeeper, Consul, or an embedded library. The bug surface is enormous and silent data loss is the failure mode.
5. Production essentials.

Related Problems

CAP Theorem and PACELCeasyLoad Balancing: L4 vs L7, Algorithms, Health CheckseasyCaching Strategies: Cache-aside, Write-through, Write-backeasySQL vs NoSQL: When to Pick WhicheasySharding Strategies: Range, Hash, Directory, Geomedium

Approach

  1. Pick an existing implementation: etcd, ZooKeeper, Consul, or roll consensus into your system via a library (HashiCorp Raft, Etcd-io Raft).
  2. Size the cluster — 3 nodes (1 failure tolerated) for non-critical; 5 for high availability.
  3. Always odd-numbered. Even = split-vote risk; the extra node doesn't increase fault tolerance.
  4. Snapshot regularly; truncate log to bound growth.
  5. Use joint consensus for membership changes, never naive replace.
  6. For read scaling, use leader lease + ReadIndex; only relax to follower reads if your consistency story allows it.
  7. Geo-distribute carefully — latency-bound; cross-region writes hurt. Often run consensus per-region with cross-region async replication.
  8. Monitor leader election rate, commit latency, log size, snapshot age.

Raft in detail

Three roles: follower, candidate, leader.

Term: monotonically increasing logical clock. Each term has at most one leader.

Election: follower timeout → candidate → request votes → majority → leader.

AppendEntries: leader sends entries with prev-log-index + prev-log-term. Followers reject if mismatch (log-matching property).

Commit: leader marks entry committed once majority has it; applies to state machine.

Safety: leader-completeness — leader for term T contains all entries committed in prior terms.

Membership change: joint consensus (Cold ∪ Cnew) or single-node-at-a-time.

Components

  • Replicated log on each node (append-only, persistent).
  • State machine that applies committed entries deterministically.
  • Term number (logical clock).
  • Heartbeats from leader (also serve as keepalive).
  • Election timer (randomized to avoid simultaneous candidacies).
  • Snapshot mechanism + log truncation.
  • Membership configuration (joint consensus protocol).
  • ReadIndex / lease for consistent reads.

Trade-offs

Strong consistency at the cost of majority availability. Lose quorum, lose writes.

Read scalability is poor by default — every read goes through leader for strong consistency.

Write latency bounded by 1 cross-node RTT — fast within DC, slow across regions.

Membership changes are subtle — easy to get wrong without joint consensus.

Snapshotting is essential for any long-running cluster.

Operational complexity: leader election storms, slow followers, network partitions all need handling.

Common interview/practice mistakes

  • Even number of nodes (4, 6). Doesn't help fault tolerance, increases split-vote risk.
  • Believing reads scale by adding nodes. They don't, unless you relax consistency.
  • Running 7+ nodes for 'safety'. Latency degrades; same fault tolerance as 5.
  • Cross-region consensus for low-latency workloads. Geo-Raft is real but slow; consider regional + replication.
  • Rolling your own. The bug surface is enormous; use etcd, ZooKeeper, or libraries.