Raft Consensus Algorithm

Overview

Raft is a consensus algorithm designed to be understandable. It allows a cluster of nodes to agree on a sequence of commands, even when some nodes fail. Raft is the foundation of many modern distributed systems:

• etcd -- Kubernetes configuration store
• Kafka KRaft -- Kafka metadata consensus (replacing ZooKeeper)
• ClickHouse Keeper -- ClickHouse coordination service
• CockroachDB -- Distributed SQL database
• HashiCorp Consul -- Service discovery and configuration
• TiKV -- Distributed key-value store (TiDB)

Architecture

5-Node Cluster

A cluster of 5 nodes that maintain a replicated log. Each node can be in one of three states:

• LEADER: Handles all client requests, replicates log entries
• FOLLOWER: Passive, responds to Leader's RPCs
• CANDIDATE: Actively seeking votes to become Leader

Replicated Log

Each node maintains an ordered log of entries. The Leader ensures all followers have identical logs. Each entry has a term number and index.

State Machine

Once a log entry is committed (replicated to majority), it's applied to the state machine. All nodes apply the same entries in the same order, achieving consistent state.

Key Concepts

Terms

Raft divides time into terms (numbered sequentially). Each term begins with an election. At most one leader can be elected per term. Terms act as a logical clock for detecting stale leaders.

Majority Quorum

With N nodes, a majority is N/2 + 1. For 5 nodes, majority = 3. Operations (commits, elections) require majority agreement. This guarantees that any two majorities overlap by at least one node, preventing conflicting decisions.

Election Timeout

Followers expect heartbeats from the Leader every ~150ms. If no heartbeat is received for a randomized timeout period (150-300ms), the follower becomes a Candidate and starts an election. The randomization prevents simultaneous elections.

Log Consistency Check

Every AppendEntries RPC includes prevLogIndex and prevLogTerm. A follower rejects the RPC if its log doesn't match at that point. The Leader then backtracks until it finds the point where logs agree, then sends all missing entries.

Safety Guarantee

Raft guarantees that committed entries are never lost, even during network partitions. A leader in a minority partition cannot commit new entries (can't reach majority). When the partition heals, uncommitted entries from the minority are safely discarded.

Scenarios

1. Normal Operation -- Client command replicated to majority, committed, applied to state machine
2. Leader Election -- Leader crashes, randomized timeout, RequestVote, majority vote, new Leader
3. Split Vote + Re-election -- Two simultaneous candidates, neither gets majority, re-election in new term
4. Log Consistency -- Disconnected follower rejoins, Leader uses consistency check to catch it up
5. Network Partition -- Cluster splits, only majority partition can commit, safe recovery after healing