System Design Replication
Quorum
Friday 6:12 PM: checkout must not show a stale balance, but the recommendation feed next to it can. Both hit the same replicated store. The difference is how many copies must agree before the user gets an answer.
is that dial: pick , , and per operation so freshness, latency, and availability match the product rather than a cluster slogan.
Overlap journey
Enough replicas acknowledge the new version before the write is treated as done.
The read set must overlap a completed write so at least one replica is fresh.
Wait for R answers, compare versions, and return the newest comparable value.
Push the winning version to stale peers in the background after the read.
Try it: tune quorum W, R, and N
Each replica stores a version label for one key. A write needs W acknowledgements from the live set; a read waits for R responses and returns the highest timestamp. Toggle replicas down to see availability trade-offs.
- R + W > N
- No
- Live replicas
- 5
- Last read
- —
- Next write label
- v2
Replica A
livev1
Replica B
livev1
Replica C
livev1
Replica D
livev1
Replica E
livev1
Set N, W, and R, then mark replicas down to see when writes and reads succeed. R + W > N is the classic overlap rule for strict quorums.
Find the overlap. With N=5, W=3, R=3, any two quorums share at least one replica, which is why a completed write can appear on a later read when versions are comparable.
Stress failures. Mark two replicas down and try W=3. The write should fail while R=2 may still succeed on the remaining three, returning the last committed value.
What actually happens
Start with the checkout path above and slow it down. With N=3, W=2, R=2, a write stores version v2 on replicas A and B. A later read of B and C may see {v2, v1}. The client returns v2 and repairs C. That overlap is why helps you observe a completed quorum write when replica sets are strict and versions are comparable. It is not a free linearizability proof (single-copy real-time behavior).
Latency follows the nth-fastest replica: R=2 waits for the second response; W=3 waits for the third ack. Higher quorums make slow replicas matter more to p99 (the slow end of the latency distribution).
plus keep accepting writes when owners are down. Availability rises; treat freshness guarantees as weaker until handoff and complete.
Correctness invariant for money-like paths with strict membership: after a completed write with W acks, a subsequent read with R responses (R + W > N, comparable versions) must observe that write or fail, not silently invent a newer history. Overlap alone does not guarantee linearizability. You still need version comparison, intended replica sets (not sloppy stand-ins), and stronger real-time machinery for single-copy semantics.
The same N=3, W=2, R=2 story as a four-step path: write, overlap, read, then client merge.
Write quorum W=2
A and B store v2
Overlap on replica B
R + W > N
Read quorum R=2
B returns v2, C returns v1
Client picks latest version
How to choose N, R, and W
Once you see that overlap is a dial, three questions decide where to set , , and .
1. Is stale data dangerous? Payments and inventory usually need . Feeds and analytics often allow R=1 or W=1 when eventual consistency is fine.
2. Where do users live? Prefer for regional latency; accept that other regions may lag until cross-region repair.
3. Can you fail open? keeps writes alive during outages; fails rather than weaken overlap.
Simple rule of thumb
N=3, R=2, W=2 is a useful starting example for overlapping replica sets, not sufficient protection for money or inventory. A balance update needs an atomic rule such as “debit only when the resulting balance is valid”, and concurrent callers must not both act on the same old value. Use a store with the required conditional-write or transaction guarantees, then explain how its replication protocol provides those guarantees. Relax read freshness separately for counters or feeds that tolerate lag.
The R + W > N formula
The choice section picks numbers; this is what those letters mean and what overlap does (and does not) buy you.
Number of replicas in the intended set for a key.
Minimum replicas that must acknowledge a write.
Minimum replicas that must answer a read.
→ quorum-write overlap
With N=3, W=2, and R=2, the sum exceeds N, so any two-member read set intersects any two-member acknowledged write set. If A and B store v2, reading B and C exposes v2 and possibly an older v1. The coordinator must compare versions and handle concurrent or partially completed writes according to the protocol. Reading only C with R=1 can return v1; waiting for more replicas is useful only when the returned versions are interpreted correctly.
What else linearizability needs
- Comparable versions (or a total write order) so the client can name the newest value.
- on the intended set; weakens overlap until repair finishes.
- Real-time single-copy behavior usually needs a primary or consensus path, not R/W counts alone.
Common configurations and numbers to know
With the formula in hand, these are the usual N/W/R presets and a payment-path capacity sketch using the same N=3, R=2, W=2 starting point from the rule of thumb above.
Strong (3 / 2 / 2)
Financial and inventory paths; tolerates one replica failure while keeping write-read overlap.
Write-heavy (3 / 1 / 3)
Logging and ingestion: fast writes, then strong reads that wait for all three.
Read-heavy (3 / 3 / 1)
Config data: durable writes to all replicas, then any single fresh read.
Eventual (3 / 1 / 1)
View counts and analytics where R+W ≤ N and stale reads are acceptable.
Majority (5 / 3 / 3)
Raft/Paxos-style majority; tolerates two failures with R+W greater than N.
Local quorum
Regional freshness with lower latency; remote regions may lag until repair.
Numbers to know
N=3 replicas, payment path wants R=2, W=2. Steady 5k reads/sec and 500 writes/sec.
Assume three intended replicas, 500 logical writes per second, and 5,000 reads per second. W=2 describes the acknowledgement threshold; a coordinator may still send every write to all three replicas, producing 1,500 replica write applications per second. If it contacts exactly two replicas for each read, that is 10,000 read requests; contacting all three and returning after two would generate 15,000. Separate requests sent from responses awaited when estimating capacity.
With strict membership, losing one replica leaves two reachable replicas and permits R=2 and W=2 operations. Losing two prevents these operations from reaching their thresholds. Lowering a feed read to R=1 can improve latency and failure tolerance, but it may contact the only replica that missed the latest write. A successful response and a fresh response are different requirements.
Worked timelines
The presets above are easier to trust when you walk a few write/read paths and failure budgets side by side.
| Config | Write path | Read path | Result |
|---|---|---|---|
| N=3, W=2, R=2 | A,B store v2 | B=v2, C=v1 | Return v2; repair C |
| N=3, W=1, R=1 | A stores v2 | C may return v1 | Fast; stale allowed |
| N=5, W=3, R=2 | A,B,C store v2 | D,E may both be v1 | R+W=N → no guarantee |
| Sloppy quorum | Temps accept write | Owners may lack v2 | Availability up; overlap weak |
| N / W / R | Write failures tolerated | Read failures tolerated | Freshness note |
|---|---|---|---|
| 3 / 2 / 2 | 1 | 1 | Overlap if versions comparable |
| 3 / 1 / 1 | 2 | 2 | Stale reads until repair |
| 3 / 3 / 1 | 0 | 2 | Any single read fresh after write |
| 5 / 3 / 3 | 2 | 2 | Majority; R+W>N |
| 5 / 3 / 2 | 2 | 3 | R+W=N → stale pair possible |
Write v2 acked by A,B (C still on v1).
Fresh path: read B+C → {v2,v1} → return v2, repair C.
Stale if you cheat with R=1 and only hit C → v1.
After A dies: W=2 still works on B+C; R=2 still works.
Two dead → quorum writes/reads fail.Failure timeline, and what still breaks after the fix
Putting the tables together, here is how overlap can look fine on paper while linearizability still fails, then the strict versus sloppy choice, majority votes for leaders, and the latency/availability trade-offs at scale.
Timeline: overlap without linearizability
T0 Client writes v2; W=2 acks from A,B (C still v1). R+W>N satisfied for completed write T1 Concurrent client starts a read that contacts B (v2) slowly and C (v1) quickly T2 Sloppy path earlier parked a write on temp node D; owners A/B not yet repaired T3 Another read hits D+C with incomparable or incomplete versions → stale or conflicting view T4 Overlap math looked fine on paper; real-time single-copy (linearizability) still fails Fix Compare versions; prefer strict quorum for money; use primary/consensus when you need linearizability
Counterexample to "R + W > N means linearizable": overlap is a necessary condition for seeing a completed quorum write under Dynamo-style assumptions, not the Herlihy & Wing real-time model by itself.
vs
A strict write succeeds when W distinct members of the designated replica set acknowledge it. It does not require every designated member to be reachable: N=3 and W=2 can still succeed with one member down. If fewer than W are reachable, the operation waits within its deadline or fails instead of silently substituting unrelated nodes. Membership changes require special care because the overlap argument assumes everyone agrees on the relevant replica set.
Sloppy: temps hold writes via until owners recover; availability rises.
: A=42, C=41 with R=2 → return 42, background-fix C.
Majority for leader election
With five voters, a majority is three and any two majorities share at least one voter. If every voter durably grants at most one vote per term, two candidates cannot both win in that term. Across different terms, additional log-freshness and commitment rules preserve history. A partition of two nodes versus three lets only the three-node side form a new majority, but the isolated old leader may still believe it leads until the protocol detects its loss of authority.
Still fails when…
- Sloppy stand-ins accept writes outside the intended set until handoff and repair finish.
- Cross-region quorum makes p99 latency user-visible even when overlap math is satisfied.
- Read repair storms hot keys after recovery when many stale peers catch up at once.
Trade-offs
- R=1 is the fastest single reply; R=2 waits on the 2nd-fastest; R=3 waits on the slowest.
- For N=3: W=1 tolerates two failures; W=2 tolerates one; W=3 tolerates zero.
- Choose per-operation guarantees: transactional or conditional updates for balances and stock; weaker replica reads may suit profiles and feeds. A QUORUM label alone does not enforce business invariants.
From the basic idea to a production design
Beginner explanation
For each operation, choose how many replicas must agree before the user gets a response. More agreement gives fresher data but raises latency and lowers availability.
Advanced answer
Discuss replication factor, local vs cross-region quorum, read repair, hinted handoff, timeout budgets, and whether the quorum rule actually overlaps under the failure model you chose.
What to watch in production
- Pick consistency level per API path
- Monitor tail latency by consistency level
- Track unavailable replicas and repair backlog
- Document regional failover behavior
Questions worth answering
- What are N, R, and W for this workload?
- Can the system accept writes during a partition?
- How do stale replicas get repaired?
Failure modes to cover
- Sloppy quorum weakens expected overlap
- Cross-region quorum makes p99 latency unacceptable
- Read repair overloads hot keys after recovery
Choosing and explaining quorum
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
Define N, R, and W before discussing consistency guarantees.
R + W > N gives overlap for observing a completed quorum write only when reads and writes go to the intended replica set. It is not linearizability by itself.
Use tunable consistency per operation: stronger for money and inventory, weaker for feeds and analytics.
When it belongs
The system stores replicated data and can read from multiple replicas.
The interviewer asks how stale reads are prevented or tolerated.
A partition should trade off availability against freshness explicitly.
How it fails
Sloppy quorum writes land outside the normal replica set.
Read repair creates hot-key load after recovery.
Cross-region quorum makes p99 latency user-visible.
Trade-offs to weigh
Higher R or W increases freshness but lowers availability.
Local quorum improves latency but weakens global freshness.
Strong reads cost more capacity than eventually consistent reads.
Common misunderstandings
Claiming R + W > N guarantees linearizability.
Forgetting version comparison and conflict resolution.
Treating quorum overlap and leader consensus as the same thing.
Going deeper
Quorum
The mechanism and its boundary
Quorum reads and writes choose how many replicas must participate before an operation succeeds. The overlap rule gives freshness only when the read and write sets really intersect and versions can be compared.
Read/write overlap
Write W replicas
Read R replicas
Overlap node
Pick newest version
Work through the sizing assumptions
When it belongs
Data is replicated and reads can choose among replicas. The design needs tunable freshness, latency, and availability. You can explain conflict repair for stale replicas.
Assumptions that matter
Replica placement and quorum scope are known. Version comparison is deterministic. Timeouts are tuned so slow replicas do not dominate every read.
Easy mistakes
The inequality R + W > N establishes set overlap, not a complete consistency protocol; reads still need to identify the relevant version and handle concurrent or incomplete writes. Sloppy quorums and hinted writes may acknowledge substitute nodes outside the usual replica set, so the simple overlap argument no longer follows from the numbers alone. A quorum spanning regions pays for the required distant responses, so include that network delay before promising a low-latency user read.
How it fails
Read repair overwhelms hot keys after recovery. A partition leaves one side unable to reach quorum. Stale replicas return old versions when reads use low R.
Trade-offs to name
Increasing R or W improves read-write overlap under fixed replica-set and versioning assumptions, but requires more reachable replicas and can increase the latency of completion. A local quorum avoids distant acknowledgements and therefore helps regional latency, while leaving a separate question of when another region can observe that write. Small read and write requirements can keep operations available through more failures, but permit more stale observations and make a reliable repair process essential.
Wrap-up
You have seen the dial, the overlap rule, and the ways it still fails. Use these exercises to check the ideas stuck, then follow the references for the primary sources.
Exercises
- Pick N/R/W for two APIs. Payment balance read and public like-count share one cluster with N=3. Choose R and W for each, state whether R+W>N, and name the user-visible failure when one replica dies.
- Sloppy quorum review comment. A design enables "for availability" on inventory. Write the review comment that explains how overlap assumptions weaken until finishes, and what you would require instead for sold-stock.
- Latency budget. Replica latencies are 5ms, 12ms, 80ms. For R=1, R=2, and R=3, estimate the wait for the read quorum and decide which setting breaks a 50ms p99 SLO.
Topic-specific references
- DeCandia et al., Dynamo (SOSP 2007) : N/R/W, sloppy quorum, and hinted handoff in a production AP store.
- Herlihy & Wing, "Linearizability" : the real-time single-copy model quorum overlap does not automatically buy.
- Cassandra consistency levels : concrete R/W knobs and local vs multi-DC quorum.
Key takeaway
Quorum is a per-operation dial: R + W > N for overlap when replica sets are strict, weaker settings when speed matters more than freshness, sloppy quorum when availability must win briefly, and read repair to heal what drifted. Name N, R, and W before promising consistency, and do not call overlap linearizability.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Reason about N/R/W, partial and sloppy quorums, hinted handoff, read repair, kth-response latency, conflicts, and the limits of overlap.
Explain the decision
Why does R + W > N not alone guarantee linearizability?
Read the reasoning
Clock/version, coordinator, concurrent-write, sloppy-quorum, failure, and read-repair semantics still determine whether the newest write is observed.
Apply it to a production scenario
A sloppy quorum writes to fallback nodes during partition. What happens after recovery?
Read one approach
Hinted handoff moves versions to intended owners, conflicts are reconciled, and tombstone/version rules prevent resurrection.
Work through the numbers
For N=5, W=3, R=3, how many replicas may be unavailable for both operations?
Read the worked calculation
Two, assuming the same reachable set can satisfy each; latency is the third response.
Reason through a failure
What must read repair preserve?
Read the recovery reasoning
It propagates a causally newest/merged version and never overwrites a concurrent version solely because its response arrived later.