SQL 120 🛢️ Consensus Protocols in Distributed Databases (Raft and Paxos)
Consensus protocols are the mechanism by which a cluster of independent servers agrees on a single ordered sequence of operations, even when some servers fail or messages are delayed. In a distributed database, this agreement is what allows a write to be replicated to multiple nodes without divergence: every replica applies the same operations in the same order, and the database behaves as if it were a single machine. The two protocols that dominate this space are Paxos and Raft. Paxos was formalized first and underpins systems like Google Spanner. Raft was designed explicitly to be more understandable and has become the default choice for newer distributed databases such as CockroachDB, YugabyteDB, and etcd .
This chapter covers both protocols, the problem they solve, the mechanics of leader election and log replication, and the specific differences that determine when one is chosen over the other. It also examines how Spanner uses Paxos within its architecture and why Raft’s design choices made it the more common choice in modern open-source systems.
Key point: Both protocols guarantee safety—no two leaders can commit conflicting entries for the same log position. They differ in leader election mechanics and log reconciliation, and those differences affect understandability, implementation complexity, and operational behavior more than they affect the fundamental safety guarantee.
Why consensus protocols exist
The replication divergence problem. When a database replicates data across multiple nodes, each node must apply the same sequence of writes. If two nodes receive writes in different orders, they end up with different data. A consensus protocol ensures that all non-faulty nodes agree on the same order, and that a write is only considered committed once a majority of nodes have stored it . Without this agreement, replication produces inconsistency rather than resilience.
The leader failure problem. Most consensus protocols use a leader to serialize writes. When the leader fails, a new leader must be elected, and the election must guarantee that the new leader has all previously committed entries. If a node with an incomplete log becomes leader, it could overwrite committed data, violating durability. Both Paxos and Raft solve this, but in different ways . Raft’s solution is a log-up-to-date check during voting; Paxos distributes terms across servers and requires a more nuanced reconciliation.
The understandability problem. Paxos is famously difficult to understand and implement correctly. The original description was presented as a mathematical proof, and the protocol has many variants and optimizations that obscure the core mechanism. Raft was designed with a specific goal: to be understandable. It separates the problem into leader election, log replication, and safety, and it uses stronger constraints (like the log-up-to-date voting rule) to simplify reasoning . This design choice is why Raft has been adopted by more new systems despite Paxos’s longer history.
a. Paxos: The Original Consensus Protocol
Paxos solves consensus for a single value (or a sequence of values, in Multi-Paxos). The protocol involves three roles: proposers, acceptors, and learners. In practice, a single server often plays all three roles. A value is chosen when a majority of acceptors have accepted it .
The protocol proceeds in two phases. In the prepare phase, a proposer sends a prepare request with a proposal number to the acceptors. Each acceptor promises not to accept any proposal with a lower number and returns any value it has already accepted. The proposer must adopt the value with the highest proposal number among the responses . In the accept phase, the proposer sends an accept request with the chosen value and proposal number. If a majority of acceptors accept, the value is chosen .
For a replicated log, Multi-Paxos elects a distinguished proposer (leader) to skip the prepare phase for subsequent entries, reducing the protocol to a single round-trip per entry . This is the form used in practice. Google Spanner uses Paxos to replicate each split (partition) across data centers, with one replica acting as the Paxos leader for writes and strongly consistent reads . The Paxos leader coordinates writes, and a majority of replicas must store the mutation before the transaction commits .
The weakness of Paxos is not safety but liveness and understandability. Proposers can block each other by competing with higher proposal numbers, and the protocol can spin without reaching agreement . The leader-based Multi-Paxos variant mitigates this, but the underlying complexity remains.
b. Raft: Understandable Consensus
Raft decomposes consensus into three subproblems: leader election, log replication, and safety. A server is always in one of three states: follower, candidate, or leader. Time is divided into terms, each beginning with an election. A term has at most one leader .
Leader election begins when a follower’s election timeout expires without receiving a heartbeat from the leader. The follower becomes a candidate, increments the term, and requests votes from other servers. A server grants its vote only if the candidate’s log is at least as up-to-date as its own . This log-up-to-date check is the critical safety mechanism: it prevents a server with missing committed entries from becoming leader. A candidate that receives votes from a majority becomes leader and begins sending heartbeats to maintain authority .
Log replication follows a simple pattern. The leader appends client commands to its log and sends them to followers via AppendEntries RPCs. Once a majority of servers have stored the entry, it is committed, and the leader applies it to its state machine and returns the result to the client . Followers apply committed entries in order. If a follower’s log diverges from the leader’s, the leader sends the missing entries, and the follower overwrites its conflicting entries with the leader’s version .
The key design choice that distinguishes Raft from Paxos is the log-up-to-date voting rule. In Raft, a follower will not vote for a candidate whose log is less complete than its own. This ensures that the new leader always has all committed entries, without the more complex reconciliation that Paxos requires . The trade-off is that Raft elections may take slightly longer in some failure scenarios, but the protocol is simpler to reason about and implement.
Complete Example Session
// ============================================
// PART 1: THE CONSENSUS PROBLEM
// ============================================
// N servers must agree on a sequence of log entries
// Safety: no two leaders commit different entries for the same index
// Liveness: eventually a leader is elected and makes progress
// ============================================
// PART 2: PAXOS ROLES
// ============================================
// Proposer: proposes a value
// Acceptor: votes on proposals
// Learner: learns the chosen value
// In practice, one server plays all roles
// ============================================
// PART 3: PAXOS PREPARE PHASE
// ============================================
// Proposer sends prepare(n) to acceptors
// Acceptor: if n > highest promised, promise not to accept < n
// Returns any previously accepted value
// Proposer adopts highest-numbered value from responses
// ============================================
// PART 4: PAXOS ACCEPT PHASE
// ============================================
// Proposer sends accept(n, value) to acceptors
// Acceptor: if n >= highest promised, accept the value
// If majority accepts, value is chosen
// ============================================
// PART 5: MULTI-PAXOS OPTIMIZATION
// ============================================
// Elect a distinguished proposer (leader)
// Leader skips prepare phase for subsequent entries
// Single round-trip per entry instead of two
// Spanner uses this form
// ============================================
// PART 6: RAFT STATES
// ============================================
// Follower: passive, responds to RPCs
// Candidate: requesting votes
// Leader: handles client requests, replicates log
// Time divided into terms, one leader per term
// ============================================
// PART 7: RAFT LEADER ELECTION
// ============================================
// Election timeout expires → follower becomes candidate
// Increments term, requests votes
// Follower grants vote only if candidate's log is
// at least as up-to-date as its own
// Majority votes → candidate becomes leader
// ============================================
// PART 8: RAFT LOG REPLICATION
// ============================================
// Leader appends client command to log
// Sends AppendEntries to followers
// Majority stores entry → committed
// Leader applies to state machine, returns result
// Followers apply committed entries in order
// ============================================
// PART 9: RAFT LOG RECONCILIATION
// ============================================
// Follower log may diverge from leader
// Leader sends missing entries
// Follower overwrites conflicting entries
// Leader's log is authoritative
// ============================================
// PART 10: SPANNER'S PAXOS USAGE
// ============================================
// Each split replicated across data centers
// One replica is Paxos leader
// Writes go through leader, majority must store
// TrueTime provides timestamps for external consistency
// Multi-split transactions use 2PC over Paxos groupsThe ten parts trace the mechanics of both protocols and their relationship. Parts 3 through 5 show Paxos phases and the Multi-Paxos optimization. Parts 6 through 9 show Raft’s state machine and log replication. Part 10 shows how Spanner applies Paxos in practice.
Quick Reference
Protocol Comparison
| Feature | Paxos (Multi-Paxos) | Raft |
|---|---|---|
| Roles | Proposer, acceptor, learner | Follower, candidate, leader |
| Leader election | Prepare/accept rounds | RequestVote with log-up-to-date check |
| Log reconciliation | Complex, distributed terms | Leader overwrites follower log |
| Understandability | Low (famously difficult) | High (designed for clarity) |
| Used by | Google Spanner, Chubby | CockroachDB, YugabyteDB, etcd |
Raft States
| State | Behavior |
|---|---|
| Follower | Passive, responds to RPCs |
| Candidate | Requests votes, increments term |
| Leader | Replicates log, sends heartbeats |
Safety Guarantees
| Guarantee | Paxos | Raft |
|---|---|---|
| Only one leader per term | Yes | Yes |
| New leader has all committed entries | Yes | Yes (via voting rule) |
| Committed entries never lost | Yes | Yes |
Best Practices
✅ Do This:
-- Use Raft for new systems that need understandable consensus
-- The log-up-to-date voting rule simplifies implementation -- ✅-- Use Multi-Paxos for high-throughput replication where the
-- leader is stable and prepare phase can be skipped -- ✅-- Monitor leader election frequency
-- Frequent elections indicate network instability or timeouts -- ✅❌ Don’t Do This:
-- Implement Paxos from scratch without extensive testing
-- The protocol has subtle edge cases that are easy to get wrong -- ❌-- Assume Raft is simpler to operate than Paxos
-- Both require careful tuning of timeouts and quorum sizes -- ❌Common Pitfalls
| Pitfall | Why It Happens | Fix |
|---|---|---|
| Split-brain (two leaders) | Network partition with outdated leader | Quorum requirement prevents this |
| Committed entry lost | Leader without up-to-date log elected | Raft voting rule prevents this |
| Election livelock | Competing candidates split votes | Randomized election timeouts |
| Slow replication | Leader waits for all followers | Majority quorum is sufficient |
Real-World Examples
1. Spanner Paxos Group
Each split replicated across data centers via Paxos
Leader handles writes and strongly consistent reads2. CockroachDB Raft Range
Each range is a Raft group
Leaseholder co-located with Raft leader for reads3. YugabyteDB Tablet Raft
Each tablet has its own Raft group
Leader serves writes, followers replicate4. etcd Raft
Kubernetes cluster state stored in etcd
Raft provides consensus for the key-value store5. Raft Log-Up-To-Date Check
Follower grants vote only if candidate's log
is at least as complete as its own6. Multi-Paxos Prepare Skip
Stable leader skips prepare phase
One round-trip per log entry7. Raft Term Increment
Each election increments term
Higher term supersedes lower8. Raft Heartbeat
Leader sends periodic AppendEntries (empty)
Followers reset election timeout on receipt9. Paxos Majority Quorum
Value chosen when majority of acceptors accept10. Raft Quorum Size
N=3 tolerates 1 failure (quorum 2)
N=5 tolerates 2 failures (quorum 3)Visual
Paxos Message Flow (Multi-Paxos)
┌──────────────────────────────────────────────────────────────┐
│ CLIENT │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ LEADER │ Distinguished proposer │
│ │ (Proposer) │ Skips prepare for subsequent entries │
│ └────────┬────────┘ │
│ │ accept(n, value) │
│ ▼ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ ACCEPTOR 1 │ │ ACCEPTOR 2 │ │ ACCEPTOR 3 │ │
│ │ │ │ │ │ │ │
│ │ accept │ │ accept │ │ accept │ │
│ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │ │
│ └───────────────┼───────────────┘ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Majority (2 of 3)│ │
│ │ → CHOSEN │ │
│ └─────────────────┘ │
│ │
│ Prepare phase skipped after leader established. │
│ Single round-trip per entry. │
│ │
└──────────────────────────────────────────────────────────────┘Raft Leader Election
┌──────────────────────────────────────────────────────────────┐
│ FOLLOWER CANDIDATE │
│ │
│ ┌─────────────────┐ ┌─────────────────┐ │
│ │ Heartbeat │ │ Timeout expires │ │
│ │ received │ │ Increment term │ │
│ │ Reset timeout │ │ Request votes │ │
│ └─────────────────┘ └────────┬────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Other followers │ │
│ │ check log: │ │
│ │ is candidate's │ │
│ │ log up-to-date? │ │
│ └────────┬────────┘ │
│ │ │
│ ┌────────────┴────────────┐ │
│ ▼ ▼ │
│ ┌──────────┐ ┌──────────┐ │
│ │ YES: │ │ NO: │ │
│ │ Grant │ │ Deny │ │
│ │ vote │ │ vote │ │
│ └────┬─────┘ └──────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Majority votes? │ │
│ │ → LEADER │ │
│ └─────────────────┘ │
│ │
│ Log-up-to-date check prevents incomplete leader. │
│ │
└──────────────────────────────────────────────────────────────┘Raft Log Replication
┌──────────────────────────────────────────────────────────────┐
│ LEADER │
│ ┌─────────────────┐ │
│ │ Client command │ │
│ │ appended to log │ │
│ └────────┬────────┘ │
│ │ AppendEntries │
│ ▼ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ FOLLOWER 1 │ │ FOLLOWER 2 │ │ FOLLOWER 3 │ │
│ │ │ │ │ │ │ │
│ │ Store entry │ │ Store entry │ │ Store entry │ │
│ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │ │
│ └───────────────┼───────────────┘ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Majority stored │ │
│ │ → COMMITTED │ │
│ └────────┬────────┘ │
│ ▼ │
│ ┌─────────────────┐ │
│ │ Apply to state │ │
│ │ machine, reply │ │
│ └─────────────────┘ │
│ │
│ Leader's log is authoritative. │
│ Followers overwrite conflicting entries. │
│ │
└──────────────────────────────────────────────────────────────┘Spanner’s Layered Architecture
┌──────────────────────────────────────────────────────────────┐
│ SPLIT (key range) │
│ │
│ ┌─────────────────────────────────────────┐ │
│ │ PAXOS GROUP │ │
│ │ │ │
│ │ Replica 1 (Leader) │ │
│ │ Replica 2 │ │
│ │ Replica 3 │ │
│ │ │ │
│ │ Writes go through leader │ │
│ │ Majority must store before commit │ │
│ └─────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────┐ │
│ │ TRUETIME │ │
│ │ Timestamps assigned to transactions │ │
│ │ Commit-wait ensures external consistency│ │
│ └─────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────┐ │
│ │ 2PC (for multi-split transactions) │ │
│ │ Coordinates across Paxos groups │ │
│ └─────────────────────────────────────────┘ │
│ │
│ Paxos handles replication per split. │
│ TrueTime handles ordering. │
│ 2PC handles atomicity across splits. │
│ │
└──────────────────────────────────────────────────────────────┘Summary
| Item | Value |
|---|---|
| Consensus problem | Agreement on ordered log across replicas |
| Paxos roles | Proposer, acceptor, learner |
| Paxos phases | Prepare, accept |
| Multi-Paxos | Leader skips prepare for subsequent entries |
| Raft states | Follower, candidate, leader |
| Raft election | RequestVote with log-up-to-date check |
| Raft replication | AppendEntries, majority commit |
| Spanner consensus | Paxos per split |
| CockroachDB consensus | Raft per range |
| YugabyteDB consensus | Raft per tablet |
Key takeaways:
- Both protocols guarantee safety; they differ in election and reconciliation. Paxos and Raft both ensure that committed entries are never lost and that no two leaders commit conflicting entries for the same index. Raft’s log-up-to-date voting rule simplifies the reconciliation logic, which is why it is easier to implement correctly .
- Raft was designed for understandability. The protocol separates leader election, log replication, and safety into distinct components. This decomposition is why newer systems like CockroachDB, YugabyteDB, and etcd chose Raft over Paxos .
- Multi-Paxos is the practical form of Paxos. A distinguished leader skips the prepare phase for subsequent entries, reducing the protocol to a single round-trip. Spanner uses this form for each split, with one replica acting as the Paxos leader .
- Spanner layers Paxos with TrueTime and 2PC. Paxos handles replication within a split. TrueTime provides timestamps for external consistency. 2PC coordinates transactions that span multiple splits . Each layer solves a distinct problem.
- Quorum size determines fault tolerance. A cluster of 2f+1 replicas can tolerate f failures. A three-node cluster tolerates one failure; a five-node cluster tolerates two. This is a property of the quorum requirement, not the specific protocol .
Remember: Consensus protocols are the foundation of any distributed database that claims strong consistency. They solve the problem of agreement among unreliable nodes, and they do so by requiring a majority quorum for every decision. Paxos and Raft are two solutions to the same problem. Paxos was formalized first and underpins Google’s infrastructure. Raft was designed to be understandable and has become the default for open-source systems. The choice between them is less about capability and more about implementation complexity and ecosystem familiarity. For a system that needs consensus, using an established implementation of either protocol is almost always better than building one from scratch.
Stop using slow, ad-bloated tool sites! 🤮
🔎 Search “KandZ Tools” on Google to use many professional utilities for free.
KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)
⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free
🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!