Chapter 12: Raft — Consensus Made Understandable

Curriculum: Distributed Systems from First Principles Chapter: 12 of 24 Part: 5 — Consensus Prerequisites: Chapter 11 (consensus problem, FLP, quorums, safety vs liveness, Paxos overview) Estimated reading time: 85–95 minutes

Opening

Chapter 11 ended with Paxos: correct, proven, and notoriously hard to implement because the paper leaves critical details unspecified. Every team that implemented Multi-Paxos built something slightly different and discovered new edge cases that Lamport never addressed. Diego Ongaro and John Ousterhout's 2014 response to this was Raft — a consensus algorithm designed explicitly for understandability. Not the most theoretically elegant, not the highest performance, but fully specified: every edge case described, every design decision explained, no room for implementation divergence. Their thesis included a user study showing that students who learned Raft could answer questions about it more accurately than students who learned Paxos.

Raft's key decomposition: instead of tackling consensus as one monolithic problem, decompose it into three relatively independent sub-problems — leader election, log replication, and safety. Solve each sub-problem cleanly, and the whole becomes tractable. This chapter builds all three from the ground up, traces every important failure scenario, and ends with how etcd, CockroachDB, and Consul implement Raft in production.

Part 1: The Replicated Log — What We're Trying to Build

Before the algorithm, the target. Raft's goal is maintaining an identical replicated log across all nodes in the cluster.

5-node Raft cluster, steady state:

Leader (Node 1):   [1:set x=3][2:set y=1][3:del z][4:set x=9]  ← commit index: 4
Follower (Node 2): [1:set x=3][2:set y=1][3:del z][4:set x=9]
Follower (Node 3): [1:set x=3][2:set y=1][3:del z][4:set x=9]
Follower (Node 4): [1:set x=3][2:set y=1][3:del z][4:set x=9]
Follower (Node 5): [1:set x=3][2:set y=1][3:del z][4:set x=9]

Every node has identical log entries in identical positions.
State machine on each node applies entries in order: x=9, y=1, z deleted.

Each log entry has an index (its position in the log, 1-based) and a term (the election term during which the leader created it). The term is the key safety mechanism — it's what lets nodes detect stale leaders and prevent log corruption during leader transitions.

A client write arrives at the leader. The leader appends it to its log, replicates it to followers, waits for quorum acknowledgement, marks it committed, applies it to its state machine, and responds to the client. That sequence is what "a Raft write" means. Let's now understand each piece.

Part 2: Leader Election — Choosing Who's in Charge

Raft time is divided into terms — consecutive integers starting from 1. Each term begins with an election. If a leader is elected, it serves for the rest of the term. If an election fails (split vote), the term ends with no leader and a new term and new election begin immediately.

Terms are the logical clock of Raft. Every message carries the sender's current term. If a node receives a message with a higher term than its own, it immediately updates its term to the higher value and steps down to follower state. If a node receives a message with a lower term, it rejects it. This ensures that messages from stale leaders (that haven't heard about a newer election) are always ignored.

Each term has a term number, stored durably on disk by every node.

The election mechanism

Every node starts as a follower. Followers expect regular heartbeats from the current leader. If a follower doesn't hear from the leader within its election timeout (a random value between 150 ms and 300 ms in Raft's reference implementation), it assumes the leader has crashed and initiates an election.

Why random? Chapter 11 explained: randomness breaks symmetry. If all followers used the same timeout, they'd all start elections simultaneously, all vote for themselves, all get 1 vote, and no one achieves quorum — a perpetual split vote. Randomised timeouts stagger the election starts: the node with the shortest timeout (say, 157 ms) typically starts first, requests votes before the others time out, and wins before competition starts.

The election sequence:

The two conditions for granting a vote are both important. The "haven't voted yet" condition ensures each node votes for at most one candidate per term — preventing two candidates from simultaneously achieving quorum. The "log at least as up-to-date" condition is the safety mechanism — covered in Part 4.

When a candidate becomes leader, it immediately sends heartbeat messages (AppendEntries RPC with no log entries) to all followers to establish authority and reset their election timeouts. From this point, the leader sends heartbeats at least every 50 ms (well within follower timeout windows) to prevent new elections while it's healthy.

Handling vote splitting

Despite randomised timeouts, split votes still occasionally occur — two nodes might time out close together and both collect partial votes. Raft handles this simply: if a candidate's election timeout fires again before it wins (meaning the election has gone on too long), it increments its term again and starts a new election. No special protocol needed — the next round's randomisation will usually produce a winner.

Split vote scenario:

Term 5 election:
  Node C starts election (term=5), gets votes from {C, D} — needs 3
  Node E starts election (term=5), gets votes from {E, A} — needs 3
  Node B hasn't voted yet but hasn't heard from either
  → Nobody reaches quorum before timeouts fire again

Term 6 election:
  Nodes C, E both increment to term=6
  Randomised timeouts: C=162ms, E=271ms
  → C starts first, wins before E's timeout fires

Before going further, watch an election happen. Kill the leader, see which follower's timer runs out first, then rig a tie and watch the term end with no winner.

Part 3: Log Replication — Getting Entries Onto All Nodes

Once elected, the leader handles all client writes. When a client writes set x=9:

1. The leader appends the entry to its own log: {index: 5, term: 3, command: "set x=9"}
2. The leader sends AppendEntries RPC to all followers in parallel:
   codeCopy

   AppendEntries(
     term: 3,
     leaderId: A,
     prevLogIndex: 4,        ← index of entry just before the new one
     prevLogTerm: 3,         ← term of that preceding entry
     entries: [{index:5, term:3, cmd:"set x=9"}],
     leaderCommitIndex: 4    ← highest index the leader has committed
   )
   

3. Each follower receiving the RPC:
   • Checks that prevLogIndex and prevLogTerm match its own log at that position
   • If match: appends the new entries, acknowledges
   • If mismatch: rejects (the follower's log diverges — handled in Part 5)
4. Once the leader receives acknowledgements from a quorum (itself + 2 others in a 5-node cluster), the entry is committed.
5. The leader applies the committed entry to its state machine, responds to the client.
6. The leader piggybacks the updated leaderCommitIndex in the next heartbeat, so followers know to apply entries up to that index.

The client gets a response at 1 ms — one network round trip. The followers apply the entry slightly later (on the next heartbeat) but that's fine: they don't serve reads unless specifically configured to do so (more on that below).

Pipelining for throughput

Raft doesn't need to wait for one entry to commit before sending the next. The leader can pipeline: send entries 5, 6, 7 to followers simultaneously, track acknowledgements separately, and advance the commit index as each quorum is achieved. This is how Raft implementations reach 100,000+ commits/second — not by making individual round trips faster, but by keeping many in flight simultaneously.

Part 4: Safety — The Election Restriction That Prevents Log Loss

This is the most important safety property in Raft, and it's worth understanding precisely because it prevents a subtle but catastrophic failure mode.

The scenario: The leader has committed an entry at index 17. It crashes. A new election occurs. A follower that doesn't have index 17 in its log wins the election. The new leader starts overwriting logs. Index 17 — a committed entry — is now gone. A client was told their write succeeded. The write is now lost. The database has corrupted.

Raft prevents this with the election restriction: a node only grants a vote to a candidate if the candidate's log is at least as up-to-date as the voter's log.

"At least as up-to-date" is defined precisely:

• If the candidate's last log entry has a higher term than the voter's, the candidate is more up-to-date.
• If they have the same last term, the candidate with the longer log is more up-to-date.
• If both are equal, they're equally up-to-date (tie — voter can grant).

Why this works:

Entry committed at index 17 means: a quorum (≥3 of 5 nodes) has it.
For a new leader to be elected, it needs votes from a quorum (≥3 of 5 nodes).
Any quorum of 3 must share at least 1 node with the commit quorum of 3.
That shared node has entry 17.
That shared node will only vote for a candidate with log ≥ its own.
So the winning candidate must have log ≥ that of the shared node.
So the winning candidate must have entry 17.

Therefore: any elected leader has all committed entries. ✓

This is the proof sketch for Raft's Leader Completeness Property: if a log entry is committed in a given term, that entry will be present in the logs of all future leaders. This property is what makes Raft safe — committed entries are never lost.

Let's trace it with numbers:

5-node cluster, after some entries committed:

Node A (leader): [1:t1][2:t1][3:t2][4:t2][5:t3] ← committed through 4
Node B:          [1:t1][2:t1][3:t2][4:t2][5:t3]
Node C:          [1:t1][2:t1][3:t2][4:t2]         ← missing entry 5
Node D:          [1:t1][2:t1][3:t2][4:t2]
Node E:          [1:t1][2:t1][3:t2]                ← missing entries 4, 5

Entry 4 is committed (A, B, C, D all have it — quorum of 4).
Entry 5 is NOT committed yet (only A and B have it — 2, not quorum).

A crashes. New election:
  - Can E win? E's last entry is index 3, term 2.
    Node B would check: E's lastLogTerm=2, B's lastLogTerm=3. B's is higher.
    B refuses to vote for E. C, D also have lastLogTerm=2 — would they vote for E?
    C's last is index 4, term 2. E's last is index 3, term 2. C has longer log.
    C refuses. D refuses (same). E cannot win. ✓
    
  - Can C win? C's last entry is index 4, term 2.
    B won't vote (B's lastLogTerm=3 > C's lastLogTerm=2).
    But C doesn't need B: a majority of 5 is 3 votes.
    C votes for itself. D's log is identical to C's (index 4, term 2) → D grants.
    E's log is shorter (index 3) → E grants.
    C gets C, D, E = 3 votes. C CAN win. ✓ (and this is safe)
    C has entry 4 — the committed one. It does NOT have entry 5, so as
    leader it will overwrite entry 5 on B. That's allowed: entry 5 was
    never committed, so no client was ever told it succeeded.

  - Can B win? B's last entry is index 5, term 3.
    C, D, E all have lastLogTerm ≤ 3 and lastLogIndex ≤ 5. B is at least as up-to-date.
    B gets votes from C, D, E (plus itself = 4 votes). B wins.
    B has entries 1-5, including committed entry 4. ✓

  Whoever wins first — B or C — the committed entry 4 survives.
  Only E (missing a committed entry) is guaranteed to lose.

The election restriction does not force the most up-to-date node to win — C can beat B. What it guarantees is narrower and exactly enough: the winner always holds every committed entry. Uncommitted entries (like entry 5) may be lost, which is fine, because no client was ever told they succeeded.

The second half of safety: a leader only counts replicas for its own term

The election restriction alone is not quite enough. There is one more rule, and it is the most-missed detail in Raft interviews:

A leader only marks an entry committed by counting replicas if that entry is from the leader's current term. Older entries become committed indirectly, when a newer current-term entry after them is committed.

Why: an entry from an old term can sit on a majority of nodes and still be overwritten.

5 nodes. Index 2 is the interesting slot.

term 2: S1 leads, writes [2:t2] to S1, S2 only. Crashes.
term 3: S5 wins (votes from S3, S4, S5 — their logs are no worse), writes [2:t3]
        to S5 only. Crashes.
term 4: S1 wins again, re-replicates its old [2:t2] to S3.
        Now [2:t2] is on S1, S2, S3 — a MAJORITY.
        If S1 declared it committed now and then crashed...
term 5: S5 can still win: its last entry has term 3 > term 2 on S2, S3, S4,
        so they vote for it. S5 overwrites index 2 with [2:t3] everywhere.
        An entry that was "on a majority" is gone. ✗

With the rule, S1 in term 4 does not declare [2:t2] committed when it reaches a majority. It first appends a term-4 entry at index 3 and replicates that to a majority. Once [3:t4] is on a majority, S5 (last term 3) can no longer win, and index 2 is committed along with it. This is why a new Raft leader immediately appends a no-op entry for its own term: it is how the leader gets earlier entries committed quickly.

Part 5: Log Divergence — Healing After a Bad Leader

Network partitions and leader failures can leave followers with logs that diverge from what the new leader has. A follower might have extra entries that the old leader sent but never committed (they were lost when the leader crashed). Raft must heal this divergence.

The rule: the leader's log is always correct. Followers must match the leader. If a follower has extra uncommitted entries, they are overwritten. The leader never overwrites its own log — only followers do.

How the leader detects divergence: the prevLogIndex and prevLogTerm fields in AppendEntries. The follower checks: "does my log at prevLogIndex have the entry with prevLogTerm?" If not, it rejects the RPC.

When the leader receives a rejection, it decrements its nextIndex for that follower (its estimate of where their logs start to diverge) and retries with an earlier prevLogIndex. It keeps going back until it finds the point where the logs match, then sends all entries from that point forward.

After a messy leader transition:

Leader (Node B): [1:t1][2:t1][3:t2][4:t2][5:t3][6:t3]  ← correct log
Follower E:      [1:t1][2:t1][3:t2][7:t1][8:t1]         ← diverged

(E has entries 7, 8 from an old, unreachable leader in a prior term)

Healing:
B sends AppendEntries(prevLogIndex=5, prevLogTerm=t3, entries=[6:t3])
E checks: does my log[5] have term t3? No — E only has 4 entries that match B.
E rejects.

B decrements nextIndex for E to 5:
B sends AppendEntries(prevLogIndex=4, prevLogTerm=t2, entries=[5:t3, 6:t3])
E checks: does my log[4] have term t2? Yes! ✓
E accepts: deletes everything after index 4 (entries 7, 8 gone), appends 5 and 6.

Follower E after healing: [1:t1][2:t1][3:t2][4:t2][5:t3][6:t3] ✓

The divergent entries 7 and 8 are simply overwritten. They were never committed (if they had been committed, the election restriction would have prevented a leader without them from winning), so deleting them is safe. No client was ever told these writes succeeded.

This healing mechanism is why Raft is self-correcting: a cluster that experienced a messy period of network partitions and leader churn will automatically converge to a consistent state once a stable leader emerges and the network heals.

Part 6: Handling the "I'm the Leader but Am I Really?" Problem

One subtle safety issue: a leader that gets partitioned away from the cluster might not know it's been replaced. It's still running, still accepting client writes, still appending to its log — but it can't replicate to anyone because it's partitioned. Meanwhile, the rest of the cluster elects a new leader. Now there are two nodes that believe they are leader.

Is this a problem? Let's trace it:

5-node cluster partitioned:

Partition A: [Node 1 (old leader)] — isolated
Partition B: [Node 2, 3, 4, 5] — quorum, elects Node 2 as new leader

Client writes to old leader (Node 1):
  Node 1 appends to its log.
  Node 1 tries to replicate to {2, 3, 4, 5} — network partitioned, all fail.
  Node 1 never achieves quorum.
  Node 1 NEVER commits the entry.
  Node 1's write eventually times out. Client gets an error.

Client writes to new leader (Node 2):
  Node 2 replicates to {3, 4, 5} — achieves quorum.
  Node 2 commits. Client gets success.

Partition heals:
  Node 1 receives heartbeat from Node 2 with higher term.
  Node 1 recognises Node 2 as the real leader and steps down.
  Node 1's uncommitted entry is overwritten by Node 2's entries.

The old partitioned leader cannot commit anything — it cannot reach quorum. So no client receives a false success from it. The quorum requirement is what makes this safe: a leader without quorum can't commit, and if it can't commit, it can't corrupt the system.

The only client-visible effect: writes to the old leader time out and return errors. The client must retry against the new leader. This is an availability degradation (errors during the partition) but not a correctness violation (no committed writes are lost).

Now run the two-leader scenario yourself. The old leader keeps accepting writes it can never commit — watch what happens to them when the partition heals.

Part 7: Log Compaction — Snapshots

A replicated log that only grows forever would require infinite disk space. After months of operation, the log of a heavily-used etcd cluster could be tens of gigabytes. Recovery from a snapshot is also much faster than replaying thousands of log entries. Raft solves this with snapshots.

Each node independently takes periodic snapshots of its state machine state. A snapshot captures the complete state at a specific log index — the full key-value store state, for example, at log entry 10,000. Everything before that index can then be discarded from the log.

Before snapshot at index 10000:

Log: [1:set x=1][2:set y=2]...[9999:del z][10000:set x=99]
State at index 10000: {x=99, y=12, ...complete key-value state...}

After snapshot:

Snapshot file: {lastIncludedIndex: 10000, lastIncludedTerm: 7, state: {x=99, y=12, ...}}
Log: [10001:...][10002:...][10003:...]  ← entries before 10000 discarded

When a new node joins the cluster (or a very lagging node needs to catch up), the leader sends the snapshot directly rather than replaying the entire log. The follower installs the snapshot (replacing its state machine state entirely with the snapshot's state) and then receives only the log entries after the snapshot's lastIncludedIndex.

The InstallSnapshot RPC is Raft's mechanism for this. It's less frequently used than AppendEntries — only when a follower is so far behind that the log entries it needs have already been compacted away.

Slow follower (F) joining after long absence:

Leader has: snapshot at index 10000, log entries [10001..10200]
F has: nothing (new node) or log entries [1..500] (very stale)

Leader sends: InstallSnapshot(snapshot at index 10000)
F installs: discards its log, applies snapshot state directly
F's state: {x=99, y=12, ...} at index 10000

Leader then sends: AppendEntries with [10001..10200]
F becomes current.

Part 8: Cluster Membership Changes — Adding and Removing Nodes

Adding or removing nodes from a live Raft cluster is one of the trickiest operations because during the transition, the cluster must not have two independent quorums that can each make decisions — the split-quorum problem.

The naive approach (just update the configuration and restart) creates a window where some nodes use the old config (old quorum definition) and others use the new config (new quorum definition). If the old quorum and new quorum can make independent decisions, you have two separate consensus groups — split-brain.

Raft uses joint consensus for safe membership changes. The cluster first transitions to a joint configuration that requires quorums from both the old and new membership simultaneously. Then it transitions to the new configuration alone.

Old config: {A, B, C} — quorum needs 2
New config: {A, B, C, D, E} — quorum needs 3

Joint config: {A,B,C} ∪ {A,B,C,D,E} — quorum needs 2 from old AND 3 from new

During joint config, a decision requires:
  - Majority of {A,B,C}: at least 2 of {A,B,C}
  - AND majority of {A,B,C,D,E}: at least 3 of {A,B,C,D,E}

This prevents old or new config alone from making independent decisions.
Once joint config is committed, transition to new config alone.

A simpler alternative (used in production by etcd and Consul) is single-server membership change: add or remove exactly one server at a time. The mathematical key: adding or removing one server at a time preserves the property that the old and new quorums always overlap. You can never create disjoint majorities by changing membership one node at a time.

One-at-a-time safety:

Old: {A,B,C} — quorum=2. Old quorum can be {A,B}.
Add D: {A,B,C,D} — quorum=3. New quorum can be {A,B,C}. 
Old quorum {A,B} ∩ new quorum {A,B,C} = {A,B} ← overlap guaranteed.

Add E: {A,B,C,D,E} — quorum=3. Any old quorum {A,B,C,D} still overlaps any new quorum.
Remove A: {B,C,D,E} — quorum=3. Overlap with previous config preserved.

etcd's production recommendation: change membership one node at a time. This is what most operators do in practice.

Part 9: Read-Only Queries — A Subtle Safety Trap

Reads seem simple — just return the current state machine value. But there's a trap.

Suppose Node A is the leader with a fully up-to-date log. A client asks for key X. Node A reads from its state machine and returns the value. Safe? Not necessarily — Node A might be a partitioned old leader that doesn't know it's been replaced. The new leader might have committed a more recent write to X. Node A's value is stale. The client received a linearizability violation: it's reading data that is no longer current.

Raft prevents this with read index confirmation. Before serving a read, the leader:

1. Records the current commit index.
2. Sends a round of heartbeats to a quorum of followers.
3. If quorum responds — confirming the leader is still active and hasn't been replaced — serves the read.

This ensures the leader is confirmed current before responding. No stale reads.

An optimisation: leases. If the leader knows its heartbeat interval is T ms and election timeout is always greater than T ms, then after receiving a quorum heartbeat acknowledgement at time t, the leader knows it is the recognised leader until at least time t + (election_timeout - clock_drift). Within this "lease" window, it can serve reads without another quorum round trip. This trades the certainty of round-trip confirmation for the speed of a local RAM read, with bounded clock-skew risk.

etcd implements both options: Linearizable reads do the quorum round trip. Serializable reads serve from local state (faster but potentially stale by a heartbeat interval).

Part 10: Raft in Production — etcd, CockroachDB, Consul

etcd

etcd is the consensus backbone of Kubernetes — every Pod definition, Service, ConfigMap, Secret, and cluster state is stored in etcd. All Kubernetes API server writes go through etcd's Raft consensus before being acknowledged. etcd uses a pure Go implementation of Raft, with a storage backend called bbolt (a B-Tree key-value store, not LSM — etcd's write rate is low enough that B-Tree is fine).

etcd's operational concerns: cluster size should be 3 or 5 (not more — Raft consensus latency increases with cluster size as you need more nodes to acknowledge). etcd is not designed for high throughput: 10,000 writes/second is near the upper limit for a well-tuned cluster. If Kubernetes generates more write traffic than that, etcd becomes the bottleneck. Kubernetes operators sometimes separate etcd clusters for different API groups to spread load.

etcd exposes a watch API: clients can watch a key prefix and receive a notification when any key under that prefix changes. This is implemented by having the Raft log act as a change event stream — the client watches the log for entries matching its prefix. This is how Kubernetes controllers work: the Deployment controller watches for changes to Deployment objects and reacts.

CockroachDB

CockroachDB (CRDB) is a distributed SQL database that uses Raft for data replication. Unlike etcd (which runs one Raft group for the whole cluster), CRDB runs thousands of Raft groups simultaneously — one per range (the CRDB equivalent of a shard). Each range is a 64 MB chunk of key space. A 1 TB database has roughly 16,000 ranges, each with its own leader, its own log, and its own election process.

This multi-group Raft approach (sometimes called Multi-Raft) allows CRDB to scale horizontally while maintaining strong consistency: each range independently achieves consensus, so adding nodes increases the number of parallel Raft groups that can be active simultaneously. A 3-node CRDB cluster can run 16,000 concurrent Raft groups, each making progress independently.

The coordination challenge: 16,000 Raft leaders all sending heartbeats to their followers creates significant network traffic. CRDB optimises this by coalescing heartbeats — a single heartbeat message covers many Raft groups between the same two nodes.

Consul

Consul uses Raft for its service discovery and key-value store backend. Every registered service, health check, and configuration value goes through Raft consensus. Consul's Raft implementation is the hashicorp/raft library — a standalone Go Raft implementation also used by Nomad and Vault.

One distinctive Consul design: prevoting. Before starting a real election (incrementing the term and requesting votes), a candidate first sends a "PreVote" request. Other nodes respond to indicate whether they would grant a real vote. Only if the pre-vote succeeds does the candidate start a real election. This prevents a partitioned node from disrupting the cluster when it reconnects: it might have a very high term from repeated failed elections while isolated, and sending that high term would force all cluster nodes to step down unnecessarily. Pre-voting lets the cluster check "would you elect this node?" without committing to the disruption.

TiKV

TiKV is the distributed key-value layer of TiDB (a distributed SQL database from PingCAP). Like CRDB, TiKV uses Multi-Raft — one Raft group per region (TiKV's name for range). TiKV is implemented in Rust on top of RocksDB (Chapter 10's LSM engine). This combination — Raft for consensus, RocksDB for local storage — is the production pattern for high-performance distributed databases: Raft handles replication correctness, RocksDB handles write-optimised local storage.

Part 11: What Raft Does Not Solve

Raft guarantees that all nodes agree on the same log. It does not guarantee anything about the performance of that agreement or the overall system's availability beyond its own scope.

Raft does not prevent slow followers from becoming election problems. A follower that is very slow (slow disk, GC pause) may not respond to heartbeats in time, triggering a false election. The mitigation: tune election timeouts to be much larger than normal heartbeat round trips.

Raft does not handle Byzantine failures. Byzantine fault tolerance (BFT) covers nodes that actively lie, send conflicting messages, or behave arbitrarily — as opposed to crash failures (nodes simply stop). Raft assumes nodes either follow the protocol or crash. Blockchain consensus (PBFT, Tendermint, Casper) is designed for Byzantine faults. For a database cluster inside a trusted network, Byzantine faults are not relevant — a machine follows Raft or it crashes, it doesn't fabricate messages.

Raft does not give you linearizable reads for free. As Part 9 showed, serving reads from the leader requires quorum confirmation. Serving reads from followers is always potentially stale. Many Raft implementations (including early etcd versions) had linearizability bugs in their read path.

Raft does not solve distributed transactions. A single Raft group agrees on a log. Cross-shard transactions across multiple Raft groups still require a distributed transaction protocol — two-phase commit, Percolator, or similar. CockroachDB implements Raft for per-range replication and a separate distributed transaction protocol (based on Percolator) for cross-range atomicity. Chapter 13 covers this.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

A 5-node Raft cluster (A=leader, B, C, D, E) has committed entries through index 20. The log state is:

A: [1..20] committed, [21, 22] uncommitted (just appended, not yet replicated)
B: [1..20] committed
C: [1..20] committed  
D: [1..18] committed, [19, 20] in log but not yet acknowledged as committed
E: [1..15] committed

Node A crashes. An election begins. Trace which nodes can win the election and why. For each possible winner, describe what happens to entries 19–22 on each follower after the new leader takes over. Is it possible for entries 21 and 22 to survive? What must have been true about them before A crashed for them to survive? If entry 20 was committed, can a new leader be elected that doesn't have entry 20? Prove your answer using the quorum intersection argument.

Problem 2 — Design from Scratch

Design a distributed configuration management service using Raft. Requirements: stores key-value configuration for 500 microservices, each service watches its own configuration key for changes, configuration values change infrequently (average 10 writes/minute across all services), but 500 services are reading their configs every 30 seconds (about 17 reads/second).

Specify: cluster size and node placement (same region vs multi-region), read path (linearizable round-trip vs lease-based vs follower reads — which is appropriate given the read-to-write ratio?), how watches are implemented on top of the Raft log, how you handle the case where a service's config watcher misses an update (e.g., if the service was disconnected), and how you take configuration snapshots to bound recovery time. What is the maximum recovery time after a full cluster restart if the log has 10 million entries? After snapshotting?

Problem 3 — Synthesis

Connect Raft's safety properties to Chapter 6's consistency models and Chapter 5's replication lag.

A Raft cluster (leader + 2 followers) serves a banking application. The leader commits a write: "transfer $100 from account A to account B." A client immediately reads account B's balance from the leader using lease-based reads (no quorum round trip). The leader's lease was granted 200 ms ago, the lease duration is 500 ms, so it's still valid.

First: does this read satisfy linearizability? Justify using Chapter 6's definition — a linearizable read must return a value consistent with some total order where each read returns the value of the most recent preceding write. Second: what is the maximum clock skew between nodes that would make lease-based reads unsafe? Third: the banking application uses a read replica (follower) for balance queries to reduce leader load. A user transfers money, then immediately checks their balance via a different API call routed to the follower. What consistency model is the follower providing? Trace the specific failure: the transfer was committed on the leader 50 ms ago, follower apply lag is 80 ms. Connect this directly to Chapter 5's replay lag and Chapter 6's eventual consistency definition.

Problem 4 — Go Deeper

Raft's election restriction uses log comparison (last log term, then log length) to determine "more up-to-date." This comparison has an edge case: what if two nodes have exactly the same lastLogTerm and lastLogIndex?

First: is this possible in a healthy cluster? Under what conditions does it arise? Second: if it arises, both nodes will grant votes to each other (symmetric up-to-dateness). Draw a scenario with N=5 where this creates a split vote across multiple terms. How many terms can pass before the symmetry is broken? Third: Raft's randomised election timeout is supposed to break symmetry — but if two nodes have exactly the same log state and both time out at exactly the same time (possible with identical hardware and OS schedulers), what prevents an infinite split-vote loop? Is this a theoretical concern or a practical one? How do production Raft implementations (etcd, Consul) handle it? Fourth: if you were to change the election restriction to allow a node to grant votes to candidates with a slightly less up-to-date log (within some delta), what safety property would you be weakening and what specific failure scenario would you be enabling?

Problem 5 — Connect to Previous Chapters

This problem integrates Raft with the entire storage stack built across Chapters 1–12.

CockroachDB stores data in RocksDB (Chapter 10's LSM engine) on each node. Each 64 MB range of key space has its own Raft group. When a client writes a row:

1. The SQL layer translates the write to a key-value operation.
2. The key is routed to the correct range's Raft leader (Chapter 8's consistent hashing determines range, not node).
3. The Raft leader appends the operation to its Raft log.
4. The Raft log entry is replicated to 2 followers via AppendEntries.
5. On commit (quorum ack), the entry is applied to the RocksDB state machine on each node.

Trace the full I/O path for a single committed write: how many times is the data written to disk across the leader and two followers, counting WAL writes (both Raft's WAL and RocksDB's WAL from Chapter 2) and SSTable flushes (Chapter 10)? What is the minimum latency for a committed write given: intra-datacenter network round trip = 0.5 ms, RocksDB WAL sequential write = 0.1 ms, memtable write = 0.01 ms? How does pipelining (sending the next write before the first is committed) change the throughput vs latency trade-off for this full stack? At what pipeline depth does disk I/O become the bottleneck rather than network latency?

What's Coming Next

You now have a complete picture of how single-shard consensus works: Raft elects a leader, replicates a log, commits with quorum, and heals divergence after failures. But the banking problem from Problem 3 hinted at an unsolved issue: what happens when a transaction spans multiple Raft groups — multiple shards? Transferring money from account A (shard 1) to account B (shard 7) requires atomically debiting one and crediting the other. If the debit commits but the credit fails (the shard 7 Raft group is partitioned), the money disappears. This is the distributed transaction problem — and it's the hardest problem in Chapter 13.

Chapter 12 complete. Problem 1 (failure trace on specific log states) and Problem 5 (full I/O path through the stack) are the most technically demanding — work them with pencil and paper, not just in your head. The log state trace in Problem 1 is exactly the scenario interviewers draw on a whiteboard for senior distributed systems roles. Problem 5 is the synthesis question that confirms you understand how all the layers interact — from network packets to memtable writes to Raft quorums to client responses. If you can trace that path confidently, you can design any storage system.