Distributed Consensus: Raft & Paxos Explained

The Problem: Replicated State Machines

Before diving into a specific algorithm, let's formalize the problem we're trying to solve. Imagine you have a critical service—like a metadata store for an LLM registry or a user access control system—that must remain available even if a server crashes. The standard approach is to run multiple identical copies of this service on different servers. This is known as a replicated state machine.

The challenge is to ensure that if a client sends a command (e.g., "update user X's permissions"), this command is executed identically on all replicas, and in the same order as all other commands. If we can guarantee this, the replicas will always have the same state and will appear to the outside world as a single, highly reliable machine. The job of a consensus algorithm is to manage the log of commands across all replicas to achieve this consistency.

The following article provides a concise introduction to this concept.

Raft: A "Understandable" Consensus Algorithm

While several consensus algorithms exist, the most famous being Paxos, we will focus on Raft. The creators of Raft designed it with a primary goal of being easier to understand and implement than Paxos, without sacrificing correctness. Its core strategy is to decompose the complex problem of consensus into three more manageable subproblems:

1. Leader Election: Electing one server to act as the cluster's leader.
2. Log Replication: The leader accepts commands from clients and ensures they are replicated safely across the other servers (followers).
3. Safety: A set of rules that guarantee correctness, particularly during leader changes, ensuring that committed data is never lost.

Let's begin with a high-level overview of these components and the different roles a server can play in a Raft cluster.

As the video explained, every server in a Raft cluster is in one of three states at any given time: Leader, Follower, or Candidate. Time is also divided into terms, which are sequentially numbered periods. Each term begins with an election, and at most one leader can exist per term. These two concepts—states and terms—are fundamental to how Raft operates.

Phase 1: Leader Election

Everything in Raft revolves around the leader. All client requests are directed to the leader, which is solely responsible for managing the replicated log. Without a leader, the cluster can't make progress. So, how is a leader chosen?

The process begins when servers start up in the follower state.

• A follower remains passive, simply responding to messages from leaders or candidates.
• Each follower has a randomized election timeout. If a follower doesn't receive any communication (a "heartbeat") from a leader before this timeout expires, it assumes the leader has crashed.
• The follower then transitions to the candidate state. It increments the current term number, votes for itself, and sends RequestVote RPCs to all other servers.
• Other servers will grant their vote to the candidate if they haven't already voted in the current term and if the candidate's log is sufficiently up-to-date (a key safety feature we'll return to).
• If the candidate receives votes from a majority of servers in the cluster, it becomes the new leader.
• The new leader immediately starts sending AppendEntries messages to all followers, which serve as heartbeats and assert its authority.

Two other outcomes are possible during an election:

1. Another server becomes leader first: The candidate receives a heartbeat from a new leader (with an equal or greater term number) and reverts to the follower state.
2. Split vote: If multiple followers become candidates at the same time, votes may be split so that no candidate achieves a majority. In this case, the election for that term fails. The candidates time out and start new elections in a new term. The randomized timeouts make repeated split votes highly unlikely.

For someone with your background, seeing the mechanics in more detail will be valuable. The following video by Martin Kleppmann provides a pseudocode-level walkthrough of the election process.

Phase 2: Log Replication

Once a leader is elected, the system can start processing client requests. This is the core function of the cluster: log replication.

The flow is as follows:

1. A client sends a command (e.g., SET x = 100) to the leader.
2. The leader appends the command to its local log as a new entry. Each entry is marked with the current term number.
3. The leader then sends this new entry to all of its followers via AppendEntries RPCs.
4. Followers receive the AppendEntries message. They perform a consistency check to ensure their log matches the leader's up to the preceding entry. If it matches, they append the new entry to their own log and send an acknowledgment back to the leader.
5. Once the leader has received acknowledgments from a majority of followers, it considers the entry committed. This is the point of no return. A committed entry is guaranteed to be durable and will eventually be executed by all state machines.
6. The leader applies the command to its own state machine (e.g., actually sets x = 100).
7. The leader can now respond to the client with the result.
8. In subsequent AppendEntries RPCs, the leader informs the followers which entries have been committed. The followers then apply those committed entries to their own state machines.

The following image provides a fantastic end-to-end visualization of this entire process, from election to achieving a consistent state.

To again see the mechanics behind this, let's return to Martin Kleppmann's detailed explanation.

Phase 3: Safety

The processes for leader election and log replication seem robust, but they rely on a crucial third component: safety. Raft includes several rules that are essential to guaranteeing that the system is correct and never loses committed data.

The central safety concern is what happens when a leader crashes and a new one is elected. How do we ensure the new leader doesn't undo or contradict work that was already committed by the previous leader?

This is guaranteed by the Leader Completeness Property: any leader elected for a new term must contain all log entries committed in previous terms.

Raft enforces this with a simple but critical rule during the voting process:

• When a candidate requests votes, it includes information about its log (the index and term of its last entry).
• A follower will refuse to vote for a candidate if the follower's own log is more "up-to-date" than the candidate's log. "More up-to-date" is defined as having a last entry with a higher term, or the same term but a longer log.

This voting restriction ensures that a server with a stale log cannot become leader. Since an entry must be replicated on a majority of servers to be committed, and any new leader must have received votes from a majority, there's a crucial overlap. This overlap guarantees that any new leader's log will contain all previously committed entries. This makes it safe for the new leader to force followers' logs to conform to its own, as it knows it isn't overwriting any committed data.

A Complete Reference

We have covered a lot of ground, from high-level concepts to the detailed mechanics of RPCs. The following image is an invaluable reference. It's a condensed summary of the entire Raft algorithm, taken directly from the original paper. As an experienced engineer, you'll likely appreciate having all the rules for server states, RPCs, and state transitions in one place.

Conclusion

In this lesson, we demystified the process of achieving consensus in a distributed system by dissecting the Raft algorithm. You now have a solid mental model for how strongly consistent systems are built.

Key takeaways include:

• Consensus through a Leader: Raft simplifies consensus by electing a single leader to coordinate the system and serialize all operations.
• Leader Election: A robust, fault-tolerant election process based on heartbeats, timeouts, and majority voting ensures a leader is always available (as long as a majority of the cluster is online).
• Log Replication: The leader replicates client commands to followers. An entry is considered committed and durable once it is stored on a majority of servers.
• Safety is Paramount: The Leader Completeness Property, enforced by the election voting rules, is the key safety mechanism. It guarantees that a newly elected leader has all previously committed entries, preventing data loss during leader transitions.

We've now seen how to build a small, fault-tolerant cluster that can agree on a consistent state. However, AI systems often deal with data volumes that far exceed the capacity of a single cluster. This leads to our next topic: How do we scale a stateful service when the data no longer fits on one machine (or one Raft group)? In the next lesson, we will explore data partitioning and sharding, the fundamental techniques for horizontally scaling stateful systems.