Skip to content

Consensus: Raft / Paxos#

Problem statement (interviewer prompt)

Design a replicated state machine across 5 nodes such that all replicas agree on the order of operations even with crashes and message loss. Tolerate up to 2 node failures. Explain leader election, log replication, safety properties, and how reads are served.

A leader-based protocol where a quorum (majority) of replicas agree on each entry before commit. Tolerates (N-1)/2 failures.

flowchart LR
  C([Client])
  L[Leader]
  F1[Follower 1]
  F2[Follower 2]
  F3[Follower 3]
  F4[Follower 4]
  C --> L
  L --> F1
  L --> F2
  L --> F3
  L --> F4
  F1 -.ack.-> L
  F2 -.ack.-> L
  F3 -.ack.-> L
  F4 -.ack.-> L

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class C client;
    class L,F1,F2,F3,F4 service;

flowchart TB
  subgraph Roles
    LR[Leader]
    FOL[Followers]
    CAND[Candidate]
  end

  subgraph Phases[Raft Phases]
    LE[Leader Election<br/>RequestVote RPC]
    LR2[Log Replication<br/>AppendEntries RPC]
    SAFE[Safety: Election restriction +<br/>commit only current-term entries]
    SNAP[Log Compaction /<br/>Snapshots]
    CFG[Membership Change<br/>joint consensus]
  end

  subgraph State[Persistent State]
    PT[currentTerm]
    PV[votedFor]
    LOG[(log entries<br/>term, index, cmd)]
  end

  subgraph Replication[Replication]
    Q[Majority quorum]
    COMMIT[Commit Index]
    APPLY[Apply to State Machine]
  end

  subgraph Variants[Variants]
    BP[Basic Paxos]
    MP[Multi-Paxos]
    EPX[EPaxos - leaderless]
    FPX[Fast Paxos]
    ZB[Zab - ZooKeeper]
    VR[Viewstamped Replication]
  end

  subgraph Failures
    SP[Split vote]
    NP[Network partition]
    DL[Delayed RPC]
  end

  Client[Client] --> LR
  LR --> LR2
  LR2 --> FOL
  FOL -.ack.-> LR
  LR --> Q --> COMMIT --> APPLY
  LR -. heartbeat .-> FOL
  FOL -. timeout .-> CAND --> LE --> LR
  LR --> SNAP
  Variants --- LE
  Failures --- LE

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Client client;
    class LR,FOL,CAND,LE,SNAP,CFG,PT,PV,Q,COMMIT,APPLY,BP,MP,EPX,FPX,ZB,VR,SP,NP,DL service;
    class LR2,SAFE,LOG datastore;

Raft cheat sheet#

  • Term: monotonically increasing logical clock; one leader per term.
  • RequestVote: candidate asks for votes; granter must have at least as up-to-date a log.
  • AppendEntries: leader replicates entries; serves as heartbeat when empty.
  • Commit rule: entry committed when stored on majority and leader has committed an entry from current term.
  • Membership change: joint configuration C_old,new then C_new.

Paxos vs Raft#

  • Paxos: hard to implement, classical, decouples roles (proposer/acceptor/learner).
  • Multi-Paxos ≈ Raft with elected leader + log of values.
  • Raft simplifies via strong leader and contiguous log.

Performance#

  • Latency = 1 RTT to majority. With 5 nodes, lose 1 RTT to slowest of 3.
  • Throughput bound by leader fsync.
  • Optimizations: pipelined AppendEntries, batched fsync, read leases / read-index.

Where it's used#

  • etcd, Consul, CockroachDB, TiKV, MongoDB (replica set), Kafka KRaft, RethinkDB, Google Chubby (Paxos), Spanner (Paxos per group), Aurora.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD Pub/Sub & message brokers topics, consumer groups, delivery semantics pub-sub-pattern
HLD Raft / Paxos consensus replicated state machine via majority quorum consensus-raft-paxos
HLD Leader/follower replication sync/semi-sync/async replication, failover replication-leader-follower
HLD LSM vs B-Tree engines WAL, memtable, SSTables, compaction storage-engines-lsm-btree
LLD State machines FSM, HSM, transitions, guards state-machines
LLD Testing strategy pyramid, doubles, TDD, contracts testing-strategy
LLD Behavioural patterns Strategy, Observer, State, Command, Chain behavioral-patterns

Quick reference#

Problem#

Replicate a state machine across N nodes so all apply the same ordered commands, even with crashes & message loss. Tolerate f failures with 2f+1 nodes.

Safety properties#

  • Election safety: at most one leader per term.
  • Log matching: if two logs share a (term,index), all prior entries match.
  • Leader completeness: a committed entry is in every future leader's log.
  • State machine safety: never applies different commands at same index.

Liveness#

  • Requires majority of nodes reachable.
  • Randomized election timeout prevents split votes.
  • Pre-vote phase avoids term inflation by partitioned nodes.

Optimizations#

  • Batching + pipelining AppendEntries.
  • Read-index / lease reads: leader serves reads without log append by confirming it's still leader.
  • Learner / non-voting members to scale reads or join slowly.
  • Witness / co-located: 2 voting + 1 witness for cheap quorum.

Common pitfalls#

  • Linearizable reads through stale leader - fix with read-index.
  • Disk fsync absolutely required for currentTerm/votedFor.
  • Snapshot install must not regress committed entries.

Refs#

  • Diego Ongaro, John Ousterhout: "In Search of an Understandable Consensus Algorithm" (Raft, USENIX ATC '14).
  • Lamport: "The Part-Time Parliament" (1998); "Paxos Made Simple" (2001).
  • Howard et al.: "Flexible Paxos: Quorum intersection revisited".
  • Heidi Howard's PhD thesis; Jepsen analyses of etcd/Consul.

FAQ#

What is consensus in distributed systems?#

Consensus is the problem of making a group of nodes agree on a single value or sequence of values despite crashes and message loss. It is the foundation of replicated state machines.

What is the difference between Raft and Paxos?#

Both achieve consensus with the same safety properties. Raft is designed for understandability with explicit leader election and log replication phases. Paxos is older, more abstract, and harder to implement correctly.

How many nodes do I need for Raft?#

Use an odd number, typically 3 or 5. A cluster of N nodes tolerates (N-1)/2 failures. Five nodes survive two failures, which is the sweet spot for production etcd or Consul clusters.

How does Raft elect a leader?#

When a follower's election timeout expires it becomes a candidate, increments its term, and asks for votes. A node that wins a majority becomes leader and starts sending heartbeats and log entries.

Which systems use Raft in production?#

etcd, Consul, CockroachDB, TiKV, MongoDB replica sets, Kafka's KRaft mode, and HashiCorp Nomad all use Raft. Google Chubby and Spanner use Paxos variants.

Further reading#

Curated, high-credibility sources for going deeper on this topic.