Raft Consensus Algorithm

What is the Raft consensus algorithm?

Raft is a consensus algorithm designed to be more understandable than Paxos while providing equivalent guarantees. Consensus means a cluster of nodes agrees on a sequence of values - even in the presence of node failures - forming a reliable replicated state machine.

Raft is used by: etcd (Kubernetes configuration store), CockroachDB, TiKV, Consul, RethinkDB.

The Problem Raft Solves

In a distributed system, how do N nodes agree on a sequence of operations, even when some nodes crash or messages are delayed? If each node independently accepts writes, they'll diverge. Consensus ensures all nodes apply the same operations in the same order.

Raft's Three Subproblems

1. Leader Election

• At any time, one node is the Leader; others are Followers or Candidates
• Leader handles all client writes and replicates to followers
• Followers send heartbeats to detect leader liveness
• If a follower doesn't receive a heartbeat within the election timeout (150-300ms), it becomes a Candidate and calls an election

Election process:

1. Candidate increments its term (logical clock) and votes for itself
2. Sends RequestVote RPC to all other nodes
3. A node grants its vote if: it hasn't voted this term AND candidate's log is at least as up-to-date
4. Candidate needs a majority of votes to become Leader
5. If no majority within timeout -> start new election with higher term

2. Log Replication

• Client sends write to Leader
• Leader appends entry to its local log
• Leader sends AppendEntries RPC to all followers
• Once a majority of followers acknowledge -> entry is committed
• Leader notifies followers of commit; followers apply to state machine
• Leader responds to client

Key: entries are committed only once acknowledged by a majority. A failed follower doesn't block progress.

3. Safety (Log Consistency)

Raft guarantees:

• Election Safety: At most one leader per term
• Leader Append-Only: Leader never overwrites its log
• Log Matching: If two logs have the same index and term, they are identical up to that point
• Leader Completeness: If an entry is committed, all future leaders will have it

Term Numbers

Terms are monotonically increasing integers that act as logical clocks:

• Each term begins with an election
• A node that sees a higher term immediately reverts to Follower
• Stale leaders (disconnected and reconnected) are automatically demoted by seeing a higher term

Split-Brain Prevention

Raft prevents split-brain by requiring a majority quorum:

• In a 5-node cluster, 3 nodes must acknowledge any write (majority of 5)
• If a network partition splits the cluster 2/3, only the partition with 3 nodes can make progress
• The minority partition cannot elect a leader (can't reach majority) -> no writes -> no divergence

etcd and Kubernetes

etcd uses Raft to store Kubernetes cluster state (pod specs, service definitions, config maps). All kubectl commands are linearisable reads/writes through the etcd Raft cluster. Leader is single-master for writes; reads can optionally go to followers (with staleness risk).

Raft vs Paxos

	Raft	Paxos
Understandability	High (designed for it)	Complex
Leader	Explicit, single leader	Multiple proposers possible
Log structure	Explicit, sequential	Less structured
Adoption	etcd, CockroachDB	Google Chubby, Zookeeper (ZAB)

Interview Angle

Raft is frequently asked in senior distributed systems interviews. Key points: leader election (majority vote), log replication (majority acknowledgement before commit), term numbers as logical clocks, and split-brain prevention via quorum. You don't need to know every detail - demonstrate understanding of the majority quorum principle and why it prevents split-brain.