Skip to main content
Raft Consensus Protocol

​
Track 2: Consensus Protocols

Consensus is the most critical topic in distributed systems. Master this track to ace Staff+ interviews at top companies.
Track Duration: 36-46 hours
Modules: 5
Key Topics: FLP Impossibility, Paxos, Raft, Viewstamped Replication, ZAB

​
Module 6: The Consensus Problem

​
What is Consensus?

Consensus is getting multiple nodes to agree on a single value, despite failures. The dinner reservation analogy: Imagine five friends trying to agree on a restaurant via a group chat where messages can be delayed, arrive out of order, or never arrive at all — and some friends might close the app mid-conversation. That is the consensus problem. It sounds trivial until you realize that “just pick the first suggestion” breaks when two people suggest simultaneously, and “wait for everyone to respond” breaks when someone goes offline. Every consensus protocol is fundamentally a clever answer to the question: “How do we make a group decision when we can’t even hold a reliable meeting?”

​
Use Cases for Consensus

Leader Election

Nodes agree on who the leader isExamples:
  • Database primary selection
  • Kafka partition leader
  • Kubernetes control plane

Distributed Locking

Nodes agree on who holds the lockExamples:
  • Zookeeper locks
  • Redis Redlock
  • etcd leases

Configuration Management

Nodes agree on system configurationExamples:
  • Cluster membership
  • Feature flags
  • Service discovery

State Machine Replication

Nodes agree on sequence of commandsExamples:
  • Replicated databases
  • Distributed logs
  • Blockchain

​
FLP Impossibility Theorem

The Most Important Result: Consensus is impossible in an asynchronous system with even one faulty process.

​
Safety vs Liveness

​
Module 7: Paxos Protocol

​
The Original Consensus Algorithm

Paxos was invented by Leslie Lamport in 1989 (published in 1998 after being rejected for being “too whimsical” in its original Greek parliament metaphor). Despite being notoriously difficult to understand — Lamport himself said “The Paxos algorithm, when presented in plain English, is very simple” and the community collectively disagreed — it’s the foundation of modern consensus.
Why Paxos is hard to grok: The difficulty is not in any single step but in understanding why each step is necessary. Every rule in Paxos exists to prevent a specific failure scenario. The “promise” mechanism prevents split decisions. The “use highest accepted value” rule prevents overwriting an already-chosen value. If you find yourself confused, ask: “What goes wrong if I skip this step?” The answer is always a concrete safety violation.

​
Basic Paxos Step by Step

Proposer selects a unique proposal number n and sends Prepare(n) to all acceptors.
Acceptor behavior on receiving Prepare(n):

​
Paxos with Failures

This is where Paxos shines - handling failures:

​
Why Paxos is Safe

​
Multi-Paxos

Basic Paxos decides ONE value. Multi-Paxos decides a SEQUENCE:

​
Module 8: Raft Consensus (Deep Dive)

Most Asked in Interviews: Raft is designed to be understandable. You MUST be able to explain it clearly. The original Raft paper by Ongaro and Ousterhout was explicitly motivated by the observation that students and practitioners struggled to implement Paxos correctly. Raft achieves the same safety guarantees as Multi-Paxos but decomposes the problem into three relatively independent sub-problems: leader election, log replication, and safety. This decomposition is what makes it teachable and implementable.
For a full, implementation-focused treatment with invariants, failure scenarios, and a build-from-scratch roadmap, see the dedicated Raft Deep Dive.

​
Why Raft?

​
Raft State Machine

Raft Consensus State Machine

​
Raft Terms

​
Leader Election

​
Log Replication

The shared notebook analogy: Log replication is like a team that must keep identical lab notebooks. The leader writes an entry in their notebook and sends a copy to every team member. Each team member writes the entry in their own notebook, but only after checking that their previous entries match the leader’s — if there is a discrepancy, the leader walks them back until they find where their notebooks agree, then replays everything from that point forward. An entry is “committed” (permanent) only when a majority of team members have it in their notebooks. This ensures that even if some notebooks are destroyed, the committed entries survive. The core of Raft - replicating commands across nodes:

​
AppendEntries RPC

​
Log Matching Property

​
Safety: Leader Completeness

Critical Property: If a log entry is committed in a given term, that entry will be present in the logs of all leaders for all higher terms.

​
Handling Cluster Membership Changes

Distributed pitfall: Membership changes are the most bug-prone part of any consensus implementation. The Raft paper’s joint consensus protocol is correct but complex. In practice, most production systems (etcd, Consul) use single-server changes — adding or removing one node at a time — because this guarantees that old and new majorities always overlap without needing a joint configuration. The rule is simple: never change more than one node between committed configuration entries. If you need to go from 3 nodes to 5, add one node, wait for it to catch up, then add the second.

​
Log Compaction (Snapshots)

​
Module 9: Viewstamped Replication

An alternative consensus protocol that predates Paxos:

​
Module 10: ZAB (Zookeeper Atomic Broadcast)

​
ZAB Protocol

​
Zookeeper Guarantees

​
Comparison: Paxos vs Raft vs ZAB

​
Advanced: EPaxos (Egalitarian Paxos)

Staff+ Level: EPaxos is an advanced topic that shows deep understanding of consensus trade-offs. It’s less commonly asked but demonstrates expertise.

​
EPaxos Protocol Flow

​
When to Consider EPaxos

​
Advanced: Pipelining & Batching Optimizations

Production consensus systems use several optimizations to achieve high throughput despite the fundamental requirement of disk I/O and network round-trips.

​
1. Request Pipelining

Instead of waiting for each request to commit before starting the next, leaders can process multiple requests concurrently.
Key Insight: Requests at different pipeline stages use different resources (CPU for append, network for replicate, disk for commit). Pipelining maximizes resource utilization.

​
2. Batching Log Entries

Instead of one network round-trip per entry, batch multiple entries into a single AppendEntries RPC.
Batching Trade-offs: Adaptive Batching: Modern systems (TiKV, etcd) use adaptive batching:
  • Low load: Send immediately (minimize latency)
  • High load: Batch aggressively (maximize throughput)

​
3. Parallel Disk I/O

The leader can write to its own log while simultaneously sending AppendEntries to followers.

​
4. Group Commit (fsync Batching)

fsync() is expensive (~10ms on HDD, ~0.1ms on NVMe). Instead of fsync per entry, batch multiple entries into one fsync.
Result: 1000 entries with 1 fsync instead of 1000 fsyncs = ~1000x throughput improvement for disk-bound workloads.

​
5. Flow Control & Backpressure

Prevent slow followers from causing unbounded memory growth on the leader.

​
Performance Numbers (etcd Benchmarks)

Staff Tip: In interviews, mention that “naive Raft” achieves ~1000 ops/s, but production systems like etcd/TiKV achieve 100K+ ops/s through these optimizations. This shows you understand the gap between textbook algorithms and production systems.

​
Practical Implementation Guide

​
Building a Production Consensus System

1

Start with Raft (Not Paxos)

Raft is designed for understandability. If you’re building consensus from scratch:
2

Test Adversarially

3

Performance Tuning

4

Production Checklist

​
Common Implementation Bugs

These bugs have caused real production outages. Watch out for them!

​
Module 11: Quorum Loss & Disaster Recovery

A critical “Principal Level” operational reality: What happens when you lose a majority of your nodes forever? (e.g., a region outage or physical data corruption).

​
The Quorum Loss Problem

Consensus protocols (Paxos/Raft) are designed to block when a majority is lost. This is Safe but leads to Permanent Unavailability.
  • In a 3-node cluster, if 2 nodes are destroyed, the remaining node cannot reach consensus.
  • You cannot simply “add new nodes” because adding nodes requires a consensus vote, which you can’t get.

​
Recovery Strategies

​
1. Forced Reconfiguration (The “God Mode” fix)

Most production implementations (etcd, Consul, Zookeeper) provide a tool to manually override the configuration.
  • Process:
    1. Stop the remaining node.
    2. Use a tool to rewrite the conf file or metadata on disk to say: “The cluster now only consists of ME.”
    3. Restart the node. It now has a majority (1/1) and can process writes.
    4. Gradually add new nodes to rebuild the cluster to N=3N=3 or N=5N=5.

​
2. Seed-based Recovery

In systems like Cassandra or FoundationDB, you can bootstrap a new cluster from a snapshot of the surviving node’s data and “re-seed” the consensus state.

​
3. The “Stale Read” Escape Hatch

If you only need to recover data (not resume writes), you can often perform Stale Reads from the remaining nodes by bypassing the consensus layer and reading directly from the state machine (SSTables/RocksDB). Staff Tip: Disaster recovery is the only time you should ever touch the internal state of a consensus engine. Mention the “etcd disaster recovery” guide in interviews to show you understand that safety isn’t just about code, but about operational survival.

​
Key Interview Questions

Answer structure:
  1. Follower times out (no heartbeat from leader)
  2. Converts to candidate, increments term
  3. Votes for itself, sends RequestVote to all
  4. Other nodes vote (if haven’t voted, log is up-to-date)
  5. If majority votes → becomes leader, sends heartbeats
  6. If receives AppendEntries from valid leader → becomes follower
  7. If timeout again → new election with higher term
Key points to mention:
  • Randomized timeouts prevent split votes
  • Log up-to-date check ensures safety
  • At most one leader per term
Answer: Scenario: Leader has replicated entry to 2/5 nodes and crashes
  1. Followers detect leader failure (timeout)
  2. New election starts
  3. Only nodes with the entry CAN become leader (election restriction)
  4. New leader has the entry, completes replication
  5. Entry gets committed when new-term entry is committed
Key insight: Raft never loses committed entries. An entry replicated to majority WILL be in new leader’s log.
Answer:
  1. Each proposer picks unique proposal number (higher wins)
  2. Acceptor promises to reject lower numbers
  3. If proposer’s Prepare rejected → retry with higher number
  4. In Accept phase, use highest accepted value from promises
  5. System makes progress when one proposer “wins”
Key insight: The “use highest accepted value” rule preserves safety even with competing proposers.
Answer: FLP Impossibility proves this:
  1. Can’t distinguish slow from dead
  2. Adversarial schedule can always prevent decision
  3. Must choose: safety OR guaranteed termination
Practical workaround: Assume partial synchrony (eventually messages arrive). Raft/Paxos do this with timeouts.
Answer:

​
Hands-On Project: Implement Raft

Raft Implementation Lab

Build a complete Raft implementation:Phase 1: Leader Election
  • Implement RequestVote RPC
  • Handle election timeouts
  • State transitions (follower → candidate → leader)
Phase 2: Log Replication
  • Implement AppendEntries RPC
  • Log matching checks
  • Commit index tracking
Phase 3: Persistence
  • Persist term, votedFor, log
  • Recovery after restart
Phase 4: Snapshots
  • Implement log compaction
  • InstallSnapshot RPC
Recommended Resources:
  • MIT 6.824 Labs
  • Raft visualization: raft.github.io
  • etcd/raft source code

​
Next Steps

Continue to Track 3: Replication Strategies

Learn single-leader, multi-leader, and leaderless replication patterns

​
Interview Deep-Dive

Strong Answer:
  • Assume a 5-node cluster (A, B, C, D, E) where A is the current leader. The partition splits into (minority) and (majority).
  • On the minority side: A continues sending heartbeats to B, and B responds. A also tries to send heartbeats to C, D, E but gets no response. If A tries to commit a new write, it needs 3 acknowledgments (majority of 5). It can only get 2 (A itself and B), so A cannot commit any new entries. A remains the leader of term T on its side, but it is operationally frozen — it can accept client requests but cannot commit them. Eventually, depending on the implementation, A may step down or reject client writes directly.
  • On the majority side: C, D, and E stop receiving heartbeats from A. After a randomized election timeout (e.g., 150-300ms), one of them — say C — times out first, increments the term to T+1, votes for itself, and sends RequestVote to D and E. Both grant votes (since they have not voted in term T+1 and C’s log is at least as up-to-date). C becomes the leader of term T+1 with a majority quorum of . This side can now accept and commit new writes.
  • When the partition heals: A sends a heartbeat to C with term T. C responds with term T+1. A sees a higher term, immediately steps down to follower, and adopts term T+1. Any uncommitted entries in A’s log (entries accepted during the partition but not committed) may be overwritten by C’s log during the next AppendEntries exchange. This is safe because those entries were never committed — no client received a success response for them.
Follow-up: What if the old leader A managed to replicate an entry to B during the partition but could not commit it. Is that entry lost after partition healing?Yes, that entry can be lost, and this is by design. Raft’s safety guarantee applies only to committed entries (replicated to a majority). An entry replicated to only 2 of 5 nodes is not committed. After the partition heals, the new leader C will send AppendEntries to A and B. If C’s log diverges from A’s at the position of the uncommitted entry, C’s log wins. A and B truncate their logs to match C’s. The uncommitted entry is overwritten. The client that submitted that write either received a timeout (if A could not commit) or received no response, so the client knows to retry. This is why Raft requires majority acknowledgment before returning success to the client — it ensures that any committed entry survives any subsequent leader change.
Strong Answer:
  • Raft and Multi-Paxos solve the same fundamental problem — replicated state machines — but with different design philosophies. Raft prioritizes understandability by decomposing the problem into leader election, log replication, and safety as separate subproblems. Multi-Paxos prioritizes flexibility by defining consensus on individual log slots independently.
  • The key structural difference: Raft requires a strong leader. All writes go through the leader, and the leader’s log is always the authoritative truth. Multi-Paxos can operate with a “distinguished proposer” (de facto leader) for performance, but any node can propose for any log slot. This means Multi-Paxos can continue making progress even if the leader is temporarily slow (another node proposes for that slot), while Raft must wait for a leader election.
  • I would choose Multi-Paxos (or variants like EPaxos) in geo-distributed deployments where leader-based protocols create latency hotspots. If you have 5 data centers across continents, Raft forces all writes through one leader, adding cross-continent latency. EPaxos (an extension of Paxos) allows any node to propose, and non-conflicting commands can be committed in a single round trip to the nearest quorum. This can cut write latency in half for geo-distributed workloads.
  • I would choose Raft for everything else. The implementation is more straightforward, the debugging is simpler (one leader means one source of truth), and the ecosystem is mature (etcd, Consul, TiKV, CockroachDB all use Raft).
Follow-up: What is the “dueling proposers” problem in Paxos and how does Multi-Paxos solve it?In basic Paxos, any node can propose at any time. If two nodes simultaneously propose for the same slot with different values, they each execute Phase 1 (Prepare) with increasing proposal numbers. Node A sends Prepare(1), Node B sends Prepare(2). B’s higher number causes acceptors to reject A’s subsequent Accept(1). A retries with Prepare(3), which preempts B. This can livelock: neither proposer makes progress because each keeps preempting the other. Multi-Paxos solves this by electing a stable leader (distinguished proposer) who handles all proposals. Once elected, the leader skips Phase 1 entirely for subsequent slots — it only needs Phase 2 (Accept), cutting the message count in half. The leader acts as a “gatekeeper” that serializes proposals, eliminating the dueling problem. If the leader fails, any node can start Phase 1 for the next slot, triggering a de facto leader change. This is why Multi-Paxos in practice looks very similar to Raft — both have leaders, both skip the first round after election.
Strong Answer:
  • You can absolutely have an even number of nodes, but it is almost never a good idea. Consider a 4-node Raft cluster: the majority quorum is 3 (more than half of 4). You can tolerate exactly 1 failure. Now consider a 3-node cluster: the majority quorum is 2, and you can also tolerate exactly 1 failure. So going from 3 to 4 nodes gives you zero additional fault tolerance while increasing the number of nodes that must acknowledge each write (from 2 to 3), which increases latency.
  • This is why consensus clusters almost always use odd numbers: 3 (tolerates 1 failure), 5 (tolerates 2), 7 (tolerates 3). Each additional pair of nodes increases fault tolerance by exactly one.
  • There is an edge case where even numbers appear: Flexible Paxos allows asymmetric quorums where the write quorum and read quorum can differ, as long as their sum exceeds N. In that model, a 4-node cluster with write quorum 3 and read quorum 2 could be useful if reads are much more frequent than writes. But this is an advanced configuration that most systems do not support out of the box.
Follow-up: What about a 2-node consensus cluster? Is that ever valid?A 2-node consensus cluster has a majority quorum of 2, meaning both nodes must agree on every write. This provides zero fault tolerance: if either node goes down, the cluster cannot make progress. It is strictly worse than a single node for availability (you now have two points of failure instead of one) while providing the benefit of data redundancy (if one node’s disk fails, the other has a copy). In practice, 2-node clusters are used as primary-backup pairs with an external arbiter — a lightweight “witness” node that participates only in leader elections and stores no data. etcd supports a “learner” node for this purpose. The witness breaks the tie during elections, giving you effective 3-node quorum behavior with only 2 full data replicas. This is useful when storage is expensive but you still need fault tolerance.
Strong Answer:
  • Safety means “nothing bad ever happens.” For Raft, safety means: (1) at most one leader per term, (2) a committed entry is never lost or overwritten, (3) if two logs contain an entry with the same index and term, they are identical and all preceding entries are identical. Safety properties must hold under all circumstances — crashes, partitions, message delays, any adversarial schedule of events.
  • Liveness means “something good eventually happens.” For Raft, liveness means: the system eventually elects a leader and makes progress (commits entries). Liveness requires timing assumptions — specifically, that the broadcast time is much less than the election timeout, which is much less than the mean time between failures. If the network is completely asynchronous (unbounded delays), Raft’s liveness is not guaranteed (per FLP impossibility).
  • Raft never violates safety. Even under the worst network conditions, two different leaders cannot commit conflicting entries for the same log index. This is ensured by the election restriction (candidates must have an up-to-date log) and the log matching property (AppendEntries checks prevLogIndex/prevLogTerm).
  • Raft can violate liveness. If the election timeout is too short relative to network latency, the cluster can enter a cycle of perpetual elections where no candidate wins a majority before the next timeout fires. This is mitigated by randomized election timeouts, but it is theoretically possible (though statistically improbable) for this to continue indefinitely. In practice, poor timeout tuning is the most common cause of Raft liveness issues.
Follow-up: Describe a concrete production scenario where Raft’s liveness could be compromised.Imagine a 5-node Raft cluster deployed across 3 availability zones, with 2 nodes in AZ-1, 2 in AZ-2, and 1 in AZ-3. The cross-AZ latency is 5ms. The election timeout is set to 150-300ms. Now suppose AZ-3 experiences severe network congestion, increasing its latency to 500ms. The node in AZ-3 keeps timing out and starting elections (incrementing the term), which forces the current leader to step down whenever it receives a RequestVote with a higher term. But the AZ-3 node cannot win the election because its AppendEntries responses are too slow. The result: the disruptive node repeatedly triggers elections, preventing any leader from maintaining stability. Raft addresses this with the “Pre-Vote” extension: before incrementing its term and starting a real election, a candidate sends a PreVote request to check if it would win. If the majority rejects the PreVote (because they already have a functioning leader), the candidate does not proceed, preventing the disruptive election cycle. etcd and TiKV both implement Pre-Vote for this reason.