Raft

Raft clusters maintain a single leader responsible for all client interactions and log replication. Followers are passive replicas. If a follower's election timer expires (indicating no leader heartbeat), it becomes a candidate and initiates an election by requesting votes. A candidate wins and becomes leader if it receives votes from a majority of the cluster. This ensures at most one leader can be elected per term (a monotonically increasing logical clock).

All data changes are handled by appending entries to the leader's log. Each log entry contains a command, a term number when it was created, and an index. The leader replicates entries to all followers. An entry is considered committed and safe to apply to the state machine once it has been replicated to a majority of servers. Raft guarantees log matching: if two logs contain an entry with the same index and term, they are identical in all preceding entries.

Raft's core safety property is State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index. This is enforced by:

• Election Restriction: Only servers with up-to-date logs can become leader.
• Leader Append-Only: Leaders never overwrite or delete entries in their log.
• Commitment Rule: A leader only commits entries from its current term once they are replicated; it then implicitly commits all preceding entries.

Raft includes a mechanism for safely changing the set of servers in the cluster (e.g., adding or removing a node) without compromising availability. It uses a joint consensus approach as an intermediate step. The cluster first transitions to a configuration that includes both the old and new sets (C_old,new). Once this joint consensus is committed, it transitions to the new configuration (C_new). This two-phase process prevents split-brain scenarios where two disjoint majorities could form.

To prevent logs from growing indefinitely, Raft uses snapshotting. Each server takes compacted snapshots of its applied log entries, which fully captures the state machine's state up to a specific index. The log prefix before that index can then be discarded. Leaders can send snapshots to lagging followers that have discarded needed log entries via an InstallSnapshot RPC. This is crucial for long-running systems to manage storage.

Clients communicate exclusively with the leader. If a client sends a request to a follower, the follower redirects it. For linearizable semantics, Raft leaders must ensure they are still the leader before responding to a write request. A common technique is for the leader to commit a no-op entry at the start of its term. Read-only requests can be handled without log entries but require the leader to verify its authority (e.g., with a lease or by exchanging heartbeats with a quorum) to prevent stale reads.

A family of consensus protocols predating Raft, known for its theoretical elegance but notorious complexity. While Raft prioritizes understandability for implementation, Paxos is often considered more flexible for certain theoretical edge cases.

• Core Difference: Raft uses strong leadership and log-centric operations, whereas classic Paxos is often described as a peer-to-peer agreement on individual values.
• Practical Impact: Raft's design, with its clear separation into leader election, log replication, and safety, has made it the more commonly implemented algorithm in production systems like etcd and Consul.

A system property where consensus is maintained even when some components fail arbitrarily or maliciously. Raft is a Crash-Fault Tolerant (CFT) algorithm, meaning it assumes nodes fail only by stopping (crashing).

• BFT vs. CFT: BFT protocols (e.g., Practical Byzantine Fault Tolerance) are far more complex, as they must handle "lying" nodes that send conflicting messages. Raft cannot tolerate Byzantine faults.
• Use Case: BFT is critical for adversarial environments like certain blockchain networks or high-security financial systems, whereas Raft is sufficient for trusted data center environments.

The data replication strategy that Raft implements. A single elected leader node sequences all client write operations, appending them to its log and replicating them to follower nodes.

• Mechanism: The leader manages the complete replication flow, ensuring all followers have consistent, ordered logs. Followers only accept entries from the current leader.
• Benefits: This model simplifies client interaction (all writes go to the leader) and provides a clear, linearizable ordering of commands, which is essential for building consistent distributed state machines.

A durability mechanism central to Raft's operation. All state changes are first recorded as append-only entries in a persistent log before being applied to the actual state machine.

• Purpose: The WAL ensures that committed operations are not lost after a crash. Upon restart, a node can replay its log to reconstruct its last known state.
• In Raft: The replicated log is the WAL. The consensus process ensures this log is consistently duplicated across nodes before entries are considered committed and applicable.

The primary application of the Raft consensus algorithm. Raft's core purpose is to maintain identical, replicated logs across servers, which are then used to drive identical deterministic state machines.

• How it Works: Client commands are logged and agreed upon via Raft. Once a log entry is committed, it is applied (e.g., applyLog) to the service's state machine (e.g., a key-value store).
• Result: All servers execute the same commands in the same order, so their state machines produce identical outputs and states, creating a fault-tolerant service.

The minimum number of votes required for a cluster to make progress. In Raft, a quorum is a majority of the server nodes (floor(N/2) + 1).

• Leader Election: A candidate must receive votes from a quorum of servers to become leader.
• Log Commitment: A log entry is committed once it has been replicated to a quorum of nodes. This guarantees the entry is durable and will be present in any future leader's log.
• Fault Tolerance: A Raft cluster can tolerate the failure of F nodes where N = 2F + 1, ensuring a quorum is always available.