Skip to content

Consensus (Raft Overview)

1. What is it? (2-3 lines)

Raft is a distributed consensus algorithm designed by Ongaro and Ousterhout to be understandable and equivalent to Paxos in fault-tolerance and performance. It guarantees that a cluster of nodes agrees on a replicated log of state machine commands despite network partitions and node crashes.

2. Why does it exist?

Classical Paxos is notoriously difficult to understand, implement, and prove correct in production systems. Raft decomposes consensus into three independent sub-problems: Leader Election, Log Replication, and Safety, simplifying formal verification and production implementation.

3. Where is it used?

  • Infrastructure Coordinators: etcd (Kubernetes control plane state), HashiCorp Consul/Nomad.
  • Distributed SQL Databases: CockroachDB, TiDB, YugabyteDB.
  • Messaging Platforms: Apache Kafka (KRaft mode metadata quorum).

4. How does it work? (simple flow)

  1. Node States: Every node exists in one of three states: Leader, Follower, or Candidate.
  2. Leader Election: Follower timeout triggers election \(\rightarrow\) Candidate requests votes \(\rightarrow\) Candidate receiving majority votes (\(\lfloor N/2 \rfloor + 1\)) becomes Leader for current Term.
  3. Log Replication:
  4. Client sends command to Leader.
  5. Leader appends command to its local log and sends AppendEntries RPC to all Followers.
  6. Once a majority of Followers ACK writing the log entry to disk, the Leader commits the entry.
  7. Leader executes command on its state machine and returns result to client.
  8. Leader notifies Followers to commit the entry in subsequent AppendEntries heartbeats.
  9. Safety Guarantee: A node can only be elected Leader if its log contains all committed entries from all previous terms (Leader Completeness Property).

5. Advantages

  • Understandable and modular architecture compared to Paxos.
  • Strong Leader property simplifies log replication and linearizable reads/writes.
  • Guarantees strict linearizable consistency across \(N\) nodes while tolerating \(\lfloor (N-1)/2 \rfloor\) node failures.

6. Limitations

  • Single-Leader bottleneck: All log entry writes must route through the single active Raft Leader.
  • High network latency overhead: Every write requires a round-trip RPC to a majority of nodes before committing.
  • Requires an odd number of cluster nodes (3, 5, 7) for optimal majority quorum fault tolerance.

7. Common interview questions (10)

  1. How does Raft decompose the distributed consensus problem into 3 sub-problems?
  2. What is the role of the Term number in Raft log replication and leader elections?
  3. How does Raft handle split-vote scenarios during leader elections?
  4. What is the Leader Completeness Property and how does Raft enforce it during voting?
  5. How does Raft resolve log inconsistencies when a new Leader takes over after a crash?
  6. How does Multi-Raft (used in CockroachDB/TiDB) scale write throughput beyond a single Raft group?
  7. What is Joint Consensus and how does Raft handle dynamic cluster membership changes?
  8. How does a Read Index / Lease Read allow Raft leaders to serve linearizable reads without log appends?
  9. How does Paxos differ fundamentally from Raft?
  10. How does etcd use Raft to maintain state consistency for Kubernetes clusters?

8. Common misconceptions

  • Misconception: Raft writes commands directly to the state machine before consensus. Fact: Commands are written to the uncommitted log first; commands apply to the state machine ONLY after majority quorum ACK commitment.
  • Misconception: Any follower can win an election. Fact: Followers reject candidate votes if the candidate's log is less up-to-date than their own.

10. 30-second cheat sheet

  • Role: Agreement on a replicated log across \(N\) nodes. Tolerates \(\lfloor (N-1)/2 \rfloor\) node failures.
  • Key Flow: Client \(\to\) Leader \(\to\) AppendEntries to Followers \(\to\) Majority ACK \(\to\) Commit \(\to\) Apply to State Machine.
  • Majority Rule: Majority = \(\lfloor N/2 \rfloor + 1\) (3 nodes need 2; 5 nodes need 3).
  • Safety Rule: Candidate MUST possess all committed log entries to win election.