Leader and Follower

Background

Distributed systems keep multiple copies of data for fault tolerance and higher availability. A system can use quorum to keep replicas consistent: a write is only considered successful once a majority of nodes have applied it, and a read only considered valid once it has queried a majority. But quorum by itself only bounds staleness — it does not give replicas a way to order concurrent writes to the same key. If two clients write to different replicas at nearly the same time, each replica may see the writes arrive in a different order, and the replicas can permanently disagree about which value is current, even though each write individually reached a majority.

Solution: elect a single writer

The leader-follower pattern fixes the ordering problem by letting only one node — the leader — accept writes and decide their order. The leader appends every write to its own log first, then replicates that log, in order, to the followers. Followers only accept entries from the current leader and otherwise serve as warm backups; some systems also let followers serve reads to spread out load, at the cost of those reads possibly being slightly stale. If the leader fails, the followers run an election and promote one of themselves to be the new leader.

How a leader is chosen: Raft's election protocol

Most production systems (etcd, Consul, CockroachDB, Kafka's KRaft controller) use a Raft-style protocol to pick and re-pick a leader without human intervention.

• Heartbeats. The current leader periodically sends empty AppendEntries RPCs ("heartbeats") to every follower. As long as a follower keeps hearing from the leader, it stays a follower and resets its election timer.
• Randomized election timeout. Each follower picks its own randomized timeout (e.g., 150-300 ms). If it hears no heartbeat before the timeout fires, it assumes the leader is gone, increments its term counter, votes for itself, and becomes a candidate. Randomizing the timeout, rather than using one fixed value for every node, is what keeps two followers from becoming candidates at the exact same instant and splitting the vote every round.
• RequestVote RPC. The candidate asks every other node to vote for it in the new term, including its own lastLogIndex and lastLogTerm.
• Log up-to-date restriction. A node grants its vote only if the candidate's log is at least as up to date as its own (higher lastLogTerm, or the same lastLogTerm with a lastLogIndex that is greater-or-equal). This is the safety rule that stops a node with a stale, shorter log from ever getting elected and silently discarding committed entries.
• Majority wins. Once a candidate collects votes from a majority of the cluster, including its own vote, it becomes leader for that term and immediately starts sending heartbeats to establish authority and reset every follower's timer.

Worked example: a write, step by step

Take a 3-node cluster: leader L and followers F1, F2, all currently on term 4 with the log committed through index 100.

1. A client sends SET x=42 to L. L appends it to its own log as {index:101, term:4, cmd:"SET x=42"} — uncommitted so far.
2. L sends AppendEntries to F1 and F2 in parallel, carrying the new entry and leaderCommit=100.
3. F1 replies success almost immediately. L now has itself and F1 holding the entry — 2 out of 3 nodes, a majority. L marks index 101 committed, applies x=42 to its own state machine, and replies to the client.
4. F2 is momentarily slow and hasn't acked yet — this is fine. Commit only ever needs a majority, not all replicas.
5. On the next heartbeat, L sends leaderCommit=101 to F2. Once F2 has the entry in its own log, it advances its local commit index to min(leaderCommit, its own last log index) and applies x=42. This is how a lagging follower catches up to a commit it missed the first round — through leaderCommit on a later RPC, not through a special repair path.

Worked example continued: the leader crashes

The cluster keeps taking writes and both followers catch up; the log is now committed through index 105 on L, F1, and F2, all at term 4. Then L crashes.

1. F1's randomized election timeout (180 ms) fires before F2's (260 ms). F1 increments its term to 5, votes for itself, and becomes a candidate.
2. F1 sends RequestVote{term:5, candidateId:F1, lastLogIndex:105, lastLogTerm:4} to F2 — 105/4 is exactly what was committed before the crash, so nothing was lost.
3. F2 checks its own log: also lastLogIndex:105, lastLogTerm:4. The candidate's log is at least as up to date, so F2 grants its vote for term 5.
4. F1 now has 2 votes out of 3, a majority, and becomes leader for term 5. It immediately sends a heartbeat to F2 to establish itself and reset the election timer.
5. If the old leader L restarts, the first RPC it sees carrying term 5 tells it a newer term exists; it steps down to follower and adopts term 5.

The split-brain gap, and how fencing tokens close it

Raft's term-and-majority rule guarantees at most one leader can be elected per term inside the Raft cluster itself. The dangerous gap is at the boundary where that leader acts on external systems. Imagine L hits a long garbage-collection pause or a network partition: from the outside it looks dead, so the cluster elects F1 as leader for term 5 while L is still frozen. When L resumes, it hasn't seen any RPC with a higher term yet, so for a brief window it still believes it is the leader of term 4 and may keep issuing writes to a downstream store — at the same time F1 is doing the same thing as the legitimate term-5 leader. That is split brain: two nodes acting as leader concurrently.

The standard fix, Kleppmann's fencing-token pattern, is to make every write to a shared downstream resource carry a monotonically increasing token — the Raft term number works perfectly as this token, since it only ever increases, exactly once per election. The downstream resource remembers the highest token it has ever accepted and rejects any write that arrives with a lower one. So when the stale L (token 4) finally sends its write, the resource has already accepted a write fenced with token 5 from F1, and rejects L's write outright — even though L still thinks it is in charge.

When to reach for a leader, and when not to

Leader-follower is not the only way to replicate writes, and it is not always the right one. The decision comes down to what you are willing to give up.

Reach for leader-follower when you need a simple "there is exactly one writer" mental model, strong consistency without application-level conflict resolution, and read replicas to scale out reads — this is why primary-replica relational databases, Kafka's per-partition leader, and Raft-based coordination stores such as etcd and Consul all use it.

Avoid adding a leader, and prefer leaderless or multi-leader replication instead, when: (1) you need concurrent writes accepted in multiple regions with low latency in each, and a round trip to one leader sitting in one region is unacceptable; (2) your data can tolerate eventual consistency and has a natural way to reconcile conflicts, such as shopping carts, presence indicators, counters, or CRDTs; or (3) the failover unavailability window itself is the problem — a system that must never stall on writes, even for the seconds it takes to elect a new leader, is better served by a design where any reachable node can take a write immediately.

Compared to the bare quorum from the previous lesson: quorum alone (W + R > N) guarantees a reader will see the most recent write, but it does not order concurrent writes from different clients — two overlapping quorum writes to the same key can still race and leave replicas holding different "latest" values. A leader removes that race by serializing all writes through one log, at the price of the failover gap and single-writer bottleneck described above. Choose the leader when total order is worth that price; choose leaderless or quorum-only replication, or multi-leader replication, when write availability and multi-region latency matter more than total order and your application can absorb the resulting conflicts.

Pitfalls

• Election timeouts that are too short, or not randomized across nodes, cause repeated split votes and leadership thrashing — multiple followers time out at once, split the vote, retry, and split again, so the cluster spends more time re-electing than serving writes.
• Reading from a follower can return stale data; only treat follower reads as fresh if the application can tolerate replication lag, or route reads that must be current back to the leader.
• The leader is a hard ceiling on write throughput — once its single-node capacity is saturated, adding more followers does nothing for write scaling, only for reads and durability.
• A network partition that leaves the leader on the minority side makes that side correctly refuse writes to preserve safety — this looks like an outage from the minority side even though the majority side is healthy and still serving.
• Skipping fencing tokens when a Raft-elected leader also drives non-idempotent external side effects, such as writing to blob storage or calling a payment API, reopens the split-brain window described above — a paused or partitioned "zombie" leader can keep firing real-world effects after it has been deposed.

Sources

• Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm (Raft)", USENIX ATC 2014 — election protocol, terms, RequestVote, and the log-up-to-date safety rule.
• Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly, 2017 — leaderless and quorum replication, conflict resolution via vector clocks and last-write-wins, and the fencing-token pattern for safe leader handoff.
• Educative, "Grokking the System Design Interview" — Leader and Follower building block, the original background and solution framing this lesson builds on.