Consensus | System Design Interview Handbook

🗳

Why Consensus Is Needed

anywhere "exactly one" must be true

Consensus is getting a set of machines to agree on a single value even when some of them fail. You need it wherever exactly one of something must be true across the cluster: one leader (Replication), one holder of a distributed lock (Concurrency Control), one authoritative cluster membership list (Discovery), one agreed config value. Get disagreement here and you get split brain, double execution, corruption.

🌫

Why It's Hard

you can't tell slow from dead

On an asynchronous network, a silent node is indistinguishable from a slow one — no reply could mean crashed, or just lagging. FLP (the Fischer-Lynch-Paterson result) makes it formal: in a fully asynchronous network where even one node can fail, no algorithm can guarantee consensus in bounded time. You can't have perfect agreement, guaranteed termination, and fault tolerance all at once.

ℹ️

Practical systems sidestep FLP with timeouts and randomness: assume a node that's silent past a timeout is dead, and use random delays to break ties. That trades FLP's theoretical impossibility for "works with overwhelming probability," which is enough. Quorums are the other half of the answer.

➗

Quorums

majority overlap is the whole trick

The core mechanism is a majority. Require more than half the nodes to agree on anything, and a beautiful property falls out: any two majorities must share at least one node. That shared node can't vote for two conflicting decisions, so two leaders can never both win, two conflicting values can never both commit.

  5 nodes. A majority is 3.
     any set of 3 ─┐
     any other 3 ─┘  MUST overlap in ≥1 node (3+3 > 5)
                     that node refuses to back both → no split decision

  This is why clusters are ODD: 3, 5, 7.
     3 nodes tolerate 1 failure   (majority of 3 = 2)
     5 nodes tolerate 2 failures  (majority of 5 = 3)
     an even count adds a node without adding fault tolerance (4 also tolerates 1)

Odd sizes are the norm because they maximize fault tolerance per node: 5 nodes survive 2 failures, and a 6th node doesn't buy a third. The cluster keeps working as long as a majority is alive; lose the majority and it stops accepting writes rather than risk a split decision — the CP choice (CAP).

📋

Raft: The One to Know

designed to be teachable

Raft splits consensus into two understandable pieces: elect a leader, then replicate a log through it. Time is divided into terms, each with at most one leader.

  LEADER ELECTION
     followers wait for the leader's heartbeat.
     heartbeat missing past a RANDOM timeout ─▶ become candidate,
        bump term, request votes from all
     get a majority ─▶ become leader, start heartbeating
     random timeouts make simultaneous candidates (split votes) rare;
        a split vote just retries next term

  LOG REPLICATION
     client write ─▶ leader appends to its log ─▶ sends to followers
        followers ack ─▶ once a MAJORITY has it, leader COMMITS
        ─▶ applies to state machine, tells followers to commit, replies to client

An entry is committed only once a majority has stored it, so a committed write survives any minority failure. On a leader crash, a follower times out and starts an election. On a partition, only the side with a majority can elect a leader and make progress — the minority side stalls, which is what prevents split brain. On a split vote, nobody gets a majority and the randomized timeouts resolve it next term.

🏛

Paxos

older, equivalent, notoriously hard

Paxos came first and solves the same problem with the same power, but it's famously hard to understand and to implement correctly — Raft was explicitly designed as a teachable replacement. In practice you'll see Multi-Paxos (Paxos optimized for a stream of decisions) inside older systems. Name it, note that Raft superseded it for most new designs, and move on.

🌍

Consensus in the Wild

small cluster, big fleet

You rarely implement consensus — you use a system that already did. ZooKeeper, etcd, and Consul are consensus-as-a-service: hand them your leader election, locks, and config, and they run Raft (or Zab) underneath. Many databases embed it directly — CockroachDB, etcd, and Kafka's KRaft mode use Raft internally for their own coordination.

  THE PATTERN: keep the consensus cluster SMALL, the data fleet BIG

  ┌──────────────────────────┐        ┌─────────────────────────────────┐
  │  consensus cluster (3–5)  │  ◀───  │  large stateless / data fleet    │
  │  etcd / ZooKeeper         │  reads │  hundreds of nodes               │
  │  leader, locks, config,   │  coord │  serve the actual traffic        │
  │  membership               │        │  no consensus on the hot path    │
  └──────────────────────────┘        └─────────────────────────────────┘

💰

What Consensus Costs

never on the hot path

Every consensus decision needs a round trip to a majority and a durable write on each — so throughput is low and latency includes that quorum wait. That's fine for the handful of coordination decisions a system makes; it's fatal for high-volume data.

⚠️

Never route high-volume data through consensus. Put coordination — who's leader, who holds the lock, what's the config — in the small consensus cluster, and keep the actual read/write traffic on the big fleet using replication for the data plane (Replication). "Coordination through etcd, data through replicated shards" is the shape. Pushing every write through Raft is a classic way to build something that can't scale.

📋

Quick Reference

coordination need → tool

Coordination need	Reach for
Leader election	etcd / ZooKeeper / Consul (Raft)
Distributed lock	Same, with lease + fencing token
Cluster membership	Consensus store
Config that must be consistent	etcd / Consul KV
High-volume data	NOT consensus — replication + sharding

Raft state	Meaning
Follower	Default; applies the leader's log, resets election timer on heartbeat
Candidate	Timed out; requesting votes for a new term
Leader	Won a majority; handles writes and heartbeats
Term	Logical clock; each has ≤1 leader, bumped on every election
Commit	Entry stored on a majority — now durable and applied

ℹ️

The one-liners to keep ready. Consensus makes "exactly one" true across machines. It's hard because you can't tell slow from dead (FLP); quorums answer it — any two majorities overlap, so no split decision, which is why clusters are odd-sized. Raft is the one to know: terms, elected leader, majority-committed log. Use etcd/ZooKeeper rather than building it, keep the consensus cluster small, and never put high-volume data through it.