DEV Community

Cover image for Distributed Consensus: Raft vs Multi-Paxos & State Machine Replication
Shinde Aditya
Shinde Aditya

Posted on Originally published at initnode.dev

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

#architecture #database #distributedsystems #systemdesign

This deep dive was originally published on InitNode Signal. Explore the interactive systems curriculum on InitNode Graph.

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.

flowchart LR
    subgraph ClientLayer["Client Layer"]
        C1["Client 1"]
        C2["Client 2"]
    end

    subgraph NodeA["Node A (Leader)"]
        SM_A["Deterministic State Machine"]
        Log_A["Replicated Append-Only Log"]
        Cons_A["Consensus Module"]
    end

    subgraph NodeB["Node B (Follower)"]
        SM_B["Deterministic State Machine"]
        Log_B["Replicated Append-Only Log"]
        Cons_B["Consensus Module"]
    end

    subgraph NodeC["Node C (Follower)"]
        SM_C["Deterministic State Machine"]
        Log_C["Replicated Append-Only Log"]
        Cons_C["Consensus Module"]
    end

    C1 -->|Command Proposal| Cons_A
    C2 -->|Command Proposal| Cons_A

    Cons_A <-->|Consensus Protocol RPC| Cons_B
    Cons_A <-->|Consensus Protocol RPC| Cons_C

    Cons_A -->|Append| Log_A
    Cons_B -->|Append| Log_B
    Cons_C -->|Append| Log_C

    Log_A -->|Committed Entries| SM_A
    Log_B -->|Committed Entries| SM_B
    Log_C -->|Committed Entries| SM_C

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. 
sequenceDiagram
    autonumber
    actor Proposer as Proposer (Node A)
    participant Acceptors as Acceptor Quorum (N/2 + 1)
    actor Learners as Learners / State Machine

    Note over Proposer, Acceptors: Phase 1: Prepare & Promise (Ballot Acquisition)
    Proposer->>Acceptors: Prepare(ballot_n)
    Acceptors-->>Proposer: Promise(ballot_n, max_accepted_val, max_accepted_ballot)

    Note over Proposer, Acceptors: Phase 2: Accept & Accepted (Value Commitment)
    Proposer->>Acceptors: Accept(ballot_n, proposed_val)
    Acceptors-->>Proposer: Accepted(ballot_n, proposed_val)
    Acceptors-->>Learners: Commit Decided Value

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:

sequenceDiagram
    autonumber
    actor Client
    participant Leader as Stable Multi-Paxos Leader
    participant Acceptors as Acceptors Quorum

    Note over Leader,Acceptors: Stable Leadership Established (Phase 1 pre-executed)
    Client->>Leader: WriteCommand(X = 10)
    Leader->>Acceptors: Accept(slot_101, ballot_5, X=10)
    Acceptors-->>Leader: Accepted(slot_101, ballot_5)
    Note over Leader: Quorum Achieved (1 RTT)
    Leader-->>Client: Success (Committed in Slot 101)

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. 
stateDiagram-v2
    [*] --> Follower

    Follower --> Candidate: Election Timeout Fires (No Heartbeat)
    Candidate --> Candidate: Split Vote / Timeout (Increment Term, New Ballot)
    Candidate --> Leader: Receives Votes from Majority Quorum
    Candidate --> Follower: Discovers New Leader or Higher Term
    Leader --> Follower: Discovers Peer with Higher Term

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:

Role Operational Invariant & Responsibilities
Follower Passive. Responds to incoming RequestVote and AppendEntries RPCs from Candidates and Leaders. Never initiates RPCs. If no communication is received within a randomized election timeout, transitions to Candidate.
Candidate Active Campaigner. Increments logical currentTerm, votes for itself, and broadcasts RequestVote RPCs to all peers. Strives to collect $\lfloor N/2 \rfloor + 1$ affirmative votes.
Leader Authoritative Master. Handles all client proposals, dictates log appending, coordinates commit indices, and broadcasts periodic AppendEntries heartbeats (every $50\text{ms}$) to suppress follower elections.

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, \quad \text{Votes}(\text{Node C}) = 2 \quad (\text{Threshold } \ge 3)$$

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

sequenceDiagram
    autonumber
    participant NodeA as Node A (Timeout: 170ms)
    participant NodeB as Node B (Timeout: 290ms)
    participant NodeC as Node C (Timeout: 240ms)

    Note over NodeA: 170ms timer fires first!
    NodeA->>NodeA: Become Candidate, Term = 2, Vote for Self
    NodeA->>NodeB: RequestVote(Term=2, CandidateId=A, LastLogIdx=10, LastLogTerm=1)
    NodeA->>NodeC: RequestVote(Term=2, CandidateId=A, LastLogIdx=10, LastLogTerm=1)
    NodeB-->>NodeA: VoteGranted(Term=2)
    NodeC-->>NodeA: VoteGranted(Term=2)
    Note over NodeA: Majority (3/3) Reached!
    NodeA->>NodeA: Become Leader
    NodeA->>NodeB: AppendEntries Heartbeat(Term=2)
    NodeA->>NodeC: AppendEntries Heartbeat(Term=2)
    Note over NodeB,NodeC: Timers reset to 0

Raft eliminates split-vote livelocks using randomized election timeouts:

$$T_{\text{election}} \in [T_{\text{min}}, T_{\text{max}}] \quad (\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.

flowchart TD
    subgraph LeaderLog["Leader Log (Term 2)"]
        L1["[1] Term:1 (Set X=5)"]
        L2["[2] Term:1 (Set Y=2)"]
        L3["[3] Term:2 (Set Z=9) - COMMITTED"]
        L4["[4] Term:2 (Set X=8) - UNCOMMITTED"]
    end

    subgraph Follower1Log["Follower 1 Log"]
        F1_1["[1] Term:1 (Set X=5)"]
        F1_2["[2] Term:1 (Set Y=2)"]
        F1_3["[3] Term:2 (Set Z=9)"]
    end

    subgraph Follower2Log["Follower 2 Log (Lagging / Inconsistent)"]
        F2_1["[1] Term:1 (Set X=5)"]
        F2_2["[2] Term:1 (Set Y=2)"]
        F2_3["[3] Term:1 (Set Z=1) ⚠️ MISMATCH"]
    end

    L3 -->|Replicated to Majority| F1_3
    L4 -.->|In Flight| F1_1
    L3 -->|Leader forces match: Overwrite Slot 3| F2_3

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.

flowchart LR
    subgraph InactiveLog["Compacted into Snapshot"]
        S1["Entry 1: Set a=1"]
        S2["Entry 2: Set b=2"]
        S3["Entry 3: Set a=5"]
        S4["Entry 4: Set c=8"]
    end

    subgraph Snapshot["Raft Snapshot File"]
        State["State Machine State:\n{a: 5, b: 2, c: 8}\nLast Included Index: 4\nLast Included Term: 2"]
    end

    subgraph ActiveLog["Active In-Memory Log"]
        L5["Entry 5: Term 2 (Set d=12)"]
        L6["Entry 6: Term 3 (Set a=9)"]
    end

    InactiveLog -->|Point-in-Time Discard| Snapshot
    Snapshot -.->|Persisted to Disk| ActiveLog

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:

flowchart TD
    subgraph DisjointMajorities["Split Quorum Risk during Naive Reconfiguration"]
        OldQuorum["Old Config (Nodes 1, 2, 3)\nMajority = 2\n(Nodes 1, 2 elect Node 1)"]
        NewQuorum["New Config (Nodes 1, 2, 3, 4, 5)\nMajority = 3\n(Nodes 3, 4, 5 elect Node 5)"]
    end

    OldQuorum ---|Simultaneous Existence| NewQuorum

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

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

sequenceDiagram
    autonumber
    participant Leader
    participant QuorumOld as Old Majority (C_old)
    participant QuorumNew as New Majority (C_new)

    Note over Leader: Step 1: Propose Joint Config C_old,new
    Leader->>QuorumOld: AppendEntries(C_old,new)
    Leader->>QuorumNew: AppendEntries(C_old,new)
    Note over Leader: Requires separate majorities from BOTH C_old AND C_new

    Note over Leader: Step 2: Commit C_old,new & Propose C_new
    Leader->>QuorumOld: AppendEntries(C_new)
    Leader->>QuorumNew: AppendEntries(C_new)
    Note over Leader: Fully transitioned to C_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

Architectural Vector Multi-Paxos (Chubby, Spanner) Raft (etcd, CockroachDB, TiKV, KRaft)
Primary Design Philosophy Symmetric mathematical abstraction; consensus separated from state machine. Understandability, symmetric role decomposition, strong leader hierarchy.
Leader Model Weak / Emergent leader. Multiple proposers can propose values simultaneously; leader is an optimization to skip Phase 1. Strong Leader. All proposals, log replication, and commit decisions flow strictly through the leader.
Log Gaps ("Holes") Allowed. Slots can be committed out of order ($S_1, S_3$ committed while $S_2$ pending). Requires no-op filling. Forbidden. Logs are strictly contiguous. Entry $k$ cannot be committed unless entries $1 \dots k-1$ are committed.
Leader Election Mechanism External lease manager, Paxos ballot voting, or Chubby master lock. Randomized Election Timers ($150\text{ms} - 300\text{ms}$) with built-in term progression.
Read Linearizability Master leases with physical clock synchronization (TrueTime in Spanner). ReadIndex Protocol / Leader Leases with quorum heartbeat confirmation.
Dynamic Membership Complex epoch-based reconfiguration protocols; prone to race conditions without formal proofs. Joint Consensus ($C_{\text{old}} \to C_{\text{old,new}} \to C_{\text{new}}$) and single-server atomic transitions.
Formal Verification TLA+ specifications for core single-decree Paxos; Multi-Paxos implementations frequently diverge from spec. Verified in TLA+, Coq, and rigorously tested in production via Jepsen.

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.

flowchart TD
    subgraph NetworkPartition["Asymmetric Network Partition (3 vs 2 Split)"]
        subgraph MajorityPartition["Majority Partition (Quorum = 3)"]
            NodeB["Node B (New Leader, Term 2)"]
            NodeC["Node C (Follower)"]
            NodeD["Node D (Follower)"]
        end

        subgraph MinorityPartition["Minority Partition (Isolated)"]
            NodeA["Node A (Stale Leader, Term 1)"]
            NodeE["Node E (Follower)"]
        end
    end

    ClientW["Client Write"] -->|Rejected: No Quorum| NodeA
    ClientR["Client Read (Stale!)"] -.->|Stale Read Risk without ReadIndex| NodeA
    ClientW2["Client Write"] -->|Committed: 3/5 Majority| NodeB

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!

sequenceDiagram
    autonumber
    participant NodeE as Partitioned Node E
    participant NodeB as Healthy Leader (Term 2)
    participant NodeC as Follower C (Term 2)

    Note over NodeE: Pre-Vote Protocol Active!
    NodeE->>NodeB: PreVoteRequest(NextTerm=3, LastLogIdx=4)
    NodeE->>NodeC: PreVoteRequest(NextTerm=3, LastLogIdx=4)
    Note over NodeB,NodeC: Reject PreVote: Heartbeats are active!
    NodeB-->>NodeE: PreVoteDenied
    NodeC-->>NodeE: PreVoteDenied
    Note over NodeE: Term is NOT incremented! Cluster is NOT disrupted!

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.

package raft

import (
    "context"
    "fmt"
    "math/rand"
    "sync"
    "time"
)

type Role int

const (
    Follower Role = iota
    Candidate
    Leader
)

func (r Role) String() string {
    switch r {
    case Follower:
        return "FOLLOWER"
    case Candidate:
        return "CANDIDATE"
    case Leader:
        return "LEADER"
    default:
        return "UNKNOWN"
    }
}

// LogEntry encapsulates a replicated state command
type LogEntry struct {
    Index   int
    Term    int
    Command string
}

// RequestVoteArgs RPC payload
type RequestVoteArgs struct {
    Term         int
    CandidateID  int
    LastLogIndex int
    LastLogTerm  int
}

// RequestVoteReply RPC response
type RequestVoteReply struct {
    Term        int
    VoteGranted bool
}

// AppendEntriesArgs RPC payload
type AppendEntriesArgs struct {
    Term         int
    LeaderID     int
    PrevLogIndex int
    PrevLogTerm  int
    Entries      []LogEntry
    LeaderCommit int
}

// AppendEntriesReply RPC response
type AppendEntriesReply struct {
    Term    int
    Success bool
}

// RaftNode represents an active consensus node
type RaftNode struct {
    mu        sync.Mutex
    peers     []*RaftNode
    nodeID    int
    role      Role

    // Persistent State
    currentTerm int
    votedFor    int
    log         []LogEntry

    // Volatile State
    commitIndex int
    lastApplied int

    // Leader-specific Volatile State
    nextIndex  map[int]int
    matchIndex map[int]int

    // Timers & Triggers
    heartbeatInterval time.Duration
    electionResetTime time.Time
    ctx               context.Context
    cancel            context.CancelFunc
}

// NewRaftNode initializes a consensus actor
func NewRaftNode(nodeID int, peersCount int) *RaftNode {
    ctx, cancel := context.WithCancel(context.Background())
    node := &RaftNode{
        nodeID:            nodeID,
        role:              Follower,
        currentTerm:       0,
        votedFor:          -1,
        log:               []LogEntry{{Index: 0, Term: 0, Command: "INIT_ROOT"}},
        commitIndex:       0,
        lastApplied:       0,
        nextIndex:         make(map[int]int),
        matchIndex:        make(map[int]int),
        heartbeatInterval: 50 * time.Millisecond,
        ctx:               ctx,
        cancel:            cancel,
    }

    node.resetElectionTimeout()
    go node.runElectionTimer()
    return node
}

func (rn *RaftNode) SetPeers(peers []*RaftNode) {
    rn.mu.Lock()
    defer rn.mu.Unlock()
    rn.peers = peers
}

func (rn *RaftNode) resetElectionTimeout() {
    // Uniform random timeout: 150ms to 300ms
    d := time.Duration(150+rand.Intn(150)) * time.Millisecond
    rn.electionResetTime = time.Now().Add(d)
}

func (rn *RaftNode) runElectionTimer() {
    ticker := time.NewTicker(10 * time.Millisecond)
    defer ticker.Stop()

    for {
        select {
        case <-rn.ctx.Done():
            return
        case <-ticker.C:
            rn.mu.Lock()
            if rn.role != Leader && time.Now().After(rn.electionResetTime) {
                rn.startElection()
            }
            rn.mu.Unlock()
        }
    }
}

func (rn *RaftNode) startElection() {
    rn.role = Candidate
    rn.currentTerm++
    rn.votedFor = rn.nodeID
    rn.resetElectionTimeout()
    term := rn.currentTerm
    lastLogIdx := len(rn.log) - 1
    lastLogTerm := rn.log[lastLogIdx].Term

    fmt.Printf("[Node %d] Election timeout! Starting election for Term %d\n", rn.nodeID, term)

    votesReceived := 1
    var voteMu sync.Mutex

    for _, peer := range rn.peers {
        if peer.nodeID == rn.nodeID {
            continue
        }

        go func(target *RaftNode) {
            args := RequestVoteArgs{
                Term:         term,
                CandidateID:  rn.nodeID,
                LastLogIndex: lastLogIdx,
                LastLogTerm:  lastLogTerm,
            }
            reply := target.RequestVote(args)

            rn.mu.Lock()
            defer rn.mu.Unlock()

            if reply.Term > rn.currentTerm {
                rn.currentTerm = reply.Term
                rn.role = Follower
                rn.votedFor = -1
                rn.resetElectionTimeout()
                return
            }

            if rn.role == Candidate && reply.Term == rn.currentTerm && reply.VoteGranted {
                voteMu.Lock()
                votesReceived++
                currentVotes := votesReceived
                voteMu.Unlock()

                // Quorum achieved: majority = (N / 2) + 1
                if currentVotes > len(rn.peers)/2 && rn.role != Leader {
                    rn.role = Leader
                    fmt.Printf("⚡ [Node %d] WON ELECTION! Became LEADER for Term %d\n", rn.nodeID, rn.currentTerm)
                    for _, p := range rn.peers {
                        rn.nextIndex[p.nodeID] = len(rn.log)
                        rn.matchIndex[p.nodeID] = 0
                    }
                    go rn.runHeartbeatBroadcaster(rn.currentTerm)
                }
            }
        }(peer)
    }
}

func (rn *RaftNode) RequestVote(args RequestVoteArgs) RequestVoteReply {
    rn.mu.Lock()
    defer rn.mu.Unlock()

    // 1. Term check
    if args.Term > rn.currentTerm {
        rn.currentTerm = args.Term
        rn.role = Follower
        rn.votedFor = -1
    }

    reply := RequestVoteReply{Term: rn.currentTerm, VoteGranted: false}

    // 2. Voting safety conditions
    lastLogIdx := len(rn.log) - 1
    lastLogTerm := rn.log[lastLogIdx].Term
    logOk := args.LastLogTerm > lastLogTerm || (args.LastLogTerm == lastLogTerm && args.LastLogIndex >= lastLogIdx)

    if args.Term == rn.currentTerm && (rn.votedFor == -1 || rn.votedFor == args.CandidateID) && logOk {
        reply.VoteGranted = true
        rn.votedFor = args.CandidateID
        rn.resetElectionTimeout()
        fmt.Printf("[Node %d] Voted for Node %d in Term %d\n", rn.nodeID, args.CandidateID, args.Term)
    }

    return reply
}

func (rn *RaftNode) runHeartbeatBroadcaster(term int) {
    ticker := time.NewTicker(rn.heartbeatInterval)
    defer ticker.Stop()

    for {
        select {
        case <-rn.ctx.Done():
            return
        case <-ticker.C:
            rn.mu.Lock()
            if rn.role != Leader || rn.currentTerm != term {
                rn.mu.Unlock()
                return
            }

            for _, peer := range rn.peers {
                if peer.nodeID == rn.nodeID {
                    continue
                }

                go func(target *RaftNode) {
                    rn.mu.Lock()
                    prevIdx := rn.nextIndex[target.nodeID] - 1
                    prevTerm := rn.log[prevIdx].Term
                    entries := rn.log[rn.nextIndex[target.nodeID]:]

                    args := AppendEntriesArgs{
                        Term:         rn.currentTerm,
                        LeaderID:     rn.nodeID,
                        PrevLogIndex: prevIdx,
                        PrevLogTerm:  prevTerm,
                        Entries:      entries,
                        LeaderCommit: rn.commitIndex,
                    }
                    rn.mu.Unlock()

                    reply := target.AppendEntries(args)

                    rn.mu.Lock()
                    defer rn.mu.Unlock()

                    if reply.Term > rn.currentTerm {
                        rn.currentTerm = reply.Term
                        rn.role = Follower
                        rn.votedFor = -1
                        rn.resetElectionTimeout()
                        return
                    }

                    if rn.role == Leader && reply.Term == rn.currentTerm {
                        if reply.Success {
                            rn.nextIndex[target.nodeID] = prevIdx + len(entries) + 1
                            rn.matchIndex[target.nodeID] = rn.nextIndex[target.nodeID] - 1
                        } else {
                            // Step back nextIndex on mismatch
                            if rn.nextIndex[target.nodeID] > 1 {
                                rn.nextIndex[target.nodeID]--
                            }
                        }
                    }
                }(peer)
            }
            rn.mu.Unlock()
        }
    }
}

func (rn *RaftNode) AppendEntries(args AppendEntriesArgs) AppendEntriesReply {
    rn.mu.Lock()
    defer rn.mu.Unlock()

    reply := AppendEntriesReply{Term: rn.currentTerm, Success: false}

    if args.Term < rn.currentTerm {
        return reply
    }

    if args.Term > rn.currentTerm {
        rn.currentTerm = args.Term
        rn.role = Follower
        rn.votedFor = -1
    }

    rn.resetElectionTimeout()

    // Verify log consistency at PrevLogIndex
    if args.PrevLogIndex >= len(rn.log) || rn.log[args.PrevLogIndex].Term != args.PrevLogTerm {
        return reply
    }

    // Append any new entries not already in local log
    rn.log = append(rn.log[:args.PrevLogIndex+1], args.Entries...)

    if args.LeaderCommit > rn.commitIndex {
        rn.commitIndex = min(args.LeaderCommit, len(rn.log)-1)
    }

    reply.Success = true
    return reply
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
Enter fullscreen mode Exit fullscreen mode

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

graph TD
    A[Production Distributed Systems] --> B[Spanner: Multi-Paxos + TrueTime]
    A --> C[etcd: Core Raft Quorum]
    A --> D[CockroachDB: Multi-Raft Partition Ranges]
    A --> E[Kafka KRaft: Event Log Quorum Controller]

    B --> B1[External Consistency via GPS Atomic Clocks]
    C --> C1[Kubernetes Single-State Coordinator]
    D --> D1[Millions of 64MB Consensus Ranges]
    E --> E1[Replaces ZooKeeper with In-Memory Raft Event Log]

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 $\epsilon$ (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 

flowchart TD
    Start[Choose Consensus Architecture] --> Q1{Is Global Scalability > 100k writes/sec required?}

    Q1 -- Yes --> MultiRaft[Multi-Raft Range Architecture\nCockroachDB / TiKV / Spanner]
    Q1 -- No --> Q2{Do you have hardware atomic clocks?}

    Q2 -- Yes --> PaxosTrueTime[Multi-Paxos + TrueTime Leases\nGoogle Spanner]
    Q2 -- No --> Q3{Is implementation clarity & verifiability paramount?}

    Q3 -- Yes --> Raft[HashiCorp / etcd Raft\netcd, Consul, Kafka KRaft]
    Q3 -- No --> ClassicPaxos[Custom Multi-Paxos Engine]

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).

Top comments (1)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.