Consensus Algorithms, Underground (Part 2) — The Crash Failure Family: Paxos and Raft

Part 1 established that crashes and delays are indistinguishable, that majority quorums do not protect anything outside the cluster, and that the log and the applied state are different things. This part covers the first family built on that substrate: the crash failure model, in which nodes stop but do not lie.

Paxos: Nothing but Intersecting Majorities

Paxos targets the safe decision of a single value across multiple nodes where crash failures may occur.

Proposals carry monotonically increasing numbers. Once a majority has accepted a higher-numbered proposal, older proposals are rejected. The basic structure has two phases: Prepare/Promise and Accept/Accepted.

class Acceptor:
    def __init__(self):
        self.promised = -1
        self.accepted_number = None
        self.accepted_value = None

    def prepare(self, number):
        if number <= self.promised:
            return None
        self.promised = number
        return self.accepted_number, self.accepted_value

    def accept(self, number, value):
        if number < self.promised:
            return False
        self.promised = number
        self.accepted_number = number
        self.accepted_value = value
        return True

After obtaining Promises from a majority, the proposer adopts the highest-numbered previously accepted value, if one exists. This is the core of Paxos: the proposer does not push its own value, it defers to a value that may already have been decided.

responses = [a.prepare(n) for a in acceptors]
responses = [r for r in responses if r is not None]

if len(responses) >= quorum:
    previously_accepted = [r for r in responses if r[0] is not None]
    if previously_accepted:
        value = max(previously_accepted)[1]

    accepted = sum(a.accept(n, value) for a in acceptors)
    decided = accepted >= quorum

The safety argument is simple. The only property Paxos uses is that any two majority quorums intersect. With five nodes a majority is three, and any two sets of three share at least one node. That shared node carries the previous decision candidate forward into the next proposal.

Basic Paxos and Multi-Paxos

Basic Paxos decides a single value. A database needs a continuous log, so Multi-Paxos is used in practice. While a stable leader exists, Prepare is skipped and only Accept is repeated for each log slot.

leader
 ├─ ACCEPT slot=101 value=A
 ├─ ACCEPT slot=102 value=B
 └─ ACCEPT slot=103 value=C

With this optimization included, the runtime shapes of Multi-Paxos and Raft converge. Their principal difference lies in how leader election and log consistency are specified. Comparative studies likewise find substantial commonality between Raft and Paxos, with leader election identified as the main distinction.

Google’s Spanner and Chubby lineage replicates data per Paxos group. Modern implementations, however, are not the Basic Paxos of the paper but bespoke Multi-Paxos with persistence, leader leases, reconfiguration, snapshots, and batching.

Raft: The Same Safety, Decomposed into Something Implementable

Raft’s goal is to structure crash tolerance equivalent to Paxos into a form implementers can understand. The official site likewise describes it as an algorithm with fault tolerance and performance equivalent to Paxos, designed for understandability.

Raft partitions the problem explicitly: leader election, log replication, safety, membership changes, and log compaction.

from dataclasses import dataclass

@dataclass
class Entry:
    term: int
    command: bytes

class RaftNode:
    def __init__(self, node_id, peers):
        self.node_id = node_id
        self.peers = peers
        self.state = "follower"
        self.current_term = 0
        self.voted_for = None
        self.log = []
        self.commit_index = -1
        self.last_applied = -1

The minimum state requiring persistence is currentTerm, votedFor, and log[]. Responding before these are durably written to disk allows a node to vote for multiple candidates in the same term after a restart, or to lose entries it had accepted.

Leader Election

A follower becomes a candidate once the election timeout expires.

def start_election(self):
    self.state = "candidate"
    self.current_term += 1
    self.voted_for = self.node_id
    votes = 1

    for peer in self.peers:
        response = peer.request_vote(
            term=self.current_term,
            candidate_id=self.node_id,
            last_log_index=len(self.log) - 1,
            last_log_term=self.log[-1].term if self.log else 0,
        )
        if response.term > self.current_term:
            self.become_follower(response.term)
            return
        votes += int(response.granted)

    if votes >= self.quorum():
        self.become_leader()

The voter verifies that the candidate’s log is at least as up to date as its own.

def request_vote(self, term, candidate_id, last_log_index, last_log_term):
    if term < self.current_term:
        return VoteResponse(self.current_term, False)

    if term > self.current_term:
        self.become_follower(term)

    local_term = self.log[-1].term if self.log else 0
    local_index = len(self.log) - 1

    up_to_date = (
        last_log_term > local_term
        or (last_log_term == local_term and last_log_index >= local_index)
    )

    can_vote = self.voted_for in (None, candidate_id)
    granted = can_vote and up_to_date

    if granted:
        self.voted_for = candidate_id
        self.persist_term_and_vote()

    return VoteResponse(self.current_term, granted)

This up-to-date check prevents a node missing committed entries from becoming leader. Where Paxos recovers past values at proposal time, Raft restricts eligibility for election itself.

Log Replication

The leader sends AppendEntries carrying the index and term of the preceding entry.

def append_entries(self, term, prev_index, prev_term, entries, leader_commit):
    if term < self.current_term:
        return False

    if prev_index >= 0:
        if prev_index >= len(self.log):
            return False
        if self.log[prev_index].term != prev_term:
            return False

    insert_at = prev_index + 1
    for i, entry in enumerate(entries):
        pos = insert_at + i
        if pos < len(self.log) and self.log[pos].term != entry.term:
            self.log = self.log[:pos]
        if pos == len(self.log):
            self.log.append(entry)

    self.persist_log()

    if leader_commit > self.commit_index:
        self.commit_index = min(leader_commit, len(self.log) - 1)

    return True

On a mismatch, the follower truncates its uncommitted suffix and aligns with the leader’s log.

What Raft Actually Solved

Raft’s value lies less in inventing new safety properties than in making explicit the boundaries an implementation needs.

• A term denotes a generation
• Only one vote is cast per term
• Votes go only to candidates at least as up to date as the voter
• prevLogIndex and prevLogTerm verify continuity
• Commitment advances only after an entry from the current term is replicated to a majority
• Entries from earlier terms are committed indirectly, together with a current-term entry

The last two rules are easy to overlook. The fact that an entry from an earlier term is present on a majority is not sufficient to declare it committed.

Viewstamped Replication and Zab: The Same Skeleton, Different Names

Viewstamped Replication manages primary/backup replication with view numbers as generations.

view 10: primary=A
view 11: primary=C

The structure is close to Raft’s term. The primary orders operations and replicates them to a quorum of backups. On primary failure a view change occurs, recovering the most recent log from a quorum.

Zab (ZooKeeper Atomic Broadcast) is a leader-based atomic broadcast designed for ZooKeeper. Its aim is not to decide values one at a time, but to give every replica the same order of update history. The transaction ID conceptually pairs a generation with a counter.

zxid = (epoch, counter)

On leader change, the new leader confirms it holds the most recent history and synchronizes followers before accepting new proposals. Where Raft restricts election eligibility via log consistency, Zab places an explicit history-synchronization phase at leader startup.

Raft, Multi-Paxos, Viewstamped Replication, and Zab are close relatives in implementation structure.

epoch / view / term
stable leader
ordered log
majority replication
leader replacement

They differ in the vocabulary used to explain safety, and in the rules for what state is recovered at leader change.

EPaxos: Eliminating the Round Trip to the Leader

In Raft and Multi-Paxos every write passes through a single leader. In a geo-distributed deployment this becomes latency directly.

Tokyo client → US leader → Tokyo replica

A Tokyo client writing to a Tokyo replica still requires a round trip to the leader in the US.

EPaxos removes the fixed leader so that any replica may propose. Rather than placing every operation into a single global order immediately, it agrees on the dependencies between conflicting operations.

@dataclass
class Command:
    id: str
    reads: set[str]
    writes: set[str]

def conflicts(a: Command, b: Command) -> bool:
    return bool(
        a.writes & b.writes
        or a.writes & b.reads
        or b.writes & a.reads
    )

def dependencies(command, known_commands):
    return {
        other.id for other in known_commands
        if conflicts(command, other)
    }

Mutually commutative requests, such as operations on different keys, can be decided on the fast path.

The cost is implementation complexity. Dependency graph management, cycle resolution, fast quorums, a recovery protocol, and computing an executable order are all required, and performance depends on the conflict rate. It is effective for low-conflict workloads, but when every operation updates the same key or the same metadata, dependencies concentrate and the advantage of the fast path shrinks.

Flexible Paxos: Quorums Need Not Be Identical

Standard Paxos uses a majority in both Phase 1 and Phase 2. Safety, however, does not require quorums of the same kind to intersect.

Phase-1 quorum ∩ Phase-2 quorum ≠ ∅

With nine nodes, a design using 7 for Phase 1 and 3 for Phase 2 is valid. Phase 2 dominates in steady state, so writes under a stable leader can proceed with a small quorum; leader change, in exchange, requires a large one.

This is an important perspective in consensus design: not every operation must use the same quorum, and the frequent path can be made light while the rare recovery path is made heavy. Availability failure patterns change accordingly, so “smaller quorum, therefore faster” is not a valid conclusion on its own.

Multi-Raft: Shrinking the Unit of Agreement

In a single large Raft group, every write concentrates on one leader. Data is therefore split into many ranges, with a Raft group per range.

range 1: A B C   leader=A
range 2: B C D   leader=C
range 3: C D E   leader=E

CockroachDB splits data into Ranges and replicates each Range as an independent Raft group. Writes go to the Range’s Raft leader and commit after replication to a majority of logs. TiKV likewise performs Raft replication per data range as a transactional KV store implemented in Rust.

Multi-Raft does not eliminate the problem; it reduces the granularity. New problems appear instead.

• Tick management for hundreds of thousands of Raft groups
• Increased heartbeat traffic
• Contention between Range splits and membership changes
• Leader concentration on hot Ranges
• Transactions spanning multiple Ranges
• I/O saturation from snapshot transfer

What the Papers Do Not Say

From here on lies the part that algorithm papers do not cover. An instructional Raft fits in a few hundred lines; what production requires is everything around it.

Ordering of Persistence

incorrect:            correct:
  send success          write WAL
  write WAL             fsync
                        send vote or success

In practice, the ordering among the WAL, metadata, data pages, and snapshots must be designed as well.

Batching and Backpressure

Calling fsync per entry is slow, so proposals are grouped. Larger batches increase throughput and also increase latency.

batch = []
deadline = now() + MAX_DELAY

while len(batch) < MAX_BATCH and now() < deadline:
    command = try_receive()
    if command:
        batch.append(command)

append_and_fsync(batch)
replicate(batch)

When a follower lags, sending AppendEntries without limit inflates memory and the send queue.

if peer.inflight_bytes > MAX_INFLIGHT:
    pause_replication(peer)
else:
    send_append_entries(peer)

etcd’s Raft library implements optimistic pipelining, flow control, batching of messages and log entries, and protection against unbounded log growth when quorum is lost.

Snapshots and Log Compaction

A log retained forever keeps growing.

if applied_index - snapshot_index > SNAPSHOT_THRESHOLD:
    snapshot = state_machine.serialize()
    persist_snapshot(snapshot, applied_index)
    truncate_log(before=applied_index)

Getting the order wrong makes recovery impossible. The safe baseline order is as follows.

1. produce the state machine snapshot
2. persist the snapshot metadata
3. confirm the snapshot is definitely readable
4. delete the corresponding log entries

Membership Changes

Switching from three nodes to five in one step can produce two majorities — one under the old configuration, one under the new — that do not intersect. Raft therefore uses joint consensus.

C_old → C_old,new → C_new

During the transition, a quorum is required under both configurations.

Linearizable Reads

Being the leader does not license returning the latest value unconditionally, because the node may be a stale leader after a partition. There are three main approaches.

etcd’s Raft implements both ReadIndex-style and lease-style linearizable reads.

Separating the Algorithm from I/O

etcd’s Raft library models Raft as a deterministic state machine. The inputs are a local tick or a network message; the outputs are messages to send, entries to persist, and state changes. Networking, disk, and application to the state machine are left to the caller.

for {
    select {
    case <-ticker.C:
        node.Tick()

    case msg := <-network:
        node.Step(ctx, msg)

    case ready := <-node.Ready():
        wal.Save(ready.HardState, ready.Entries)
        transport.Send(ready.Messages)
        applySnapshot(ready.Snapshot)
        applyCommitted(ready.CommittedEntries)
        node.Advance()
    }
}

This structure is not a stylistic preference. Embedding socket communication and disk I/O directly into the Raft core makes fault injection, deterministic testing, and replay verification all impractical. etcd’s official raftexample likewise separates the Raft server, the KV store applying committed updates, and the REST API.

The periphery a production Raft implementation carries looks roughly like this.

Raft core
 ├─ durable WAL
 ├─ snapshot manager
 ├─ transport / TLS and identity
 ├─ message deduplication
 ├─ batching / backpressure
 ├─ membership changes
 ├─ read index / leader lease
 ├─ clock assumptions
 ├─ disk failure handling / corruption detection
 ├─ metrics / tracing / fault injection
 └─ rolling upgrade / state-machine versioning

Deciding to write a consensus algorithm from scratch for a new database or distributed storage system therefore warrants caution. For the crash failure model in particular, it is more realistic to use a proven library separated as a state machine — etcd/raft or TiKV’s raft-rs — and build the storage, transport, and application layers oneself.

Summary

• The only tool Paxos uses is that any two majority quorums intersect. The proposer propagates a value that may already have been decided, not its own.
• Raft decomposed the same safety into implementable rules: restricted election eligibility and log continuity checks. It is structurally close to Multi-Paxos, VR, and Zab.
• EPaxos removes the fixed leader to cut geo-distributed round trips; Flexible Paxos showed that the frequent path and the rare recovery path can use different quorums.
• Multi-Raft shrinks the unit of agreement; it is not leaderlessness. Tick management and hot Ranges appear as new problems.
• Most of a production implementation lives outside the papers: persistence ordering, batching, backpressure, snapshots, membership changes, and linearizable reads.

Part 3 raises the failure model one level, to Byzantine faults in which nodes not only stop but send signed, contradictory information, covering PBFT through HotStuff and the DAG-BFT designs that separate data dissemination from ordering.