Phase 3 · Chapter 3

Leader Election & Raft

How distributed systems agree on who's in charge — and why it's harder than it sounds

What this chapter does to you: Every distributed system with more than one node eventually asks: who makes the final decision? Leader election is how distributed systems answer that question without human intervention. After this chapter, you will understand why consensus is hard, how Raft solves it with a clean mental model, and why etcd, CockroachDB, and Kafka all use it to coordinate.

Part 1: Why You Need a Leader

In a distributed system, multiple nodes must sometimes agree on one value or one course of action. Without coordination, chaos:

Scenario — no leader: Your Postgres cluster has 3 nodes. Primary crashes. All 3 surviving nodes decide to write to disk simultaneously. They have different data. Which is authoritative? Answer: nobody knows. Data is corrupted.

Scenario — with leader: Your cluster has a designated leader. All writes go to the leader. Leader replicates to followers. If leader crashes:

• Followers detect the crash (heartbeat timeout)
• They run an election
• One follower becomes the new leader
• Writes resume — to the new leader
• No human intervention needed

Leader election is the mechanism that makes distributed systems self-healing.

Systems that use leader election:

• Postgres (Patroni uses etcd/Consul for leader election)
• Kafka (ZooKeeper, later KRaft — both are leader election systems)
• Redis Sentinel (elects a new primary when the current one fails)
• Kubernetes (etcd stores all cluster state; leader coordinates)

Part 2: The Consensus Problem

Leader election is a specific case of the consensus problem:

A set of nodes must agree on a single value, even when some nodes fail or messages are delayed.

This sounds simple. It is not. The FLP impossibility theorem (Fischer, Lynch, Paterson, 1985) proves that no deterministic consensus algorithm can guarantee both safety and liveness in an asynchronous network where even one node can fail.

• Safety: All nodes agree on the same value. No two nodes decide differently.
• Liveness: All nodes eventually decide. The system doesn't stall forever.

FLP says you can have at most one of these guaranteed simultaneously in an asynchronous system (one where message delivery time has no upper bound).

The practical escape hatch: Real networks are not purely asynchronous. Messages usually arrive within a bounded time. Practical algorithms (Paxos, Raft) assume partial synchrony — the network is usually well-behaved — and achieve both safety and liveness most of the time. They sacrifice liveness only when the network is genuinely broken (partition), which is acceptable.

Part 3: Raft — The Understandable Consensus Algorithm

Paxos (the original consensus algorithm, 1989) is famously hard to understand. Raft (2013) was explicitly designed to be understandable. It solves the same problem with a clearer structure.

Raft decomposes consensus into three sub-problems:

1. Leader election — which node is in charge?
2. Log replication — how does the leader spread its decisions?
3. Safety — how do you ensure only one leader exists and logs don't diverge?

Node States in Raft

Every node in a Raft cluster is in exactly one of three states:

FOLLOWER   → default state. Listens to leader. Votes in elections.
CANDIDATE  → running for leader. Requesting votes.
LEADER     → accepted by majority. Handles all writes.

State transitions:

Terms — Raft's Logical Clock

Raft divides time into terms — consecutive integers.

Each term begins with an election. The winner leads for that term. If no winner (split vote), a new term begins immediately.

Every Raft message carries the sender's current term number. If a node receives a message with a higher term: it immediately updates its term and reverts to FOLLOWER. This prevents stale leaders from causing damage.

Terms are Raft's way of detecting and discarding stale information.

Leader Election — Step by Step

Why random timeouts? To prevent all nodes from becoming candidates simultaneously (split vote). The node with the shortest timeout becomes a candidate first, usually wins before others time out. Simple, elegant, effective.

Split Vote — What Happens

4 nodes. N1 and N3 both time out simultaneously. Both become candidates.

In practice, split votes are rare because random timeouts stagger the candidates.

Log Replication — How the Leader Spreads Writes

Once elected, the leader handles all writes. Every write is a log entry.

The key guarantee: A log entry is committed only after a majority of nodes have written it to their log. A committed entry will survive any future leader election — because the new leader must have gotten votes from a majority, and at least one voter in that majority had the committed entry.

This is the safety guarantee: committed entries are never lost.

Safety — Why Only One Leader Exists

Term numbers prevent two leaders in the same term: A node only votes once per term. Majority means > half. Two majorities in the same term is impossible — they'd need to share more than half the nodes.

Log completeness ensures the right node wins future elections: Raft's vote-granting rule: a follower only votes for a candidate whose log is at least as up-to-date as its own.

"Up-to-date" = candidate's last log entry has a higher term, or same term and equal-or-greater index.

This ensures the node with the most complete log becomes leader. A stale node can never win an election.

Try it before moving on. Each tab asks you to predict first: an election, a split vote, a majority commit, and a partition where two nodes both think they lead.

Part 4: Raft in Practice — etcd

etcd is the Raft implementation that powers Kubernetes. All Kubernetes state (pods, services, deployments) lives in etcd.

Why 3 or 5 nodes?

3 nodes: tolerates 1 failure (majority = 2 of 3). 5 nodes: tolerates 2 failures (majority = 3 of 5). 7 nodes: tolerates 3 failures (majority = 4 of 7).

More nodes = more failures tolerated. But also more nodes to replicate to = higher write latency. 5 nodes is the practical sweet spot for most systems.

Why odd numbers? Even-numbered clusters have asymmetric failure modes. 4 nodes: a 2-2 split partition means neither side has majority. Complete outage. 5 nodes: a 3-2 split means the 3-node side can still form a majority and keep working.

Part 5: Raft vs Paxos vs ZAB

All solve the same consensus problem. Raft's advantage is clean mental model — easier to implement correctly, easier to reason about.

Part 6: Leader Election Without Raft — The Simple Cases

For systems that don't need the full Raft protocol, simpler leader election mechanisms exist.

Redis-Based Election (Simple, Non-Byzantine)

const LOCK_KEY = 'leader:lock'
const TTL_MS = 10_000
let isLeader = false
let heartbeat = null

// Each server tries to acquire a "leader" lock in Redis
async function tryBecomeLeader(serverId) {
  const acquired = await redis.set(
    LOCK_KEY,
    serverId,
    'NX',            // only if not exists
    'PX', TTL_MS     // expires in 10 seconds
  )

  if (acquired) {
    isLeader = true
    startLeaderHeartbeat(serverId)   // renew lock every 3 seconds
    return true
  }
  return false   // someone else is leader
}

// Renew ONLY if I still hold the lock — as ONE atomic step.
// A separate GET then EXPIRE has a race: the lock can expire and be taken by
// another server between the two commands, and you would extend THEIR lock.
const RENEW_IF_OWNER = `
  if redis.call('GET', KEYS[1]) == ARGV[1] then
    return redis.call('PEXPIRE', KEYS[1], ARGV[2])
  end
  return 0
`

function startLeaderHeartbeat(serverId) {
  heartbeat = setInterval(async () => {
    try {
      const renewed = await redis.eval(RENEW_IF_OWNER, 1, LOCK_KEY, serverId, TTL_MS)
      if (renewed !== 1) stepDown()      // someone else owns it now
    } catch (err) {
      stepDown()                          // can't reach Redis = can't prove I'm leader
    }
  }, 3000)
}

function stepDown() {
  isLeader = false
  clearInterval(heartbeat)
  // stop any leader-only work here (cron loop, cache warmer, ...)
}

If the leader crashes, the lock expires after 10 seconds. Another server acquires it. New leader within 10 seconds. No Raft needed.

The caveat: This is still not safe in all scenarios. The leader might pause (GC pause, VM freeze, slow disk) for longer than the TTL. The lock expires, a new leader is elected — but the old leader wakes up, has not run its heartbeat yet, and still thinks it is leader. For a moment, two servers act as leader. No amount of checking inside the old leader fixes this: the pause can happen right after the check.

The real fix: fencing tokens. Every time leadership changes, hand out a number that only goes up (e.g. INCR leader:epoch when you acquire the lock, or etcd's revision number). The leader sends that token with every write it makes, and the resource being written to rejects any token lower than the highest one it has seen:

Old leader (token 33) pauses ──────────────────────▶ wakes, writes with token 33 → REJECTED
New leader (token 34) acquires lock, writes with token 34 → accepted (storage now remembers 34)

-- the protected resource enforces it
UPDATE jobs SET status = 'running', fence = 34
WHERE id = 7 AND fence < 34;      -- a stale leader's write matches 0 rows

This is the standard follow-up question on any distributed lock: "What if the lock holder pauses?" The answer is fencing tokens — the lock alone is never enough. (It is also the core of the well-known critique of Redis's multi-node Redlock algorithm: without fencing, timing-based locks cannot guarantee safety.)

For low-stakes leadership (cron job coordination, cache warming) where a rare double run is harmless or the job is idempotent, Redis-based election is fine. For critical state (database primary), use consensus (etcd/Consul/ZooKeeper), and still fence the writes.

Part 7: The Vocabulary Map

Part 8: Practice Problems

Problem 1 (Raft Election): 5-node Raft cluster. Term 3. N1 is leader. N1 crashes. Nodes N2, N3, N4, N5 remain.

N3 and N5 both time out and start elections simultaneously. N3 sends RequestVote(term=4) and N5 sends RequestVote(term=4).

Votes:

• N2 receives N3's request first → votes for N3
• N4 receives N5's request first → votes for N5
• N3 votes for itself
• N5 votes for itself

Result: N3 has 2 votes, N5 has 2 votes. Split.

What happens next? Trace the exact steps through the next election attempt. At what point does one node definitely win?

Problem 2 (Log Safety): 3-node cluster. N1 is leader in term 2. Log:

N1 (leader): [1:term1:SET x=1] [2:term1:SET y=2] [3:term2:SET z=3]
N2 (follower): [1:term1:SET x=1] [2:term1:SET y=2]
N3 (follower): [1:term1:SET x=1]

Entry at index 3 (SET z=3) has only been replicated to N1. N1 crashes before entry 3 is committed.

N2 and N3 start election. Which one can become leader? Why can N3 NOT become leader? After the new leader is elected, what happens to entry 3 (SET z=3)?

Problem 3 (Practical Design): AttemptIQ needs a cron job that runs every minute to update leaderboards. It must run exactly once, even when 3 app servers are running simultaneously.

Design the leader election mechanism:

• Should you use Raft (via etcd) or Redis-based election? Why?
• What is the TTL on your lock and why?
• What happens if the elected leader crashes after 30 seconds mid-job?
• How do you ensure the job completes rather than silently dying?

Problem 4 (The Unavailability Window): 3-node Raft cluster (N1 leader, N2, N3 followers). N1 crashes. Election timeout is 150-300ms. etcd's default election timeout is 1,000ms.

Calculate:

• Minimum time before a new leader is elected
• Maximum time before a new leader is elected
• During this window, what happens to write requests?
• What happens to read requests (assuming linearizable reads require leader)?
• Is this acceptable for: a) a payment system? b) a caching layer config? c) Kubernetes?

End of Phase 3, Chapter 3.