Raft

Raft ensures system liveness through a stable leader election process. All nodes begin as followers. If a follower receives no communication from a leader or candidate within its election timeout, it transitions to candidate, increments its term, and requests votes. A candidate becomes leader if it receives votes from a majority of the cluster. This process guarantees that at most one leader can be elected per term, preventing split-brain scenarios.

All client requests are handled by the leader, which appends them to its local log. The leader then replicates these log entries to all follower nodes. An entry is considered committed and safe to apply to the state machine once it has been replicated to a majority of nodes. This majority-commit rule ensures safety—committed entries are durable and will be present in the logs of all future leaders, even after failures.

Raft's core safety property is the State Machine Safety guarantee: if any server has applied a particular log entry to its state machine, no other server will ever apply a different command for the same log index. This is enforced by the leader's AppendEntries RPC, which includes the index and term of the preceding log entry. A follower only accepts new entries if this matches its own log, ensuring log consistency across the cluster.

Raft employs a strong leader model, simplifying the management of the replicated log. Only the leader can accept client commands and replicate them to followers. Followers respond passively to RPCs, redirecting clients to the current leader. This centralizes complex logic (like managing log consistency) in one place, which is a key factor in Raft's understandability compared to leaderless or multi-leader consensus approaches like Paxos.

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 where the cluster temporarily operates under both the old and new configuration during the transition. This prevents the classic problem where two disjoint majorities could form, each believing it is the legitimate leader, which could lead to data loss or inconsistency.

To prevent logs from growing indefinitely, Raft incorporates log compaction. Each server takes periodic snapshots of its entire state machine. Once a snapshot is taken, all log entries prior to the snapshot's last included index can be discarded. Leaders can send these snapshots to lagging followers via an InstallSnapshot RPC, allowing them to catch up efficiently without requiring the full, ancient log history. This is crucial for long-running systems.

A consensus algorithm is a fault-tolerant distributed protocol that enables a group of nodes or agents to agree on a single data value or sequence of actions despite the failure of some participants. It is the foundational category to which Raft belongs.

• Core Purpose: To achieve state machine replication, ensuring all non-faulty participants apply the same commands in the same order.
• Key Properties: Must provide safety (nothing bad happens, e.g., inconsistency) and liveness (something good eventually happens, e.g., progress).
• Contrast with Raft: While Paxos is famously complex, Raft was explicitly designed for understandability through strong leadership and decomposed sub-problems (leader election, log replication, safety).

Paxos is a family of consensus algorithms for asynchronous networks, predating Raft and serving as the theoretical benchmark. It ensures a group of agents can agree on a single value even if some agents fail or messages are delayed.

• Historical Context: Published by Leslie Lamport in 1998, it was long considered the standard but was notoriously difficult to understand and implement correctly.
• Comparison to Raft: Unlike Raft's single, durable leader, classic Paxos often uses a sequence of possibly different proposers. Raft's design choices, like its strong leadership model and log-centric approach, were direct responses to Paxos's complexity.
• Legacy: Paxos remains critical for understanding distributed consensus theory, while Raft is often chosen for practical implementations.

Byzantine Fault Tolerance (BFT) is the property of a consensus system to reach agreement correctly even when some participants fail arbitrarily or behave maliciously (so-called Byzantine failures).

• Fault Model: Raft is designed for crash-fault tolerance (nodes stop working). BFT protocols like PBFT handle a broader, more severe Byzantine fault model where nodes can send conflicting or incorrect messages.
• Implications: BFT requires more complex message-passing (often requiring 3f+1 nodes to tolerate f faulty ones) and cryptographic verification. Raft is simpler and more performant but assumes nodes are not malicious.
• Use Case: BFT is essential for adversarial environments like certain blockchains or high-security financial systems, whereas Raft is suited for trusted clusters (e.g., within a datacenter).

Two-Phase Commit (2PC) is a distributed consensus protocol that ensures atomicity (all-or-nothing completion) across multiple participants in a transaction. It is a coordination protocol, not a full consensus algorithm like Raft.

• Mechanism: A coordinator manages a voting phase (where participants vote 'yes' or 'no') and a decision phase (where the coordinator instructs all to commit or abort).
• Key Difference from Raft: 2PC is a blocking protocol—if the coordinator fails, participants may be left in an uncertain state requiring manual intervention. Raft provides high availability through leader election and replicated logs.
• Typical Use: 2PC is commonly used in distributed database transactions to coordinate commits across shards, whereas Raft is used to replicate the state of a single service or log.

State Machine Replication (SMR) is the fundamental technique implemented by consensus algorithms like Raft. It ensures that multiple replicas of a deterministic service start from the same state and execute the same sequence of commands, thus remaining identical.

• How Raft Achieves It: Raft's core function is to maintain a replicated log. Once a log entry is committed, it is applied to the service's state machine (e.g., a key-value store) in the same order on every node.
• Benefit: Provides fault tolerance. If the leader fails, any other replica with an up-to-date log can become leader and continue service without data loss.
• Critical Detail: The service's business logic must be deterministic; given the same input log, all replicas must produce the same output state.

The CAP theorem is a fundamental principle in distributed systems stating that a networked shared-data system can provide only two out of three guarantees simultaneously: Consistency, Availability, and Partition tolerance.

• Raft's Position: Raft is a CP (Consistent & Partition Tolerant) system. Under a network partition, it prioritizes consistency over availability.
• Mechanism: During a partition, the majority side can elect a leader and continue operating (remaining consistent). The minority side cannot process writes because it cannot achieve a majority, thus becoming unavailable for writes to preserve consistency.
• Design Implication: Understanding CAP is crucial for selecting Raft; it is ideal for scenarios where data correctness is paramount, and temporary unavailability during partitions is acceptable.