Consensus & Replication

Chapter 1: State Machine Replication

Before we dive into the mechanics of consensus, we need to understand the fundamental idea that makes consensus useful. The idea is old — Leslie Lamport described it in 1978 — and it is beautifully simple: if you have a deterministic state machine (a program that always produces the same output for the same input), and you feed it the same sequence of inputs, it will always end up in the same state.

This is State Machine Replication (SMR): run the same deterministic program on multiple servers, feed them the exact same commands in the exact same order, and they will all have the exact same data. The problem reduces to one thing: agreeing on the order of commands.

What Makes a State Machine Deterministic?

A deterministic state machine is one where the next state depends only on the current state and the input. No randomness, no reading the system clock, no consulting external services. Given state S and command C, the next state S' is always the same.

Examples of deterministic state machines:

The critical non-example: a state machine that reads System.currentTimeMillis(). Two replicas processing the same command at slightly different real-time moments will get different timestamps, and their states will diverge. If you need timestamps, the leader assigns them before replicating the command.

Taming Non-Determinism

Real applications contain many sources of non-determinism. The SMR approach must eliminate all of them. Here is how production systems handle each one:

The Two-Part Architecture

Every replicated system built on SMR has two cleanly separated layers:

The beauty of this separation: the consensus layer knows nothing about keys or values — it just orders opaque byte strings. The state machine knows nothing about nodes or elections — it just processes commands in order. You can swap out either layer independently.

Why Total Order Matters

Consider two commands arriving nearly simultaneously: "SET x = 10" and "SET x = 20". If replica A processes them in order (10, then 20), it ends with x = 20. If replica B processes them in the opposite order (20, then 10), it ends with x = 10. The replicas have diverged — and they will never converge unless you fix the ordering.

Total order broadcast (also called atomic broadcast) is the guarantee that all nodes deliver the same messages in the same order. It is equivalent to consensus — if you can solve one, you can solve the other. This equivalence was proven by Chandra and Toueg in 1996.

Code: A Minimal Replicated State Machine

python
class KVStateMachine:
    """A deterministic key-value store state machine."""
    def __init__(self):
        self.store = {}        # The actual state: key -> value
        self.last_applied = 0  # Index of last applied log entry

    def apply(self, entry):
        """Apply a single log entry. MUST be deterministic."""
        cmd = entry["command"]
        if cmd == "SET":
            self.store[entry["key"]] = entry["value"]
            return "OK"
        elif cmd == "GET":
            return self.store.get(entry["key"], None)
        elif cmd == "DELETE":
            self.store.pop(entry["key"], None)
            return "OK"

    def apply_log(self, log, commit_index):
        """Apply all committed but unapplied entries."""
        while self.last_applied < commit_index:
            self.last_applied += 1
            result = self.apply(log[self.last_applied])
        return result  # Return result of last applied entry

# Three replicas, same log, same state:
log = [
    None,  # Index 0 is unused (Raft logs are 1-indexed)
    {"command": "SET", "key": "x", "value": 10},
    {"command": "SET", "key": "y", "value": 20},
    {"command": "SET", "key": "x", "value": 30},
]

r1, r2, r3 = KVStateMachine(), KVStateMachine(), KVStateMachine()
for r in [r1, r2, r3]:
    r.apply_log(log, commit_index=3)

assert r1.store == r2.store == r3.store  # Always true!
# All replicas: {"x": 30, "y": 20}

This is the entire idea. The hard part is not the state machine — it is getting all replicas to agree on the same log. That is what Raft does, and it is the subject of the next two chapters.

Raft in Three RPCs

Raft is remarkably compact. The entire protocol consists of just three remote procedure calls (RPCs):

That is the entire Raft protocol. Three messages. Everything else — leader election, log replication, commit tracking, log repair, snapshot transfer — is built from combinations of these three RPCs. This simplicity is Raft's greatest engineering achievement.

Data Flow: What Moves Over the Wire

To implement SMR, you need to understand exactly what data moves where. Here is the concrete data flow for a write operation in a Raft-based key-value store:

Total network traffic for one write in a 5-node cluster: ~50 bytes (client request) + 4 x ~300 bytes (AppendEntries to 4 followers) + 4 x ~20 bytes (responses) + ~10 bytes (client response) = approximately 1.3 KB. For 10,000 writes/sec, that is ~13 MB/s of consensus traffic — well within the capacity of a 1 Gbps network link. Consensus is not network-limited; it is latency-limited (waiting for fsync and round trips).

Chapter 2: Leader Election

We established that replicated state machines need a total-ordered log. In Raft, one node is responsible for ordering the log: the leader. Every other node is a follower. The leader receives all client requests, appends them to its log, and replicates them to followers. But what happens when the leader crashes?

The followers must detect the failure and elect a new leader. This is leader election — the first of two core mechanisms in Raft (the second is log replication, covered next chapter). The election protocol must guarantee one critical property: at most one leader per term.

Terms: Raft's Logical Clock

Raft divides time into terms, numbered consecutively starting from 1. Each term begins with an election. If the election succeeds, the winner serves as leader for the rest of that term. If the election fails (no candidate gets a majority — a split vote), the term ends with no leader, and a new term begins immediately.

Terms serve as a logical clock. Every message in Raft carries the sender's current term. If a node receives a message with a higher term than its own, it immediately updates its term and becomes a follower. If a node receives a message with an older term, it rejects it. This mechanism ensures that stale leaders discover they have been replaced.

The Three States

Every Raft node is always in exactly one of three states:

The Election Protocol, Step by Step

Here is exactly what happens when a follower decides to start an election:

Voting Rules

When a node receives a RequestVote, it applies two rules:

Rule 1: One vote per term. Each node can vote for at most one candidate in any given term. Votes are persistent (written to stable storage before responding). This ensures that at most one candidate can receive a majority in any term.

Rule 2: Log up-to-date check. A node refuses to vote for a candidate whose log is less "up-to-date" than its own. Raft defines "up-to-date" as: higher last-log term wins; if terms are equal, longer log wins. This critical check ensures that the leader always has all committed entries. We will see why in the next chapter.

Persistent State: What Survives a Crash

Three pieces of state in Raft must be written to stable storage (disk) before responding to any RPC. If a node crashes and restarts, it recovers these from disk:

Everything else — commit index, last applied index, next/match index arrays — can be reconstructed from the persistent state and communication with the cluster. This is why Raft implementations use a Write-Ahead Log (WAL): before accepting any RPC, the node fsync's the relevant state changes to its WAL. Only after the fsync completes does it respond.

Split Votes and Randomized Timeouts

What if two followers time out simultaneously and both start elections? They each vote for themselves and send RequestVote to the other three nodes. If the votes split evenly (each candidate gets 2 votes including their own, but neither reaches the majority of 3), neither wins. The term ends with no leader.

Raft handles this with randomized election timeouts. Each node picks a random timeout between 150ms and 300ms. Because the timeouts differ, it is unlikely that two nodes will start elections at the same instant. In practice, split votes are rare — they occur in about 5-10% of elections in a healthy cluster, and almost never recur twice in a row.

The timeout range matters. The Raft paper recommends that the election timeout be at least 10x the network round-trip time. If your network RTT is 1ms (same data center), an election timeout of 150-300ms is appropriate. If your RTT is 50ms (cross-region), you need 500ms-1000ms election timeouts. The heartbeat interval should be much smaller than the election timeout — typically 100ms for same-DC deployments.

Pre-Vote: Preventing Disruptive Rejoiners

Raft has an optional extension called Pre-Vote that solves a subtle problem. Imagine a node that gets partitioned from the cluster. Its election timeout fires repeatedly, and it increments its term each time — from 5 to 6, 7, 8, 50, 100... When the partition heals, it reconnects with a very high term. Every other node sees this high term and immediately steps down to follower, disrupting the cluster even though the rejoining node has a stale log and cannot win the election.

Pre-Vote adds a preliminary round: before incrementing its term, a candidate sends a "pre-vote" request. Other nodes check if they would vote for this candidate, but without actually recording a vote or changing their term. Only if the candidate gets a pre-vote majority does it proceed to a real election. A partitioned node will fail the pre-vote (its log is stale), so it never disrupts the cluster.

Election Correctness: Why At Most One Leader

The proof is elegant. Suppose two candidates, A and B, both claim to win election in term T. Each must have received votes from a majority of the N nodes. But any two majorities overlap (they share at least one node). That shared node voted for both A and B in the same term T. But Rule 1 says a node can vote for at most one candidate per term. Contradiction. Therefore, at most one candidate can win per term.

Chapter 3: Log Replication

The leader has been elected. Now it must do its job: accept commands from clients, append them to its log, replicate the log to followers, and tell followers when entries are safe to apply. This is log replication — the second core mechanism in Raft, and the one that actually moves data.

Anatomy of a Log Entry

Each entry in the Raft log has three fields:

The combination of (index, term) uniquely identifies a log entry across the entire cluster. Two entries with the same index and term are guaranteed to contain the same command. This is the Log Matching Property.

AppendEntries: The Replication RPC

The leader sends AppendEntries RPCs to each follower. This is the workhorse of Raft — it handles both replication and heartbeats (an AppendEntries with no new entries is a heartbeat). Here is what the message contains:

The Consistency Check

When a follower receives AppendEntries, it checks: "Do I have an entry at prevLogIndex with term prevLogTerm?" If yes, the follower's log is consistent with the leader's up to that point, and it can safely append the new entries. If no, the follower rejects the request.

When the leader gets a rejection, it decrements prevLogIndex and retries. It keeps backing up until it finds a point where the logs agree, then it overwrites the follower's log from that point forward. This is how Raft repairs inconsistent logs after crashes and leader changes.

Commit Index: When Is It Safe to Apply?

An entry is committed once the leader has replicated it to a majority of nodes. The leader tracks a commit index — the highest log index known to be committed. It advances the commit index each time a new majority is reached, and piggybacks the commit index on every AppendEntries message. Followers apply committed entries to their state machines.

There is a subtle safety rule: a leader can only commit entries from its own term. It cannot commit entries from previous terms by counting replicas alone. Why? Because an entry from a previous term might have been replicated to a majority, but that majority might not overlap with the majority that elected the current leader. The current leader commits previous-term entries indirectly, by committing a new entry from its current term (which then implicitly commits all preceding entries).

Step-by-Step: A Replication Round

Code: AppendEntries Handler

python
def handle_append_entries(self, leader_term, prev_idx, prev_term,
                           entries, leader_commit):
    # Rule: reject if leader's term is stale
    if leader_term < self.current_term:
        return False, self.current_term

    # Become follower if leader's term is newer
    if leader_term > self.current_term:
        self.current_term = leader_term
        self.state = "follower"
        self.voted_for = None

    # Reset election timer (leader is alive)
    self.reset_election_timer()

    # Consistency check: do I have the expected entry?
    if prev_idx > 0:
        if prev_idx >= len(self.log):
            return False, self.current_term  # My log is too short
        if self.log[prev_idx].term != prev_term:
            return False, self.current_term  # Term mismatch

    # Append new entries (overwrite conflicts)
    idx = prev_idx + 1
    for entry in entries:
        if idx < len(self.log):
            if self.log[idx].term != entry.term:
                self.log = self.log[:idx]  # Truncate conflicting tail
                self.log.append(entry)
            # else: already have this entry, skip
        else:
            self.log.append(entry)
        idx += 1

    # Update commit index
    if leader_commit > self.commit_index:
        self.commit_index = min(leader_commit, len(self.log) - 1)

    return True, self.current_term

Worked Example: Log Repair After a Crash

Let us trace through a concrete scenario. We have a 3-node cluster (Leader, F1, F2). The leader has committed entries 1-3. Then the leader crashes, F1 becomes the new leader, and adds entry 4. Meanwhile, F2 was down and missed entry 3. Here is the state:

F1 sends AppendEntries to F2 with prevLogIndex=3, prevLogTerm=1, entries=[entry 4]. F2 checks: "Do I have an entry at index 3?" No — F2's log only has entries 1-2. F2 rejects.

F1 backs up: sends AppendEntries with prevLogIndex=2, prevLogTerm=1, entries=[entry 3, entry 4]. F2 checks: "Do I have entry at index 2 with term 1?" Yes! F2 accepts, appends entries 3 and 4. Now F2's log matches F1's log. The repair is complete.

Snapshots: When the Log Gets Too Long

The log grows forever — every command ever executed is stored. Eventually it will consume all available disk space. The solution is snapshotting: periodically, a node serializes its current state machine state to disk, then discards all log entries up to the snapshot point. If a lagging follower needs entries that have been discarded, the leader sends the snapshot instead of individual entries via an InstallSnapshot RPC.

python
class RaftNodeWithSnapshots:
    def __init__(self):
        self.log = [None]    # 1-indexed
        self.snapshot = None  # Serialized state machine state
        self.snapshot_index = 0  # Last index included in snapshot
        self.snapshot_term = 0   # Term of last snapshot entry
        self.state_machine = KVStateMachine()

    def take_snapshot(self):
        """Compact the log by snapshotting current state."""
        self.snapshot = self.state_machine.serialize()
        self.snapshot_index = self.state_machine.last_applied
        self.snapshot_term = self.log[self.snapshot_index].term
        # Discard log entries up to snapshot
        self.log = [None] + self.log[self.snapshot_index + 1:]
        # Log now starts at snapshot_index + 1

    def handle_install_snapshot(self, leader_term, snapshot_data,
                                 last_included_index, last_included_term):
        """Follower receives a snapshot from the leader."""
        if leader_term < self.current_term:
            return False
        # Replace state machine with snapshot
        self.state_machine = KVStateMachine.deserialize(snapshot_data)
        self.snapshot = snapshot_data
        self.snapshot_index = last_included_index
        self.snapshot_term = last_included_term
        # Discard entire log (snapshot is more recent)
        self.log = [None]
        self.state_machine.last_applied = last_included_index
        return True

Chapter 4: Consistency Models

We have been talking about "replicas agreeing" — but what exactly does "agree" mean from a client's perspective? If I write a value and then immediately read it, will I see my own write? If someone else reads it a millisecond later, will they see it too? The answers depend on the consistency model the system provides.

A consistency model is a contract between the distributed system and its clients. It defines which read results are "legal" given the writes that have occurred. Stronger models are easier for programmers to reason about but more expensive to implement. Weaker models allow more flexibility (and higher performance) but force programmers to handle strange behaviors.

The Hierarchy

There are four main consistency models you need to know, ordered from strongest to weakest:

Linearizability: The Gold Standard

Linearizability means the system behaves as if there is a single copy of the data, and every operation is atomic. Formally: you can assign a "linearization point" to each operation (a single instant between invocation and response) such that the results are consistent with a sequential execution in that order.

The practical consequence: once a write completes and the client gets an acknowledgment, ALL subsequent reads (by ANY client, on ANY node) must see that write or a later one. You can never go back to seeing a stale value.

Sequential Consistency: Same Order, But Maybe Not Real Time

Sequential consistency is weaker than linearizability in one key way: it does not require the global order to match real time. If client A writes x=1, and later (in wall-clock time) client B writes x=2, a sequentially consistent system could order B's write before A's — as long as all nodes see the same order, and each individual client's operations appear in the order submitted.

Causal Consistency: Respecting "Happened Before"

Causal consistency only orders operations that are causally related. If I post a message and you reply to it, everyone must see my message before your reply (causal relationship). But if two users independently post messages with no causal link, different nodes can show them in different orders.

Causal consistency is attractive because it is the strongest consistency model that does not require consensus for every operation. You can implement it with vector clocks and dependency tracking, without a single leader. This makes it much faster than linearizability in geo-distributed systems.

Eventual Consistency: The Bare Minimum

Eventual consistency says: if you stop writing, all replicas will eventually converge to the same value. That is the entire guarantee. While writes are ongoing, different clients can see different values. Reads can go backward. Two clients reading at the same time can get different results. It is the wild west — but it is fast and available.

Worked Example: Same Operations, Four Models

Let us trace through a concrete scenario. Client A writes x=1 at time T=0, gets ACK at T=5. Client B reads x at T=6. What are the legal read results under each model?

Now change the scenario: Client A writes x=1, gets ACK, then tells Client B "I just wrote x=1, please read it." This creates a causal dependency. Under causal consistency, B must now see x=1 (because B's read causally depends on A's write via the out-of-band communication). Under eventual consistency, B can still see x=0.

When to Use What

Code: Testing Linearizability

python
from dataclasses import dataclass
from itertools import permutations

@dataclass
class Op:
    client: str
    op_type: str     # "write" or "read"
    value: int       # value written or read
    start: float     # invocation time
    end: float       # response time

def is_linearizable(ops):
    """Brute-force linearizability check (NP-hard in general)."""
    # Try every possible ordering of operations
    for perm in permutations(ops):
        if _valid_sequential(perm) and _respects_realtime(perm):
            return True
    return False

def _valid_sequential(perm):
    """Check if this ordering produces valid read results."""
    register = None
    for op in perm:
        if op.op_type == "write":
            register = op.value
        elif op.op_type == "read":
            if op.value != register:
                return False  # Read got wrong value
    return True

def _respects_realtime(perm):
    """Check that ordering preserves real-time precedence."""
    for i in range(len(perm)):
        for j in range(i + 1, len(perm)):
            # If perm[j] ended before perm[i] started in real time,
            # then perm[j] must come before perm[i] in the ordering.
            if perm[j].end < perm[i].start:
                return False
    return True

# Example: is this linearizable?
history = [
    Op("A", "write", 1, 0.0, 0.5),
    Op("B", "read",  1, 0.3, 0.8),
    Op("A", "write", 2, 0.6, 1.0),
    Op("B", "read",  2, 0.9, 1.3),
]
print(is_linearizable(history))  # True: order W(1), R(1), W(2), R(2) works

Chapter 5: Chain Replication

Raft is not the only way to build a replicated system with strong consistency. There is an alternative that is conceptually simpler, has better throughput under certain workloads, and is used in production at Microsoft (Azure Storage) and Amazon (EBS, S3 internal components). It is called chain replication.

The core idea: instead of a leader broadcasting to all followers in parallel (Raft's approach), arrange the replicas in a chain. Writes enter at the head and flow through each node in sequence until they reach the tail. Reads are served exclusively from the tail. When the tail has a write, every node before it also has that write — so the tail always has the most committed state.

How It Works

Chain Replication vs Raft

Failure Handling

When a node in the chain fails, the chain must be repaired:

The critical point: chain replication does not handle reconfiguration itself. It relies on an external configuration manager — typically a Raft or Paxos-based system like ZooKeeper — to detect failures, decide the new chain membership, and notify all nodes. This is why chain replication and Raft are complementary, not competing: you use Raft for the small, critical metadata service, and chain replication for the large, high-throughput data path.

CRAQ: Chain Replication with Apportioned Queries

CRAQ (2009, Jeff Terrace and Michael Freedman at Princeton) extends chain replication to allow reads from any node, not just the tail. Each node stores two versions of each object: "clean" (committed) and "dirty" (received but not yet confirmed by the tail). When a non-tail node receives a read and has only a clean version, it serves it directly. If it has a dirty version, it asks the tail for the latest committed version number and serves accordingly.

CRAQ dramatically improves read throughput because reads are distributed across all N nodes instead of concentrated at the tail. The consistency guarantee remains linearizable.

Throughput Analysis: Why Chain Replication Wins for Large Objects

Consider a cluster of 5 nodes, each with 1 Gbps network bandwidth. A client writes 1 MB objects.

The key insight: Raft's leader is a bandwidth bottleneck because it sends every entry to every follower. The leader's outbound bandwidth scales as O(N) where N is the cluster size. Chain replication's head sends each entry to only one successor — O(1) outbound per node. For large objects (like the 256 KB extent blocks in Azure Storage), this difference is enormous.

Real-World Chain Replication: Azure Storage

Microsoft Azure Storage uses a variant of chain replication called extent-based replication for its blob, table, and queue services. Each storage extent (a contiguous chunk of data, typically 1-3 GB) is replicated across 3 nodes in a chain. The configuration manager (a Paxos-based service called the "Stream Manager") handles chain membership and failure detection.

Azure Storage processes hundreds of billions of transactions per day across millions of chains. Each chain independently replicates its data without coordinating with other chains. This design gives them both strong consistency (per-chain) and massive scalability (millions of independent chains).

Code: Chain Replication Node

python
class ChainNode:
    def __init__(self, node_id, successor=None, is_tail=False):
        self.id = node_id
        self.store = {}          # key -> value
        self.pending = {}        # key -> value (dirty, not yet confirmed)
        self.successor = successor
        self.is_tail = is_tail

    def handle_write(self, key, value, client_callback=None):
        """Process a write. Forward to successor or commit if tail."""
        if self.is_tail:
            # Tail: commit and ACK client
            self.store[key] = value
            if client_callback:
                client_callback("OK")
        else:
            # Non-tail: store as pending, forward to successor
            self.pending[key] = value
            self.store[key] = value  # optimistic local update
            self.successor.handle_write(key, value, client_callback)

    def handle_read(self, key):
        """Only the tail serves reads in basic chain replication."""
        assert self.is_tail, "Reads must go to the tail!"
        return self.store.get(key, None)

# Build a 4-node chain
tail = ChainNode("tail", is_tail=True)
n3   = ChainNode("n3", successor=tail)
n2   = ChainNode("n2", successor=n3)
head = ChainNode("head", successor=n2)

# Write flows: head -> n2 -> n3 -> tail
head.handle_write("x", 42, lambda r: print(f"Client got: {r}"))
# Read from tail
print(tail.handle_read("x"))  # 42

Chapter 6: Consensus Showcase

Time to put everything together. Below is a full 5-node Raft cluster simulation. You can send client requests, kill nodes, create network partitions, and watch the system respond in real time. This is Raft in action: leader election, log replication, commit advancement, and failure recovery.

Observations to Make

Raft vs Chain: When to Use Which

After experimenting with both simulations above, here is the decision framework:

Production Performance Numbers

To ground your understanding, here are real-world performance numbers from production consensus systems:

Notice the pattern: all consensus systems have write latencies in the low-millisecond range within a single region (dominated by fsync + network RTT) and tens-to-hundreds of milliseconds cross-region (dominated by speed-of-light latency). This is the fundamental performance ceiling of consensus — you cannot beat the speed of light and the cost of durable writes.

Chapter 7: Consensus in Practice

Now you understand the theory: state machine replication, leader election, log replication, consistency models, chain replication. But where does consensus actually show up in production systems? And equally important: when should you NOT use consensus?

The Big Three Coordination Services

What to Store in Consensus

Consensus is expensive. Every write must be replicated to a majority before it is committed. Latency is at least one network round trip (more for cross-region). Throughput is limited by the leader's capacity. You should use consensus for small, critical data — not for bulk storage.

etcd: The Kubernetes Brain

Every Kubernetes cluster runs etcd as its single source of truth. When you run kubectl apply -f deployment.yaml, the API server writes the deployment spec to etcd. The scheduler watches etcd for unscheduled pods. The kubelet watches for pods assigned to its node. All state transitions go through etcd.

etcd stores the entire Kubernetes cluster state: pods, services, config maps, secrets, RBAC rules, custom resources. A typical production cluster's etcd holds 2-8 GB of data. This small size is by design — consensus does not scale to terabytes.

python
# Using etcd via Python client (etcd3 library)
import etcd3

client = etcd3.client(host="localhost", port=2379)

# Write (goes through Raft consensus)
client.put("/services/web/leader", "node-42")

# Linearizable read (goes through leader)
value, metadata = client.get("/services/web/leader")
print(value)  # b'node-42'

# Watch for changes (streaming)
events_iterator, cancel = client.watch("/services/web/", prefix=True)
for event in events_iterator:
    print(f"Key: {event.key}, Value: {event.value}")

# Distributed lock using lease (TTL-based)
lease = client.lease(ttl=10)  # 10-second lease
# If this process crashes, the lock auto-releases in 10s
client.put("/locks/job-processor", "me", lease=lease)

etcd Performance Characteristics

Understanding etcd's performance envelope is critical for production deployments. Here are the numbers you need to know:

Linearizable Reads: Three Approaches

Raft guarantees linearizable writes by default (they go through the leader and are committed to a majority). But reads are trickier. Here are three approaches, from safest to fastest:

etcd uses ReadIndex by default. When a client issues a linearizable read, the leader (1) records the current commit index, (2) sends a heartbeat to confirm it is still the leader, and (3) waits for its state machine to reach the recorded commit index before serving the read. This avoids the cost of replicating reads through the log while still guaranteeing linearizability.

ZooKeeper: The Original Coordination Service

ZooKeeper predates etcd and Consul. It uses a hierarchical namespace (like a filesystem) where each node is called a znode. Two special znode types power most use cases:

ZooKeeper Distributed Lock: Step by Step

The ZooKeeper distributed lock recipe uses sequential ephemeral znodes. Here is how it works:

python
from kazoo.client import KazooClient

zk = KazooClient(hosts="localhost:2181")
zk.start()

# Acquire a distributed lock
lock = zk.Lock("/locks/my-resource", "worker-42")
with lock:
    # This block runs with exclusive access.
    # If this process crashes, the ephemeral znode
    # auto-deletes, and the next waiter gets the lock.
    print("I hold the lock!")
    do_critical_work()

# Lock is automatically released when exiting the 'with' block.
# Under the hood: ZK deletes the ephemeral sequential znode.

Consul: Service Discovery + Consensus

Consul by HashiCorp combines a Raft-based KV store with built-in service discovery and health checking. Unlike etcd (which is a pure KV store) or ZooKeeper (which is a hierarchical namespace), Consul is purpose-built for microservice coordination.

When NOT to Use Consensus

Consensus is the wrong tool when:

Chapter 8: Interview Arsenal

This chapter is your cheat sheet for system design interviews. It covers the comparison table every interviewer expects, the coding drills, and the design questions that come up repeatedly.

The Consensus Protocol Comparison

Key Concepts Quick Reference

Common Interview Questions

Q: How does Raft guarantee that a new leader has all committed entries?

A: The "log up-to-date" voting rule. A follower refuses to vote for a candidate whose log is less up-to-date (lower last term, or same last term but shorter log). Since committed entries are on a majority, and the new leader must get votes from a majority, the intersection contains at least one node with every committed entry. The candidate must be at least as up-to-date as that node.

Q: What happens if the Raft leader commits an entry and then crashes before broadcasting the commit?

A: The entry is on a majority of nodes. The new leader will have it (by the voting rule above). The new leader will re-replicate it to any followers that are missing it, and then commit it as part of its own term. No committed entry is ever lost.

Q: Design a distributed lock service.

A: Use a consensus-based system (etcd, ZooKeeper). Store locks as keys. Attach a lease/TTL so locks auto-release if the holder crashes. Include a fencing token (monotonically increasing number) with each lock grant. The token is checked by the resource being protected — if the resource sees a stale token, it rejects the operation. This prevents the "process pauses during GC, lock expires, another process acquires, first process resumes and does damage" problem.

Coding Drill: Implement RequestVote

python
class RaftNode:
    def __init__(self, node_id, total_nodes):
        self.id = node_id
        self.current_term = 0
        self.voted_for = None   # Persisted: who did I vote for this term?
        self.log = [None]       # 1-indexed, log[0] is a sentinel
        self.state = "follower"
        self.total_nodes = total_nodes

    def last_log_term(self):
        return self.log[-1].term if len(self.log) > 1 else 0

    def last_log_index(self):
        return len(self.log) - 1

    def handle_request_vote(self, candidate_term, candidate_id,
                             candidate_last_log_idx, candidate_last_log_term):
        """Handle a RequestVote RPC. Return (term, vote_granted)."""

        # Rule 0: If candidate's term < mine, reject
        if candidate_term < self.current_term:
            return self.current_term, False

        # If candidate's term > mine, update my term, reset vote
        if candidate_term > self.current_term:
            self.current_term = candidate_term
            self.voted_for = None
            self.state = "follower"

        # Rule 1: One vote per term
        if self.voted_for is not None and self.voted_for != candidate_id:
            return self.current_term, False

        # Rule 2: Log up-to-date check
        my_last_term = self.last_log_term()
        my_last_idx = self.last_log_index()
        log_ok = (candidate_last_log_term > my_last_term or
                  (candidate_last_log_term == my_last_term and
                   candidate_last_log_idx >= my_last_idx))

        if not log_ok:
            return self.current_term, False

        # Grant vote
        self.voted_for = candidate_id
        return self.current_term, True

Coding Drill: Leader Heartbeat Loop

python
import threading
import time

class RaftLeader:
    def __init__(self, peers, heartbeat_interval=0.1):
        self.peers = peers            # List of follower addresses
        self.interval = heartbeat_interval
        self.running = False
        self.next_index = {}          # peer -> next log index to send
        self.match_index = {}         # peer -> highest replicated index
        self.log = [None]
        self.commit_index = 0
        for p in peers:
            self.next_index[p] = len(self.log)
            self.match_index[p] = 0

    def start_heartbeats(self):
        self.running = True
        self._thread = threading.Thread(target=self._heartbeat_loop)
        self._thread.daemon = True
        self._thread.start()

    def _heartbeat_loop(self):
        while self.running:
            for peer in self.peers:
                self._send_append_entries(peer)
            time.sleep(self.interval)

    def _send_append_entries(self, peer):
        ni = self.next_index[peer]
        prev_idx = ni - 1
        prev_term = self.log[prev_idx].term if prev_idx > 0 else 0
        entries = self.log[ni:]  # Entries to send (empty = heartbeat)

        # Send RPC (simplified — real impl uses async I/O)
        success = self._rpc(peer, prev_idx, prev_term, entries)

        if success:
            self.next_index[peer] = len(self.log)
            self.match_index[peer] = len(self.log) - 1
            self._try_advance_commit()
        else:
            # Back up and retry next heartbeat
            self.next_index[peer] = max(1, self.next_index[peer] - 1)

    def _try_advance_commit(self):
        """Advance commit index if a majority has replicated."""
        for n in range(len(self.log) - 1, self.commit_index, -1):
            # Count nodes that have entry n (including self)
            count = 1  # self
            for p in self.peers:
                if self.match_index[p] >= n:
                    count += 1
            if count > (len(self.peers) + 1) / 2:
                self.commit_index = n
                break

The Raft Safety Argument — How to Explain It in an Interview

Interviewers love to ask "prove that Raft is safe" or "why can't committed entries be lost?" Here is the argument in three steps:

Step 1: Leader Completeness. If an entry is committed in term T, then every leader in terms T+1, T+2, ... has that entry in its log. Why? Because the entry is committed = replicated to a majority. The new leader got votes from a majority. These two majorities overlap (share at least one node). The shared node has the committed entry. The voting rule ensures the new leader is at least as up-to-date as this node. Therefore the new leader has the entry.

Step 2: Log Matching. If two logs have an entry with the same index and term, they are identical up to that point. This is maintained inductively by the AppendEntries consistency check.

Step 3: State Machine Safety. If a server applies entry at index I to its state machine, no other server will ever apply a different entry at index I. This follows from Leader Completeness + Log Matching: the entry at index I was committed, so every future leader has it, so it can never be overwritten.

Advanced Topic: Membership Changes

How do you add or remove nodes from a running Raft cluster without downtime? This is one of the hardest problems in consensus. The original Raft paper proposed joint consensus: a transitional configuration where both the old and new membership must agree. But this is complex to implement.

In practice, most Raft implementations (including etcd) use a simpler approach: single-server changes. You add or remove one server at a time. The key insight: when you change the cluster by exactly one node, the old majority and the new majority always overlap. This means there is no point in time where two independent majorities can exist.

Raft Optimizations for Interviews

Interviewers sometimes ask "how would you make Raft faster?" Here are the standard optimizations:

Design Questions to Practice

Quick-Fire: True or False

Chapter 9: Connections

You now understand the core of distributed consensus: why replication needs coordination, how Raft structures that coordination with leader election and log replication, what consistency models define the client-visible guarantees, and how chain replication offers an alternative topology. Let us place this knowledge in context.

What We Covered vs What We Skipped

The Evolution of Consensus

Understanding the historical progression helps you see why Raft exists and what problem each algorithm was solving:

The Landscape Beyond Crash Faults

Everything in this lesson assumes crash-fault tolerance: nodes either work correctly or stop. In the real world, there are situations where this is not enough:

Byzantine fault tolerance (BFT) requires 3f+1 nodes to tolerate f Byzantine faults, compared to 2f+1 for crash faults. The message complexity is O(n²) instead of O(n). This makes BFT 3-10x more expensive than crash-fault consensus, which is why cloud systems do not use it — they trust their own hardware.

Related Lessons

The One Diagram to Remember

Seminal Papers Worth Reading

The Mental Model

After this lesson, you should have a clear mental picture of how consensus fits into distributed systems:

This separation — control plane vs data plane, consensus vs replication, metadata vs data — is the organizing principle of every well-designed distributed system. Master it, and every distributed systems paper, blog post, and interview question will make sense.

Checklist: What You Should Be Able to Do

After completing this lesson, test yourself. You should be able to:

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."
— Leslie Lamport