30-Second Glance
- Distributed consensus is how a cluster of unreliable nodes agrees on one value, one leader, or one log order — despite crashes and partitions.
- You pay for it only where correctness is non-negotiable: leader election, partition/rebalance membership, locks, and config (IPs, replication schema, partition maps).
- Core machinery: monotonic terms/epochs to reject stale actors, majority quorums so any two decisions overlap, and a commit rule (majority-replicated in the current term) that survives leader changes.
- Safety ("never two leaders, never lose a commit") beats liveness: minority partitions stall or re-elect fruitlessly rather than diverge.
- Production faces: Raft (leader + RequestVote/AppendEntries, used via etcd) and Zab (ZooKeeper Atomic Broadcast); coordination services wrap them as a thin reliable config store.
Distributed consensus is how a group of unreliable machines agrees on a single value — one leader, one log order, one commit decision — despite crashes, delays, and partitions. Everything else in this folder is either the problem statement or one working answer.
Start with Linearizability: the correctness contract consensus usually implements (every operation appears to happen atomically, in real-time order). Consensus is the mechanism; linearizability is the guarantee you buy with it.
The two answers that matter
Single-leader consensus (Raft leader election + Raft writes). Nodes elect one leader; the leader sequences all writes and replicates its log. Reads and writes go through the leader, so ordering is trivially consistent. This is the production default (etcd, Consul, ZooKeeper, CockroachDB ranges). Cost: a leader election pause on failure, and write throughput capped by one node's replication fan-out.
Leaderless agreement (quorums, CRDTs). No leader; overlapping read/write sets (w + r > n) or mergeable data types give availability without coordination. Cheaper and always writable, but the guarantee is weaker — see the six holes in the Quorums retrofit. Use when writes must never block; use consensus when they must never disagree.
Where consensus hides in an interview design
- KGS / ID allocator failover (URL Shortener §6.1): active-standby behind a lease from Coordination Services — the lease itself is a consensus-backed primitive.
- Shard ownership and rebalancing (Rebalancing Partitions): exactly one worker must own each partition range at a time; consensus (or a consensus-backed lock service) arbitrates the handover.
- Exactly-once fan-out (News Feed / Twitter §6): idempotent consumers (
ZADD NX) plus a consensus-backed offset/lock keep retries from double-delivering. - Say it: "consensus sits on the control plane (who owns what), never on the per-request hot path — that would cost a coordination round-trip per request."
Core Concepts
- Problem: N nodes, crash and network-partition failures, need one agreed outcome (leader, value, log prefix) with no split brain.
- Terms: Monotonically increasing election numbers; every RPC carries one, and stale terms are rejected — the universal "ignore the old leader" filter.
- Quorums: Majorities (w + r > n style) force overlap, so two elections or two commits cannot both succeed independently.
- Leader completeness: A new leader must hold every previously committed entry — enforced by voting only for at-least-as-up-to-date candidates plus careful commit rules.
- Log matching + backfill: Same index + same term implies identical prefix; the leader overwrites divergent follower suffixes until logs converge.
- Reads: Leader reads are linearizable but slow; follower reads need a sync/lease check or they risk staleness.
- Cost: Consensus is slow and can go unavailable in a minority partition — so reserve it for small critical state, not hot application data.
- Safety over liveness: The protocol would rather stall (no leader, no commits) than let two sides diverge — unavailability is the price of never being wrong.
- Election mechanics (Raft flavor): Missed heartbeats trigger candidacy; one vote per term per node; randomized timeouts dissolve split votes; AppendEntries from a higher term forces step-down.
- Write mechanics (Raft flavor): Client → leader append → AppendEntries fan-out → majority commit → apply → reply; committed entries are linearizable and survive crashes.
- Hub role: This note is the index for the track — linearizability (the promise), clocks and vectors (the ordering tools), Raft election and writes (the mechanism), coordination services (the packaging).
Where To Go Next
- Promise: Linearizability — what "one copy" costs and CAP's real wording.
- Clocks: Lamport Clocks and Version Vector — causal order and concurrency detection.
- Mechanism: Raft Leader Election and Raft Writes — terms, votes, logs, commits.
- Packaging: Coordination Services — ZooKeeper/etcd as the thin config layer over consensus.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Single-leader + consensus election (Raft/Zab) | No split brain; linearizable log; clear failover | Election pauses; minority side unavailable; write latency of majority round-trips | Locks, config, partition maps, DB replication control-plane |
| Leaderless quorums without consensus | Always writable somewhere; low tail latency | Concurrent-write conflicts; no total order; not linearizable | High-availability data plane that tolerates merges |
| 2PC-style atomic commit | All-or-nothing across shards | Blocking coordinator; slow; fragile under partitions | Multi-shard secondary-index updates needing immediate agreement |
| Gossip / anti-entropy convergence | Decentralized, partition-healing | Only eventual; no recency or ordering promise | CRDT state, membership hints, background repair |
Interview One-Liners
Q: What problem does consensus actually solve? A: Getting crash- and partition-prone nodes to agree on a single leader, value, or log order without split brain.
Q: Why do terms exist? A: Monotonic term numbers let every node detect and reject messages from stale leaders and elections.
Q: Why do elections and commits need majorities? A: Any two majorities overlap, so two candidates can't both win one term and a commit can't be silently lost.
Q: When is a Raft entry safe to call committed? A: Only once it is majority-replicated in the leader's current term — majority alone in an old term is unsafe.
Q: What happens to a minority partition? A: It can't elect a working leader or commit — it spins in elections until connectivity returns, preserving safety over availability.
Q: Why keep consensus off the hot data path? A: It is inherently slow (majority round-trips, leader bottleneck); use it for small critical config and elections, and serve hot data from faster, weaker stores.
Related
- Linearizability — the guarantee consensus implements
- The Raft Consensus Algorithm - Leader Election — how a leader is chosen
- Raft Writes — how the leader replicates the log
- Coordination Services — ZooKeeper/etcd leases in practice
- Atomic Commit and Two-Phase Commit (2PC) — consensus's blocking cousin for transactions