Concept 18: Distributed Consensus — Raft, Paxos, and the Art of Agreeing With Strangers

System Design Bible — File 18 Difficulty: ★★★★★ Prerequisites: File 07 (Message Queues — the log as a data structure, and why an ordered append-only sequence is the universal shape of replicated state), File 08 (Consensus & Replication — the survey-level tour of CAP, quorums, and replication models; this file is the deep dive that File 08 promised), File 11 (Databases — the write-ahead log, fsync, and what durability physically costs), File 15 (Idempotency — why "did my request actually apply?" is the hardest question in distributed systems), File 17 (Distributed IDs — the "avoid coordination" instinct; here we finally pay for coordination on purpose), plus the fundamentals unpacked in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

Consensus is the single hardest topic in this bible, and the reason is not that the algorithms are complicated — Raft fits on two pages — but that the problem is subtle in a way that only becomes visible once you internalize five uncomfortable facts about the physical world. Every one of the algorithms in §4 is a response to one of these facts. Skip this section and Raft will look like arbitrary bureaucracy; read it and Raft will look inevitable.

0.1The failure models — what exactly is a "failure"?#

When we say "a node fails," we are not saying one thing. Distributed systems theory defines a hierarchy of failure models, ordered from friendliest to most hostile, and every consensus algorithm is defined relative to exactly one of them. Choosing the wrong model in an interview — designing for the wrong adversary — is a classic tell.

Crash-stop (fail-stop). The node runs correctly, then halts forever and never returns. It never sends a wrong message; it just stops. This is the friendliest model and it is also unrealistic: real servers reboot.

Crash-recovery. The node runs correctly, crashes (losing everything in its RAM — its volatile memory — because RAM is erased when power is lost), then comes back up and rejoins. This is the model Raft and Paxos actually target, and it forces a specific, expensive design decision: any piece of state whose loss would break correctness must be written to persistent storage — disk or SSD — and physically flushed there before the node acts on it. That flush is the fsync system call you met in File 11: it tells the operating system "do not merely put this in your page cache (the OS's in-RAM buffer of recently written disk data); push it to the physical device and don't return until the device says it's durable." An fsync on a spinning disk costs 5–10 ms; on a datacenter SSD with a power-loss-protected write cache, 0.1–1 ms. Consensus is slow largely because crash-recovery forces an fsync into the critical path. Remember this number — it comes back in §7.

Omission failures. The node is alive and correct but some of its messages vanish — dropped by a congested switch, silently discarded by a full socket buffer, blocked by a misconfigured firewall rule. A special and vicious case is the network partition (File 08 §2.3): a link failure that splits the cluster into groups that can each talk internally but not across. Omission is not a separate adversary so much as the reason we can never trust silence.

Byzantine failures. The node is arbitrarily wrong: it can lie, send different messages to different peers, forge, replay, or be actively controlled by an attacker. The name comes from Lamport's "Byzantine Generals Problem" — generals besieging a city must agree to attack or retreat, but some generals are traitors who send "attack" to one neighbor and "retreat" to another. Tolerating this is strictly more expensive: you need 3f+1 nodes to tolerate f Byzantine faults (versus 2f+1 for crashes), and cryptographic message authentication throughout. §4.10 covers these algorithms.

The decisive judgment: inside your own datacenter, with your own binaries, on your own network, crash-recovery + omission is the right model — nodes crash and messages drop, but your etcd node is not maliciously lying to you. Byzantine tolerance is for systems where the participants are mutually distrusting organizations (blockchains, cross-bank settlement). Saying "we'll use PBFT for our internal metadata store" in an interview is a red flag: you tripled the cost to defend against an adversary who, if he existed, already has root on the machine and can corrupt the state directly. Hold this: consensus algorithms are answers to a specific adversary; name your adversary before you choose your algorithm, and inside one company that adversary is the crash and the dropped packet, not the liar.

0.2The synchrony models, and why timeouts are the only tool you have#

The second axis is how much you may assume about time.

A synchronous system has known upper bounds: every message arrives within Δ, every node executes a step within Φ. Under this assumption, failure detection is perfect — wait Δ, hear nothing, the node is definitively dead. Consensus in a synchronous system is easy. Real networks are not synchronous: a garbage-collection pause in a JVM can freeze a process for seconds, a TCP retransmission after packet loss adds hundreds of milliseconds, a congested link can queue traffic arbitrarily.

An asynchronous system assumes no bounds at all: messages arrive eventually but you cannot say when, and processes run at arbitrary relative speeds. This is the honest model of the internet — and it is the model in which consensus is provably impossible (§0.3).

The model everyone actually builds for is partial synchrony (Dwork, Lynch, Stockmeyer, 1988): the system behaves asynchronously for an unknown finite period, but eventually enters a stable period where bounds hold. Real networks match this: mostly a few hundred microseconds inside a datacenter, occasionally a 30-second meltdown during a switch failure.

Now the consequence that shapes every algorithm in this file. In an asynchronous or partially-synchronous system, you cannot distinguish a crashed node from a slow node or an unreachable one. All three look identical: silence. Your only detection tool is the timeout — "I have heard nothing for T milliseconds, so I will act as if you are dead." That is not knowledge, it is a bet, and every timeout setting is a trade between two failure modes:

Typical production values: etcd defaults to a 100 ms heartbeat interval and a 1000 ms election timeout — meaning a dead leader costs about one second of write unavailability. Across a WAN (wide-area network — links between geographically separated datacenters, where round trips run 30–150 ms), those numbers must be scaled up 5–10×, which is why global consensus groups have multi-second failover. Hold this: the timeout is the only failure detector you get, it is always a guess, and its value simultaneously sets your false-failover rate and your worst-case downtime — there is no setting that is good at both.

0.3Safety vs liveness, and the FLP impossibility result#

Every correctness claim about a distributed protocol falls into exactly two categories, and keeping them apart is what separates people who understand consensus from people who have memorized Raft.

A safety property says "nothing bad ever happens." For consensus: never decide two different values; never lose a committed entry; never let two leaders both commit in the same term. Safety violations are catastrophic and unrecoverable — a lost committed write is a customer's money that no longer exists, and no amount of waiting fixes it.

A liveness property says "something good eventually happens." For consensus: eventually a leader is elected; eventually every submitted command commits. Liveness violations are unavailability — painful, page-your-oncall, but the system is still correct, and when the network heals, progress resumes.

Now, FLP (Fischer, Lynch, Paterson, 1985), the most important impossibility result in the field: in an asynchronous system where even a single process may crash, there is no deterministic algorithm that guarantees consensus is always reached. The intuition of the proof: because you cannot distinguish "crashed" from "slow," an adversarial scheduler can always find a moment to delay exactly the message that would tip the decision, keeping the system in an undecided state forever.

The engineering response — and this is the sentence to say in an interview — is: every practical consensus algorithm sacrifices liveness, never safety. Raft and Paxos are always safe: no matter how pathological the network, they will never decide two different values. What they cannot promise is that they will always make progress. When the network misbehaves badly enough, they stall — and then resume when it heals. Because real networks are partially synchronous, "eventually" arrives quickly in practice, so the theoretical impossibility costs you a few seconds of downtime rather than correctness.

This also reframes CAP (File 08 §3): a CP system's "no availability during a partition" is the liveness sacrifice, chosen deliberately so safety survives. Hold this: consensus algorithms trade liveness for safety because FLP forbids having both — and that is the right trade, since unavailability is a bad hour while a safety violation is a bad company.

0.4The replicated state machine — the only thing consensus is actually for#

Consensus in the abstract ("agree on one value") looks useless — who needs to agree on one number? The bridge from theory to practice is the Replicated State Machine (RSM), and it is the single most important mental model in this file.

The construction has three parts:

So replication of state reduces entirely to replication of an ordered log, and that reduces to: for each log index, get all replicas to agree on which command occupies it. That is single-value consensus, run once per slot. This is why the theory ("agree on one value") is worth anything: run it once per log index and you have replicated any program you like.

Client cmd ──► [ Consensus module ] ──► replicated log ──► [ State machine ]
                      │                  ┌──────────────┐        │
                      └── agrees on ────►│1:SET x=5     │        └─► x=5, y=2
                          each slot      │2:SET y=2     │
                                         │3:DEL z       │  (identical on every node)
                                         └──────────────┘

Everything else in this file — terms, elections, quorums, snapshots — exists to protect the invariant "the log prefix is identical on every replica." Hold this: consensus does not replicate data, it replicates a totally-ordered log of commands; determinism turns one agreed order into one agreed state, which is why "the log is the database" (File 07 §1.2) is literally true.

0.5Quorum intersection — the one trick the entire field rests on#

You met quorums in File 08 §2.4. Here is why they are the mechanism, stated so it can never be forgotten.

A quorum is any subset of nodes large enough to act on behalf of the cluster. A majority quorum in a cluster of N nodes is any ⌊N/2⌋+1 of them: 2 of 3, 3 of 5, 4 of 7. The property that makes it magical is arithmetic and absolute: any two majorities must share at least one member. Two sets of size 3 drawn from 5 nodes cannot be disjoint — 3+3=6 > 5, so by the pigeonhole principle at least one node is in both.

Why this single fact is the whole field: it means information cannot be lost across changes of leadership. If a value was accepted by a majority, then any future majority — including the one that elects the next leader — contains at least one node that saw it. So the new leader is guaranteed to be able to learn about every committed value, provided it asks a majority and takes the most recent thing it hears. Committed data survives leadership change not because we carefully hand it over, but because it is mathematically impossible to assemble a majority that has never heard of it.

The same fact prevents split-brain (File 08 §2.5 — two nodes both believing they are leader and both accepting writes, silently forking your data). Two leaders would each need a majority to commit; two majorities intersect; the shared node refuses the second one (§2.2's term rule). Not two leaders committing. Ever.

Three corollaries interviewers probe:

Hold this: majority quorums work because two majorities cannot be disjoint, which makes committed information impossible to lose and split-brain impossible to commit — everything else in consensus is bookkeeping around this one pigeonhole argument.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

Distributed consensus is a protocol by which a group of nodes, some of which may crash and all of whose messages may be delayed, dropped, or reordered, agree on a single value — and, run repeatedly, on a single totally ordered sequence of values — such that four properties hold:

The analogy that survives contact with the details: a committee that governs by written minutes and majority vote, where members regularly fall asleep mid-meeting. Nobody trusts anybody's memory, so every decision must be recorded in the minutes of a majority of members before it counts. Every chairperson is elected for a numbered term, and the numbering matters more than the person: if a chair wakes from a nap and starts issuing orders, anyone who has since seen a higher term number simply says "you're term 4, we're on term 7" and ignores them. When a new chair takes over, they don't restart the agenda — they first read the minutes of a majority of members and adopt whatever the latest recorded decisions are, which is exactly §0.5's intersection guarantee: the only way for the new chair to miss a passed motion would be for a majority to have never recorded it, in which case it never passed.

Every mechanism in Raft maps onto that picture: terms are chair numbers, AppendEntries is dictating the minutes, the commit index is "recorded by a majority," and the election restriction is "you may only become chair if your minutes are at least as complete as those of everyone who votes for you."

1.2"The Why" — what forced this to exist#

Four hard limits, each of which alone would demand consensus.

One machine is a finite, mortal thing. A single server holding your cluster's configuration will eventually lose a power supply, a disk, or a datacenter. Reliability demands replication (File 08 §0.1) — but the instant there are copies, they can disagree, and disagreement in metadata is worse than in data: two nodes each believing they own shard 7 causes double writes and lost updates.

The network makes "who is in charge?" undecidable locally. §0.2's lesson has a brutal corollary: a node cannot determine its own status. A leader that has been partitioned away has no way to know it has been deposed — from inside, a partition looks exactly like "everyone else got quiet." Any design where a node decides for itself that it is the leader produces two leaders during every partition. The only fix is to make leadership a fact held by a majority, not a belief held by an individual.

Some decisions are physically unsafe to duplicate. Charging a card twice, allocating the same IP to two VMs, letting two nodes write the same file region, promoting two replicas of a shard: these are not "eventually consistent" problems, they are wrong. File 15 taught idempotency as the defense against duplicate requests; consensus is the defense against duplicate decisions. Some decisions must be singular, and only a majority-witnessed decision is singular.

Eventual consistency cannot express constraints. A Dynamo-style leaderless store (File 08 §4.3) is a superb choice for a shopping cart, where two concurrent adds can be merged. It cannot enforce "this username is unique," "this seat is sold once," or "this account never goes negative," because those are statements about a global state that no single replica can evaluate. Uniqueness and non-negativity require a single agreed order of operations. That is consensus.

The cost these limits force you to accept is a physical one: a committed write requires at least one network round trip to a majority plus a durable disk flush. In-datacenter that's ~0.5 ms of network plus ~0.5–1 ms of fsync per commit; cross-region it's 30–150 ms of speed-of-light round trip that no amount of money removes. This is why the senior instinct is: use consensus for the small, precious, must-be-singular state, and keep the bulk of your data out of it.

1.3What Consensus Solves — and What It Charges#

The price, stated honestly. Every committed write costs one majority round trip plus a durable flush, so per-key write throughput is bounded by roughly 1 / (RTT + fsync) for un-batched writes — a few thousand per second in-datacenter, low tens per second across continents. Write throughput does not improve by adding nodes; it gets slightly worse (bigger majority, more traffic from the leader). All writes funnel through one leader, so a single consensus group is a scaling ceiling — you break it by sharding into many groups (§7.4). And you inherit real operational complexity: quorum loss requires unsafe manual recovery, and a partitioned minority is simply down. Consensus is not a database; it is the smallest possible amount of agreement, sold at a premium.

2The Recursive Sub-Concept Tree#

Every term the rest of the file uses, defined from scratch.

2.1Sub-Concept: The Log, the Index, and the Commit Index#

The log is an array of entries, each holding {term, index, command}. The index is the entry's position — 1, 2, 3, … — and it is the slot number that consensus agrees on. The term stamped in each entry records which leadership era created it, and it is the field that makes stale data detectable later (§2.2).

Two pointers matter enormously and are constantly confused:

Entries above commitIndex are uncommitted: they exist on some nodes but not a majority, and they may still be overwritten by a future leader. This is the crucial asymmetry — an uncommitted entry is a proposal that may yet be erased; a committed entry is history. A client must never be told "success" until the entry's index is ≤ commitIndex.

2.2Sub-Concept: Terms, Ballots, and Epochs — logical time#

Wall clocks are useless here (File 17 §0.3 — they drift and jump backwards). Instead, consensus uses logical time: a monotonically increasing integer that counts leadership eras. Raft calls it a term, Paxos calls it a ballot or proposal number, ZAB and Kafka call it an epoch. Same idea.

Rules that make it work: every message carries the sender's term. On receiving a higher term, a node immediately adopts it and reverts to follower — accepting that it has been superseded. On receiving a lower term, a node rejects the message and replies with its own current term, informing the stale sender that it has been left behind.

This gives you fencing for free: a leader that was partitioned away and comes back with term 4 finds a cluster at term 7 and is instantly demoted by the first reply it receives. It cannot do damage, because no majority will accept its stale-term requests. The term number is the mechanism by which a stale leader is disarmed without anyone having to notify it. Terms must survive crashes, so currentTerm is one of the fields that gets fsynced (§0.1).

2.3Sub-Concept: Roles — Follower, Candidate, Leader (and Learner, Witness, Observer)#

Raft's core roles:

Three auxiliary roles that appear in production systems and interviews:

2.4Sub-Concept: Proposer, Acceptor, Learner (the Paxos vocabulary)#

Paxos names roles in the protocol rather than roles of machines; one physical server usually plays all three.

The mapping to Raft: Raft's leader is a proposer that has won the right to be the only proposer; all Raft nodes are acceptors and learners. Raft is, in a precise sense, Multi-Paxos with a strong-leader restriction and a log-continuity rule bolted on to make it comprehensible.

2.5Sub-Concept: The Two-Phase Shape (Prepare/Promise, Accept/Accepted)#

Nearly every consensus protocol has the same skeleton, and recognizing it is what makes Paxos and Raft look like one idea:

Basic Paxos runs both phases per value. Multi-Paxos and Raft run Phase 1 once per leadership term (that is the election) and then run only Phase 2 per entry — which is why steady-state consensus costs one round trip, not two. This is the single most valuable structural insight in the file: leader election is Phase 1, amortized over thousands of commands.

2.6Sub-Concept: Linearizability (what strong consistency actually means)#

Linearizability is the strongest single-object consistency model: the system behaves as if there were exactly one copy of the data and every operation took effect instantaneously at some point between its invocation and its response, with that point-order respecting real time. Concretely: if write W completes at 10:00:00.000, then every read that starts after that instant must see W or something newer. There is no "I read a stale value for a moment."

Why it matters here: consensus gives you a total order on writes, but reads are not automatically linearizable. A follower can serve you an old value; worse, a deposed leader that hasn't yet learned it was deposed will happily serve you its stale local state. §5.3 covers the three ways to fix this (ReadIndex, lease reads, log reads). This is the most common correctness bug in home-grown consensus deployments and a favorite interview probe: "your leader is partitioned but still thinks it's leader — what does it return to a read?"

Distinguish it from serializability (File 11 §7): serializability is about multi-object transactions being equivalent to some serial order; linearizability is about single-object operations respecting real-time order. Spanner's "external consistency" is both at once — strict serializability.

2.7Sub-Concept: State Machine Safety and the Log Matching Property#

Raft's correctness rests on two named invariants worth memorizing.

Log Matching Property: if two logs contain an entry with the same index and the same term, then (a) they store the same command, and (b) all preceding entries are identical too. Part (b) is the powerful half: matching a single (index, term) pair certifies the entire prefix. It is enforced by the consistency check in §3.3 — every AppendEntries carries the (index, term) of the entry immediately preceding the new ones, and the follower refuses the append unless it has exactly that entry. By induction, a log that ever accepts an append is identical to the leader's up to that point.

State Machine Safety: if a node has applied an entry at index i to its state machine, no other node will ever apply a different entry at index i. This is the property that makes the RSM (§0.4) valid, and it is guaranteed by the election restriction (§3.4) plus the commit rule (§5.2).

2.8Sub-Concept: Split Vote and Randomized Timeouts#

If several followers time out simultaneously, they all become candidates in the same term, and votes split — say 2/2/1 across five nodes. Nobody gets a majority (each node votes at most once per term), the term ends with no leader, timers expire, and it can happen again. This is a liveness failure, not a safety one (§0.3): no wrong decision, just no progress.

Raft's fix is beautifully cheap: randomize the election timeout per node per attempt (etcd picks uniformly from roughly [T, 2T], e.g. 1000–2000 ms). One node's timer almost always fires meaningfully earlier, it wins the vote before others wake, and its heartbeats reset everyone's timers. The probability of repeated split votes decays geometrically. Cost: expected failover time rises by half the randomization window. Compare Paxos, which has no built-in tiebreak and can livelock — two proposers repeatedly out-bidding each other's ballot numbers, each Phase-1 invalidating the other's Phase-2, forever — which is why practical Paxos deployments bolt on leader election and randomized backoff anyway.

2.9Sub-Concept: Leases and Fencing Tokens#

A lease is a lock with an expiry: "you are the leader until time T unless renewed." Its purpose is to let a node act without checking with a quorum on every operation — the leader can serve reads locally as long as it holds an unexpired lease, because the protocol guarantees no one else can be leader during that window.

Leases depend on clocks, so they need a safety margin: the granting nodes promise not to elect a new leader for lease_duration after their last vote, and the holder self-demotes at lease_duration − ε, where ε covers maximum clock drift between the machines. If your clocks can skew by more than ε, the lease is unsound and two leaders can briefly overlap — this is precisely why Spanner needed TrueTime (§10.2).

A fencing token is the belt-and-braces defense, and it is the answer to the classic "distributed lock is not enough" problem. Every lock grant carries a monotonically increasing number (the term/epoch works perfectly). The resource being protected — the storage layer, the file system, the database — records the highest token it has seen and rejects any request bearing a lower one. Now the nightmare scenario is safe: holder A acquires the lock with token 33, suffers a 40-second garbage-collection pause, loses the lease, B acquires with token 34 and writes; A wakes up believing it still holds the lock and writes — and the storage layer rejects A's write because 33 < 34. Say this in an interview: a distributed lock without fencing is not safe, because you cannot stop a process that has stopped listening; you can only make its writes bounce off the target.

2.10Sub-Concept: Snapshots and Log Compaction#

The log grows forever, which is untenable: disk fills, and a restarting node would have to replay years of history. Snapshotting solves it: periodically, serialize the state machine's current state to disk along with the lastIncludedIndex and lastIncludedTerm it reflects, then discard all log entries at or below that index.

The complication this creates: a follower that has fallen far behind may need entries the leader has already deleted. The protocol therefore needs an extra RPC — Raft's InstallSnapshot — by which the leader ships the whole snapshot instead of individual entries. Trade-offs: snapshots cost CPU and I/O (a naive implementation stalls the state machine while serializing, so real systems use copy-on-write — taking a cheap logical copy where pages are only physically duplicated when modified — as Redis does with fork() and as LSM-tree stores do naturally via immutable files, File 11 §3). And shipping a multi-gigabyte snapshot over a busy network can starve normal traffic, so implementations rate-limit it.

2.11Sub-Concept: Atomic Broadcast (Total Order Broadcast)#

Atomic broadcast is the primitive "deliver these messages to every node, in the same order, with the same set." It is equivalent to consensus — each can implement the other, which is a formal result worth quoting. Building broadcast from consensus: agree on slot 1's message, then slot 2's, and so on. Building consensus from broadcast: broadcast your proposal, decide the first message delivered.

Why it matters practically: it tells you the log-based systems you already know (Kafka, File 07) and the consensus systems here are the same species. Kafka's ISR replication is a total-order broadcast for a partition; its controller quorum (KRaft, §10.3) is literally Raft. The log is the universal interface between agreement and state.

3Deep-Dive Mechanics — Raft End to End#

Raft was designed in 2013 with an explicit goal Paxos never had: understandability. Ongaro and Ousterhout decomposed the problem into three near-independent pieces — leader election, log replication, and safety — and imposed a strong-leader restriction so that data flows in exactly one direction: leader → followers, never the reverse. Nearly every consensus system built after 2014 (etcd, Consul, TiKV, CockroachDB, RethinkDB, Kafka KRaft, Neo4j) chose Raft for that reason alone.

3.1The state machine of a node#

                     times out,                    receives majority
                   starts election                     of votes
   ┌──────────┐  ───────────────►  ┌───────────┐  ─────────────────►  ┌────────┐
   │ FOLLOWER │                    │ CANDIDATE │                      │ LEADER │
   └──────────┘  ◄───────────────  └───────────┘  ◄─────────────────  └────────┘
        ▲          discovers current leader          discovers node with
        │          or higher term                    higher term
        └──────────────── starts up / recovers from crash ────────────

Per-node persistent state (must be fsynced before responding to any RPC — §0.1): currentTerm, votedFor (who I voted for in this term), and log[]. Volatile state: commitIndex, lastApplied. Leaders additionally keep, per follower, nextIndex (the next entry to send) and matchIndex (the highest entry known replicated there).

Why votedFor must be durable: without it, a node that votes for A, crashes, restarts, and votes for B in the same term could manufacture two majorities and therefore two leaders — a safety violation born of one un-flushed write.

3.2Leader election, step by step#

"Up-to-date" is defined precisely: compare lastLogTerm first — higher term wins; if equal, longer log wins.

3.3Log replication, step by step#

 client ──write("SET x=5")──► LEADER (term 7)
                                │  1. append locally at index 12, fsync
                                │
         ┌──────────────────────┼──────────────────────┐
         ▼                      ▼                      ▼
   AppendEntries{         AppendEntries{         AppendEntries{
     term:7,                term:7,                term:7,
     prevLogIndex:11,       prevLogIndex:11,       prevLogIndex:11,
     prevLogTerm:7,         prevLogTerm:7,         prevLogTerm:7,
     entries:[12:SET x=5],  entries:[...],         entries:[...],
     leaderCommit:11 }      leaderCommit:11 }      leaderCommit:11 }
         │                      │                      │
   FOLLOWER A               FOLLOWER B             FOLLOWER C (slow/down)
   check idx11/term7 ✓      check ✓                 (no reply)
   append + fsync           append + fsync
   reply success            reply success
         │                      │
         └──────────┬───────────┘
                    ▼
     Leader sees matchIndex ≥ 12 on itself + A  → 2 of 3 = MAJORITY
     commitIndex = 12  →  apply to state machine  →  reply OK to client
                        →  next heartbeat carries leaderCommit=12,
                           so followers apply it too

The heart of it is the consistency check: every AppendEntries names prevLogIndex/prevLogTerm. A follower appends only if it has exactly that entry. If not, it replies success:false, and the leader **decrements nextIndex for that follower and retries**, walking backwards until the logs match, then overwriting the follower's divergent suffix. (Naive backtracking is one round trip per missing entry, so real implementations return a hint — the conflicting term and the first index of that term — and the leader jumps back a whole term at a time.) This is what enforces the Log Matching Property (§2.7): the follower's log becomes a byte-for-byte copy of the leader's prefix, with any garbage from an old term truncated away.

Overwriting a follower's entries is legal precisely because those entries were uncommitted (§2.1) — no client was ever told they succeeded, so erasing them breaks no promise. Interviewers love this question; the answer is one sentence: "Raft only ever truncates entries that were never committed, so it never destroys an acknowledged write."

3.4The election restriction — why committed data can never be lost#

Suppose a leader commits entry 12 on itself and follower A (a majority of three), then dies before B learns of it. If B could become leader, entry 12 — for which a client already holds a success response — would vanish. Raft forbids this with one rule in step 3 above: a voter refuses its vote to any candidate whose log is less up-to-date than its own.

The argument, and it is exactly §0.5: entry 12 is committed, so it sits on a majority. Any winning candidate needs votes from a majority. Those two majorities intersect in at least one node, and that node holds entry 12 — so it will refuse to vote for B, whose log lacks it. B therefore cannot assemble a majority. Committed entries are not transferred to the new leader; they are made a prerequisite for becoming leader. That inversion is the elegant core of Raft's safety.

3.5End-to-end trace of a failover#

Cluster {S1, S2, S3}, S1 leader in term 7, log committed through index 20.

4The Consensus Algorithm Family — Exhaustive Breakdown#

Full RULE 4 treatment for each. This is the canonical taxonomy: the Paxos line (Basic → Multi → Fast → Flexible → EPaxos → Cheap), the leader-based practical line (Viewstamped Replication, ZAB, Raft), and the Byzantine line (PBFT → HotStuff → Nakamoto).

4.1Basic (Single-Decree) Paxos#

What it is. Lamport's 1998 original: get a group to agree on one value, once, with no leader, tolerating crashes and arbitrary message delay.

Mechanism. Two phases, both requiring a majority. Each proposer picks a globally unique, monotonically increasing proposal number n (typically counter × num_nodes + node_id, which guarantees uniqueness without coordination).

Phase 1 (Prepare/Promise). Proposer sends Prepare(n) to acceptors. An acceptor that has never promised a number ≥ n replies Promise(n, (n_accepted, v_accepted)) — promising to reject anything lower, and reporting the highest-numbered value it has already accepted, if any.

Phase 2 (Accept/Accepted). If a majority promised, the proposer must now choose the value: if any promise reported an accepted value, it MUST propose the one with the highest accepted number (this is the recovery rule that preserves a possibly-chosen value); only if all promises were empty may it propose its own. It sends Accept(n, v); acceptors that haven't promised higher accept and reply. A majority of accepts = chosen, forever.

Worked example. Acceptors A, B, C. P1 sends Prepare(1) → all promise (empty). P1 sends Accept(1, "x") → A and B accept before P1 crashes; C never hears it. Now P2 sends Prepare(2) → B replies with (1, "x"), C replies empty; that's a majority. P2 wanted to propose "y" but the rule forces it to propose "x". Accept(2, "x") → chosen. Agreement preserved even though the original proposer died mid-flight and the value was on a bare majority.

Why it works. Quorum intersection (§0.5): any Phase-1 majority overlaps any earlier Phase-2 majority, so a possibly-chosen value is always discovered; the "adopt the highest-numbered accepted value" rule then makes it impossible to choose a different value afterwards.

Pros. Provably minimal and correct under the weakest assumptions. Fully leaderless and symmetric — no election needed, no special node. Tolerates f failures with 2f+1.

Cons. Two round trips (4 message delays) per value — brutal. No progress guarantee: competing proposers can livelock, each Prepare invalidating the other's Accept indefinitely. And it decides one value; it says nothing about building a log. It is famously hard to implement from the paper — "Paxos Made Live" (Google, 2007) is a paper entirely about how much the paper leaves out.

Complexity. 2 RTTs, ~4N messages per decision; O(1) state per acceptor (one promised number, one accepted pair).

When to use it. Almost never directly, with one important exception: one-shot decisions where there is no natural leader and contention is rare — e.g., agreeing on the sealed final length of a log segment during recovery, which is exactly what Cloud Spanner/Chubby-style reconfiguration paths do. For a stream of decisions, always upgrade to §4.2.

4.2Multi-Paxos#

What it is. Basic Paxos amortized: elect a stable leader once, then skip Phase 1 for every subsequent value.

Mechanism. The distinguished proposer runs Phase 1 once with proposal number n, but for all future log slots simultaneously ("Prepare(n) for every index ≥ k"). The promises come back reporting any accepted values in those slots, which the leader must re-propose (recovery). Thereafter, each new command needs only Phase 2: Accept(n, index, cmd) → majority → committed. Steady state: one round trip per command.

Worked example. Leader L wins Phase 1 for ballot 5 covering slots 100+. Client sends SET a=1 → L assigns slot 100, sends Accept(5,100,"SET a=1"), majority accepts, committed in one RTT. Next command → slot 101, same. If L crashes, a new proposer runs Phase 1 with ballot 6, learns whatever was accepted in 100–103, re-proposes the highest-numbered ones (possibly filling gaps with no-ops), and takes over.

Why it works. Identical safety to Basic Paxos — Phase 1 is still performed on every leadership change, which is the only time recovery is needed.

Pros. One RTT per command in steady state, which is the theoretical floor for a leader-based protocol. Slots can be filled out of order and in parallel (pipelined), so a slow slot doesn't block later ones — a genuine throughput advantage over Raft.

Cons. Out-of-order acceptance means logs can have holes, and the state machine still must apply in order — so a single stuck slot stalls application. Recovery therefore requires explicitly probing and no-op-filling gaps, which is a large part of why Multi-Paxos implementations are notoriously fiddly. The paper leaves leader election, membership change, and log compaction entirely as exercises.

Complexity. 1 RTT and ~2N messages per command steady-state; 2 RTTs on leader change.

When to use it. When you need maximum throughput and can afford a difficult implementation — Google's Chubby, Spanner, and Megastore are all Multi-Paxos. For a new system in 2020s, choose Raft unless you specifically need out-of-order pipelining, because Raft's ecosystem of tested libraries is far richer.

4.3Raft#

What it is. Multi-Paxos restructured for understandability: a strong leader, plus the rule that logs may never have holes.

Mechanism. Fully described in §3: randomized-timeout leader election with the up-to-date-log restriction, AppendEntries with a previous-entry consistency check that forces log prefixes to match, commit at majority matchIndex.

Why it works. Log Matching + Election Restriction + the term rule (§2.7, §3.4, §2.2) combine to give State Machine Safety.

Pros. By far the most implementable — the no-holes rule means a follower's log is always a clean prefix, so recovery is a simple backwards walk rather than gap-probing. One RTT per command in steady state, same as Multi-Paxos. The paper specifies membership change, snapshots, and client interaction, so you are not inventing the hard parts. Enormous ecosystem: etcd/raft, HashiCorp raft, TiKV, Copycat, and dozens more, all battle-tested.

Cons. The no-holes rule forbids out-of-order commits, so head-of-line blocking is real: one slow entry delays all later ones. The single strong leader is a throughput ceiling and a hotspot — all client traffic and all replication fan-out lands on one machine (mitigated by sharding into many Raft groups, §7.4). Leader-based means every write from a distant region pays a WAN round trip to the leader's region, whereas EPaxos (§4.8) can commit locally.

Complexity. 1 RTT + 1 fsync per commit; 2N messages per entry; election costs one randomized timeout plus one RTT.

When to use it. Default choice for any new leader-based replicated system — metadata stores, config stores, per-shard replication, control planes. Use something else only for a specific reason: WAN-latency symmetry (EPaxos), Byzantine participants (HotStuff), or an existing Paxos investment.

4.4Viewstamped Replication (VR)#

What it is. Oki & Liskov's 1988 protocol — predating Paxos's publication — that solved practical replicated state machines directly, without going through "agree on one value."

Mechanism. A view (≈ term/epoch) has a designated primary chosen deterministically as view_number mod N — no vote needed to choose who, only to confirm the change. The primary orders client requests, assigns op-numbers, sends Prepare, and commits on a majority of PrepareOK. On primary failure, replicas run view change: send StartViewChange/DoViewChange containing their logs to the next primary-in-rotation, which adopts the most complete log among a majority and broadcasts StartView.

Why it works. Same majority-intersection recovery: the new primary sees a majority of logs and takes the most up-to-date, so committed operations survive.

Pros. Round-robin primary selection avoids split votes entirely — there is exactly one candidate per view. Was designed as an RSM from day one, so it addresses client sessions and reconfiguration natively. VR Revisited (2012) is arguably clearer than the Raft paper.

Cons. Round-robin can hand leadership to a poor choice — a slow, distant, or freshly-restarted node — where Raft's election naturally favors an up-to-date node that timed out first. Comparatively tiny ecosystem, so you would be writing it yourself.

When to use it. Rarely chosen fresh today; know it because interviewers at systems-heavy companies use "how does VR differ from Raft?" to separate readers-of-papers from readers-of-blog-posts. The answer: deterministic rotating primary and log-transfer-based view change, versus voted leader and log-completeness-based election.

4.5ZAB (ZooKeeper Atomic Broadcast)#

What it is. The protocol inside Apache ZooKeeper, purpose-built for a primary-backup system where what matters is broadcasting state deltas in order.

Mechanism. Three phases — discovery (new leader learns the most up-to-date history from a quorum), synchronization (leader forces its history onto followers, truncating divergence), broadcast (steady state: two-phase PROPOSE → majority ACK → COMMIT). Transactions carry a zxid, a 64-bit identifier whose high 32 bits are the epoch and low 32 bits are a counter — logical time (§2.2) with the ordering baked into the ID (compare File 17's Snowflake layout: the same "put the ordering in the identifier" trick).

Why it works. Same intersection argument, with an extra guarantee: prefix ordering — if a leader proposes a then b, every follower delivers a before b, and a new leader never delivers a proposal without all its predecessors. That is what makes ZooKeeper's client-visible ordering guarantees so strong.

Pros. Delivers exactly what a coordination service needs: FIFO ordering per client, plus watch notifications (a client registers interest in a znode — a node in ZooKeeper's hierarchical namespace — and gets a one-shot callback when it changes). Extremely mature; a decade of production hardening.

Cons. Not a general consensus library — it is fused to ZooKeeper's data model. The extra COMMIT broadcast makes it chattier than Raft. Java/JVM operational baggage (garbage-collection pauses are a classic source of spurious ZooKeeper session expiry, §11.2).

When to use it. You don't implement ZAB; you deploy ZooKeeper. Choose ZooKeeper over etcd when you need its hierarchical namespace, ephemeral znodes (nodes that vanish when the creating session ends — the classic primitive for presence and lock release on crash), and watches, or when your ecosystem (HBase, older Kafka, Hadoop) already requires it. Choose etcd for a simpler HTTP/gRPC key-value API, a Go binary with no JVM tuning, and native lease/watch semantics.

4.6Fast Paxos#

What it is. An optimization that cuts the common case from 2 message delays to 1 by letting clients send values directly to acceptors, skipping the leader.

Mechanism. The leader pre-authorizes a "fast round." Clients broadcast their value straight to all acceptors, which accept whatever arrives first. If enough acceptors independently accept the same value, it is chosen in one message delay. Collisions (two clients' values arriving in different orders at different acceptors) are detected and resolved by falling back to a normal, leader-coordinated round.

Why it works. The fast path demands a larger quorum — roughly 3N/4 rather than N/2+1 — because two fast quorums must intersect in enough nodes to make a conflicting choice detectable.

Pros. Lowest possible latency when contention is near-zero: one message delay from client to acceptors.

Cons. Larger quorums mean less fault tolerance and more tail-latency exposure (you wait on more nodes). Collisions cost more than the normal path would have (you pay the fast attempt and then the recovery round), so under contention Fast Paxos is strictly worse. Substantially harder to implement and reason about.

When to use it. Only when writes are spatially partitioned so conflicts are genuinely rare and single-digit-millisecond latency is worth the complexity. Very rare in production. Know it as the "there is a 1-delay lower bound and here's how you'd reach it" answer.

4.7Flexible Paxos (FPaxos)#

What it is. A 2016 result that is one of the best "did you actually understand quorums?" interview weapons: majority quorums are sufficient but not necessary. All that safety requires is that every Phase-1 (election) quorum intersects every Phase-2 (replication) quorum — Phase-2 quorums need not intersect each other at all.

Mechanism. Choose Q1 (election) and Q2 (replication) with |Q1| + |Q2| > N. With N=5, instead of 3-and-3, you can run Q2 = 2, Q1 = 4: every write needs only 2 acknowledgements (faster commits, less tail-latency exposure), while leader election requires 4 nodes (rarer, and it's fine for it to be expensive).

Why it works. Phase 1 is the only moment recovery reads happen; as long as the recovering leader's quorum touches every prior replication quorum, it discovers every possibly-committed value. Two replication quorums never need to see each other because the leader alone orders their contents.

Pros. Directly reduces steady-state write latency and load — the dominant cost — by shifting the burden onto the rare election path. Composes naturally with geo-deployments: keep Q2 nodes close together.

Cons. Fault tolerance becomes asymmetric and must be reasoned about carefully: with Q1=4 of 5, losing two nodes means you can still commit (Q2=2 is satisfiable) but cannot elect a new leader — so the cluster works until the leader dies, then is stuck. That "works until it doesn't" mode is operationally treacherous. Few mainstream systems expose the knob.

When to use it. When write latency is critical, elections are rare, and you have the operational maturity to run the asymmetric-failure analysis. Also: use it as the explanation for why witness/observer topologies and Raft's non-voting learners are safe.

4.8EPaxos (Egalitarian Paxos)#

What it is. Leaderless Multi-Paxos: any replica can commit any command, and only conflicting commands need extra work.

Mechanism. Each command is proposed by whichever replica received it, along with its dependency set — the commands it interferes with (two commands interfere if they touch the same key and at least one is a write). Non-interfering commands commit in one round trip to a fast quorum, with no leader involved. Interfering ones take a second round trip to agree on dependency order. Execution orders commands by topologically sorting the dependency graph (breaking cycles by a deterministic sequence number), so the RSM still applies a single order.

Why it works. Consensus is only needed on relative order between conflicting operations; commutative operations don't need an agreed order at all — a deep observation the whole design rests on.

Pros. No single leader means no hotspot and no leader-region latency penalty — in a 5-region deployment, every client commits at the speed of its nearest quorum, which is transformative for global write latency. Leader failure causes no election stall.

Cons. Conflict detection and dependency-graph execution are complex and add per-command CPU and memory; under high conflict rates (a hot key) it degrades below Multi-Paxos. Correctness is subtle enough that published versions have had bugs found years later. Very few production implementations.

When to use it. Geo-distributed, write-heavy, low-conflict workloads where per-region write latency dominates — and you have a systems team that can own it. Name-drop it in interviews as the answer to "how would you avoid making all your Tokyo writes cross the Pacific to a Virginia leader?"

4.9Cheap Paxos & Witness Replicas#

What it is. Reducing the cost of fault tolerance by noticing that some quorum members don't need to store data.

Mechanism. Run f+1 full replicas plus f auxiliary/witness nodes that vote but store only metadata (the term and the latest index). Normal operation uses the full replicas; witnesses are pulled into quorums only when a full replica is unavailable, and the system then works to restore f+1 full copies quickly.

Pros. Tolerates f failures at roughly half the storage and I/O cost of 2f+1 full replicas — significant when the state is large. Widely used in practice: SQL Server Always On's file-share witness, MongoDB's arbiter, Azure Storage's witness deployments, and cross-region setups where a cheap third-region witness breaks ties without paying to store a third copy.

Cons. Reduced redundancy in degraded mode — if a full replica dies while a witness is in the quorum, you may be down to one full copy, so a second failure is data loss. Witnesses also encourage the anti-pattern of a 2+1 topology whose real fault tolerance is 1, which people forget under pressure.

When to use it. Large state, cost-sensitive, with strong operational discipline about rebuilding replicas fast. Also the standard way to place a tie-breaker in a third region cheaply.

4.10The Byzantine Family — PBFT, HotStuff, Nakamoto#

Included for taxonomy completeness (§0.1's hostile end) and because interviewers ask "what if a node lies?"

PBFT (Practical Byzantine Fault Tolerance, Castro & Liskov 1999). Three phases — pre-prepare, prepare, commit — over 3f+1 nodes with cryptographically signed messages. Nodes wait for 2f+1 matching messages before advancing, which is what makes a lie detectable: a liar cannot produce 2f+1 agreeing honest witnesses to a false statement. Pros: tolerates arbitrary malice with immediate finality (once committed, never reversed). Cons: O(N²) messages per decision — every node talks to every node — which caps practical size around a few dozen nodes; needs a public-key infrastructure. When: small, permissioned, mutually-distrusting groups (consortium ledgers, aviation/aerospace control).

HotStuff (2018, and its cousin Tendermint). Restructures BFT so all communication routes through a rotating leader with threshold signatures (a scheme where 2f+1 partial signatures combine into one compact signature verifiable in constant size), collapsing messages to O(N) per phase, plus a linear leader-rotation ("pacemaker"). Pros: scales BFT to hundreds of nodes; responsive (advances at network speed, not on fixed timeouts). Cons: still crypto-heavy; extra phase adds latency vs Raft. When: modern permissioned blockchains — this is the family Libra/Diem and many chains adopted.

Nakamoto consensus (Bitcoin-style). A completely different design point: open membership (anyone may join, so you cannot count nodes at all) with probabilistic finality. Instead of quorums, participants race to solve a computational puzzle (proof of work); the longest valid chain wins. Pros: works with unknown, unbounded, anonymous participants. Cons: astronomically expensive in energy, minutes-to-hours to reach practical finality, and finality is only probabilistic — a sufficiently long competing chain can still reorganize history. When: permissionless, open-membership systems only. Never for internal infrastructure; saying otherwise is disqualifying.

4.11Comparison Table#

4.12The Decision Rule#

Say this out loud in an interview:

5The Hard Parts of Raft Nobody Teaches You#

These four subsections separate people who read a blog post from people who have operated a cluster. They are also the highest-yield interview material in the file.

5.1Membership changes — why the naive approach corrupts your cluster#

The problem. You want to grow {A,B,C} into {A,B,C,D,E}. If nodes switch configuration at different moments — and they must, because the change propagates as a message — there is an interval where the old configuration's majority and the new configuration's majority are disjoint. Concretely: A and B (majority of the old 3) elect A as leader for term 5, while C, D, E (majority of the new 5) elect C as leader for term 5. Two leaders, same term, both able to commit. Split-brain, from a routine scale-up.

Solution 1 — Joint consensus (the original Raft paper). Move through an intermediate configuration C_old,new in which every decision requires separate majorities from both the old and the new configuration. Because a joint decision needs both, no decision can be made by only-old or only-new — the disjoint-majority window is closed by construction. The leader appends C_old,new to the log (configuration changes are log entries, so they are ordered relative to every write), commits it under joint rules, then appends C_new and commits under new rules. Cost: two configuration transitions, more code, and a genuinely tricky rule — a node uses the latest configuration in its log even if that entry is uncommitted, which is unintuitive but required for liveness.

Solution 2 — Single-server changes (the "simpler" approach, used by etcd). Add or remove exactly one node at a time. The insight: old and new majorities always overlap when the size changes by one (majority of 3 = 2, majority of 4 = 3; any 2-subset and any 3-subset of the 4 nodes must share a member). One configuration entry, no joint state. Cost: growing 3→5 requires two sequential changes, and a subtle bug (found in 2015, after publication) means an implementation must commit a no-op in the current term before accepting a new configuration change to avoid a rare case where an uncommitted config from a prior term reappears. Every serious implementation now does this.

The operational rule. Always add a new node as a learner first (§2.3), let it catch up, then promote it to voter. Adding an empty node directly as a voter enlarges the quorum instantly while the new member is useless — in a 3→4 change your majority jumps from 2 to 3, and the fourth node cannot help, so you have reduced availability during the very operation intended to increase it.

5.2The commit rule everyone gets wrong (Raft §5.4.2)#

The rule: a leader may only commit entries from its own current term by counting replicas. Entries from previous terms become committed only indirectly, when an entry from the current term that follows them is committed.

Why — the scenario that motivates it. Term 2 leader S1 replicates entry 3 to S2 and then crashes; entry 3 is on 2 of 5, not committed. S5 becomes leader in term 3 with a different entry 3 (it never saw S1's), then crashes without replicating. S1 recovers and becomes leader again in term 4; it replicates its old term-2 entry 3 to a majority (S1, S2, S3) and — if it were allowed to commit on replica count alone — declares it committed and answers the client. Now S5, whose log has a higher term at index 3, wins the term-5 election (the up-to-date check compares term first), and overwrites the entry S1 just declared committed. A committed entry destroyed. Safety violated.

The fix in operational terms: on winning an election, a Raft leader immediately appends a no-op entry in its own term. Committing that no-op — which requires a fresh majority in the current term — sweeps all preceding entries into the committed prefix legally, because the Log Matching Property (§2.7) means any node holding the no-op holds everything before it. This is why §3.5 step 5 had S2 append a no-op, and it is why a newly-elected leader briefly cannot serve linearizable reads: it does not yet know its own commit index until that no-op commits.

If an interviewer asks one deep Raft question, it is usually this one. The one-line answer: "A leader can't commit prior-term entries by replica count, because a later leader with a higher-term entry at the same index could still legally overwrite them; it commits a no-op in its own term instead, which carries the prefix with it."

5.3Linearizable reads — three mechanisms, three trade-offs#

A naive read served from the leader's local state is not linearizable (§2.6): the leader may have been deposed seconds ago by a partition it hasn't noticed, and will confidently serve stale data. Three fixes:

(a) Log read (read as a write). Push the read through the log as an ordinary entry. Pros: trivially correct, zero new mechanism. Cons: pays a full round trip and an fsync per read, and pollutes the log with entries that change nothing — catastrophic for a read-heavy workload. When: only if reads are rare or you want the read recorded for audit.

(b) ReadIndex. The leader records its current commitIndex as the read index, sends one round of heartbeats to confirm a majority still recognizes it as leader, waits until lastApplied ≥ readIndex, then serves the read from local memory. Pros: correct without any clock assumption; no disk write; heartbeats for many concurrent reads can be batched into one round, so per-read cost amortizes to nearly nothing under load. Cons: still one network round trip of latency on the read path (~0.5 ms in-DC, 100 ms+ cross-region). When: the safe default; etcd's --consistency=l reads work this way.

(c) Lease read (leader lease). The leader holds a time-based lease (§2.9): as long as now < last_heartbeat_success + election_timeout − clock_drift_bound, no other node can have been elected, so the leader serves reads purely locally, zero network cost. Pros: fastest possible — microseconds. Cons: correctness depends on bounded clock drift, and if a machine's clock jumps (VM migration, bad NTP), two leaders can overlap and you get a stale read. This is precisely the hazard Spanner's TrueTime was invented to bound. When: read-dominated workloads with well-managed NTP; CockroachDB and TiKV both use leader leases, and etcd offers it behind a flag.

(d) Follower reads (the honorable mention). Let followers serve reads to shed load. Naively this gives you stale reads (fine for many use cases — say so explicitly). To make them safe, the follower asks the leader for the current read index and waits until it has applied that far, trading one round trip to the leader for the ability to serve the data locally — worth it when the data transfer is large or the follower is near the client.

Decision rule: default to ReadIndex with batching; upgrade to lease reads only if you control clock discipline and reads dominate; use follower reads to scale read throughput, and be explicit with the interviewer about whether they're stale or read-index-safe.

5.4Pre-Vote and CheckQuorum — the two patches every real implementation has#

The disruption problem. A node partitioned away from the cluster keeps timing out and incrementing its term: 8, 9, 10, 11… When the partition heals, it broadcasts RequestVote{term: 47}. Every node — including the perfectly healthy leader — sees a higher term and, per §2.2's rule, immediately steps down. The cluster is forced into an election it did not need, and the disruptive node can't even win (its log is behind, §3.4). A single flapping node repeatedly stalls a healthy cluster.

Pre-Vote fixes it: before incrementing its term, a candidate runs a dry-run election — "would you vote for me, hypothetically, at term+1?" Peers answer no if they've heard from a live leader recently. The partitioned node gets no pre-votes, never increments its real term, and disturbs nobody. Cost: one extra round trip on every genuine election, slightly slowing legitimate failover. Every production Raft (etcd, TiKV, HashiCorp) enables it.

CheckQuorum attacks the other side of the same coin: a leader that cannot reach a majority should step down on its own rather than continue to believe it is leader (and serve stale lease reads). Implementation: each election-timeout interval, the leader checks whether it received responses from a majority; if not, it demotes itself to follower. This bounds the window in which a partitioned leader can serve stale data — essential for lease reads to be safe.

Together these two, plus leader transfer (a graceful handoff RPC where a leader tells a chosen follower to start an election immediately, used before planned maintenance so failover takes milliseconds instead of a full election timeout), constitute the "real world Raft" patches that appear in every mature implementation and in almost no tutorials.

6Consensus vs Atomic Commit vs Locking — Three Things Everyone Confuses#

6.1Consensus vs Two-Phase Commit (2PC)#

They look alike — both have two phases and a coordinator — and they solve opposite problems.

Consensus asks: "which value do we choose?" It needs only a majority to agree, so it tolerates a minority of failures and still makes progress.

Two-phase commit (atomic commit) asks: "does this transaction commit or abort across several different systems?" It requires unanimity — every participant must vote yes, because any one of them may hold a constraint that forbids the transaction. Unanimity means any single participant failure blocks the outcome, and worse: if the coordinator crashes after participants voted yes but before broadcasting the decision, participants are stuck holding locks with no way to learn the answer. This is 2PC's infamous blocking problem. (Three-phase commit adds a pre-commit phase to reduce blocking, but is unsafe under network partitions and is essentially never used.)

The synthesis that impresses interviewers: the fix for 2PC's blocking is to make the coordinator fault-tolerant by replicating its decision log with consensus — which is exactly what Google Spanner does (each participant group is a Paxos group, and 2PC runs across those groups), what CockroachDB does with Raft, and what "consensus and 2PC are complementary, not competing" actually means. Consensus makes each participant highly available; 2PC makes the multi-participant transaction atomic.

6.2Consensus vs Leader Election vs Distributed Locking#

These three are frequently used as synonyms and are not.

Leader election is one application of consensus: agree on the value "who is the leader for epoch N." You can also do it without running consensus yourself — by storing the leadership claim in an external consensus-backed store (etcd, ZooKeeper), which is what almost every application should do.

Distributed locking is another application, and the dangerous one. A consensus store can tell you "you hold the lock," but as §2.9 established, it cannot make you stop running. A garbage-collection pause, a hung disk I/O, or a CPU-starved container can freeze a lock holder past its lease expiry; when it wakes, it still believes it holds the lock. The lock service is correct, and your data is corrupt. The mandatory mitigation is fencing tokens validated by the resource itself. If a candidate proposes "we'll use Redis/etcd for a distributed lock" and doesn't mention fencing, that is the gap to probe — and if you're the candidate, mention it unprompted.

Also worth knowing: Redlock (a multi-Redis-instance locking scheme) is widely criticized precisely because it relies on bounded clock drift and process pause times without providing fencing; the safe pattern is a consensus-backed lease plus a token the storage layer enforces.

6.3When you should NOT use consensus#

Say this proactively — it demonstrates judgment rather than pattern-matching:

7Performance Engineering — Making Consensus Fast Enough to Use#

7.1The latency budget, with real numbers#

One commit costs: leader's local fsync (0.1–1 ms on datacenter SSD, 5–10 ms on spinning disk) in parallel with the network round trip to followers (0.3–0.7 ms same-datacenter, 1–2 ms cross-AZ, 30–70 ms US-coast-to-coast, 120–180 ms trans-Pacific), plus each follower's own fsync, and then the leader waits for the ⌊N/2⌋+1-th response — so you always wait for the median-ish node, which makes tail latency (File 12's p99 discussion) the thing that actually bites.

Practical implications: a 3-node in-datacenter Raft group commits in ~1–2 ms, so an un-batched, un-pipelined single client sees ~500–1,000 writes/sec. That number horrifies people until they apply §7.2, after which the same cluster does 30,000–100,000+ writes/sec.

7.2Batching and pipelining — the two multipliers#

Batching amortizes the fixed costs: the leader collects all commands that arrive during the current round trip and sends them as one AppendEntries with many entries, and each node does one fsync for the whole batch. Since fsync and RTT costs are nearly independent of payload size, batching 100 commands costs barely more than batching 1 — a ~100× throughput gain at the cost of a fraction of a millisecond of added latency for the earliest command in the batch. This is the same "amortize the expensive sequential I/O" idea as Kafka's producer batching (File 07 §5) and an LSM tree's memtable flush (File 11 §3).

Pipelining removes the stop-and-wait: the leader sends entry N+1 without waiting for N's acknowledgement, keeping multiple batches in flight (the classic bandwidth-delay-product argument — with a 1 ms RTT and 10 Gbps links, stop-and-wait uses a rounding error of the available bandwidth). It must handle out-of-order and lost responses, and if a follower rejects an entry the leader must roll nextIndex back and resend the whole in-flight window — which is why implementations bound the number of in-flight batches.

A third, often forgotten: the leader can send AppendEntries to followers before its own fsync completes, because the commit condition is "a majority has it durably" — and the leader is only one member of that majority. Overlapping local disk with remote network is a free ~30–50% latency reduction, and it is exactly what modern implementations do.

7.3Where to put the nodes (geo topology)#

Three placements, three trade-offs:

All in one datacenter: ~1 ms commits, but a datacenter failure takes everything down. Acceptable only when a higher layer handles regional failover.

Across 3 availability zones in one region (AZs are physically separate datacenters within a region, typically 1–2 ms apart): ~2–3 ms commits and survives losing an entire AZ. This is the default correct answer for a production consensus group, and it is what AWS/GCP/Azure customers should say by reflex.

Across 3 regions: survives losing a whole region, but every commit pays the round trip to the second-nearest region — 30–70 ms continental, 150 ms+ intercontinental — on every write, forever. Mitigations: place the leader in the region with the most writes; use a witness (§4.9) in the third region so you pay tie-breaking cost but not full-replica cost; or use Flexible Paxos quorums (§4.7) so the replication quorum is the two closest nodes.

7.4Multi-Raft — how you actually scale past one group#

A single consensus group has a hard ceiling: one leader, one ordered log, one machine's CPU and NIC. The universal answer is not a better algorithm — it is many groups.

Partition the keyspace into ranges or shards (File 04), and run an independent Raft group per shard, with leaders spread evenly across machines so every machine leads some groups and follows others. Throughput now scales linearly with shard count, because unrelated shards never coordinate. This is precisely how CockroachDB (one Raft group per ~512 MB range), TiKV (one per region), and Kafka KRaft-era partitioning work.

The costs you must name: (a) heartbeat explosion — 10,000 groups × 10 heartbeats/sec × N followers is enormous background traffic, solved by batching heartbeats per node-pair rather than per-group (TiKV's "hibernate regions" goes further and stops heartbeating idle groups entirely); (b) a transaction spanning shards now needs 2PC across groups (§6.1), with all its cost; (c) rebalancing ranges as data grows requires moving Raft group members around, which is a membership change (§5.1) per move.

The senior framing: "Consensus doesn't scale up, it scales out — you don't make one Raft group faster, you make thousands of small ones and keep transactions inside a single group whenever the data model allows."

8Pros, Cons & Trade-offs#

8.1Benefits — and why each is true#

Strong consistency you can actually reason about. Because all writes pass through one leader into one totally ordered log, and reads can be made linearizable (§5.3), the system behaves like a single machine that never fails. This eliminates an entire universe of bugs — no conflict resolution, no read-repair, no "eventually" caveats leaking into product logic. The value is not just correctness; it's the reduction in the number of states your application code has to handle.

Automatic failover with zero data loss. The election restriction (§3.4) guarantees a new leader's log contains every committed entry, so failover is safe by construction rather than by careful operator procedure. Compare asynchronous primary-replica replication (File 08 §4.1), where promoting a lagging replica silently loses acknowledged writes — the exact failure that has caused famous production data-loss incidents.

Split-brain is impossible, not merely unlikely. Majority quorums plus term numbers (§0.5, §2.2) make two concurrent committing leaders a mathematical impossibility, not a race you hope to lose rarely. This is qualitatively different from heartbeat-based failover schemes that mitigate split-brain with timing heuristics.

Tolerates the realistic failure set. A 5-node group survives any 2 simultaneous failures — machine crashes, disk failures, a whole AZ, rolling restarts during deploys — with zero downtime and no operator action.

Self-healing and operable. A recovered node re-syncs automatically via the consistency check (§3.3) or a snapshot (§2.10). Cluster membership changes online (§5.1). You can do rolling upgrades one node at a time without ever taking a write outage.

8.2Costs & Trade-offs — rigorously#

Latency floor set by physics. Every write costs a majority round trip plus a durable flush; you cannot buy your way below the speed of light. Mitigation: co-locate the group in one region across AZs (§7.3), batch and pipeline aggressively (§7.2), keep the leader near the writers, and keep large data out of the log (§6.3).

Write throughput does not scale with cluster size — it degrades. Adding nodes raises the majority threshold and multiplies the leader's outbound traffic. Mitigation: 5 nodes is the sweet spot; scale via multi-Raft sharding (§7.4), not bigger groups.

Minority partitions are hard down. A node cut off from the majority can serve neither writes nor linearizable reads. This is CP by choice (File 08 §3), and the honest framing is that you chose unavailability over inconsistency. Mitigation: offer explicitly-labeled stale reads from followers for use cases that tolerate them, and be sure clients degrade gracefully rather than hanging.

Losing quorum is an emergency with an unsafe recovery. Lose 2 of 3 nodes and the cluster cannot elect, cannot commit, and cannot recover itself. The only path back is a forced reconfiguration — telling a surviving node "pretend you are the whole cluster" — which can silently discard committed writes that lived only on the dead nodes. Mitigation: 5 nodes across 3 AZs, aggressive monitoring of quorum health, frequent snapshots stored off-cluster, and a rehearsed runbook — do not improvise this at 3 a.m.

Operational complexity that is easy to underestimate. Disk-full on one node can wedge a leader (it cannot fsync, so it cannot commit); clock skew breaks lease reads; a slow-disk node drags p99 because it may be in the majority; snapshots cause I/O storms; a wrong membership-change procedure can destroy a cluster. Mitigation: use a mature implementation, monitor per-follower matchIndex lag, alert on leader-election rate (not just leader identity), and reserve disk headroom.

Every commit is an fsync, which is hostile to cheap storage. Mitigation: NVMe or SSDs with power-loss-protected write caches; never run a consensus node on network-attached storage with unpredictable latency.

8.3The Senior Rule#

Put as little as possible in consensus, and shard what you do put there. Consensus is the most expensive primitive in distributed systems — it costs a round trip, a disk flush, and permanent operational attention. Reserve it for the small, precious, must-be-singular decisions (who is the leader, who owns this shard, what is the current epoch, is this seat sold), keep the bulk data in systems built for bulk data, and when one group is no longer enough, add groups rather than nodes. The candidate who says "I'd store the 200 KB of cluster metadata in a 5-node etcd across three AZs and keep the 40 TB of user data out of it" is the one who has done this before.

9Interview Diagnostic Framework (Symptom → Solution)#

10Real-World Engineering Scenarios#

10.1etcd + Kubernetes — the control plane of the modern internet#

Kubernetes stores all cluster state — every Pod, Service, Secret, ConfigMap, node registration, and leader lock — in etcd, a Raft-based key-value store. Trace a deployment:

Takeaway: Kubernetes is, architecturally, a consensus log with controllers attached — every component reads the same ordered log and reconciles reality toward it. It also shows the §8.3 rule in practice: etcd holds megabytes of metadata, never the container images or application data.

10.2Google Chubby & Spanner — consensus at planetary scale#

Chubby (2006) is Google's Multi-Paxos-based lock service: five replicas per cell, one elected master, coarse-grained locks and small files. Its most quoted lesson is that although it was built as a lock service, its dominant use became name service — everyone used it to answer "who is the primary?" — which is why the industry converged on ZooKeeper/etcd-shaped coordination services.

Spanner builds on this to deliver globally distributed, externally consistent transactions:

Takeaway: global strong consistency is achievable, but the price is Paxos per shard, 2PC across shards, and custom time hardware in every datacenter to bound clock uncertainty. When an interviewer asks "why can't everyone just do what Spanner does," the answer is: because most companies cannot install atomic clocks, and commit-wait means you pay the uncertainty window on every write.

10.3Kafka's KRaft — replacing ZooKeeper with Raft#

Kafka historically stored its metadata (topics, partitions, leaders, ISR membership) in ZooKeeper (ZAB, §4.5). This had structural problems: the controller had to load all metadata from ZooKeeper on failover — tens of seconds for large clusters — and operators had to run and tune two distributed systems.

KRaft (production-ready in Kafka 3.3, ZooKeeper removed in 4.0) folds metadata into Kafka itself:

Takeaway: the same log abstraction serves data and metadata; embedding Raft removed an entire external dependency and turned a slow full-state reload into an ordered incremental log tail. It is also a clean example of §2.3's learner role at scale — hundreds of brokers consume the consensus log without ever voting.

11Interview Gotchas & Failure Modes#

11.1Classic Questions (and the crisp answers)#

"Why do consensus clusters use an odd number of nodes?" Fault tolerance is (N−1)/2 rounded down, so 4 nodes tolerate the same single failure as 3 while requiring a larger majority and one more fsync per commit. The extra node adds cost and latency and buys zero additional fault tolerance.

"Can Raft ever lose a committed entry?" No. A committed entry is on a majority; any future leader needs votes from a majority; the two intersect, and the intersecting node refuses to vote for a candidate whose log lacks it (§3.4). Uncommitted entries can be truncated — but no client was ever told they succeeded.

"What happens if two nodes become leader at the same time?" They can't in the same term — a node votes at most once per term and votedFor is fsynced. Two leaders in different terms can transiently exist (a partitioned old leader), but the old one cannot commit anything, because no majority will accept a lower term (§2.2), and it is demoted by the first higher-term reply it sees.

"Is a read from the Raft leader linearizable?" Not by default — a partitioned leader may not know it was deposed. You need ReadIndex (a heartbeat round confirming leadership) or a lease read with a bounded clock-drift margin (§5.3).

"Raft vs Paxos — which and why?" Same guarantees, same steady-state cost of one round trip. Raft mandates a strong leader and a hole-free log, which makes it dramatically easier to implement correctly and has a rich ecosystem; Multi-Paxos permits out-of-order commits for higher pipelined throughput at much higher implementation complexity. Choose Raft unless you have a specific reason.

"Why does a new Raft leader append a no-op?" Because it may not commit prior-term entries by counting replicas (§5.2 — a higher-term entry at the same index could still legally overwrite them). Committing a current-term no-op carries the whole preceding prefix into the committed set via the Log Matching Property, and it is also how the leader learns its true commit index before serving linearizable reads.

"How do you add nodes safely?" One at a time (or via joint consensus), as a learner first, promoted only after it has caught up — otherwise you enlarge the quorum with a useless member and reduce availability during the change (§5.1).

"How many nodes can fail before you lose data vs before you lose availability?" They're different numbers, and mixing them up is a common slip. With N=5: you lose availability at 3 failures (no majority), but you lose committed data only if you lose enough nodes that no surviving node holds the committed entry and you then force an unsafe reconfiguration.

"What's the difference between consensus and 2PC?" Consensus needs a majority and tolerates minority failure; 2PC needs unanimity and blocks on any participant or coordinator failure. They compose: replicate the 2PC coordinator's log with consensus (§6.1).

"Do you even need consensus here?" Often the winning answer. If operations commute, use CRDTs; if writes are independent, shard; put only must-be-singular decisions in the consensus log (§6.3).

11.2Failure Modes & Mitigations#

Election storms. Symptom: leadership changes every few seconds, writes stall repeatedly. Cause: election timeout too short relative to real network/GC latency, or a saturated leader failing to send heartbeats on time — and the resulting retries add load, worsening the cause. Mitigation: raise election timeout to ≥10× observed p99 heartbeat RTT, enable Pre-Vote, alert on election rate rather than just leader identity, and give the Raft heartbeat path its own goroutine/thread so application load can't starve it.

Disk-induced leader wedge. Symptom: leader stops committing but doesn't step down; cluster appears "up" and is useless. Cause: fsync latency spiraling (disk full, noisy neighbor, degraded NVMe) — the leader can still heartbeat but cannot durably append. Mitigation: monitor per-node wal_fsync_duration (etcd exposes this; sustained >25 ms p99 is a red alert), reserve disk headroom with hard quotas, and configure the node to step down when its own commit path stalls.

GC pause / VM stall causing false failover and stale lease reads. Symptom: healthy leader is deposed; briefly, two nodes serve reads. Cause: a multi-second stop-the-world pause (or a VM live-migration freeze) exceeds the lease. Mitigation: tune or replace the garbage collector, never run consensus nodes on oversubscribed hosts, set the clock-drift margin generously, enable CheckQuorum, and — the real fix — use fencing tokens so a stale actor's writes are rejected at the resource (§2.9).

Snapshot I/O storms. Symptom: p99 latency spikes periodically; followers fall behind right after. Cause: serializing multi-GB state while serving traffic, or shipping a full snapshot over a shared link. Mitigation: copy-on-write snapshots, off-peak scheduling, rate-limited InstallSnapshot, and separate disks for WAL and snapshot data.

Slow-follower tail latency. Symptom: p99 commit latency far exceeds p50 for no obvious reason. Cause: the majority sometimes includes a degraded node, so its latency becomes yours. Mitigation: monitor per-follower matchIndex lag and response times, evict chronically slow members, and prefer 5 nodes so a single laggard is more often excluded from the majority.

Quorum loss. Symptom: no leader, all writes fail, cluster cannot self-heal. Cause: too many simultaneous failures (an AZ outage in a badly-placed 3-node cluster, or a correlated bad deploy). Mitigation: 5 nodes across 3 AZs; automated off-cluster snapshot backups; a rehearsed forced-reconfiguration runbook that explicitly acknowledges its potential to lose committed writes — and never let anyone improvise it live.

Clock skew breaking leases. Symptom: rare stale reads under lease-read mode. Cause: NTP failure or a jump after VM migration (File 17 §0.3). Mitigation: monitor clock offset as a first-class metric, alert above the drift margin, automatically fall back to ReadIndex reads when offset exceeds the bound.

Unbounded log growth. Symptom: disks fill; restarts take forever. Cause: snapshotting disabled or misconfigured, or a stuck follower forcing the leader to retain entries. Mitigation: enforce snapshot intervals by entry count and size, and remove or rebuild followers that fall too far behind rather than retaining log forever.

Membership-change corruption. Symptom: two leaders, or a cluster that cannot elect after a resize. Cause: changing more than one node at a time, or removing a node before the new one caught up. Mitigation: strictly one change at a time, learner-first promotion, and verifying commit of each config entry before starting the next.

12Whiteboard Cheat Sheet#

════════════════════ DISTRIBUTED CONSENSUS — BOARD DUMP ════════════════════

THE PROBLEM: agree on ONE ordered log, when nodes crash and messages
             are lost/delayed/reordered, and "slow" is indistinguishable
             from "dead" (§0.2). FLP: can't have safety + guaranteed
             liveness in async → ALWAYS SACRIFICE LIVENESS, NEVER SAFETY.

THE TRICK:   any two MAJORITIES INTERSECT (3+3 > 5). Therefore committed
             info can't be lost, and two leaders can't both commit.

RSM:         same start + same commands + same order + deterministic
             = same state.  Consensus replicates the LOG, not the data.

┌──── RAFT STATE ────────────────────────────────────────────────┐
│ FOLLOWER ──timeout──► CANDIDATE ──majority votes──► LEADER      │
│     ▲                     │                            │        │
│     └──── higher term seen / legit leader heard ───────┘        │
│ PERSIST (fsync!): currentTerm, votedFor, log[]                  │
│ VOLATILE: commitIndex, lastApplied | LEADER: nextIndex[],       │
│           matchIndex[]                                          │
└─────────────────────────────────────────────────────────────────┘

WRITE PATH:  client → leader appends+fsync → AppendEntries{prevIdx,
             prevTerm, entries, leaderCommit} → follower checks prev
             matches (LOG MATCHING) → append+fsync → ack → MAJORITY
             → commitIndex++ → apply → reply client.  1 RTT + 1 fsync.

ELECTION:    term++, vote self, RequestVote{lastLogIdx,lastLogTerm}
             GRANT only if candidate log ≥ mine  ◄── makes committed
             entries a PREREQUISITE for leadership (safety)
             RANDOMIZED timeouts (150–300ms ×) kill split votes

╔══ THE 4 RULES THAT ARE ALWAYS ON THE EXAM ═════════════════════╗
║ 1. Only truncate UNCOMMITTED entries → never lose an ack'd write║
║ 2. New leader may NOT commit prior-term entries by count →      ║
║    append a NO-OP in own term (§5.2)                            ║
║ 3. Leader-local reads are NOT linearizable → ReadIndex (1 HB    ║
║    round) or lease read (needs bounded clock drift) (§5.3)      ║
║ 4. Membership: ONE node at a time (or joint consensus),         ║
║    LEARNER first, promote after catch-up (§5.1)                 ║
╚═════════════════════════════════════════════════════════════════╝

ALGORITHM MAP:
  Basic Paxos    2 RTT/value, leaderless, livelock-prone → one-shot
  Multi-Paxos    Phase1 once/term, 1 RTT/cmd, holes OK   → max tput
  RAFT           strong leader, no holes, 1 RTT/cmd      → ★ DEFAULT
  VR             rotating primary by view mod N          → know it
  ZAB            zxid=epoch|counter, 3 phases            → ZooKeeper
  Fast Paxos     1 delay, 3N/4 quorum, collisions hurt   → rare
  Flexible Paxos |Q1|+|Q2|>N, cheap writes/costly elect  → latency
  EPaxos         leaderless + dep graph, commit locally  → geo/WAN
  Cheap Paxos    f+1 full + f witnesses                  → cost cut
  PBFT/HotStuff  3f+1, signed, O(N²)/O(N)               → Byzantine
  Nakamoto (PoW) open membership, probabilistic finality → public

PRODUCTION PATCHES (in every real impl, in no tutorial):
  Pre-Vote (stop partitioned node disrupting) · CheckQuorum (leader
  self-demotes) · leader transfer (graceful failover) · batching +
  pipelining (100× tput) · send-before-own-fsync · learner nodes

NUMBERS:  fsync SSD 0.1–1ms · same-DC RTT 0.5ms · cross-AZ 1–2ms ·
          US coast-coast 60ms · trans-Pacific 150ms
          3-node in-region commit ≈ 1–2ms; batched ≈ 30–100k writes/s
          5 nodes / 3 AZs = the default correct topology
          N=3 → tolerate 1 · N=5 → tolerate 2 · NEVER use even N

SCALING:  DON'T make one group faster — RUN MANY GROUPS.
          Multi-Raft: 1 group/shard, leaders spread, batch heartbeats.
          Cross-group txn = 2PC over consensus groups (Spanner shape).

DON'T USE CONSENSUS FOR: bulk data (metadata only!) · commutative ops
          (CRDT/LWW) · independent writes (shard) · global WAN writes
          you could keep regional.

DANGER:   quorum loss = manual unsafe recovery (can lose data) ·
          lock without FENCING TOKEN is unsafe (GC pause) ·
          election storms from too-short timeouts · fsync stall wedges
          leader · clock skew breaks lease reads
════════════════════════════════════════════════════════════════════

13One-Sentence Summary for an Interviewer#

Distributed consensus is the protocol by which a cluster maintains one totally-ordered replicated log — and therefore, by determinism, one identical state machine — despite crashes, dropped packets, and the fundamental inability to distinguish a dead node from a slow one; it works because any two majority quorums must intersect, which makes committed data impossible to lose and split-brain impossible to commit, and because FLP forbids having both safety and guaranteed progress, every real algorithm sacrifices liveness and never safety; Raft is the practical default — a strong leader elected by majority under the rule that only a candidate with an up-to-date log may win, replicating entries that commit once a majority has them durably, with terms fencing off stale leaders — costing one round trip plus one fsync per commit (~1–2 ms across three AZs, 150 ms across oceans), which you make survivable with batching and pipelining and scale with many Raft groups rather than bigger ones; and the senior judgment is to put only the small, must-be-singular state — leadership, ownership, epochs, uniqueness — into consensus, serve reads through ReadIndex or a clock-bounded lease rather than naively from the leader, always pair distributed locks with fencing tokens, and remember that a minority partition is deliberately unavailable because you chose correctness over uptime.

End of File 18. Next → File 19: Observability & Monitoring — metrics, logs, traces, the four golden signals, and why "is it up?" is the hardest question to answer about a system you just made highly available. Prompt me to continue.