W plus R greater than N

Build a wide-column store (Cassandra / DynamoDB family) (13 scenes)

Scene 08 · W plus R greater than N

Make every read overlap every write on at least one replica by sliding two knobs.

Previously

If we want to be sure a read sees the latest write, we need to count replicas — not trust LWW alone.

Scene 08

Tunable consistency — W + R > N

Watch

Diagram

An RF=3 ring: three replicas hold the featured key. Each replica wears two chips — a blue W chip lit when it's part of the write set, and a green R chip lit when it's part of the read set. **Quorum** is the smallest majority — floor(RF/2)+1, so QUORUM=2 at RF=3. The **consistency level (CL)** is a per-request setting that names a quorum size: ONE, QUORUM, or ALL. The verdict box totals W+R and prints STRONG when their sum exceeds N (overlap guaranteed) or STALE possible otherwise.

W = how many replicas the write must reach

R = how many replicas the read must reach

**quorum**: smallest majority (RF=3 → 2). W+R > N → guaranteed overlap.

verdict: W+R ≤ N → sets may not overlap → stale read possible

Three replicas hold this key. W is the number of replicas a write must reach; R is the number a read must reach. At W=ONE, R=ONE the verdict says STALE possible — the write set and the read set don't have to overlap.

Implementation

Coordinator.put

fan out the write to RF replicas; ack when W reply

1def put(key, value, W):
2    replicas = ring.replicas_for(key)  # RF nodes
3    ts = now()
4    for r in replicas:
5        send_async(r, Write(key, value, ts))
6    # block until W of RF acks come back
7    acks = wait_for(replicas, count=W)
8    if len(acks) < W:
9        return Unavailable
10    return Ack

Coordinator.get

ask R replicas; pick the freshest by timestamp

1def get(key, R):
2    replicas = ring.replicas_for(key)
3    for r in replicas:
4        send_async(r, Read(key))
5    # block until R of RF responses arrive
6    responses = wait_for(replicas, count=R)
7    if len(responses) < R:
8        return Unavailable
9    winner = max(responses, key=lambda x: x.ts)
10    return winner.value

Coordinator.verdict

the geometric condition the verdict box reads off

1def verdict(W, R, N):
2    # any read set of size R and any write set of
3    # size W are subsets of the N replicas; if their
4    # sizes sum to more than N they cannot be disjoint
5    if W + R > N:
6        return 'strong'   # at least one shared replica
7    return 'stale-possible'

PreviousReplicas disagree, then converge NextPartition forces a choice