Replication & Quorums

This module is about the part of distributed systems that looks deceptively simple until production traffic, partitions, slow disks, retry storms, and inconsistent replicas make it painful.

A beginner version says: “Use R + W > N.”

A professional version asks:

• Which exact replicas hold the key?
• Which replicas acknowledged the write?
• Which replicas answered the read?
• What does “latest” mean when clocks are imperfect?
• What happens when a replica is down but the system still accepts writes?
• How do stale replicas heal?
• When can a client observe time going backward?

By the end, learners should be able to reason about quorum configurations, implement the core mechanics, and explain the failure modes without hiding behind memorized formulas.

Learning objectives

After this module, a learner should be able to:

1. Explain why replication improves availability and durability but creates consistency problems.
2. Compute read/write and write/write quorum intersection rules.
3. Prove why R + W > N matters using set intersection, not slogans.
4. Predict when a read can return stale data.
5. Implement read repair for stale replicas.
6. Implement hinted handoff and explain why it helps availability but does not magically guarantee consistency.
7. Place replicas on a consistent-hash ring while handling virtual nodes and duplicate physical owners.
8. Compare timestamp-based conflict resolution with version-vector conflict detection.
9. Build anti-entropy repair plans from divergent replica inventories.
10. Detect basic session consistency violations such as monotonic-read and read-your-writes breaks.

The uncomfortable problem replication creates

Suppose one key, user:42, is stored on three replicas:

Replica A: user:42 = "old"
Replica B: user:42 = "old"
Replica C: user:42 = "old"

A client writes a new value:

write user:42 = "new"

If all replicas are reachable and all writes succeed, the story is easy:

A = "new"
B = "new"
C = "new"

Real systems do not always get that story. The actual write may look like this:

A receives "new" and acknowledges
B receives "new" and acknowledges
C times out

Now the cluster contains two versions:

A = "new"
B = "new"
C = "old"

A read that talks only to C returns stale data. A read that talks to A and C sees both and can return the newer one. The problem is not replication itself. The problem is deciding how many replicas are enough for a read or write to be considered successful.

That is what quorums formalize.

The minimum model

For this module, start with this model:

N = replication factor: how many replicas should store each key
R = read quorum: how many replica responses are required for a successful read
W = write quorum: how many replica acknowledgments are required for a successful write

Example:

N = 3
R = 2
W = 2

The write succeeds after any two replicas acknowledge. The read succeeds after any two replicas reply.

This is not the same as saying “always contact exactly two replicas.” A coordinator may contact all replicas and return once two replies arrive. It may keep late responses for repair. It may race replicas to reduce tail latency. The quorum number is the threshold for success.

The three layers learners must separate

Most confusion comes from mixing these layers:

1. Placement layer
   Which replicas are responsible for this key?

2. Write layer
   Which responsible replicas, or fallback replicas, accepted this write?

3. Read layer
   Which replicas answered this read, and how do we merge their answers?

A safe mental model always names the set.

Responsible replicas for key K: {A, B, C}
Write acknowledgments:           {A, B}
Read responses:                  {B, C}
Intersection:                    {B}

The intersection is the bridge. If a successful write and a successful read overlap, the read has at least one path to observe that write.

Quorums are about set intersection

A quorum is a subset large enough that two relevant subsets must overlap.

For read/write safety, every successful read set of size R must overlap every successful write set of size W.

The rule is:

R + W > N

Why?

If a read set and write set did not overlap, they would contain R + W distinct replicas. But there are only N replicas total. If R + W > N, disjoint sets are impossible.

Example:

N = 3, R = 2, W = 2

Any read touches 2 replicas.
Any write touches 2 replicas.
Two sets of size 2 cannot be disjoint inside a 3-replica universe.

Concrete sets:

All possible write quorums: {A,B}, {A,C}, {B,C}
All possible read quorums:  {A,B}, {A,C}, {B,C}

Every pair overlaps.

Counterexample:

N = 3, R = 1, W = 1

Write succeeds on {A}
Read succeeds on {C}
No overlap.
The read can miss the write.

Write/write intersection

Read/write intersection is not the only concern. Two writes can race.

For write/write safety, every successful write set of size W must overlap every other successful write set of size W.

The rule is:

W + W > N

Equivalent:

W > N / 2

If write quorums do not overlap, two writes can both be accepted by disjoint groups. Later, the system must reconcile conflicting histories.

Example with unsafe writes:

N = 4, W = 2

Write X succeeds on {A, B}
Write Y succeeds on {C, D}

Both writes were successful.
No replica saw both.
The system has no natural serialization point.

Example with safe write/write intersection:

N = 5, W = 3

Any two sets of 3 inside 5 must overlap.
At least one replica sees both writes.

Quorum formulas do not solve everything

The formula R + W > N gives an intersection property. It does not automatically give a perfect database.

It assumes the successful write actually made it to a quorum of the responsible replica set. That can become subtle with sloppy quorums and hinted handoff.

It also assumes the read merge logic can identify the latest value. If you use timestamps and clocks are skewed, “latest” may be wrong. If concurrent writes occur, a single timestamp might hide conflict instead of exposing it.

It says little about latency. A read quorum of R=2 might be fast if two nearby replicas reply quickly, or slow if the second response comes from a distant region.

It says little about session behavior. A user can write a value, then be routed to another replica and read an older value unless the client or system preserves session guarantees.

Professional use of quorums is therefore two skills:

1. Know the intersection math.
2. Know what the math is not covering.

Common quorum profiles

Assume N = 3.

For N = 5, common choices include:

The important lesson is that availability and consistency are knobs, not slogans.

Availability math

A read can succeed if at least R replicas are reachable. A write can succeed if at least W replicas are reachable.

So the failure tolerance is:

read failure tolerance  = N - R
write failure tolerance = N - W

With N=3, R=2, W=2:

Reads tolerate 1 failed replica.
Writes tolerate 1 failed replica.

With N=3, R=1, W=3:

Reads tolerate 2 failed replicas.
Writes tolerate 0 failed replicas.

This is why quorum choice is a product decision, not just a technical choice. A timeline service, a shopping cart, a ledger, a chat status indicator, and a bank balance do not deserve the same setting.

Read path

A typical read flow:

1. Coordinator receives GET(key).
2. Coordinator determines responsible replicas for key.
3. Coordinator sends read requests to some or all of them.
4. Coordinator waits until it has R live responses.
5. Coordinator compares versions.
6. Coordinator returns the selected value.
7. Coordinator schedules read repair for stale replicas.

Example:

A -> value="old", timestamp=10
B -> value="new", timestamp=12
C -> timeout

R = 2

The coordinator has two live responses: A and B. It returns "new", then schedules repair for A.

The simplest repair rule:

Any live replica with timestamp < maxTimestamp is stale.

This is intentionally simple. Later in the module, learners see why timestamp-only logic is not enough for concurrent writes.

Read repair

Read repair is opportunistic healing.

During a read, the coordinator notices stale replicas and writes the newest value back to them. This does not require a separate background scan.

Read repair is useful because popular keys get healed naturally. It is insufficient because cold keys may remain stale forever. That is why real systems also use anti-entropy processes.

Read repair is also not free. It adds write traffic to read paths and can amplify load during incidents.

Implementation shape:

Input:
  responses = [(replica, value, version)]

Process:
  choose the highest version
  return its value
  repair any lower-version replica

Output:
  selected value
  list of replicas to repair

Hinted handoff

Hinted handoff handles this situation:

Responsible replicas for key K: A, B, C
B is down.

Instead of failing the write immediately, the coordinator may write to another live node, say D, with a hint:

D stores: value for K, hintFor=B

Later, when B recovers, D replays the hinted write to B.

This improves write availability. But it introduces an important distinction:

Natural responsible replica: B
Temporary holder: D

A read from only responsible replicas may not see data sitting on temporary holders unless the system’s read path accounts for sloppy writes.

That is the key professional nuance: hinted handoff is an availability mechanism, not a magic consistency proof.

Sloppy quorum vs strict quorum

A strict quorum writes only to the key’s responsible replica set.

A sloppy quorum can write to fallback nodes when responsible replicas are down.

Strict quorum mental model:

Responsible replicas: {A, B, C}
Write quorum:         any 2 of {A, B, C}
Read quorum:          any 2 of {A, B, C}

Sloppy quorum mental model:

Responsible replicas: {A, B, C}
B is down
Write accepted by:    {A, C, D}
D holds a hint for B

The write may have enough acknowledgments, but not all acknowledgments came from responsible replicas. This is often acceptable for availability-oriented systems, but learners must understand the tradeoff.

Replica placement

For one key, we talk about N replicas. Across many keys, the system must decide which physical nodes are responsible for each key.

A common model is a hash ring:

0 ------------------------------------------------------ maxHash
       A         B          C          D          A

Each node owns one or more tokens. A key is hashed into the same space. The first token at or after the key hash owns the key, then the next unique physical nodes become additional replicas.

Important details:

1. The ring wraps around.
2. Virtual nodes mean the same physical node may appear multiple times.
3. Replica placement must collect unique physical nodes, not just the next N tokens.
4. Rebalancing changes placement, which can temporarily create mixed ownership.

This is why a “quorum” is not just a number. It applies to a concrete replica set chosen by placement logic.

Latest value: timestamps are a simplification

Many beginner explanations say “return the value with the largest timestamp.” That is useful for learning, but dangerous as a full mental model.

Timestamp-based last-write-wins can lose data.

Example:

Client 1 writes email="a@example.com" at replica A
Client 2 writes phone="123" at replica B

If these are concurrent updates to the same profile object, overwriting one with the other may destroy data.

Physical clocks can also drift:

Replica A clock: 10:00:05
Replica B clock: 10:00:01

A later real-world write on B might have a smaller timestamp than an earlier write on A.

The professional alternative is to track causality.

Version vectors

A version vector records how many updates from each actor or replica are included in a version.

Example:

Version X clock: {A: 2, B: 1}
Version Y clock: {A: 1, B: 1}

X dominates Y because X has seen everything Y has seen, plus more from A.

Another example:

Version X clock: {A: 2}
Version Y clock: {B: 1}

Neither dominates the other. They are concurrent. A system must either surface a conflict, merge semantically, or choose a policy such as last-write-wins.

Dominance rule:

Clock X dominates clock Y if:
  for every actor, X[actor] >= Y[actor]
  and for at least one actor, X[actor] > Y[actor]

The set of non-dominated versions is the frontier. If the frontier has multiple conflicting values, the system has a conflict.

Anti-entropy

Read repair only repairs keys that are read. Anti-entropy repairs divergence proactively.

A simple anti-entropy loop:

1. Replica A and B compare summaries of key ranges.
2. If summaries match, skip the range.
3. If summaries differ, descend into smaller ranges.
4. Eventually identify specific divergent keys.
5. Copy newer versions to the stale side.

Merkle trees are a common way to compare ranges efficiently. This module uses a smaller algorithmic exercise: compare two inventories of key versions and produce a repair plan.

The core idea is the same: replicas do not blindly copy everything. They compare summaries or versions and repair only divergence.

Session guarantees

Even if the system is eventually consistent, a client usually expects basic session sanity.

Two important guarantees:

Read-your-writes:
  After I write version 5 of key K, I should not read version 4 of K.

Monotonic reads:
  After I read version 5 of key K, I should not later read version 4 of K.

These guarantees can be maintained by sticky routing, session tokens, causal metadata, or forcing reads to reach sufficiently fresh replicas.

Without them, users observe time travel:

POST /profile name="Mohamed" -> success
GET /profile -> name is old
refresh
GET /profile -> name is new
refresh
GET /profile -> name is old again

That behavior may be acceptable for some background analytics. It is not acceptable for user-facing workflows that imply confirmation.

Latency and quorum choice

Quorum choice affects tail latency.

Suppose five replicas have these response times:

[8ms, 12ms, 40ms, 120ms, timeout]

With R=1, the read can return after 8ms.

With R=3, the read can return after 40ms.

With R=5, the read fails or waits until timeout.

The Rth fastest live response determines the best-case read completion time when requests are sent in parallel. The same idea applies to write acknowledgments and W.

This is why “just use a bigger quorum” can be expensive.

Professional design checklist

When reviewing or building a replicated service, ask:

1. What is the replica placement algorithm?
2. Are quorums strict or sloppy?
3. What is the write acknowledgment threshold?
4. What is the read response threshold?
5. Does R + W > N hold for the responsible replica set?
6. Does W + W > N hold?
7. How are versions compared?
8. What happens on concurrent writes?
9. Is read repair synchronous or asynchronous?
10. Is there anti-entropy for cold keys?
11. Are hints bounded, expired, replayed, and monitored?
12. What session guarantees are promised?
13. What metrics prove the system is healthy?
14. What is the expected behavior during a partition?
15. Which data classes deserve stronger settings?

Metrics to watch in production

A real system needs metrics that reveal divergence and repair pressure:

quorum_read_success_total
quorum_read_failure_total
quorum_write_success_total
quorum_write_failure_total
read_repair_scheduled_total
read_repair_failed_total
hinted_handoff_pending_total
hinted_handoff_replay_lag_seconds
anti_entropy_ranges_compared_total
anti_entropy_keys_repaired_total
version_conflict_detected_total
session_read_your_writes_violation_total

Metrics are not decorative. They are how operators discover that the system is silently drifting.

Module progression

The problem set deliberately starts small and then removes simplifications:

1. Quorum Intersection
   Learn the math.

2. Quorum Availability Analysis
   Connect math to outage tolerance.

3. Read Repair
   Merge stale replica responses.

4. Quorum Read Plan
   Combine liveness, value selection, repair, and safety.

5. Hinted Handoff Targets
   Handle failed primaries with fallback nodes.

6. Replica Placement Ring
   Find the concrete replica set for a key.

7. Quorum Latency Planner
   See the latency price of larger quorums.

8. Version Vector Conflicts
   Stop pretending timestamps are causality.

9. Anti-Entropy Repair Plan
   Repair cold-key divergence.

10. Session Guarantee Checker
   Detect client-visible consistency failures.

The capstone then asks learners to assemble these pieces into a small Dynamo-style key-value simulator.

What “professional” means here

A professional does not merely know the formulas. A professional can look at an incident like this:

- Region B had packet loss.
- Writes stayed available due to hinted handoff.
- Read repair traffic spiked.
- Some users saw old profile data after successful updates.
- Anti-entropy repaired the cluster six hours later.

And explain:

- which quorum rule was or was not satisfied,
- whether the write was strict or sloppy,
- why the stale read was possible,
- which repair mechanism should have fixed it,
- which session guarantee was violated,
- and what configuration or routing change would prevent it.

That is the standard this module should train toward.