The Raft protocol is a consensus algorithm designed to manage a replicated log across a cluster of computers. Developed by Diego Ongaro and John Ousterhout at Stanford University, Raft was introduced in 2013 as an alternative to the Paxos algorithm, offering improved understandability while maintaining equivalent functionality. The protocol is widely used in distributed systems to ensure fault tolerance and consistency across multiple nodes.
Design Principles
Raft was specifically engineered to address the complexity issues associated with understanding and implementing Paxos. The algorithm emphasizes clarity through separation of concerns, decomposing the consensus problem into distinct subproblems: leader election, log replication, and safety. This modular approach makes Raft significantly more accessible to students and practitioners while maintaining strong theoretical guarantees.
The protocol operates under the assumption that network communication may be unreliable, nodes may fail, and messages may be lost, duplicated, or reordered. However, it assumes that failed nodes can recover and that message corruption is detectable through checksums. Raft tolerates up to ⌊(n-1)/2⌋ node failures in an n-node cluster while maintaining availability and consistency.
Protocol Overview
Raft implements state machine replication by maintaining a replicated log across all nodes in the cluster. Each node can exist in one of three states: leader, follower, or candidate. The leader handles all client requests and manages log replication to followers. Followers are passive nodes that respond to requests from leaders and candidates. Candidates are nodes participating in leader elections.
Time in Raft is divided into terms, which are consecutive integers that monotonically increase. Each term begins with an election, during which zero or one leader is elected. Terms act as logical clocks, allowing nodes to detect obsolete information. If a node observes a term newer than its own, it updates its term and transitions to follower state.
Leader Election Process
Leader elections in Raft are initiated when followers do not receive communication from a leader within an election timeout period, typically randomized between 150-300 milliseconds. When a follower's election timeout expires, it transitions to candidate state, increments its term, votes for itself, and sends RequestVote RPCs to all other nodes.
A node grants its vote if the candidate's log is at least as up-to-date as its own, determined by comparing the last log entry's term and index. Candidates that receive votes from a majority of nodes become leaders. To prevent split votes, election timeouts are randomized, ensuring that typically one node wins the election before others time out.
Leaders maintain authority by sending periodic heartbeats (empty AppendEntries RPCs) to all followers. If a follower does not receive heartbeats within the election timeout, it assumes the leader has failed and initiates a new election. This mechanism ensures rapid leader failure detection and recovery.
Log Replication Mechanism
Once elected, the leader accepts client requests and appends them to its local log as new entries. Each log entry contains a command for the state machine and the term when it was created. The leader then replicates these entries to followers using AppendEntries RPCs.
Followers append entries only if they are consistent with their existing log. If an entry conflicts with existing entries, the follower deletes the conflicting entry and all subsequent entries. The leader maintains a nextIndex for each follower, tracking the index of the next log entry to send. This mechanism ensures eventual consistency across all logs.
A log entry is considered committed once it is stored on a majority of nodes. The leader commits entries by applying them to its state machine and sending the updated commit index to followers. Followers apply committed entries in log order to their state machines, ensuring identical execution across the cluster.
Safety Properties
Raft guarantees several critical safety properties through its election and replication constraints. The Leader Completeness Property ensures that if a log entry is committed in a given term, it will be present in the logs of all future leaders. This is achieved by requiring candidates to have up-to-date logs and by preventing leaders from deleting entries from previous terms.
The State Machine Safety Property guarantees that if a node has applied a particular log entry to its state machine, no other node will apply a different command for the same log index. This ensures consistent state machine execution across the cluster.
Raft also enforces the Election Restriction, which prevents candidates with obsolete logs from being elected. Additionally, leaders never overwrite or delete entries from previous terms, instead waiting for new entries to commit before removing conflicting entries.
Practical Applications
Raft has been widely adopted in production systems due to its practical advantages over Paxos. Notable implementations include etcd, a distributed key-value store used in Kubernetes; Consul, a service discovery and configuration tool by HashiCorp; and CockroachDB, a distributed SQL database.
The protocol's clear specification and understandability have made it a popular choice for academic research and industrial applications requiring strong consistency guarantees. Various optimizations and extensions to Raft have been proposed, including techniques for improving performance, handling cluster membership changes, and supporting read-only operations efficiently.