Understanding Raft Consensus

The Raft Approach: Decomposition and Strong Leadership

Like Multi-Paxos, Raft is a leader-based algorithm for managing a replicated log. However, it formalizes the concept of leadership much more strongly and breaks the problem down into three key pieces:

1. Leader Election: Selecting one server to be the leader and detecting when that leader fails so a new one can be chosen.
2. Log Replication: The leader's responsibility to accept client commands, append them to its log, and ensure the followers' logs are made consistent with its own.
3. Safety: The set of rules that guarantee correctness, for example, ensuring that if a log entry is committed, it will persist and that all state machines will execute the same sequence of commands.

This entire process, from election to a consistent state, is captured nicely in the following diagram. We will be dissecting each of these phases in detail.

To begin, let's establish the foundational concepts of Raft by reading the introduction to the seminal paper, "In Search of an Understandable Consensus Algorithm."

Leader Election

Raft uses a heartbeat mechanism combined with randomized timeouts to elect a leader. When a follower stops receiving heartbeats from a leader for a certain period (its election timeout), it assumes the leader has failed, transitions to the candidate state, and starts a new election for a new term.

The candidate votes for itself and sends RequestVote RPCs to all other servers. It wins the election if it receives votes from a majority of the cluster. If it wins, it becomes leader and starts sending heartbeats. If it discovers another server has already been elected leader for the same or a newer term, it reverts to being a follower.

What happens if multiple followers become candidates at the same time? This could lead to a split vote where no candidate gets a majority. Raft solves this elegantly by randomizing the election timeouts for each server. This makes it highly probable that one server will time out first, win the election, and send heartbeats before others even start their own election campaigns.

Diego Ongaro, one of Raft's creators, provides a fantastic visualization that makes this process very clear.

Log Replication and Safety

Once a leader is elected, it's responsible for all client interaction. It appends client commands to its log and replicates them to followers using AppendEntries RPCs. An entry is considered committed once it has been replicated to a majority of servers. The leader then applies the command to its state machine and can respond to the client.

A core principle of Raft is the leader's absolute authority over the log. It never overwrites its own entries. Instead, it forces the followers' logs to match its own. This simplifies log management immensely compared to Paxos.

When a new leader comes to power, follower logs might be inconsistent with its own. Followers might be missing entries, or they might have extra, uncommitted entries from a previous leader. Raft handles this as part of the normal AppendEntries process.

• The leader maintains a nextIndex for each follower, indicating the next log entry to send.
• In each AppendEntries RPC, the leader includes the term and index of the entry preceding the new ones.
• If a follower doesn't have a matching entry at that position, it rejects the RPC.
• The leader then decrements nextIndex and retries until it finds a point of agreement. From there, it can overwrite any conflicting follower entries and append the correct new ones.

This mechanism is powerful because it cleans up all inconsistencies using a single, unified process. To ensure this is safe (i.e., we don't overwrite committed entries), Raft adds a crucial restriction to leader election:

A candidate cannot win an election unless its log is at least as up-to-date as a majority of the cluster's logs.

"Up-to-date" is defined by comparing the term and index of the last entry in the logs. This rule ensures that any newly elected leader already possesses all committed entries from previous terms, making it safe for it to take charge of the log.

The following sections of the Raft paper and Ongaro's visualization walk through these mechanics in detail.

Now, watch how the visualization illustrates the log replication and safety mechanisms.

Cluster Membership Changes

A static cluster isn't practical. Systems need to evolve; servers fail and need replacement, or capacity needs to be scaled up or down. A naive switch from an old configuration (C_old) to a new one (C_new) is dangerous. Because servers switch at different times, you could briefly have two disjoint majorities—one from C_old and one from C_new—that could elect two different leaders for the same term, violating a core safety principle.

Raft solves this with a two-phase approach called joint consensus.

1. Phase 1: Enter Joint Consensus. The leader proposes a new configuration C_old,new that includes all servers from both the old and new configurations. This configuration is stored as a special log entry. Once a server adds this entry to its log, any decisions (like committing entries or electing a leader) require a majority from C_old and a majority from C_new. This overlapping majority requirement makes it impossible for two separate leaders to be elected.

2. Phase 2: Transition to New Configuration. Once the C_old,new log entry has been committed, it is safe to transition to the final configuration. The leader then proposes a final C_new configuration entry. Once this entry is committed (which now only requires a majority from C_new), the membership change is complete. Servers not in C_new can be decommissioned.

This process is visualized in the diagram below.

Let's dive into the paper's explanation and then a practical analysis of different implementation strategies.

While joint consensus is safe and general, some implementations use a simplified approach of changing only one server at a time. This seems simpler but introduces subtle correctness and availability issues—the exact kind of deep trade-off analysis expected of a Principal Engineer.

Conclusion

In this lesson, we have deconstructed Raft's approach to consensus. By prioritizing understandability, its designers created an algorithm that is not only provably correct but also much easier to implement and reason about than its predecessors.

Here are the key takeaways:

• Leader Election: Raft uses randomized timeouts to robustly elect a single leader per term, effectively avoiding the "dueling proposers" problem we saw in basic Paxos.
• Log Replication: It employs a strong leader model where logs are made consistent by force. The leader overwrites follower inconsistencies, a process made safe by the Log Matching Property and the rules of leader election.
• Safety Guarantees: The rule preventing candidates with stale logs from being elected is the critical link that ensures committed entries are never lost.
• Membership Changes: Raft handles dynamic cluster changes safely using a two-phase joint consensus mechanism, which prevents split-brain scenarios during configuration transitions.

Compared to Multi-Paxos, Raft's components are more decoupled and its state space is more constrained, which contributes significantly to its understandability without sacrificing performance.

We have seen how Raft works in normal operation and during configuration changes. However, the true test of a consensus algorithm is its behavior under extreme network conditions. In the next lesson, we will analyze how Raft maintains safety and liveness during network partitions, including scenarios where a leader becomes isolated from its cluster.