Distributed Consensus: Raft vs Multi-Paxos & State Machine Replication

Distributed Consensus: Raft vs Multi-Paxos, State Machine Replication & Split-Brain Internals

Architectural Abstract: Building distributed systems that survive arbitrary network partitions, hardware degradation, and node crashes requires consensus—the algorithmic agreement across independent compute nodes on a linear sequence of state transitions. While Leslie Lamport's Paxos established the theoretical baseline, Diego Ongaro and John Ousterhout's Raft transformed distributed engineering by decomposing consensus into discrete, comprehensible sub-problems. This blueprint deconstructs the mathematical invariants, state machine transitions, log compaction mechanics, and failure modes of Multi-Paxos and Raft, examining how production engines like etcd, CockroachDB, TiKV, and Kafka KRaft achieve linearizable guarantees under chaotic network conditions.

---

1. The Core Dilemma: Replicated State Machines & FLP Impossibility

At the heart of distributed coordination, distributed databases, and consensus metadata quorums lies the Replicated State Machine (RSM) architecture.

The State Machine Property

If two identical, deterministic state machines start in the same initial state $S_0$ and apply the exact same sequence of input commands:

$C=[e_1,e_2,e_3,\dots ,e_k]$

they are mathematically guaranteed to traverse the identical sequence of intermediate states and arrive at the exact same final state $S_k$:

$S_k=f(S_{k-1},e_k)=f(f(\dots f(S_0,e_1),\dots ),e_k)$

Consensus is therefore reduced to an agreement problem: ensuring that all non-faulty nodes commit and execute identical log commands in the identical sequence.

---

The FLP Impossibility Result (Fischer, Lynch, Paterson — 1985)

The FLP Impossibility Theorem: In an asynchronous distributed network, no deterministic consensus protocol can guarantee both Safety and Liveness in the presence of even a single unannounced crash failure.

• Safety ("Nothing Bad Happens"): All non-faulty nodes agree on the same value, and the agreed value must have been proposed by a client (no phantom states or split-brain divergences).
• Liveness ("Something Good Eventually Happens"): Every non-faulty node eventually decides upon a value without halting or deadlocking indefinitely.

Because real-world networks (like AWS VPCs, cross-region fiber, and Kubernetes overlays) are asynchronous—meaning message delivery delays and processing times are unbounded—practical consensus algorithms (Multi-Paxos, Raft, Zab) prioritize Safety over Liveness.

They guarantee that under any arbitrary network partition or delay, the cluster will never violate linearizability. To regain liveness, they rely on partial synchrony (e.g., randomized election timers or heartbeat timeouts where communication delays are temporarily bounded).

---

2. Multi-Paxos: Theory, Ballots & Hole-Filling

Leslie Lamport’s original Classic Paxos (Single-Decree Paxos) reaches agreement on only a single log slot across a collection of three distinct roles:

1. Proposers: Nodes that advocate client values.
2. Acceptors: The consensus memory quorum that stores and votes on proposed values.
3. Learners: Nodes that execute the decided value once a quorum is achieved.

---

Classic Paxos: The 2-Phase Round Trip

Phase 1a: Prepare

A Proposer chooses a unique, monotonically increasing proposal number $n$ (where $n=\text{round}\cdot \text{total\_nodes}+\text{node\_id}$) and broadcasts Prepare(n) to a majority of Acceptors.

Phase 1b: Promise

When an Acceptor receives Prepare(n):

• If $n>\text{highest\_promised\_ballot}$, the Acceptor promises never to accept any future proposals numbered less than $n$, and returns: $\text{Promise}(n,v_{\text{max}},n_{\text{max}})$ where $v_{\text{max}}$ is the highest-numbered proposal value it has already accepted (if any), and $n_{\text{max}}$ is the ballot number at which it accepted $v_{\text{max}}$.
• If $n\le \text{highest\_promised\_ballot}$, the message is rejected or ignored.

Phase 2a: Accept

Once the Proposer receives promises from a majority ($\lfloor N/2\rfloor +1$) of Acceptors:

• It selects value $v$:
  • If any Acceptor returned a previously accepted value in Phase 1b, $v$ must be set to the value associated with the highest $n_{\text{max}}$ among all promises.
  • If no Acceptor had previously accepted a value, the Proposer is free to use its own client-provided value $v_{\text{client}}$.
• The Proposer broadcasts Accept(n, v) to the Acceptors.

Phase 2b: Accepted

When an Acceptor receives Accept(n, v):

• It accepts $(n,v)$ if and only if it has not promised to ignore ballot $n$ (i.e., $\text{highest\_promised\_ballot}\le n$).
• It broadcasts Accepted(n, v) to the Proposer and Learners.

---

Multi-Paxos: Eliminating Phase 1 Overheads

Classic Paxos requires 2 full round-trip times (RTTs) for every single log entry. In a high-throughput database, running Phase 1 for every write is catastrophic for latency.

Key Invariant: Phase 1 is executed only once per leadership epoch. For all subsequent log commands, Phase 1 is skipped entirely.

For all subsequent log entries, the Leader skips directly to Phase 2 (Accept $\to$ Accepted), reducing steady-state commit latency to 1 RTT:

---

The Complexities of Multi-Paxos in Production

While Multi-Paxos looks clean in academic papers, production implementations (such as Google’s Chubby and Spanner) encountered severe real-world engineering hurdles:

1. Log Gaps ("Holes"): In Multi-Paxos, slots can be decided out of order. If Slot 101 and Slot 103 are committed, but Slot 102 suffers packet loss, the State Machine cannot advance past Slot 100. The Leader must execute a no-op proposal in Slot 102 to fill the hole before proceeding.
2. Leader Changes with Uncommitted Slots: When a new Leader takes over, it must run Phase 1 across an unbounded range of uncommitted slots to discover any partially accepted proposals from the previous Leader.
3. Role Confusion & Quorum Invariants: Because Proposers, Acceptors, and Learners can be decoupled or co-located in arbitrary topologies, formal verification of dynamic cluster membership changes becomes intensely difficult.

---

3. Raft Deconstructed: Consensus Through Understandability

Designed by Diego Ongaro and John Ousterhout at Stanford in 2014, Raft was engineered with a primary design objective: Understandability.

Raft achieves the exact same formal safety guarantees as Multi-Paxos but decomposes the consensus problem into three strictly defined, independent sub-problems:

1. Leader Election: Selecting a single cluster leader upon startup or heartbeat failure.
2. Log Replication: Unidirectional distribution and reconciliation of log entries from the Leader to Followers.
3. Safety: Enforcing invariants that prevent state machine divergence across leadership transitions.

---

The Raft Cluster Node Invariant Matrix

At any point in logical time, each node in a Raft cluster exists in one of three mutually exclusive roles:

---

1. Randomized Election Timers & Split-Vote Prevention

In symmetric protocols, when a Leader crashes, multiple followers simultaneously time out and become candidates. If Node B and Node C both request votes at Term 2 in a 4-node cluster, each might collect 2 votes, causing a Split Vote:

$\text{Votes}(\text{Node B})=2,\text{Votes}(\text{Node C})=2(\text{Threshold }\ge 3)$

Neither candidate achieves a majority, the election times out, and the cluster risks perpetual livelock.

Raft eliminates split-vote livelocks using randomized election timeouts:

$T_{\text{election}}\in [T_{\text{min}},T_{\text{max}}](\text{typically }[150\text{ms},300\text{ms}])$

Because timeout intervals are chosen randomly from a uniform distribution, one node’s timer almost always fires significantly ahead of its peers (e.g., $170\text{ms}$ vs $240\text{ms}$). The winning candidate claims the majority votes and broadcasts heartbeats before competitors time out, ensuring elections resolve in a single round trip.

---

2. Log Replication & The Strong Leader Invariant

In Raft, logs flow strictly in one direction: from the Leader to Followers. Followers never overwrite or modify the Leader’s log entries.

The Log Matching Property

Raft enforces two critical invariants:

1. If two entries in different logs have the same index and term, they store the exact same command.
2. If two entries in different logs have the same index and term, then their logs are identical in all preceding entries.

AppendEntries Consistency Check

When the Leader sends AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit):

• The follower checks its local log at prevLogIndex.
• If the follower does not have an entry at prevLogIndex with term prevLogTerm, it rejects the request (Success = false).
• Upon rejection, the Leader decrements nextIndex for that follower and retries until a common ancestor is reached. Once the follower accepts, it overwrites any conflicting uncommitted entries with the Leader’s authoritative entries.

---

3. Log Compaction & Memory-Mapped Snapshots

An append-only log cannot grow indefinitely in memory. As transactions accumulate, disk and RAM exhaustion will crash the process.

Snapshot Structure

When the log reaches a predefined byte limit (e.g., 64MB in etcd), the state machine creates a point-in-time snapshot containing:

1. Applied State Data: The complete key-value or relational dataset state.
2. lastIncludedIndex: The highest log index applied to the snapshot.
3. lastIncludedTerm: The term of lastIncludedIndex.
4. Cluster Configuration: The active membership schema at lastIncludedIndex.

Once the snapshot is flushed to disk, all log entries through lastIncludedIndex are discarded. If a lagging follower is so far behind that its nextIndex is no longer in the Leader’s log, the Leader streams the snapshot via the InstallSnapshot RPC.

---

4. Cluster Membership Changes: Joint Consensus

Changing cluster membership dynamically (e.g., adding Node D and Node E to an existing 3-node cluster) is hazardous. If nodes switch their configuration independently, the cluster can temporarily have two disjoint majorities:

To prevent split-brain during configuration transitions, Raft uses a two-phase Joint Consensus approach:

$C_{\text{old}}⟶C_{\text{old,new}}⟶C_{\text{new}}$

1. Enter Joint Consensus ($C_{\text{old,new}}$): The Leader logs and commits a configuration entry containing both $C_{\text{old}}$ and $C_{\text{new}}$. Decisions (elections and log commits) require separate majorities from both the old configuration and the new configuration independently.
2. Finalize ($C_{\text{new}}$): Once $C_{\text{old,new}}$ is committed, the Leader creates an entry for $C_{\text{new}}$ and replicates it. Once $C_{\text{new}}$ is committed, nodes not in $C_{\text{new}}$ are gracefully shut down.

---

4. Multi-Paxos vs. Raft: Complete Architectural Comparison

---

5. Production Failure Modes & Jepsen Chaos Engineering

In mission-critical infrastructure, subtle edge-case partitions can trick consensus algorithms into returning stale data or corrupting state machines.

---

Failure Mode 1: The Phantom Leader & Stale Reads

The Scenario: A network partition isolates Node A (the Term 1 Leader) and Node E from the rest of the cluster (Nodes B, C, D). Nodes B, C, and D elect Node B as the Term 2 Leader.

• Writes: When a client sends a write to Node A, Node A attempts to replicate to Node E, achieves only $2/5$ votes, and cannot commit the write. Safety is preserved.
• Reads: If a client sends a read query to Node A, and Node A naively reads its local state machine without talking to peers, it will return stale data because Node B is actively committing new writes in Term 2!

The Fix: The ReadIndex & LeaseRead Protocols

To maintain strict linearizability ($O(1)$ read latency without writing to disk):

1. ReadIndex Protocol:
   • When a read request arrives at the Leader, it records its current commitIndex as readIndex.
   • The Leader sends a heartbeat (empty AppendEntries) to a majority of nodes to confirm it is still the legitimate leader.
   • Once confirmed, the Leader waits until its state machine has applied at least up to readIndex, and then returns the state machine value to the client.
2. Leader Leases:
   • The Leader assumes it retains leadership for a bounded lease duration (e.g., $100\text{ms}$) as long as followers do not start new elections.
   • If local clocks have bounded drift, the Leader can serve linearizable reads locally during the lease window without network round-trips.

---

Failure Mode 2: Disruptive Server & Pre-Vote Protocol

The Scenario: Node E is partitioned from the cluster. Its election timer expires. It increments its term ($\text{Term}\to 3$), broadcasts RequestVote, receives no responses, times out, increments again ($\text{Term}\to 4\dots 10$).

When the network partition heals, Node E broadcasts RequestVote(Term=10) to the cluster. When the healthy Leader (Node B, Term 2) receives Term 10, it is forced to step down to Follower, disrupting the entire cluster’s active throughput!

The Fix: The Pre-Vote Phase

Before a node increments its currentTerm, it enters a Pre-Candidate state and sends a PreVote RPC:

• Peers grant a PreVote only if:
  1. The candidate’s log is at least as up-to-date as theirs.
  2. The peer has not heard from a valid leader for longer than the minimum election timeout.
• Because healthy followers are actively receiving heartbeats from Node B, they reject Node E's PreVote. Node E never increments its term, and the active leader is never disrupted.

---

6. Implementation: Production-Grade Raft Node in Go

Below is a fully functional, concurrency-safe, production-grade implementation of a Raft Consensus Engine featuring Role State Transitions, Randomized Election Timers, Vote Counting, and AppendEntries Heartbeats in Go.

---

7. Real-World Implementations: Spanner vs. etcd vs. CockroachDB vs. KRaft

1. Google Spanner: Multi-Paxos with TrueTime

• Architecture: Spanner groups spans of data into Paxos consensus groups replicated across continents.
• The Linearizability Trick: Instead of executing Raft ReadIndex round-trips for every cross-region read, Spanner uses TrueTime (GPS receivers and atomic clocks in data centers with bounded uncertainty $[\text{earliest},\text{latest}]$).
• Commit-Wait: Spanner waits out the clock uncertainty $ϵ$ (typically $<7\text{ms}$) before committing a write, guaranteeing that read transactions at timestamp $T$ reflect all writes committed before $T$ without running read-phase consensus!

2. etcd: The Engine Behind Kubernetes

• Architecture: Implements Diego Ongaro’s Raft in pure Go (go.etcd.io/raft).
• Design Philosophy: Minimalist, single-Raft cluster (typically 3 or 5 nodes). Every Kubernetes resource create/update/delete passes through etcd's linearizable log.
• Storage: Backed by bbolt (B+ Tree copy-on-write key-value store) with automatic MVCC revisions and memory-mapped snapshotting.

3. CockroachDB & TiKV: Multi-Raft Range Architectures

• The Scaling Problem: A single Raft group cannot scale past one machine's disk I/O throughput.
• The Solution (Multi-Raft): CockroachDB splits the global keyspace into 64MB ranges. Each 64MB range forms an independent, isolated Raft consensus group across 3 nodes.
• Scale: A 100-node CockroachDB cluster manages over 500,000 independent concurrent Raft groups, balancing throughput and leader leases across hardware CPU cores.

4. Apache Kafka: KRaft (KIP-500)

• The ZooKeeper Bottleneck: ZooKeeper stored partition metadata outside Kafka, requiring slow external synchronization that limited clusters to ~200,000 partitions.
• KRaft (Kafka Raft Metadata Mode): Integrates an event-driven Raft quorum directly into the Kafka broker JVM. Metadata updates are written as standard Kafka event log records, scaling clusters to millions of partitions with sub-second controller failover.

---

8. Architectural Summary & Decision Framework

Key Engineering Takeaways:

1. Mathematical Equivalence, Divergent Usability: Raft and Multi-Paxos provide the identical safety invariants for Replicated State Machines. Raft's structural decomposition of Leader Election, Contiguous Log Replication, and Joint Consensus avoids the edge-case state-space explosion inherent in Multi-Paxos hole-filling.
2. Read Linearizability is Not Free: Naive local reads on consensus leaders violate linearizability during network partitions. Production engines must enforce ReadIndex quorum verification, Pre-Vote protocols, or synchronized physical clock leader leases.
3. Consensus Must Be Sharded: Production distributed databases never run a single global consensus loop. They employ Multi-Raft architectures, partitioning the global keyspace into thousands of discrete, localized state machines.

---

9. Architectural FAQs

Q: Why do consensus clusters almost always use 3, 5, or 7 nodes? Consensus quorums require a strict majority $\lfloor N/2\rfloor +1$. A 3-node cluster tolerates 1 failure ($3-2=1$). A 4-node cluster still requires 3 votes for a majority, tolerating the exact same 1 failure as a 3-node cluster while adding network overhead. Odd numbers ($2F+1$) maximize fault tolerance per node cost.

Q: Can a Raft leader commit an entry from a previous term directly? No! Section 5.4.2 of the Raft paper demonstrates that a Leader cannot determine commitment of an older entry simply by counting replicas. The Leader must commit an entry from its own current term by replicating it to a majority, which indirectly commits all preceding entries by the Log Matching Property.

Q: What is the difference between Linearizability and Serializability?

• Serializability: A multi-transaction property (from ACID). It guarantees that concurrent transactions yield the same final state as some sequential execution, but allows arbitrary time skew (historical reads).
• Linearizability: A single-operation, real-time recency guarantee. If operation $B$ starts after operation $A$ completes in physical time, $B$ must see $A$’s result.
• Strict Serializability (External Consistency): The gold standard combining both properties (achieved by Spanner and CockroachDB).