Raft Consensus Algorithm

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.

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.