System Design Masterclass · Module 30 · Extension of Weeks 1 & 3
Consensus: Raft (& Why Paxos Haunts It)
The math under everything you've trusted so far: etcd under Kubernetes, quorum queues in RabbitMQ, KRaft under Kafka, the k8s Lease your leader election used in Module 19. How a cluster agrees on one history when nodes crash and networks split — terms, elections, log replication, and the operational rules (odd clusters, quorum loss, the witness) that follow from the math.
~3h study~1.5h exercise1 interactive simFast track ~75 min
Fast track — read the Raft paper before?
Compresses to ~75 min. The problem framing collapses; election mechanics with the sim, the commit rule, and the operational consequences stay mandatory — the ops section is what senior discussions actually test.
§01 takeaway · 10 min
§02 election sim, all scenarios · 20 min · MANDATORY
§03 commit rule, in full · 20 min · MANDATORY
§04 operations, in full · 15 min · MANDATORY
STEP 01
What consensus adds that quorums alone don't
SKIM
Fast-track takeawayM04's W+R>N quorums guarantee reads see the latest write — they don't give a single agreed order of writes, which is why W+R>N ≠ linearizability (M04's own caveat, now explained). Consensus solves exactly that: a replicated log all nodes agree on, entry by entry, despite crashes and partitions — the primitive under linearizable stores (etcd/ZooKeeper), metadata planes (KRaft), and safe leader election (M19's k8s Lease is a key in etcd's Raft log). The famous constraint (FLP) says no algorithm can guarantee progress in a fully asynchronous system — Raft/Paxos accept possible temporary stalls (during elections) in exchange for never being wrong: safety always, liveness usually. That's a PACELC position (M03: hard PC/EC), which is why you put consensus under coordination and metadata — small, critical state — and never on the per-request data path of an OTT platform. Paxos solved this first and proved the bounds; Raft is the equivalent protocol re-derived for understandability (explicit leader, terms, unified election+replication) — which is why everything you operate ships Raft.
STEP 02
Elections: terms, votes, and randomized timers
MANDATORY
Every node is follower, candidate, or leader. Time divides into terms (monotonic epochs — M19's fencing-token idea is Raft's term, and that family resemblance is not a coincidence). Followers expect leader heartbeats; a follower that hears none for a randomized election timeout becomes a candidate: increments the term, votes for itself, requests votes. Majority → leader. Run it:
5-node cluster
Node C leads term 4; heartbeats flow. Kill it and watch randomized timeouts elect a successor — or partition a minority and watch it fail to elect anyone, which is the entire safety story.
Randomized timeouts are the genius detail: if all followers timed out together, they'd split the vote forever; random offsets (e.g. 150–300 ms) mean one node usually starts first and wins before rivals wake — elections settle in one round, typically well under a second.
One vote per term + majority required ⇒ at most one leader per term, ever — including across partitions: a minority side can candidate itself hoarse but can never gather a majority. Split-brain is prevented by arithmetic, not by hoping.
The vote has a quality bar (the safety link to §03): a node refuses to vote for a candidate whose log is less up-to-date than its own — so a stale node can't get elected and erase committed history. Elections and replication are one mechanism, which is Raft's central simplification over Paxos's separated phases.
Old leaders self-demote: a leader that was partitioned away returns, sees a higher term in any message, and instantly steps down — the term is a fencing token the whole cluster enforces (M19 §03, protocol edition).
STEP 03
Log replication and the commit rule
MANDATORY
The flow: all writes go through the leader → appended to its log (uncommitted) → replicated via AppendEntries to followers → once a majority has the entry, the leader marks it committed, applies it to its state machine, and answers the client. Followers learn the commit point from subsequent heartbeats. Client latency = one round trip to the median follower — which is why M02 priced consensus writes at ~quorum-RTT, and why cross-region Raft is expensive by construction.
AppendEntries carries a consistency check (previous entry's index+term must match), so divergent follower logs are detected and overwritten back to the last agreement point — the log is forced into a single history, mechanically.
The subtle rule that interview askers love: a leader may only advance the commit point via entries from its own term (committing prior-term entries indirectly). Without this, a specific crash-recovery interleaving lets a committed entry be overwritten (the Raft paper's Figure 8). You don't need to reproduce the proof — you need to know that "majority replicated" and "committed" are distinct states and the gap is where the subtlety lives.
What the client sees: an acked write survives any minority of failures, full stop. An un-acked write (leader crashed mid-replication) may or may not survive — which is why consensus clients still need M16 idempotency/retries: consensus removes disagreement, not ambiguity at the client boundary.
Reads have levels too: linearizable reads must go through the leader with a freshness check (leases or a quorum round — etcd's default) — a leader that's been silently deposed could otherwise serve stale reads; follower/serializable reads are cheaper and stale-tolerant (M04's read-level menu, reappearing inside the consensus box).
STEP 04
Operating consensus: the rules the math implies
MANDATORY
Odd cluster sizes, and why 4 < 3: fault tolerance = ⌈N/2⌉−1 quorum spare. 3 nodes tolerate 1; 4 nodes need a 3-quorum and still tolerate only 1 — you added a failure source without adding tolerance. 3 for most control planes, 5 for the critical ones (tolerate 2, survive one loss during maintenance of another). Never even.
Quorum loss = unavailable-for-writes, on purpose: lose the majority and the survivors refuse — that's safety working (the alternative is two histories). The runbook question written in advance: what does the estate do while etcd/KRaft is read-only — and §01's answer holds: data planes keep serving (k8s pods run, Kafka brokers serve existing metadata), only changes stall. Panic-restoring a minority into a "new cluster" is how committed data gets erased — the disaster-recovery doc must distinguish quorum-loss-wait from true rebuild-from-backup.
Three-AZ placement + the witness pattern: spread 3/5 nodes across AZs so one AZ loss keeps quorum (M25's N−1, applied to the control plane); across two sites, quorum is impossible to place safely — the fix is a lightweight witness/arbiter in a third location that votes but stores little (this is also M11's external-quorum promotion guard, now with its mechanism named).
Consensus is latency-sensitive infrastructure: heartbeats and election timers mean slow disks (fsync per append — §M27's WAL) or CPU-starved nodes cause spurious elections; etcd's dashboards of fsync/commit latency are the leading indicators. Symptom pattern worth memorizing: "cluster flaps leadership under load" ≈ disk latency or an undersized timer, not a network problem.
Membership changes are themselves consensus operations (joint consensus / one-at-a-time) — add/remove nodes one at a time via the official procedure; hand-editing peer lists is a split-brain generator.
Staff expectationThe placement judgment: consensus for coordination, metadata, and configuration (small state, correctness-critical, modest write rate) — never for the request path of a 5M-user product (M02's arithmetic forbids it; that path runs on M01/M04/M10's cached, replicated, eventually-consistent machinery coordinated by a consensus layer). And the vocabulary fluency to say in review: "that's a term/fencing problem," "that's a quorum-placement problem," "acked ≠ applied on the follower you're reading" — because at senior level, consensus questions are rarely "explain Raft" and usually "here's an outage; which invariant broke?"
STEP 05
Exercise
MANDATORY
Fast trackStep 2 (~30 min): breaking a real etcd cluster's quorum and watching it refuse writes is the safety property made physical.
1
Watch an election. 3-node etcd via docker-compose; etcdctl endpoint status to find the leader; kill it; measure re-election time from the logs (terms incrementing, votes). Then throttle the leader's disk (tc/cgroup io) instead of killing it and watch leadership flap — the §04 symptom, manufactured.
2
Break quorum properly. Kill 2 of 3: reads (serializable) still answer, writes hang/fail — capture the exact error your platform would see. Restore one node, watch writes resume, and write the two-paragraph runbook: quorum-loss symptoms, what keeps working, what NOT to do (no force-new-cluster), recovery order.
3
Implement election (stretch). Raft leader election only (skip log replication) in Java: terms, randomized timers, RequestVote over gRPC, 5 local nodes. Watching your own cluster converge — and split-vote when you remove the randomization — cements §02 permanently. (~300 lines; the Raft paper's Figure 2 is the complete spec.)
4
Paper. Inventory every consensus system your estate stands on (etcd under k8s, KRaft/ZK under Kafka, RabbitMQ quorum queues, anything Consul/Vault): node count & AZ placement, what stalls on quorum loss, disk-latency monitoring present?, and the membership-change procedure documented? Gaps → tickets; this is the audit that finds the 2-AZ etcd nobody meant to build.
Self-check
Why does a 4-node cluster tolerate no more failures than 3, and when would you still see 4 in the wild?
Quorum(4)=3, so 2 failures kill it — same single-failure tolerance as 3 nodes, with more machines to fail and bigger replication fan-out. Legitimate 4s are transitional states mid-membership-change (adding the 5th, removing to 3), or a non-voting learner (read replica/warm standby) that doesn't count toward quorum — worth checking which one your "4-node cluster" actually is.
A partitioned-away leader keeps accepting... what, exactly? Walk what its clients experience and why no data is lost.
It can append to its local log but can never commit — no majority reachable — so it never acks; client writes hang until timeout (and its lease-based reads expire). Meanwhile the majority side elects a term-N+1 leader and moves on. On heal, the old leader sees the higher term, steps down, and its uncommitted tail is overwritten by the consistency check. Clients saw timeouts, not lies — which is exactly the M15/M16 ambiguity ("did my write land?") that idempotent retry resolves.
Connect Raft's term to Module 19's fencing token in one breath.
Same primitive at two scales: a monotonic epoch attached to authority, checked at the point of effect. Raft: every message carries the term; any node seeing a higher term rejects/demotes the sender — stale leaders are fenced by the protocol itself. M19: the lock service issues the number and *your storage* must do the checking. Consensus is fencing with the verification built into every participant — which is why "just use etcd for the lock" still requires carrying the token into the resource (M19 §03): the fence only guards what checks it.
etcd reports healthy but Kubernetes deployments intermittently stall for ~2 s. Consensus-flavored hypothesis and the metric that confirms it?
Leadership flapping or slow commits from disk latency: etcd fsyncs the WAL per append (M27), so a noisy-neighbor disk stretches commit latency past heartbeat/election timers → spurious elections → writes stall for the election window, repeatedly. Confirm with etcd's wal_fsync_duration and leader_changes_seen metrics. Fix: dedicated fast disks for consensus nodes, tuned timers — and the general lesson: consensus turns your slowest disk into everyone's problem.