Raft Consensus Algorithm

Raft nodes operate in one of three states: Follower, Candidate, or Leader. A stable cluster has exactly one elected Leader. If Followers do not receive heartbeats from a Leader within a randomized election timeout, they transition to Candidate, increment their term (a logical clock), and request votes. The Candidate that receives votes from a majority of the cluster becomes the new Leader for that term. This process ensures liveness by allowing the system to recover from Leader failure.

All client state changes are appended to the Leader's log as entries. Each entry contains a command, the Leader's current term, and a sequential index. The Leader replicates entries to all Followers via AppendEntries RPCs. An entry is considered committed and safe to apply to the state machine once it has been replicated to a majority of nodes. The Leader then notifies Followers of the commit index. This majority-based replication provides fault tolerance; the cluster can tolerate the failure of (N-1)/2 nodes.

Raft guarantees that committed entries are durable and never lost. It enforces a critical Log Matching Property: if two logs contain an entry with the same index and term, they store the same command and all preceding entries are identical. The Leader enforces consistency by finding the latest log match with each Follower and overwriting any conflicting entries. The Election Safety property ensures at most one Leader can be elected per term, and the Leader Append-Only rule prevents Leaders from deleting or overwriting existing log entries.

A term is a monotonically increasing integer that acts as a logical clock, identifying Leader tenures and detecting stale information. Every RPC contains the sender's current term. If a node receives an RPC with a higher term, it updates its own term and reverts to Follower. The Leader maintains authority by sending periodic heartbeat RPCs (empty AppendEntries) to all Followers. These heartbeats reset Followers' election timers, preventing unnecessary elections while the Leader is healthy. This mechanism ensures stable leadership during normal operation.

The ultimate goal of Raft is to maintain identical, fault-tolerant state machines across all servers. The commit index is the highest index of a log entry known to be stored on a majority of servers. The Leader advances its commit index as new entries are replicated. Each server applies all log entries up to its commit index to its local state machine, in order. The last applied index tracks the most recent entry applied. This ensures all servers execute the same commands in the same order, guaranteeing state machine safety.

Raft includes a protocol for safely changing the set of servers in the cluster (e.g., adding or removing a node). A naive approach could cause split-brain scenarios. Raft's solution uses joint consensus, where the system transitions through an intermediate configuration that combines the old and new sets. Changes are implemented by replicating a special configuration entry through the standard log replication mechanism. This ensures the membership change itself is subject to the consensus protocol, maintaining safety and availability during the transition.

A fundamental durability mechanism that Raft's replicated log is built upon. The Write-Ahead Log (WAL) protocol mandates that any state modification must be first recorded to a persistent, append-only log before being applied to the actual data structure.

• In Raft, every client command is a log entry. The leader appends it to its log and replicates it to followers before any node is allowed to apply it to its state machine.
• This ensures crash recovery: after a failure, a node can replay its log to reconstruct its exact state up to the last committed entry.
• The WAL is the backbone that transforms Raft's agreement on log entries into durable, consistent state machine execution.

The overarching architectural pattern that Raft implements. State Machine Replication (SMR) is a method for making a service fault-tolerant by replicating its deterministic state machine across multiple servers.

• The core principle: if all replicas start in the same state and apply the same sequence of commands in the same order, they will produce identical outputs and end states.
• Raft's sole purpose is to maintain that replicated log which defines the agreed-upon command sequence.
• This pattern is used in systems like etcd and Consul to provide highly available key-value stores, where Raft ensures all nodes agree on the order of PUT and DELETE operations.

A critical sub-problem that Raft explicitly separates from log replication. Leader election is the process by which a distributed system selects a single node to coordinate actions and make decisions, preventing split-brain scenarios.

• Raft uses randomized election timeouts to resolve conflicts. If a follower doesn't hear from a leader, it increments its term and starts an election.
• A candidate wins an election if it receives votes from a majority (quorum) of the cluster for that term.
• This elected leader then assumes full responsibility for replicating new log entries, simplifying the management of consistency compared to leaderless approaches.

A fundamental concept in fault-tolerant voting systems. A quorum is the minimum number of votes a distributed operation requires to be considered successful and safe.

• In Raft, a majority quorum is used for both leader elections and log commitment. For a cluster of N nodes, a majority is floor(N/2) + 1.
• This ensures safety: no two leaders can be elected in the same term, as no two candidates can simultaneously obtain a majority. Similarly, a log entry is committed only when replicated to a majority.
• The quorum size directly determines the system's fault tolerance. A cluster of 2F + 1 nodes can tolerate F failures (e.g., 5 nodes tolerate 2 failures).

A catastrophic failure mode in distributed systems that consensus algorithms like Raft are designed to prevent. Split-brain occurs when network partitioning causes two or more parts of a cluster to believe they are the active leader, leading to data divergence.

• Raft's strong leadership and quorum-based voting make a true split-brain impossible. Only one partition can ever achieve a majority vote to elect a leader.
• The minority partition(s) will have candidates, but they will fail to get a majority and remain in candidate state, unable to commit new log entries.
• This guarantees that even during a network partition, at most one side of the cluster can make progress, preserving linearizability for client operations.