Distributed databases — sharding strategies, replication: Visual walkthrough

This page is the visual companion to the parent topic. If a word feels new, we define it the moment it appears.

Step 1 — What is a "replica" and what does $N$ count?

WHAT. Imagine your data — say the row user 42 → balance $100 — living not once but as several identical copies. Each copy sits on its own machine. One such copy is called a replica. The total number of replica machines we write the same row to is the number $N$ .

WHY start here. Every symbol in $W + R > N$ counts replicas. Before we can compare $W$ , $R$ , and $N$ , we must agree that they all measure the same kind of thing: boxes that each hold a full copy of the row. $N$ is simply how many boxes there are in total.

PICTURE. Below, $N = 5$ boxes stand in a row. They are identical in shape because each stores the same row. Right now none is special — that comes next.

Figure — Distributed databases — sharding strategies, replication

Step 2 — A write is "touching" a subset of the boxes

WHAT. When a client writes the new value balance $100 → $150, it does not always update all $N$ boxes. It updates $W$ of them and then tells the client "done". The chosen $W$ boxes are the write set, written $S_{W}$ . "Set" here just means the group of boxes we touched — nothing fancier than colouring some boxes in.

WHY a subset and not all. If we insisted on updating all $N$ every time, a single dead box would freeze every write. Touching only $W < N$ boxes lets writes survive some failures. So $W$ is a tunable dial for write fault-tolerance.

PICTURE. Here $N = 5$ and $W = 3$ . The three red boxes are $S_{W}$ — they now hold the fresh value $\$ 150 $. T h e tw o b l a c k b o x ess t i l l h o l d t h es t a l e$ $100$; the write did not reach them yet.

$∣ S_{W} ∣ = W$

$S_{W}$ — the group of boxes the write updated (the red ones).
$∣ S_{W} ∣$ — the size of that group, i.e. how many boxes are in it; the two vertical bars mean "count the elements".
$W$ — the number we chose; here $3$ .

Step 3 — A read also touches a subset

WHAT. To read, the client asks $R$ boxes for their copy. That group is the read set $S_{R}$ , with $∣ S_{R} ∣ = R$ . The reader collects whatever values those $R$ boxes report.

WHY only $R$ and not all. Same reason as writes: asking every box would stall on a single slow machine. $R$ is the read fault-tolerance / speed dial.

PICTURE. Same 5 boxes. The write from Step 2 left boxes 1–3 fresh (we redraw them lightly). Now a read with $R = 2$ asks boxes 4 and 5 — the red-outlined ones. Notice the danger: both of those boxes are stale. The reader would answer $\$ 100 $, mi ss in g t h e n e w er$ $150$.

WHAT. We have two coloured groups inside the same $N$ boxes: $S_{W}$ (freshly written) and $S_{R}$ (just read). A read is guaranteed fresh iff at least one box belongs to both groups — because that shared box carries the new value into the read.

WHY "iff overlap". If the groups touch, the reader sees the new value in the shared box and (using version numbers) keeps the newest — fresh guaranteed. If they can be made disjoint, then in the worst case the reader sees only stale boxes — no guarantee. So the entire problem reduces to one geometric question: can these two coloured regions be pried apart inside $N$ boxes?

PICTURE. Two scenarios side by side. Left: $S_{W}$ and $S_{R}$ overlap in the red shared box — the read sees fresh data. Right: they are disjoint — the read misses the write.

Step 5 — Pigeonhole: when are two subsets forced to overlap?

WHAT. We now find the exact condition on the numbers $W$ , $R$ , $N$ that makes overlap unavoidable, no matter how an adversary places the sets. This is a counting argument called the pigeonhole principle: if you try to fit more items into slots than there is room to keep them separate, some must collide.

WHY this tool and not another. We don't want a rule of thumb — we want a guarantee against the worst case. Pigeonhole is exactly the tool that answers "is separation impossible?" rather than "is overlap likely?". Probability would only give "usually"; pigeonhole gives "always".

PICTURE. Picture the $N$ boxes as a line of length $N$ . Lay the $W$ write-boxes as far left as possible and the $R$ read-boxes as far right as possible — the adversary's best attempt to keep them apart. If $W + R$ exceeds $N$ , the two blocks physically cannot fit without a box doing double duty (shown in red as the forced overlap).

Formally, the minimum possible overlap of a $W$ -subset and an $R$ -subset inside an $N$ -set is:

$∣ S_{W} \cap S_{R} ∣ \geq W + R - N$

$W + R$ — total "box-slots demanded" if we could keep them separate.
$N$ — total slots available.
$W + R - N$ — the spill-over: how many demands cannot find their own private slot and are forced to share. If this is $\leq 0$ the blocks fit apart; if it is $\geq 1$ they must overlap.

Step 6 — Combine: the boxed rule falls out

WHAT. We required overlap $\geq 1$ (Step 4). Pigeonhole says the guaranteed overlap is at least $W + R - N$ (Step 5). To force the guarantee, set the guaranteed minimum to satisfy our requirement:

$W + R - N \geq 1 ⟺ W + R > N$

$W + R - N \geq 1$ — "the forced overlap is at least one box."
$⟺$ — "means exactly the same as."
$W + R > N$ — strictly greater; add $N$ to both sides of $W + R - N \geq 1$ to get $W + R \geq N + 1$ , which for whole numbers is the same as $W + R > N$ .

WHY strictly greater and not $\geq$ . If $W + R = N$ exactly, the spill-over is $0$ — the adversary can line the blocks up disjointly (the failing right-hand case of Step 4). Equality is not enough; we need to tip past $N$ .

PICTURE. A number line for $N = 5$ . Everything left of the line " $W + R = 5$ " (like $2 + 2 = 4$ ) is the unsafe zone; everything strictly right (like $2 + 2$ ... no — $3 + 3 = 6$ , or $3 + 2 = 5$ ? watch out) is safe. The red mark sits at the boundary $W + R = N$ , the exact place where the guarantee is born.

Step 7 — Every case, checked against the rule

WHAT. We test the three configurations the parent note named, plus the degenerate extremes, so no scenario surprises the reader. Take $N = 3$ .

$W$	$R$	$W + R$	$> N$ ?	Meaning
$2$	$2$	$4$	✓	strong + tolerates 1 node down on both sides (default)
$3$	$1$	$4$	✓	reads super-fast; writes fail if any node is down ( $W = N$ )
$1$	$3$	$4$	✓	writes fast; reads must hit all → no read fault-tolerance
$1$	$1$	$2$	✗	fast but can read stale — sets may miss entirely

Degenerate cases (WHY they still obey the rule):

$W = N, R = 1$ : $N + 1 > N$ ✓ always — but a single dead replica blocks all writes. The rule guarantees freshness, not availability.
$W = 1, R = N$ : mirror image — reads become fragile.
$W = 0$ (write acknowledges touching nothing): then $∣ S_{W} ∣ = 0$ , the write set is empty, overlap is impossible — no read is ever fresh. The rule $0 + R > N$ needs $R > N$ , impossible, correctly flagging this as broken.

PICTURE. The safe region drawn as a shaded triangle on a $W$ – $R$ grid for $N = 3$ : the red line $W + R = N$ is the border, the shaded corner above it is every legal quorum, the three example dots sit inside it and the stale $(1, 1)$ dot sits below.

The one-picture summary

The whole derivation in one frame: $N$ boxes, a red write set of size $W$ pushed left, a read set of size $R$ pushed right, and the red forced-overlap box that appears precisely when $W + R$ crosses $N$ . That single shared box is the entire guarantee.

Recall Feynman retelling — explain it to a friend in plain words

We keep several identical copies of a row on separate machines — call the count $N$ . When we save a change, we don't bother updating all of them; we update $W$ and stop. When we read, we ask $R$ of them and take the newest answer. Now here's the only trick: a read is guaranteed to see the newest write only if the group we wrote and the group we read are forced to share at least one machine — because that shared machine is the messenger carrying the fresh value. Whether they're forced to share is pure counting: two blocks of sizes $W$ and $R$ shoved into $N$ slots can only stay apart while $W + R$ fits inside $N$ . The instant $W + R$ pokes past $N$ , at least one slot must serve both — overlap becomes unavoidable — and freshness is guaranteed. That is all $W + R > N$ says. Bump $N$ up by adding replicas and you must read or write more to keep the sum above $N$ , which is why "more copies" is not automatically "safer".

Recall Quick self-test

Why is $W + R = N$ (equality) not safe? ::: Forced overlap is $W + R - N = 0$ , so the sets can be made disjoint — a read may land entirely on stale replicas. What principle forces the overlap? ::: The pigeonhole principle: two subsets of sizes summing past $N$ cannot fit inside $N$ slots without sharing one. With $N = 5$ , is $W = 4, R = 2$ safe? ::: $4 + 2 = 6 > 5$ ✓ yes, overlap $\geq 1$ .

Related: CAP Theorem (why you sometimes choose to break the quorum for availability), Replication Lag and Read-Your-Writes (what stale reads feel like in practice), and back to the parent topic.