Consensus (Paxos & Raft)

1. What Is It?

Distributed consensus is the problem of getting a set of distributed nodes to agree on a single value — even when some nodes may crash, messages may be delayed, and the network may partition. This is the foundation of strong consistency in distributed systems.

A quorum is a majority of nodes in the cluster (e.g., 2 out of 3, or 3 out of 5). Consensus algorithms require a quorum to agree before any decision is final — this prevents two conflicting decisions from being made simultaneously.

Without consensus, distributed systems have no reliable way to elect a single leader, commit a transaction across nodes, or ensure a log is written in the same order everywhere. Consensus is what makes etcd the trusted source of truth for Kubernetes cluster state, what makes CockroachDB's transactions serializable across 10 nodes in 3 datacenters, and what makes ZooKeeper safe for distributed locks.

Paxos (Leslie Lamport, 1989/1998) was the first proven consensus algorithm and remains the theoretical foundation. Raft (Diego Ongaro and John Ousterhout, 2014) was designed to be equivalent in guarantees but dramatically easier to understand and implement — Raft is the dominant algorithm in modern systems and the one you should know for interviews.

2. How It Works

The Consensus Problem

Nodes: A, B, C (N=3)
Goal: All agree on the same value V

Constraints:
  1. Safety (agreement):  No two nodes decide different values
  2. Safety (validity):   The decided value was proposed by some node
  3. Liveness:            Eventually, some value is decided

Hard part: Network can delay/drop messages. Node B might crash.
           How do A and C know if B crashed vs. the message was delayed?

FLP Impossibility (Fischer, Lynch, Paterson, 1985): In theory, no deterministic consensus algorithm can guarantee termination in a purely asynchronous system if even one process may crash. Raft and Paxos work around this by assuming partial synchrony — messages are eventually delivered within a bounded time in practice. They guarantee safety (correct results) always, and liveness (making progress) under eventual synchrony.

Paxos — The Theoretical Foundation

Paxos was the first proven solution to distributed consensus. Leslie Lamport published "The Part-Time Parliament" in 1998 (originally written in 1989), then simplified it in "Paxos Made Simple" (2001). While historically significant, Paxos is notoriously difficult to understand and implement — Multi-Paxos (the practical extension for replicated logs) was never formally specified, leading to many incompatible implementations.

Paxos's core insight — which Raft shares — is the quorum overlap property: any two majorities of N nodes must share at least one member. That overlapping node acts as a "witness" — it has seen the previous decision, which prevents two different values from being committed simultaneously. This is the mathematical foundation all consensus algorithms build on.

In practice, Google Spanner and Google Chubby use Multi-Paxos internally. For everyone else, Raft has become the standard.

Raft — The Practical Standard

Raft was explicitly designed for understandability (it won Best Paper at USENIX ATC 2014). It provides the same safety and fault-tolerance guarantees as Paxos but decomposes consensus into three clearly separated subproblems: leader election, log replication, and safety.

Leader Election

All nodes start as Followers.
Election timeout: each follower picks a random timeout in 150-300ms.

1. Follower's timeout fires: becomes Candidate, increments term T
2. Candidate sends RequestVote(T, lastLogIndex, lastLogTerm) to all
3. A node grants its vote if:
   - It hasn't voted in term T yet
   - Candidate's log is at least as up-to-date as voter's log
4. Candidate becomes Leader if it gets votes from majority (n/2 + 1)
5. Leader sends heartbeat AppendEntries(empty) to prevent re-elections

A term is a monotonically increasing number that acts as a logical clock — it increments each time a new election starts. Every message carries the sender's term, so any node that sees a higher term immediately knows its information is outdated.

-+ResetFullscreen

Log Replication

Once a leader is elected, all client writes go through it. The leader replicates entries to followers and commits them once a quorum acknowledges:

1. Client sends write command to Leader
2. Leader appends entry to its log (not yet committed)
3. Leader sends AppendEntries(entry) to all followers in parallel
4. Followers append the entry to their local logs, ACK the leader
5. Once a majority ACK -> entry is COMMITTED
6. Leader applies entry to state machine, returns result to client
7. Leader notifies followers of commit in next AppendEntries
8. Followers apply committed entries to their state machines

A state machine is the application layer that executes the committed log entries — for example, a key-value store that processes GET/SET commands. Every node applies the same log in the same order, so all state machines end up in the same state.

-+ResetFullscreen

Safety Guarantees

These properties ensure Raft never produces incorrect results, even during leader changes:

• Election Safety: At most one leader per term
• Log Matching: If two logs have the same index/term entry, all preceding entries are identical
• Leader Completeness: A committed entry will be present in all future leaders' logs
• State Machine Safety: If a server applies log entry index i, no other server applies a different entry at index i

Raft vs Multi-Paxos

Fault Tolerance

For a cluster of N nodes, Raft/Paxos can tolerate floor((N-1)/2) failures:

Why odd numbers?: Even-sized clusters don't improve fault tolerance. N=4 tolerates 1 failure (quorum=3), same as N=3. N=4 adds a node that only costs money without improving availability. Always use odd cluster sizes.

Byzantine Fault Tolerance: Raft and Paxos assume crash-stop failures — a node either works correctly or stops entirely (it never sends incorrect data). They cannot handle Byzantine failures, where nodes actively lie or send conflicting messages. Byzantine fault tolerance requires algorithms like PBFT and needs 3f+1 nodes to tolerate f failures — vs. 2f+1 for crash-stop.

Mermaid: Raft Cluster Architecture

-+ResetFullscreen

3. Variants & Comparisons

Consensus Algorithms

ZAB vs Raft vs Paxos

ZooKeeper Atomic Broadcast (ZAB) is a consensus algorithm inspired by Paxos, used exclusively by ZooKeeper. In practice, ZAB, Raft, and Multi-Paxos all solve the same problem (replicated log with strong consistency) and have equivalent fault tolerance. The differences are in implementation details — ZAB enforces strict FIFO ordering between leader and followers and has a distinct leader activation phase.

4. When to Use It (and When NOT To)

When You Need Consensus:

• Leader election: Which node is the primary in a replica set? ZooKeeper (via ZAB) and etcd (via Raft) are used as external coordination services for this.
• Distributed transactions: A transaction spans multiple shards. All shards must agree to commit or abort. CockroachDB uses Raft within each range + distributed transactions across ranges.
• Configuration management: Kubernetes stores all cluster state in etcd — what pods are running, what services exist, what configs are active. Correctness requires consensus.
• Distributed locks: A distributed lock must be held by exactly one node. ZooKeeper ephemeral nodes use ZAB consensus for this.
• Strong consistency requirements: Any system where stale or conflicting reads are unacceptable — consensus ensures all nodes agree on the current state.

When NOT to Use Consensus:

• High-frequency writes where latency matters: Consensus requires a round-trip to a quorum before acknowledging a write (1-5ms intra-region, 50-200ms cross-region). If you need sub-millisecond writes, use async replication with eventual consistency.
• Large-scale data storage: Raft is for the control plane and coordination, not bulk data storage. etcd is not your primary database — it's for small amounts of critical metadata. (etcd recommends keeping the store under 8 GB.)
• Every inter-service communication: Don't use a consensus service as a message bus. Consensus is for coordination, not data flow.
• Simple leader-follower replication: If you only need a hot standby for availability, async replication + monitoring is simpler and faster than running a full Raft cluster.

5. Real-World Usage

etcd — Kubernetes Control Plane (Raft)

etcd is the backing store for all Kubernetes cluster state. Every pod, service, deployment, and config map is stored in etcd. Kubernetes makes reads and writes to etcd for all cluster operations. etcd uses Raft to ensure that all etcd cluster members agree on the cluster state — if the etcd leader fails, a new leader is elected via Raft within seconds, and Kubernetes continues operating. The design philosophy: it's better for the control plane to briefly pause (during election) than to apply incorrect cluster state based on stale data.

Google Spanner — Multi-Paxos for Global Consistency

Google Spanner uses Paxos-based replication for each data shard. Every write to a Spanner shard requires a Paxos quorum (majority of replicas) to agree before committing. This synchronous replication, combined with TrueTime for timestamp ordering, gives Spanner external consistency (also called linearizability — every operation appears to take effect at a single instant in time, and all observers agree on the ordering) globally across datacenters. The cost is write latency — a multi-region Paxos round-trip takes 50-200ms depending on replica placement. Google accepted this cost because incorrect billing data is far more expensive than write latency.

CockroachDB — Multi-Raft for Distributed Transactions

CockroachDB implements "Multi-Raft" — each key range (~64 MB) has its own independent Raft group with 3-5 replicas. A table split across 1000 ranges has 1000 independent Raft groups. This distributes the Raft leader responsibility across many nodes, prevents any single node from being overwhelmed by all writes, and allows independent range splits and merges. CockroachDB uses Raft for durability within each range and a two-phase commit protocol coordinated across ranges for distributed transactions.

6. Interview Cheat Sheet

5 Sentences to Show Deep Understanding

1. "Consensus solves the problem of getting distributed nodes to agree on a single value despite failures — Raft is the dominant algorithm in modern systems, tolerating floor((N-1)/2) crash-stop failures with N nodes, and requiring a quorum (majority) to make progress."

2. "Raft decomposes consensus into three clearly separated subproblems — leader election (randomized timeouts to avoid conflicts), log replication (AppendEntries RPCs from leader to followers), and safety guarantees (committed entries are never lost across leader changes) — making it dramatically easier to implement correctly than Paxos."

3. "The quorum overlap property is the core insight behind both Raft and Paxos: any two majorities of N nodes share at least one member — that overlapping node acts as a witness that has seen the previous decision, preventing two different values from being simultaneously committed."

4. "Raft uses terms as logical clocks — every message carries the sender's term, and any node that sees a higher term immediately knows its information is outdated and steps down, which prevents stale leaders from accepting writes after a new election."

5. "Raft and Paxos assume crash-stop failures (nodes stop, don't lie) — Byzantine fault tolerance (nodes that lie or behave maliciously) requires PBFT and needs 3f+1 nodes to tolerate f failures instead of 2f+1, making it significantly more expensive."

Common Follow-Up Questions

Q: How does Raft prevent stale leaders from accepting writes after a new leader is elected? A: Raft uses terms — a monotonically increasing integer that increments with each election. Every message carries the sender's term. If a node (including an old leader) receives a message with a higher term, it immediately reverts to follower. If a new leader is elected in term 8, all messages from the old leader (term 7) are rejected. This ensures an old leader that missed the partition recovery can't commit writes that bypass the new leader.

Q: What is the difference between Raft and ZooKeeper? A: ZooKeeper is a coordination service that runs ZAB (a Paxos-inspired algorithm). Raft is the algorithm itself. etcd is the ZooKeeper equivalent that uses Raft instead of ZAB. The practical choice: ZooKeeper is mature and battle-tested (10+ years in Kafka, Hadoop); etcd is the modern standard (Kubernetes ecosystem, simpler HTTP API, gRPC interface). Both provide similar guarantees.

Q: What is Multi-Raft and why does CockroachDB use it? A: In a large distributed database, all data can't fit in one Raft group's log — you'd need to replicate every write to every node. Multi-Raft divides the dataset into ranges (CockroachDB: ~64 MB each), each with its own independent Raft group. This distributes the Raft leader responsibility across many nodes, prevents any single node from being overwhelmed by all writes, and allows independent range splits and merges. The tradeoff: managing thousands of concurrent Raft groups adds operational complexity.

Q: What happens to reads during a Raft leader election? A: Linearizable reads require the leader to confirm it's still the leader (via a heartbeat round to a quorum) before serving the read — otherwise a stale leader might serve stale data. During election, the cluster has no leader, so linearizable reads pause until a new leader is elected (typically 150ms-300ms + election time). Many systems mitigate this by serving "bounded staleness" reads from any node during elections, falling back to eventual consistency briefly.

Connections to Other Building Blocks

• Replication Strategies: Raft IS the replication strategy for strong-consistency systems. Single-leader replication with automatic failover uses Raft for the leader election. etcd's Raft replaces manual PostgreSQL failover.
• CAP Theorem: Raft/Paxos systems are CP — they sacrifice availability (pause during elections or when quorum is unavailable) to preserve consistency (no stale reads, no split-brain).
• Distributed Locking: ZooKeeper (ZAB) and etcd (Raft) provide the primitive for distributed locks. A lock is just a Raft-committed write that grants exclusivity.
• Sharding & Partitioning: Multi-Raft distributes Raft groups across shards. CockroachDB uses one Raft group per key range to scale beyond what a single consensus group can handle.
• NewSQL (Spanner, CockroachDB): NewSQL databases are built on consensus. CockroachDB = Multi-Raft + distributed transactions. Spanner = Multi-Paxos + TrueTime.