Raft

Raft uses a leader-based architecture for simplicity. A stable cluster has exactly one leader; all others are followers. The leader handles all client requests and replicates log entries to followers.

• Election Terms: Time is divided into numbered terms, each beginning with an election.
• Heartbeat Mechanism: The leader sends periodic AppendEntries RPCs (heartbeats) to maintain authority. If a follower's election timeout elapses without a heartbeat, it starts an election.
• Voting Rules: A candidate requests votes from other nodes. A node votes for at most one candidate per term and only if the candidate's log is at least as up-to-date as its own. A candidate becomes leader upon receiving votes from a majority of the cluster.

All cluster state changes are captured as entries in a replicated log. The leader ensures this log is consistently replicated across all servers, providing the foundation for state machine replication.

• Log Structure: Each log entry contains a command for the state machine, the term number when it was created, and an index.
• AppendEntries RPC: The leader uses this RPC to replicate log entries and as a heartbeat. It includes the term, leader ID, previous log index/term for consistency checking, new entries, and the leader's commit index.
• Commitment Rule: An entry is committed and safe to apply to the state machine once it has been replicated to a majority of servers. The leader then applies it locally and notifies followers of the new commit index via subsequent RPCs.

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

• Election Safety: At most one leader can be elected in a given term.
• Leader Append-Only: A leader never overwrites or deletes entries in its own log; it only appends new ones.
• Log Matching: If two logs contain an entry with the same index and term, then the logs are identical in all preceding entries.
• Leader Completeness: A log entry committed in a given term will be present in the logs of leaders for all higher-numbered terms. This is ensured by the up-to-date log requirement during elections.

Raft includes a mechanism to safely change the set of servers in the cluster (e.g., adding or removing a node) without compromising availability. A naive approach could lead to split-brain scenarios where two leaders are elected in the same term.

• Joint Consensus: The original Raft paper describes a two-phase transition using joint consensus. The cluster first transitions to an intermediate configuration (Cold,new) that includes both old and new servers. Once this is committed, it transitions to the new configuration.
• Single-Server Changes: A more practical, widely implemented approach is to allow only one server to change at a time. The new configuration is appended to the log and replicated like any other entry, taking effect once committed. This simplifies implementation while maintaining safety.

The log grows indefinitely as new commands are added. To avoid unbounded storage use, Raft incorporates snapshotting to compact the log.

• Snapshot Creation: Each server takes snapshots of its applied state machine data independently. This includes all state up to a specific applied index.
• Metadata: The snapshot includes the last included index and term from the log, which are needed for consistency checks during log replication.
• InstallSnapshot RPC: A leader can send this RPC to a follower that is far behind (its log entries have been discarded). The follower replaces its entire state with the snapshot and trims its log accordingly. This allows a crashed and restarted node to catch up efficiently.

For a system to be useful, clients must be able to submit commands and receive correct responses. Raft's leader-based model dictates a specific client protocol.

• Finding the Leader: Clients initially contact a random cluster member. If that member is not the leader, it rejects the request and can include the known leader's address in the response (redirect).
• Linearizable Semantics: To provide strong consistency (linearizability), a client must retry commands with a unique ID if it does not receive a response. The leader ensures the command is executed exactly once by deduplicating using client IDs and sequence numbers.
• Read-Only Operations: To serve reads without involving the log (for efficiency), a leader must verify it is still the leader. It can do this by either committing a no-op entry to its log or by exchanging heartbeats with a majority to establish a lease before responding to the read.

A distributed algorithm that enables a group of processes or agents to agree on a single data value or sequence of actions despite the possibility of failures. Raft is a specific type of consensus algorithm designed for understandability. Key characteristics include:

• Agreement: All non-faulty processes decide on the same value.
• Validity: The decided value must have been proposed by some process.
• Termination: Every process eventually decides a value.
• Fault Tolerance: The algorithm can withstand a minority of processes failing. Consensus is the fundamental problem Raft solves, enabling reliable replicated state machines.

A foundational family of protocols for solving consensus in a network of unreliable processors. Created by Leslie Lamport, it was the dominant consensus algorithm for decades but is notoriously difficult to understand and implement correctly. Raft was explicitly designed as a more understandable alternative to Paxos. Key comparisons:

• Raft uses strong leadership and a simpler, more decomposed approach (leader election, log replication, safety).
• Paxos is a peer-to-peer protocol that can be more flexible in certain network conditions but is conceptually more complex.
• Both provide equivalent fault tolerance guarantees (surviving up to f failures with 2f+1 servers).

A core technique for implementing a fault-tolerant service by replicating a deterministic state machine across multiple nodes. Raft is a consensus algorithm that directly enables State Machine Replication (SMR). The mechanism is:

1. Client commands are appended to a replicated log (managed by Raft).
2. The consensus algorithm ensures all replicas have the same log in the same order.
3. Each replica applies the commands from the log sequentially to its local state machine. This ensures all correct replicas perform the same operations in the same order, producing identical outputs and states, which is the primary use case for Raft.

A consistency model where any read operation on a data item returns a value corresponding to the result of the most recent write operation, as perceived by all nodes. Raft provides a linearizable (the strongest form of strong consistency) interface for client operations when the leader handles all reads and writes. This contrasts with models like eventual consistency. Guarantees include:

• Linearizability: Operations appear to take effect atomically at a single point in time between invocation and response.
• Read-Your-Writes: A client will always see its own updates.
• Monotonic Reads: Successive reads will never return older data. Raft's log replication and single-leader design are engineered to deliver this guarantee.

The sub-process within a consensus algorithm like Raft by which a single node is chosen to coordinate replication and act as the authority for client requests. Raft's leader election uses a randomized timeout mechanism:

• Each server starts as a follower.
• If a follower receives no communication from a leader or candidate, it transitions to candidate and starts an election.
• The candidate requests votes from other servers. A candidate wins if it receives votes from a majority of the cluster.
• The winning candidate becomes the leader. All client commands now go through the leader. This process ensures there is at most one active leader per term (a monotonically increasing epoch), which is critical for safety.

A fundamental principle in distributed systems stating that it is impossible for a distributed data store to simultaneously provide all three of the following guarantees:

• Consistency (C): Every read receives the most recent write.
• Availability (A): Every request receives a (non-error) response.
• Partition Tolerance (P): The system continues operating despite network partitions. Raft is a CP (Consistency & Partition Tolerance) system. During a network partition, Raft prioritizes consistency:
• The partitioned side with a leader and majority remains available and consistent.
• The minority partition becomes unavailable for writes (and linearizable reads) to prevent inconsistency. This trade-off is a conscious design choice for systems requiring strong correctness guarantees.