Distributed systems
Part 2 of 5 · Raft consensusQuorums & Majority — Why 2f+1, Read Quorums & Stale Reads
N=2f+1 tolerates f crashes; majority intersection prevents conflicting commits; linearizable reads need ReadIndex/lease not blind follower reads.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Majority vs tunable quorums vs blind replica reads
Prefer
Raft majority (write) + leadership check (linearizable read)
Writes need f+1. Linearizable reads confirm the leader still leads (ReadIndex / lease). Intersection is the whole safety story.
- N=3 survives 1 crash; N=5 survives 2.
- Minority partition correctly blocks writes (CP).
- Learners do not count toward majority.
- etcd/Consul stay operable because the rule is one sentence.
Alternative
Dynamo R+W>N or follower reads as 'strong'
Tunable availability is a different product. It does not give single-copy state-machine semantics.
- R+W≤N yields conflicts / vector clocks, not one log.
- Follower reads after failover return old fencing tokens.
- N=2 'HA' Raft loses write quorum on one failure.
- Flexible Paxos can shrink live sets — rare in etcd-class stacks.
Overview
Raft (and classic majority quorum systems) size clusters as N = 2f+1 so that any majority of f+1 intersects every other majority. That intersection is the mathematical reason two leaders cannot independently commit conflicting history.
This lesson contrasts write quorums, read quorums, stale reads, and what breaks if you shrink N for "availability" without understanding the intersection property.
Majority vs flexible vs R+W>N
| Approach | Write path | Read path | Failure tolerance | Pitfall |
|---|---|---|---|---|
| Majority (Raft default) | Majority of N | Leader / ReadIndex / lease | f = floor((N-1)/2) crashes | Minority partition blocks writes |
| Strict quorum R+W>N (Dynamo-style) | W replicas | R replicas | Tunable | Conflicts / vector clocks; not SM safety |
| Flexible Paxos / grids | Quorum grids | Intersecting read/write | Can reduce live set for some ops | Harder to reason; rare in etcd-class systems |
| Follower reads (no quorum) | Majority writes | Any replica | High read avail | Stale / non-linearizable |
What fails if you choose wrong
- Deploy 2-node Raft "for HA" → one failure = no majority; worse than a single node for writes.
- Serve follower reads and call them strongly consistent → clients see old leaders' state after failover.
- Set Dynamo R+W≤N expecting Raft-like single-copy semantics → you get conflicts, not a replicated state machine.
Why 2f+1 works
With N=5, f=2. Any set of 3 servers intersects any other set of 3. Therefore:
- Two elections in the same term cannot both gather majorities.
- A newly elected leader's majority overlaps a prior commit majority → the new leader's log must contain all previously committed entries (given Raft's voting rules).
Architecture
Step 1 — Cluster N=5
- 1
S1
- nextS2
- 2
S2
- nextS3
- 3
S3
- nextS4
- 4
S4
- nextS5
- 5
S5
Step 2 — Majority A
- 6
S1
- nextS2
- 7
S2
- nextS3
- 8
S3
- nextS3 in both
Step 3 — Majority B
- 9
S3
- nextS4
- nextS3 in both
- 10
S4
- nextS5
- 11
S5
Step 4 — Intersection
- 12
S3 in both
- nextShared committed history
- 13
Shared committed history
Lesson map
Quorums & Majority — Why 2f+1, Read Quorums & Stale Reads
N=2f+1 tolerates f crashes; majority intersection prevents conflicting commits; linearizable reads need ReadIndex/lease not blind follower reads.
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"] c -->|Read key| l l -->|confirm| f f -->|majority ack| l l -->|value at| c c -->|Read key direct| f f -->|possibly old| c
Write quorum in Raft
- Leader must persist an entry on itself + enough followers so that count ≥ majority.
- With N=3, need 2; with N=5, need 3.
- If only a minority is reachable, writes stall (correct CP behavior under partitions).
Odd N is the default: even N wastes a vote without improving f cleanly (N=4 still has f=1, majority=3 — you added a server and made writes harder).
Read quorums & stale reads
Options for reads:
- Read from the leader after confirming leadership (heartbeat to majority / ReadIndex) → linearizable.
- Lease-based reads on the leader → lower latency if clocks/leases are sound.
- Follower / local reads → eventually consistent; fine for monitoring, dangerous for fencing tokens.
Sequence
- 1
Client
Step 1 linearizable read
- 2
Client → Leader
Read key
- 3
Leader → Followers
confirm leadership ReadIndex
- 4
Followers → Leader
majority ack
- 5
Leader → Client
value at commitIndex
- 6
Client
Step 2 stale path avoid for fencing
- 7
Client → Followers
Read key direct
- 8
Followers → Client
possibly old value
Availability vs correctness
| Goal | Correct lever | Wrong lever |
|---|---|---|
| Survive 1 crash | N=3 majority | N=2 |
| Survive 2 crashes | N=5 | Hope + async replication |
| Lower read latency | Lease / ReadIndex | Blind follower reads for money movement |
| Geographic HA | Multi-region etcd with care | Split brain across regions without quorum |
Raft under partition: the minority cannot safely accept writes. That is CAP consistency over availability for those clients — not "Raft is not partition tolerant."
Learners vs voters
etcd learners (and similar non-voting members) replicate the log but do not vote. They do not count toward majority. Adding a learner does not raise f. Counting proxies or learners as voters is a classic ops bug.
Sandbox: majority intersection (Python)
Any two majorities of size f+1 in 2f+1 intersect. Size-2 subsets of 4 can be disjoint — that is the N=4 intuition.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same check (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Why not N=2 for Raft?
Answer
Majority is 2; one failure loses write quorum. You get downtime without true HA. A single node at least fails shut without pretending.
What is f in 2f+1?
Answer
Maximum simultaneous crash failures tolerated while still forming a majority. N=3 → f=1. N=5 → f=2. Byzantine faults are a different algorithm (BFT).
Do read and write quorums both need majority in Raft?
Answer
Writes yes. Linearizable reads need a leadership check equivalent to intersecting the write quorum; raw follower reads do not.
How does quorum relate to CAP?
Answer
Under partition, the minority cannot safely accept writes — Raft chooses consistency over availability for those clients. The majority side still serves.
Can Flexible Paxos reduce live servers?
Answer
Yes for some phases, but production KV consensus stacks usually stick to simple majority for operability. Cite Howard & Mortier; do not implement it in an interview etcd design unless asked.
Stale read example?
Answer
Old leader partitioned; client reads a follower that has not yet received new commits → outdated balance / fencing token. That is why linearizable reads use ReadIndex or a lease.
Does larger N always mean more availability?
Answer
More crash tolerance, but a larger majority (slower / more cross-AZ chatter) and harder ops. N=7 is a choice, not a free lunch.
Intersection with elections?
Answer
A new leader's vote majority must overlap the prior commit majority → committed entries survive (with Raft log up-to-date rules). That is leader completeness, sketched in log replication.
Pitfalls
List two size-3 subsets that intersect on one node. Then try to find two disjoint size-3 subsets of 5 (you cannot). Then show two disjoint size-2 subsets of 4 — that is why N=4 is a trap.