Distributed systems
Part 1 of 5 · Raft consensusRaft Consensus — Leader Election, Log Replication & Safety
Single leader, append-only log, commit after majority; terms/roles/heartbeats/log matching vs Multi-Paxos; used in etcd/Consul/TiKV/K8s metadata.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Why Raft is the interview default for CFT log consensus
Prefer
Strong leader + terms + log matching (Raft)
One client write path. Heartbeats keep leadership. Majority persist before commit. The state space is small enough to whiteboard.
- Explicit roles: follower, candidate, leader.
- Terms are a logical clock: stale leaders are rejected.
- Production gravity: etcd, Consul, TiKV, Kubernetes metadata.
- Safety decomposes: election safety, log matching, leader completeness.
Alternative
Abstract Multi-Paxos or a ZooKeeper-shaped primary
Same CFT RSM goal. Different ops model. Wrong pick is usually ecosystem, not asymptotics.
- Multi-Paxos is more flexible (ballots, pipelining) and harder to staff.
- Zab is the right answer when you already run ZooKeeper watches/recipes.
- Rolling your own Paxos for a tiny lease store is months of silent safety bugs.
- Full comparison: Raft vs Multi-Paxos vs Zab.
Happy path — one write through Raft
Vertical cards for phones. Sequence diagram below is the same pipeline.
- 1
Client writes the leader
Followers do not take client writes. If you hit a follower, it redirects. - 2
Leader appends locally
The log is append-only. The leader never rewrites its own indices. - 3
AppendEntries to followers
Each follower persists the entries (or rejects on prevLog mismatch). - 4
Majority persist → commitIndex
An entry is committed when the current leader knows a majority stored it, and Raft's prior-term commit rule holds. - 5
Apply, then reply
Committed entries apply in order. The client success is after commit (often after apply). Apply may lag; it never reorders.
Overview
Raft is a crash-fault-tolerant consensus algorithm that elects a single leader, replicates an append-only log, and only marks entries committed after a majority of servers persist them. Compared with classic Multi-Paxos, Raft constrains the state space (strong leader, term numbers, log matching) so you can reason about elections, replication, and safety separately.
In production you meet Raft inside etcd, Consul, TiKV, and many Kubernetes control-plane components.
You should be able to:
- Draw follower → candidate → leader, with demotion on a higher term.
- Explain why votes are exclusive and why majority implies election safety.
- Walk commit vs apply, and what happens to uncommitted entries after a partition.
Raft vs Multi-Paxos vs Zab (teaser)
| Dimension | Raft | Multi-Paxos | Zab (ZooKeeper) |
|---|---|---|---|
| Leadership | Strong single leader | Leader optional / sticky proposer | Primary (leader) |
| Mental model | Explicit roles + terms | More abstract phases | Epoch + zxid ordering |
| Common tooling | etcd, Consul, TiKV | Spanner-ish / custom | ZooKeeper |
| Best when | Understandable CFT log consensus | Customizing latency / batching deeply | ZK ecosystem / watch semantics |
What fails if you choose wrong
- Treat Raft like a quorum key-value store without a log → you lose ordered state-machine apply and membership safety.
- Use ZooKeeper when you only need a small lease/config store and the team already runs etcd → duplicated ops surface.
- Roll your own Multi-Paxos for a greenfield control plane without staff who know Paxos failure modes → silent safety bugs.
Deep comparison lives in Raft vs Multi-Paxos vs Zab.
Roles, terms, and the heartbeat loop
Raft servers are always in one of three roles:
- Follower — passive; accepts
AppendEntries/RequestVotefrom higher or equal terms. - Candidate — started an election for a new term; solicits votes.
- Leader — sole client write path; sends heartbeats (empty
AppendEntries) and replicates log entries.
Time is divided into terms (monotonically increasing integers). At most one leader per term. Seeing a higher term demotes you (leader/candidate → follower) and updates currentTerm.
Decisions
- 1
Follower
- election timeoutCandidate
- 2
Candidate
- nextVote tally?
- ?
Vote tally?
- win majorityLeader
- split vote: new termCandidate
- higher term or loseFollower
- 4
Leader
- higher termFollower
Lesson map
Raft Consensus — Leader Election, Log Replication & Safety
Single leader, append-only log, commit after majority; terms/roles/heartbeats/log matching vs Multi-Paxos; used in etcd/Consul/TiKV/K8s metadata.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB c["Client"] l["Leader"] f["Followers"] sm["State machine"] c -->|propose command| l l -->|AppendEntries| f f -->|ok majority| l l -->|Step 5 apply| sm l -->|Step 6 respond| c
Leader election (overview)
- Follower election timer expires → become Candidate, increment term, vote for self, send
RequestVote. - Others grant a vote if they have not voted in this term and the candidate's log is at least as up-to-date (last term, then last index).
- Majority votes → Leader; start heartbeats immediately.
- Split vote → no majority; each Candidate times out with randomized backoff and retries.
Timeouts, randomization, pre-vote, and split-vote math: leader election deep dive.
Log replication & commit vs apply
- Client writes go only to the leader.
- Leader appends to its log, then fans out
AppendEntriesto followers. - An entry is committed when the leader knows a majority has stored it (and Raft's commit rules for prior terms are satisfied — the Figure 8 guard).
- Commit ≠ apply: committed entries are applied to the state machine in order; apply can lag commit slightly, but never reorder.
Matching, nextIndex backoff, truncation, commitIndex, and the safety sketch: log replication & commit index.
Quorums & majority
With N = 2f+1 servers, any majority (f+1) intersects every other majority — that is why Raft can tolerate f crash failures. Read quorums, learners vs voters, and stale linearizable reads: quorums & majority.
Membership changes (brief)
Raft supports joint consensus (old+new configuration overlapping) or single-server add/remove with careful sequencing so two disjoint majorities never decide differently. Mis-ordered membership changes are a classic production footgun — treat them as a dedicated review item, not a one-liner in the election answer.
End-to-end write path
Sequence
- 1
Client
Step 1 client write
- 2
Client → Leader
propose command
- 3
Leader
Step 2 append local log
- 4
Leader → Followers
AppendEntries
- 5
Followers
Step 3 persist entries
- 6
Followers → Leader
ok majority
- 7
Leader
Step 4 advance commitIndex
- 8
Leader → State machine
Step 5 apply committed
- 9
Leader → Client
Step 6 respond success
Sandbox: term + vote rules (Python)
Self-contained sketch of term / vote / up-to-date rules — not a full Raft implementation. Node B has a longer, newer log; A must not steal B's vote.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same vote rules (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Why does Raft need terms?
Answer
Terms act as a logical clock for elections. They ensure obsolete leaders (partitioned old leaders) are rejected when they contact the cluster with a stale term. Without terms you cannot tell a zombie primary from the current one.
Can there be two leaders in one term?
Answer
No — election safety: at most one leader per term because votes are exclusive and a majority is required. Two majorities of size f+1 in 2f+1 cannot be disjoint. You can briefly have two leaders in different terms; the lower term steps down on contact.
Why randomized election timeouts?
Answer
To break symmetry after split votes so one candidate usually times out first and wins. Identical timeouts → synchronized elections → split votes forever under load. Depth: election timeouts.
When is a log entry committed?
Answer
When the current leader has replicated it to a majority and (for entries from prior terms) Raft's commit restriction is satisfied — typically by committing an entry from the leader's current term. Majority alone is not enough for old-term entries (Figure 8).
Commit vs apply?
Answer
Commit is agreement that the entry is durable in the replicated log. Apply is feeding it to the state machine in index order. Apply can lag; it must not reorder. Clients usually see success after commit (often after apply).
Why majority of 2f+1?
Answer
Any two majorities intersect, so two leaders/decisions cannot form on disjoint sets. With N=5, f=2, majority=3. See quorums.
What happens if a leader is partitioned?
Answer
Followers on the majority side elect a new leader with a higher term. The old leader steps down on hearing the higher term. Uncommitted entries it held alone may be overwritten. Committed entries survive because a majority stored them and the new leader's vote rule includes the up-to-date check.
How do linearizable reads work?
Answer
Naive follower reads can be stale (old leader, or a lagging replica). Leaders often confirm leadership (heartbeat/quorum read or ReadIndex/lease) before serving linearizable reads. Follower reads are fine for dashboards; dangerous for fencing tokens.
Pitfalls
Draw N=5. Partition leader A with one follower. Majority elects B in a new term. A still has an uncommitted entry at index 10. Show: who can commit, who steps down, and whether index 10 survives. Then say what would have saved that entry (majority persist + current-term commit rule).