Raft vs. Paxos: Consensus Explained

1. The Quest for Understandable Consensus

Before diving into Raft's mechanics, it's crucial to understand why it was created. For decades, the dominant algorithm for consensus was Paxos. While correct and foundational, Paxos is notoriously difficult to understand and even harder to implement correctly. This created a gap between the theory of consensus and its practical application. Raft was designed to fill this gap.

To appreciate the context, let's start with the original Raft paper, which articulates the problems with Paxos and introduces Raft's design goals.

As the paper highlights, Raft's main innovation is its decomposition of the consensus problem into three more-or-less independent subproblems:

1. Leader Election: Electing one server to be the central coordinator.
2. Log Replication: The leader ensures all other servers have an identical log of operations.
3. Safety: Ensuring the system remains correct despite failures.

We will now examine each of these in detail.

2. Server States and the Flow of Time

Raft formalizes the roles servers can play. At any time, a server is in one of three states: Follower, Candidate, or Leader.

• Follower: A passive state. Followers simply respond to requests from leaders and candidates. All servers start as followers.
• Leader: An active state. There is at most one leader at any time. The leader handles all client requests and manages log replication.
• Candidate: An intermediate state used during the election of a new leader.

Raft also divides time into numbered terms. Each term begins with an election, and if successful, a single leader manages the cluster for the rest of the term. Terms act as a logical clock, allowing servers to detect stale information, such as a message from a previous, deposed leader. If a server receives a message with a higher term number, it immediately updates its own term and reverts to a follower state.

Let's begin our deep dive into the algorithm with a video lecture from Martin Kleppmann that walks through a detailed, pseudo-code implementation of Raft. This will resonate with your practical software engineering experience.

3. Mechanism 1: Leader Election

The leader election process is triggered when followers stop hearing from the current leader.

1. A follower waits for a certain period, called the election timeout. If it receives no communication (heartbeats) from the leader during this time, it assumes the leader has failed.
2. The follower transitions to the candidate state. It increments the current term, votes for itself, and sends RequestVote RPCs to all other servers in the cluster.
3. A server will vote for the candidate if it hasn't already voted in that term and if the candidate's log is "at least as up-to-date" as its own (we'll cover this crucial safety rule later).
4. If the candidate receives votes from a majority of servers, it becomes the new leader. It then immediately starts sending heartbeats (AppendEntries RPCs with no data) to establish its authority and prevent new elections.

What if multiple followers become candidates at the same time? This could lead to a split vote, where no candidate achieves a majority. To prevent this, Raft uses randomized election timeouts. Each follower picks a random timeout from a fixed interval (e.g., 150-300ms). This staggering makes it highly likely that only one server will time out and start an election, winning it before others time out.

Let's continue with the video to see the mechanics of this process in detail.

4. Mechanism 2: Log Replication

Once a leader is elected, its primary job is to manage the replicated log. It's the sole authority for all changes. The goal is to ensure that all followers' logs become identical to the leader's.

The process is as follows:

1. A client sends a command to the leader.
2. The leader appends the command to its own log as a new entry, tagged with the current term number.
3. The leader issues AppendEntries RPCs in parallel to all followers, sending them the new entry.
4. When a follower receives an AppendEntries RPC, it appends the new entry to its log and sends an acknowledgement back to the leader.
5. Once the leader has received acknowledgements from a majority of servers, the entry is considered committed.
6. The leader applies the command to its state machine and returns the result to the client.
7. The leader also notifies followers that the entry is committed (typically in subsequent AppendEntries RPCs), and they apply it to their own state machines.

A critical aspect is how Raft handles inconsistencies. After a crash, a follower's log might be out of sync with the new leader's. The AppendEntries RPC includes a consistency check: along with the new entries, the leader sends the index and term of the entry immediately preceding them. A follower only accepts the new entries if it has an entry at that index with that same term.

If the check fails, the follower rejects the RPC. The leader then decrements the index and retries, effectively walking backward through its log until it finds a point of agreement with the follower. From that point, it overwrites the follower's log to match its own. This mechanism elegantly forces follower logs to converge with the leader's.

Let's see this in action.

5. Mechanism 3: Safety and the Leader Completeness Property

We've seen how leaders are elected and logs are replicated. But how does Raft guarantee correctness? For example, how do we ensure a newly elected leader doesn't overwrite entries that were already committed by a previous leader?

This is ensured by the Leader Completeness Property: a leader for a given term must contain all log entries committed in all previous terms.

Raft enforces this property through a simple but powerful restriction on leader election:

• During a RequestVote RPC, a follower will deny its vote if the candidate's log is not at least as "up-to-date" as its own.

"Up-to-date" is defined by comparing the index and term of the last entry in the logs:

1. If the logs have last entries with different terms, the log with the later term is more up-to-date.
2. If the logs end with the same term, the longer log is more up-to-date.

Because a candidate must win a majority of votes, and any committed entry must exist on a majority of servers, this rule ensures that at least one of the voters will have the committed entry. By requiring the candidate's log to be at least as up-to-date as the voter's, the algorithm guarantees the candidate will also have that entry. This prevents a leader with an out-of-date log from ever being elected.

There is one final subtlety. A leader cannot conclude that an entry from a previous term is committed just because it's stored on a majority of servers. To commit an entry from a previous term, a Raft leader must first commit at least one entry from its current term. Once that current-term entry is committed, the Log Matching Property guarantees that all preceding entries are also implicitly committed.

For a formal treatment of these safety rules, the original paper provides a concise explanation.

6. Raft vs. Paxos: A Tale of Two Algorithms

Now that you understand Raft, we can contrast it with Paxos. While both solve the same problem, their design philosophies are fundamentally different. The following video by Heidi Howard offers an excellent comparison.

Here's a summary of the key differences, which you should be prepared to articulate in an interview:

The Design Gurus article provides another concise comparison that is helpful for quick review.

In essence, Raft prioritizes simplicity by enforcing stronger constraints: log entries flow one way, logs must be contiguous, and only up-to-date candidates can become leaders. Paxos is more flexible, but this flexibility comes at the cost of significant complexity. For most practical systems built today (like etcd, Consul), Raft's trade-offs have proven to be highly effective.

Conclusion

In this lesson, we moved from resolving conflicts after the fact to preventing them entirely using consensus. We performed a deep dive into the Raft algorithm, which was specifically designed for understandability and practical implementation.

Key Takeaways:

• Raft decomposes consensus into leader election, log replication, and safety.
• Leader election uses randomized timeouts to prevent split votes and elects a single leader for each term.
• Log replication is managed entirely by the leader, which forces followers' logs to match its own. An entry is committed once replicated on a majority of servers.
• Safety is guaranteed by the Leader Completeness Property, which is enforced by restricting votes to only those candidates with an "up-to-date" log.
• Raft's primary difference from Paxos is its strong leadership model and the direction of information flow during elections. Raft requires a candidate to be complete before election, while Paxos allows a candidate to become complete during election.

You now have a solid theoretical foundation in one of the most important algorithms in distributed systems. In our next lesson, we will see how this theory is put into practice by examining how leader election patterns are implemented using coordination services like ZooKeeper and etcd, the latter of which is a direct application of the Raft algorithm we've just studied.