Demystifying Distributed Consensus: From Paxos to Raft and Multi-Raft in Modern Storage Engines

The Impossibility of Naive Coordination

Building distributed storage systems is fundamentally an exercise in managing partial failure. In a single-node system running SQLite or PostgreSQL on NVMe storage, linearizability is straightforward: the operating system page cache, write-ahead log (WAL), and atomic filesystem primitives (like fsync) guarantee that once a transaction commits, all subsequent reads observe its effects.

The moment you scale across multiple independent machines connected over an asynchronous Ethernet or WAN fabric, the guarantees dissolve:

1. Network Partitions: Packets can be delayed arbitrarily, reordered, duplicated, or dropped without notification.
2. Crash-Recovery Failures: Nodes may pause due to GC stop-the-world cycles, crash and reboot with stale memory, or experience clock drift.
3. The FLP Impossibility Theorem (Fischer, Lynch, Paterson, 1985): In an asynchronous network, no deterministic consensus protocol can guarantee both safety (nothing bad happens) and liveness (something good eventually happens) in the presence of even a single unannounced fail-stop fault.

To build reliable distributed databases—such as CockroachDB, TiDB/TiKV, Google Spanner, or etcd—engineers sacrifice deterministic liveness under severe partitions to guarantee absolute safety and linearizability using quorum-based consensus protocols.

---

Why Paxos Left an Engineering Vacuum

For decades, Leslie Lamport's Paxos protocol stood as the gold standard of consensus. However, anyone who has attempted to implement Multi-Paxos in production (famously documented in Mike Burrows' Chubby paper and the Paxos Made Live report from Google) discovered a stark reality:

"There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system... The final system will be based on an unproven protocol." — Paxos Made Live, Google (2007)

Multi-Paxos does not mandate a strong leader, allows out-of-order log entries, and handles log compaction and dynamic membership changes as separate, poorly specified theoretical extensions.

In 2014, Diego Ongaro and John Ousterhout introduced Raft at Stanford, specifically designed with understandability and formal decomposability as primary design goals.

---

The Anatomy of Raft Consensus

Raft decomposes the consensus state machine problem into three autonomous sub-protocols:

1. Leader Election: Electing a single distinguished coordinator when the current term expires.
2. Log Replication: Accepting log entries from clients and propagating them in lockstep across a majority quorum.
3. Safety: Guaranteeing that if any server has applied a particular log entry at index $k$ to its state machine, no other server will ever apply a different log entry for index $k$.

+-------------------------------------------------------------------------+
|                                RAFT NODE                                |
|                                                                         |
|  +-------------------+      +------------------+      +---------------+  |
|  | Consensus Module  |<---->|   Log Entries    |<---->| State Machine |  |
|  | (Terms, Heartbeat)|      | (Index, Term, Op)|      | (Key-Value KV)|  |
|  +-------------------+      +------------------+      +---------------+  |
+-------------------------------------------------------------------------+
             ^                         ^                         ^
             | AppendEntries RPC       | RequestVote RPC         | Client Writes
             v                         v                         v

1. Randomized Election Timeouts

To prevent the dreaded "split-vote" scenario where multiple candidates continuously split the ballot evenly:

• Raft assigns every node a randomized election timeout chosen uniformly from a window (typically $150\text{ ms} - 300\text{ ms}$).
• If a follower hears no heartbeat (AppendEntries with empty payload) before its timeout expires, it increments its currentTerm, transitions to the Candidate state, votes for itself, and broadcasts RequestVote RPCs.
• The first candidate to collect votes from a strict majority ($\lfloor N/2 \rfloor + 1$) becomes the Leader and immediately floods the cluster with periodic heartbeats.

2. The Log Matching Invariant

Raft enforces a strict structural invariant across all nodes:

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

When a follower receives an AppendEntries RPC with (prevLogIndex, prevLogTerm), it verifies that its local log at prevLogIndex matches prevLogTerm. If it does not, the follower rejects the RPC. The leader then decrements nextIndex for that follower and retries until a common prefix is found, subsequently overwriting any divergent uncommitted entries.

3. The Current-Term Commit Rule (The Tricky Edge Case)

A subtle bug in naive consensus implementations involves committing entries from older terms. Raft strictly specifies:

A leader never commits an entry from an older term by counting replicas. It only commits entries from its current term by counting replicas, and once an entry from the current term is committed, all prior entries are committed indirectly by the Log Matching Property.

---

Log Compaction: Managing the Infinite Append Log

A production database cannot allow its write-ahead log to grow unbounded until the disk fills. Log compaction collapses historical transactions into a point-in-time state machine snapshot:

1. Local Snapshots: The node writes out its current state machine (e.g., an LSM snapshot) and discards log entries up to index $K$.
2. InstallSnapshot RPC: If a replica has fallen so far behind that the leader has already discarded the logs needed to catch it up, the leader streams an InstallSnapshot RPC to initialize the laggy replica directly from the latest snapshot chunk.

---

Scaling Beyond Single-Raft: The Multi-Raft Architecture

A single Raft consensus group has an inescapable physical limit:

• All writes must funnel through a single leader node.
• The maximum write throughput caps out around 10,000 to 25,000 transactions per second (governed by network round-trips and disk fsync latency).
• Storage capacity cannot exceed what a single node can persist.

To scale horizontal databases like CockroachDB and TiKV to petabytes and millions of QPS, modern systems implement Multi-Raft.

+-----------------------------------------------------------------------------+
|                            MULTI-RAFT CLUSTER                               |
|                                                                             |
|  Node A: [ Range 1 (Leader) ]   [ Range 2 (Follower) ]  [ Range 3 (Follower) ] |
|  Node B: [ Range 1 (Follower) ] [ Range 2 (Leader) ]    [ Range 3 (Follower) ] |
|  Node C: [ Range 1 (Follower) ] [ Range 2 (Follower) ]  [ Range 3 (Leader) ]   |
+-----------------------------------------------------------------------------+

How Multi-Raft Works:

1. Keyspace Range Partitioning: The continuous key range is sliced into small contiguous chunks called Ranges (typically 64 MB to 256 MB, e.g., keys ["a", "m") and ["m", "z")).
2. Independent Raft Groups: Each Range constitutes an independent 3-replica or 5-replica Raft group.
3. Co-locating Storage with LSM-Trees: All local Raft logs and state machines share an underlying storage engine (like RocksDB or Pebble) with prefixed keys (/raft_log/<range_id>/<index> and /data/<range_id>/<user_key>).
4. Dynamic Range Splitting: When a range exceeds the size limit (e.g., 96 MB), the leader proposes a special SplitCommand through Raft. Once committed, the range splits into two sibling ranges with zero downtime and independent leaders.

Through Multi-Raft, distributed storage transforms from a single coordination bottleneck into an elastic fabric capable of scaling linearly across thousands of server nodes.