Raft Consensus Algorithm

Raft uses a leader-based architecture to simplify log replication. All cluster nodes start as followers. If a follower receives no communication from a leader for its election timeout period, it becomes a candidate and initiates an election by requesting votes. A candidate wins an election and becomes the new leader if it receives votes from a majority of the cluster. This ensures at most one leader exists at any time, even after network partitions.

All state changes are handled by the leader as entries in a replicated log. The process ensures strong consistency:

• The leader appends the command to its log.
• It replicates the entry to all follower nodes.
• Once the entry is durably stored on a majority of nodes, the leader commits the entry and applies it to its state machine.
• The leader then notifies followers to apply the committed entry. This majority commitment rule guarantees that committed entries are durable and will be present in all future leader logs.

Raft provides several critical safety properties for reliable state machine replication:

• Election Safety: At most one leader can be elected in a given term (a monotonically increasing epoch).
• Leader Append-Only: A leader never overwrites or deletes entries in its log; it only appends new ones.
• Log Matching: If two logs contain an entry with the same index and term, they store the same command and all preceding entries are identical.
• 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 command for the same index.

Raft is designed to tolerate the failure of up to f nodes in a cluster of 2f + 1 nodes. It handles:

• Leader Failure: Triggers a new election. The new leader's log is guaranteed to contain all committed entries.
• Follower/Candidate Failure: These nodes can rejoin and have their logs brought up to date by the leader.
• Network Partitions: The partition containing a majority can elect a leader and continue operations; the minority partition cannot commit new entries, preserving consistency. Recovery is aided by persistent state (current term, votedFor, log) stored on stable storage before responding to RPCs.

A core design goal of Raft was understandability compared to predecessors like Paxos. This is achieved through:

• Decomposition: Separating the problem into distinct sub-problems: leader election, log replication, and safety.
• State Simplification: Nodes have only three clear roles: Follower, Candidate, or Leader.
• Strong Leadership: The leader handles all client interactions and log replication, simplifying the management of log consistency.
• Randomized Election Timeouts: These reduce the likelihood of split votes, making the system's behavior more predictable and easier to reason about.

Raft includes a mechanism to safely change the cluster's server configuration (e.g., adding or removing a node) without downtime. The standard approach uses a joint consensus transition:

• The leader replicates a special configuration entry that combines the old and new configurations (C_old, C_new).
• Decisions during joint consensus require separate majorities from both the old and new configuration sets.
• Once the joint consensus entry is committed, the leader replicates an entry for the new configuration alone (C_new). This two-phase process prevents two disjoint majorities from forming during the transition, a problem known as split brain.

A distributed systems guarantee that any read operation on a state will return the value from the most recent write operation, providing immediate data uniformity across all nodes. This is the primary guarantee provided by consensus algorithms like Raft and Paxos.

• Contrasts with eventual consistency, which allows temporary divergence.
• Essential for systems requiring linearizability, such as primary-backup databases (e.g., etcd, Consul) where stale reads are unacceptable.
• Achieved via a leader-based quorum model where a majority of nodes must acknowledge a write before it is committed.

A durability mechanism where all state modifications are first recorded as immutable, sequential entries to a persistent, append-only log before being applied to the main in-memory state. This is the fundamental data structure in Raft.

• Core to Raft's replicated log, where log entries are the unit of consensus.
• Ensures recoverability after crashes; the system replays the log to reconstruct the last known state.
• Used in databases like PostgreSQL and stateful stream processors like Apache Kafka for fault-tolerant persistence.

The technique of maintaining identical copies of an agent's or service's operational state across multiple nodes in a distributed system. Raft is a protocol for managing this replication safely.

• Primary goals are fault tolerance (surviving node failures) and high availability.
• Active replication (as in Raft): All updates go through a leader which propagates them to followers.
• Contrasts with state sharding, where the total state is partitioned, not fully copied.

The distributed process by which nodes in a cluster select a single leader responsible for coordinating updates and maintaining the replication log. This is a distinct, clearly defined phase in the Raft algorithm.

• Raft uses randomized election timeouts to prevent split votes and ensure quick convergence.
• The leader must maintain a "lease" by sending periodic heartbeats to followers; if heartbeats stop, a new election is triggered.
• Critical for providing a single serialization point for all state mutations, which simplifies the implementation of strong consistency.

A majority subset of nodes in a distributed cluster whose agreement is required to commit an operation. Raft requires a quorum for both leader election and log entry commitment.

• For a cluster of N nodes, a quorum is floor(N/2) + 1.
• Ensures safety by guaranteeing that only one leader can be elected per term and that committed entries are durable.
• Enables progress during partial failures; the cluster can operate as long as a quorum of nodes is alive and can communicate.

A weaker distributed consistency model where, in the absence of new updates, all replicas of a state will eventually converge to the same value. This contrasts with the strong consistency provided by Raft.

• Does not guarantee when replicas will become consistent.
• Common in globally distributed databases (e.g., Amazon DynamoDB, Apache Cassandra) where low latency and partition tolerance are prioritized over immediate consistency.
• Often uses mechanisms like conflict-free replicated data types (CRDTs) or last-write-wins (LWW) to resolve conflicts automatically.