Raft Consensus Algorithm

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.

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.