Back to System design
Consensus: Raft and Paxos in Plain English
hardFive servers hold a copy of the same data. A request arrives. They all have to end up agreeing on what happened and in what order — even though any of them can crash at any moment and messages can go missing.
ScaleWrite latency = 1 RTT to majority; reads = leader RTT or lease-fast
StorageLog + snapshot per node; logs truncated after snapshots
Key Concepts
1
Getting them to agree is called consensus. Raft and Paxos are two ways of doing it.
consensus
2
Why order matters so much. If the servers apply the same changes in different orders, their copies
drift apart and there is no way to say which is right. So consensus is really about agreeing on a list:
the same entries, in the same order, everywhere.
Why order matters so much.
3
Everything rests on majority. No decision counts until more than half the servers acknowledge it. With
5 servers, that is 3.
Everything rests on majority.
4
The reason is simple. Any two majorities of the same group must share at least one member. That shared
member cannot agree to two conflicting decisions, so conflicting decisions cannot both succeed.
5
This also explains why cluster sizes are odd. With 3 servers you can lose 1. With 4 you can still only
lose 1, because losing 2 leaves 2, which is not a majority. The fourth machine costs money and buys
nothing.
6
How Raft works, in order.
How Raft works, in order.
7
One server is the leader. Clients talk only to it. It writes each request into its own list, then
sends it to the others. Once a majority have stored it, the entry counts as committed and the leader
applies it and replies.
leader
8
The others expect regular heartbeats from the leader. If a server hears nothing for its timeout — usually
150 to 300 ms — it assumes the leader is gone, and asks everyone to vote for it instead. The timeouts are
deliberately random, so two servers rarely ask at the same moment.
9
A server only votes for a candidate whose list is at least as up to date as its own. That one rule is what
stops a committed entry from being lost.
10
Paxos does the same job and is harder to read. It was first described as agreeing on a single value,
with two phases. Multi-Paxos keeps a stable leader and ends up looking much like Raft. Raft's contribution
was not new theory; it was explaining the same guarantee in a way people can implement correctly.
Paxos does the same job and is harder to read.
11
What it costs. Every committed write waits for a majority to reply, so a write costs one round trip to
your middle-fastest server. Inside one data centre that is a millisecond or two. Across regions it is tens
or hundreds.
What it costs.
12
Throughput is limited by the single leader. That is why large systems do not grow one group — they split
the data into many shards and run a small consensus group for each.
13
When not to use it. Consensus suits small, important, rarely-changing data: who is the leader, what is
the configuration, who holds the lock. Running your main user data through one consensus group gives you a
slow database with a single writer. And do not implement it yourself; use etcd or ZooKeeper.
When not to use it.
14
What the interviewer is probing.
What the interviewer is probing.
15
1. "Why do you need consensus?" Probing: the problem before the algorithm. Stalls: "To keep
servers in sync." Moves up: to agree on one ordered list, so copies stay identical despite crashes and
lost messages.
1. "Why do you need consensus?"
16
2. "Why an odd number of servers?" Probing: the majority arithmetic. Stalls: "Convention." *Moves
up:* 4 tolerates the same single failure as 3, and two majorities always overlap.
2. "Why an odd number of servers?"
17
3. "The leader is cut off. What happens?" Probing: safety versus availability. Stalls: "A new
leader is elected." Moves up: the majority side elects one; the old leader cannot commit anything
because it cannot reach a majority, and it steps down when it learns of the newer term.
3. "The leader is cut off. What happens?"
18
4. "How fast is a write?" Probing: the cost model. Stalls: "Fast." Moves up: one round trip to a
majority — a couple of milliseconds locally, about 60 ms if the majority spans Mumbai and Singapore.
4. "How fast is a write?"
19
5. "Would you use Raft for your main database?" Probing: judgement. Stalls: "Yes, it is
consistent." Moves up: one leader caps throughput; use it for metadata and shard the data across many
small groups.
5. "Would you use Raft for your main database?"
Components
- Replicated log on each node (append-only, persistent).
- State machine that applies committed entries deterministically.
- Term number (logical clock).
- Heartbeats from leader (also serve as keepalive).
- Election timer (randomized to avoid simultaneous candidacies).
- Snapshot mechanism + log truncation.
- Membership configuration (joint consensus protocol).
- ReadIndex / lease for consistent reads.
Cluster size and tolerance
Nodes Majority Failures tolerated Notes
----------------------------------------------------------------
1 1 0 not a cluster
2 2 0 worse than 1: either node
failing stops progress
3 2 1 the common default
4 3 1 no gain over 3, more cost
5 3 2 for higher availability
7 4 3 rarely worth the latency Why even sizes do not help
Majority of 4 is 3. Losing 2 leaves 2, which is not a majority,
so a 4-node cluster tolerates 1 failure -- identical to 3. Latency effect of size
A write waits for the MAJORITY, not for everyone. With 5 nodes
it waits for the 3rd fastest ack, so one slow replica does not
slow writes. That is a real argument for 5 over 3 when replicas
have uneven performance. Geographic placement
3 nodes in one region ~1-2 ms commit
2 + 1 across two regions majority may require the far node
=> ~60 ms commits when the local
pair is not enough
Spread across 3 regions every commit is cross-regionRaft, step by step
Roles: follower, candidate, leader. Terms increase monotonically.
Leader election
1. Follower hears no heartbeat for its randomised election
timeout (150-300 ms).
2. It increments the term, votes for itself, requests votes.
3. A node grants a vote if it has not voted this term and the
candidate's log is at least as up to date as its own.
4. Majority of votes => leader. It sends heartbeats immediately.
5. Split vote (two candidates, no majority) => no leader this
term; randomised timeouts make a repeat unlikely. Log replication
1. Client sends a command to the leader.
2. Leader appends to its log, sends AppendEntries to followers.
3. Once a MAJORITY has written the entry, it is committed.
4. Leader applies it, replies to the client, and tells followers
the new commit index. Safety property that matters
A candidate cannot win without an up-to-date log, so a committed
entry can never be lost by electing the wrong leader. Practical timeouts
heartbeat interval ~50 ms
election timeout 150-300 ms, randomised per node
-- heartbeat must be well below election timeout, or the cluster
elects new leaders during ordinary jitter.Where consensus belongs
Good fits (small data, high value, low write rate)
Leader election for a service
Cluster membership and configuration
Distributed locks and leases
Shard assignment maps
Kafka controller metadata, Kubernetes state (etcd) Bad fits
User data at scale one leader bounds throughput
High-rate telemetry consensus per event is enormous overhead
Anything where eventual consistency is acceptable and cheaper The scaling pattern
Do not grow one consensus group. Shard the keyspace and run one
group per shard: Spanner's Paxos groups per split, CockroachDB's
Raft group per range, TiKV's Raft per region. Each group is small
(3-5 nodes) and independent, so throughput scales with shard
count rather than being capped by one leader. The rule of thumb
If the data is measured in gigabytes and read constantly by the
whole fleet, it is metadata -- consensus fits. If it is measured
in terabytes and written by users, it is data -- shard it.