Hello! Welcome to your next lesson on distributed systems.
In our last lesson on leader election, we established how a distributed group of servers can agree on a single leader to coordinate actions and prevent split-brain scenarios. We saw that Raft has a built-in mechanism for this. But electing a leader is only half the battle. Once a leader is chosen, how does it ensure that all other nodes (followers) agree on the state of the system and apply operations in the exact same order?
This brings us to the core problem of distributed consensus. Today, your learning outcome is to explain consensus algorithms at a high level (Paxos, Raft) and when they're needed. We'll explore what it means for nodes to "agree," look at the two most influential algorithms for achieving it, and identify where they are mission-critical in the systems you build and use.
For an experienced engineer, understanding consensus is a key differentiator in system design interviews, moving the conversation from "what components to use" to "how those components guarantee correctness."
1. The Problem: Achieving Agreement Amidst Chaos
At its heart, distributed consensus is about getting a group of computers to agree on a value or, more commonly, an ordered sequence of values. The canonical model for this is State Machine Replication (SMR). Imagine a simple key-value store replicated across several servers. To be reliable, every server must apply the same sequence of write operations (SET x=5, SET y=10, DELETE x) in the exact same order. If they don't, their states will diverge, leading to inconsistency.
The consensus algorithm is the engine that ensures this ordered log of operations is identical across all correct replicas, even if some servers crash or messages get delayed.
To get a formal introduction to the problem, let's watch a segment from a talk by Dr. Heidi Howard, a researcher in this field.
Heidi Howard — Paxos vs Raft: Have we reached consensus on distributed consensus?
This video, 'Paxos vs Raft: Have we reached consensus on distributed consensus?', expertly frames the problem. Dr. Howard explains why failures are the norm and how State Machine Replication, powered by a consensus algorithm, is the solution for building strongly consistent systems.
Watch from 01:33 to 07:04. Pay attention to the concept of 'linearizability' as the strongest consistency guarantee and how achieving it is delegated to the problem of building a replicated log.
As the video explains, the goal is to provide linearizability: the illusion that our distributed, replicated service is just a single, non-distributed machine. To do this, we need all replicas to agree on the history of operations. This is where consensus algorithms come in.
Every correct consensus algorithm must provide two fundamental guarantees:
| Guarantee | Category | Definition | Consequence of Violation |
|---|---|---|---|
| Agreement | Safety | All non-faulty nodes that decide on a value, decide on the same value. | Data corruption, split-brain, inconsistency. The system tells different truths. |
| Termination | Liveness | All non-faulty nodes eventually decide on a value. | The system halts or becomes unavailable. No new operations can be committed. |
Real-world algorithms like Paxos and Raft always prioritize safety. They will never allow nodes to disagree. They guarantee liveness only under certain conditions (e.g., when a majority of nodes are up and can communicate).
2. The Algorithms: Paxos and Raft
Now, let's look at the two titans of consensus. While they solve the same problem, they come from different philosophies.
Paxos: The Foundational Algorithm
Proposed by Leslie Lamport, Paxos is the original, mathematically-proven solution to consensus in an asynchronous environment with crash failures. It's incredibly influential, but also notoriously difficult to understand and implement correctly. For an interview, you are not expected to prove it, but to know its role and high-level mechanism.
The classic Paxos algorithm involves three roles (Proposer, Acceptor, Learner) and a two-phase protocol:
- Phase 1 (Prepare/Promise): A Proposer asks a majority of Acceptors to promise not to accept proposals with a lower number. This phase is for discovering any previously accepted values.
- Phase 2 (Accept/Accepted): If the Proposer gets promises from a majority, it sends an
Acceptrequest with a value. If a majority of Acceptors accept it, the value is chosen.
The key insight is that the majority (quorum) requirement in both phases ensures that if a value has been chosen, any future Proposer will find out about it in Phase 1 and be forced to propose that same value.
For building a replicated log, a variant called Multi-Paxos is used. It elects a stable leader to act as the sole Proposer, which can then skip the "Prepare" phase for subsequent log entries, reducing the protocol to a single round-trip as long as the leader is stable.
Raft: The Understandable Algorithm
Raft was created explicitly to be more understandable than Paxos, without sacrificing correctness. It achieves this by decomposing the consensus problem into three more-or-less independent parts:
- Leader Election (which we covered last lesson)
- Log Replication
- Safety
Let's focus on Log Replication.
The process is straightforward:
- The leader receives a client command.
- It appends the command to its local log.
- It sends
AppendEntriesRPCs to all followers with the new entry. - When a majority of followers have successfully written the entry to their logs, the leader considers the entry committed.
- The leader then applies the command to its state machine and notifies followers that the entry is committed, so they can apply it too.
For a quick, practical walkthrough of the full Raft protocol, the following video is excellent.
Google SWE teaches systems design | EP14: Raft in 15 minutes
Let's watch a concise summary of the entire Raft algorithm from 'Jordan has no life'. This will solidify your understanding of how leader election, log replication, and terms work together.
Watch the segment from 00:00 to 13:35. It covers the full lifecycle: what Raft is, leader election, and log replication. Focus on how the leader uses its log and follower acknowledgements to drive the system forward.
3. Paxos vs. Raft: A Head-to-Head Comparison
"What's the difference between Paxos and Raft?" is a classic senior-level interview question. A nuanced answer demonstrates deep understanding. While Raft is positioned as simpler, Dr. Howard's talk reveals they are more similar than they appear, with the primary differences lying in their specific mechanisms for ensuring safety during leadership changes.
Let's return to the talk to see a direct, expert comparison.
Heidi Howard — Paxos vs Raft: Have we reached consensus on distributed consensus?
This is the most critical part of the lesson. Dr. Howard walks through the core consensus mechanism shared by both algorithms, then highlights exactly where they diverge.
Please watch these segments carefully: The Shared Mechanism (19:19 - 26:19): Understand the common, steady-state operation of log replication. Handling Leader Failures (26:19 - 30:55): Grasp the roles, terms, and states used to manage leadership changes. The Divergence (30:55 - 39:54): This is key. Pay close attention to the different rules each algorithm uses for leader election to guarantee a new leader has an up-to-date log. Safety Proofs (39:54 - 43:42): Briefly understand how their different approaches both lead to the same safety guarantees.
Let's distill this into a table you can use in an interview.
| Aspect | Paxos (Multi-Paxos) | Raft | Interview Talking Point |
|---|---|---|---|
| Understandability | Notoriously difficult. The original paper is famously opaque. | Designed for understandability. The paper is clear and provides a full specification. | "Raft's primary design goal was understandability. Its paper is much more approachable for implementers than the original Paxos papers." |
| Leader Election | Not part of the core algorithm. It's an add-on, often implemented using Paxos itself. | A core, fully specified part of the algorithm. | "Raft integrates leader election as a first-class citizen, whereas in Paxos it's an external mechanism layered on top." |
| Leadership | Allows a more flexible, "weaker" leader. Multiple proposers can exist, but it's inefficient. | Enforces a single, strong leader. All writes must go through the leader. | "Raft's strong leader model simplifies the protocol. In steady-state, it's just the leader sending AppendEntries to followers." |
| Log Up-to-dateness | A new leader can be "ignorant." It learns about committed entries from followers during its first Prepare phase and "fills in" its log. |
A node can only become leader if its log is already at least as up-to-date as a majority of nodes. | "This is a key philosophical difference. Raft restricts who can become leader, while Paxos lets anyone try and forces them to learn. Raft's approach is simpler to reason about." |
| Log Gaps | Possible. A leader can propose an entry for slot 100 even if slot 99 is empty. | Not allowed. The log is always a contiguous array of entries. | "Raft's restriction of no log gaps simplifies log management and replication logic considerably." |
Ultimately, both achieve the same result: a fault-tolerant, replicated log.
4. When Are Consensus Algorithms Needed?
You need a consensus algorithm when you're building a system that requires strong consistency (linearizability) in the face of failures, particularly for managing a single source of truth.
This article from 'algomaster.io' provides an excellent summary of real-world systems and the consensus algorithms they use. It's a great cheat sheet.
First, review the tables in the 'Real-World Systems' section. Then read the 'Practical Recommendations' in the 'Choosing a Consensus Algorithm' section.
Here are the most common use cases:
- Distributed Databases: To coordinate transactions, manage schema changes, and replicate data. Examples: CockroachDB (Raft), TiDB (Raft), Google Spanner (Paxos).
- Coordination Services: To provide primitives like distributed locks, service discovery, and configuration management for other distributed systems. Examples: etcd (Raft), Consul (Raft), ZooKeeper (ZAB, a Paxos-like protocol).
- Distributed Message Queues: To manage metadata, broker leadership, and ensure exactly-once semantics. Examples: Apache Kafka (KRaft), RabbitMQ (Raft for Quorum Queues).
The most important interview insight is this: don't implement consensus yourself. Demonstrate you understand the principles, then state that you would use a battle-tested library or service like etcd or a Raft library. This shows both deep knowledge and practical, senior-level judgment.
Conclusion
Today, we've gone under the hood of strongly consistent systems to understand the engine that powers them.
Key Takeaways:
- Consensus algorithms solve the problem of State Machine Replication, allowing a distributed system to behave like a single, reliable machine by agreeing on an ordered log of operations.
- Paxos is the foundational, proven-correct algorithm but is notoriously complex.
- Raft is a modern alternative designed for understandability, providing the same guarantees as Paxos through a strong leader model and a more rigid structure.
- The key difference lies in how they handle leader changes: Raft restricts who can become leader, while Paxos allows any node to try and forces it to learn the log's history.
- Consensus is the bedrock of most CP (Consistent and Partition-Tolerant) systems you encounter, from databases like CockroachDB to coordination services like etcd.
In this lesson and the last, we've focused heavily on achieving strong consistency. But what about the other side of the CAP theorem? What happens when you prioritize Availability over Consistency?
Our next lesson, "Describe eventual consistency and conflict resolution strategies," will explore the world of AP systems, where replicas can diverge and we need strategies to bring them back in sync.