Paxos, Raft Consensus & Distributed Replication

Key takeaway: A cluster of N nodes tolerates up to F = floor((N - 1) / 2) concurrent failures. A quorum of Q = floor(N / 2) + 1 nodes is strictly required for leader election and committed writes.

Single database instances inevitably experience hardware failures, power outages, and routine maintenance. Without replication, a hardware crash causes permanent data loss and customer downtime. With replication, systems survive node crashes seamlessly.

Paxos, Raft Consensus & Distributed Replication

Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members. They form the foundational substrate of distributed state machines like etcd (Kubernetes), Apache Zookeeper (Kafka), and Google Spanner.

1. The Core Consensus Invariant

In an asynchronous network, messages may be delayed, duplicated, reordered, or lost; nodes may crash or pause. The consensus problem requires satisfying three properties:

Agreement: Every non-faulty node must agree on the same value.
Validity: If a value is chosen, it must have been proposed by a node.
Termination (Liveness): All non-faulty nodes eventually decide upon a value (subject to the Fischer-Lynch-Paterson FLP impossibility theorem, which states that no deterministic asynchronous consensus algorithm can guarantee termination in the presence of even one unannounced crash).

2. Raft Architecture

Raft decomposes consensus into three independent sub-problems:

Leader Election: When a cluster boots or the existing leader crashes, a new leader is elected through randomized election timeouts (150\text{--}300\text{ ms}).
Log Replication: The leader accepts log entries from clients, appends them to its local log, and propagates them to followers.
Safety: If any server has applied a particular log entry to its state machine, no other server will ever apply a different log entry for the same log index.

[ Client ] ---> 1. Write("x = 5")
                   |
                   v
         +-------------------+
         | Leader (Node A)   |
         +-------------------+
            /             \
  2. AppendEntries   2. AppendEntries
          /                 \
         v                   v
+-----------------+ +-----------------+
| Follower Node B | | Follower Node C |
+-----------------+ +-----------------+
   3. Ack ("OK")       3. Ack ("OK")

Fig 1. Raft log replication flow: leader writes to local log, awaits quorum acknowledgments, then commits.

3. Quorum Intersection Math

To prevent split-brain states where two leaders make contradictory decisions, every decision requires a Quorum (Q):

Q = \left\lfloor \frac{N}{2} \right\rfloor + 1

A 3-node cluster requires Q = 2 nodes; tolerates F = 1 failure.
A 5-node cluster requires Q = 3 nodes; tolerates F = 2 failures.

Because any two quorums must overlap by at least one node:

Q_1 \cap Q_2 \neq \emptyset

the overlapping node guarantees that the most up-to-date log entry is known during leader election.

4. Paxos vs Raft Comparison

Dimension	Multi-Paxos	Raft
Understandability	❌ Complex (subtle corner cases in log hole filling)	✅ High (explicit leader states and randomized timers)
Leader Model	Weak leader (any node can propose; leader is optimization)	Strong leader (log entries flow only from leader to followers)
Membership Changes	Complex reconfiguration protocols	Joint Consensus (`alpha_{\text{old}} → \alpha_{\text{old,new}} → \alpha_{\text{new}}`)
Production Implementations	Google Chubby, Spanner, Apache Cassandra (Paxos LWT)	etcd (Kubernetes), CockroachDB, TiKV, HashiCorp Consul

← All Concepts Next: Database Sharding & Range Partitioning →

Deep Dive & Production Considerations