Distributed databases — sharding strategies, replication: Worked examples

This page leans on tools you already met:

mod (the remainder operator): $a mod N$ is "the remainder when $a$ is divided by $N$ ". It answers "which of the $N$ numbered bins does $a$ fall into?" — that's exactly the question hash sharding asks.
The ring of Consistent Hashing: a circle of positions $[0, 2^{m})$ where a key belongs to the first node clockwise.
The pigeonhole principle behind quorums: if two sets are big enough, they must share an element.

The scenario matrix

Every problem in this topic is one of these cells. Read it top to bottom before any example.

#	Case class	What makes it "special"	Covered by
C1	Naive `mod N` resharding	measure fraction that moves as $N \to N + 1$	Ex 1
C2	A specific key under `mod` reshard	sign of "does THIS key move?" (add AND remove)	Ex 2
C3	Consistent-hashing add node	one arc moves — interior AND wrap	Ex 3 (figure)
C4	Consistent-hashing remove node	mirror case — interior AND wrap	Ex 4 (figure)
C5	Quorum — the healthy default	$W + R > N$ strictly	Ex 5
C6	Quorum — degenerate $W + R = N$	boundary: overlap can be zero	Ex 6
C7	Quorum — limiting $W = N$ or $R = N$	one extreme node = no fault tolerance	Ex 7
C8	Range-shard hotspot (zero-spread input)	all keys land in one bin	Ex 8
C9	Real-world word problem	pick topology + quorum for a business	Ex 9
C10	Exam twist	"safer replicas" trap — bigger $N$ breaks quorum	Ex 10

C1 — Naive `mod N` resharding, the whole dataset

Worked example Ex 1 · Fraction moved growing 6 → 7 shards

You run $N = 6$ shards with $600, 000$ keys and add a 7th. Under shard = hash(k) mod N, roughly how many keys must move?

Forecast: (cover the next line and guess first) — is it most of them or few of them? Answer to the forecast: almost all of them — around $6/7$ of the dataset. Now let's see why.

Here $f_{moved}$ (read "f-moved") is just a name for the fraction of keys that are forced to change shards — a number between $0$ (nobody moves) and $1$ (everybody moves). We'll build it from scratch.

Step 1 — Derive WHY a key rarely stays. Why this step? Before trusting the formula we must see where it comes from, not memorize it. A key $k$ stays only if its bin number is unchanged: $hash (k) mod N = hash (k) mod (N + 1) .$ After the change there are $N + 1$ possible bins. For a "random-looking" hash value, the new bin $hash (k) mod (N + 1)$ is equally likely to be any of the $N + 1$ residues. It coincides with the old bin only in the one lucky case out of $N + 1$ . So: $P (stays) \approx \frac{1}{N + 1}, f_{moved} = 1 - P (stays) \approx 1 - \frac{1}{N + 1} = \frac{N}{N + 1} .$

Figure — the bin lottery. The bar chart below draws every possible new bin as a column of equal height (each new bin is equally likely for a random hash). Exactly one green column is the key's old bin — the "stays" outcome. All the red columns are "moved" outcomes. Because there are $N$ red columns for every $1$ green, you can see that $f_{moved} = \frac{N}{N + 1}$ is just "red columns over total columns".

Figure — Distributed databases — sharding strategies, replication

C2 — Does this specific key move? (add AND remove)

Worked example Ex 2 · One key's fate, both directions

A key hashes to $hash (k) = 97$ . (a) You add a shard: $N : 4 \to 5$ . (b) Separately you remove one: $N : 4 \to 3$ . Does the key move in each?

Forecast: (cover the next line and guess first) — the answer is binary each time: moves or stays. Same answer both directions? Answer to the forecast: no — it moves when we add but stays when we remove. Here's the arithmetic.

Step 1 — Old shard (baseline for both). Why this step? Its current home is $97 mod 4$ . $97 mod 4 = 1 (since 4 \times 24 = 96, 97 - 96 = 1) .$

Step 2 — (a) After adding, modulus is $5$ . Why this step? Compare new bin to old. $97 mod 5 = 2 (5 \times 19 = 95) . 1 \neq = 2 \Rightarrow moves (1 \to 2).$

Step 3 — (b) After removing, modulus is $3$ . Why this step? The mirror case tests the same "old vs new bin" logic in reverse. $97 mod 3 = 1 (3 \times 32 = 96) . 1 = 1 \Rightarrow stays (bin 1).$

Verify: Direction matters per key: this key moved when we grew but stayed when we shrank — pure luck that $97 mod 3$ landed back on $1$ . Counter-check a stayer for the add case: $hash = 100$ gives $100 mod 4 = 0 = 100 mod 5$ , so it stays under add. Both signs of the outcome exist in both directions. ✓

C3 — Consistent hashing: add a node (interior AND wrap)

Figure — the ring with the stolen arc highlighted. The left panel shows the interior insert: the four blue nodes sit at $0, 25, 50, 75$ , and the red arc $[50, 60)$ is the slice the new green node E now owns. The right panel shows the wrap insert: green node F at $90$ grabs the red arc $[75, 90)$ , while the tiny slice $[90, 100)$ (drawn continuing toward the yellow $0$ -marker at the top) still walks clockwise across $0$ to node $0$ . The yellow arrow shows the clockwise direction; the yellow dot at the top is position $0$ , the wrap point.

Worked example

Forecast: (cover the next line and guess first) — in the wrap case, does F steal keys from the top arc, and does "clockwise" still work when it crosses $0$ ? Answer to the forecast: yes and yes — F takes exactly one arc $[75, 90)$ , and the clockwise rule crosses $0$ with no special-casing. Watch:

Recall the one rule: a key belongs to the first surviving node clockwise; keep walking across $0$ if needed. Every step below is just this.

Step 1 — (a) interior: who owned around 60? Why this step? By the rule, keys walk clockwise to the first node. Keys in $[50, 75)$ hit node $75$ first, so node $75$ owned them. E at $60$ inserts inside that arc, so keys in $[50, 60)$ now hit E first. $\frac{60 - 50}{100} = 0.10 \Rightarrow 0.10 \times 400, 000 = 40, 000 keys move to E.$

Step 2 — (b) wrap: who owned the top arc? Why this step? Apply the rule at the top of the ring. A key at position $80$ walks clockwise: it passes $81, 82, \dots, 99$ , finds no node, crosses $0$ , and lands on node $0$ . So before F is added, node $0$ owned the whole arc $[75, 100)$ — the interval from node $75$ (excluded) up to $100$ , which then wraps to node $0$ . There is no singleton or special point; the half-open arc $[75, 100)$ is just "everything after node $75$ until the wrap".

Step 3 — (b) size F's stolen arc. Why this step? F sits at $90$ , inside that top arc. Now a key at $80$ walks clockwise and meets F at $90$ before ever reaching $0$ . So F takes the sub-arc $[75, 90)$ . $\frac{90 - 75}{100} = 0.15 \Rightarrow 0.15 \times 400, 000 = 60, 000 keys move to F.$ Keys in $[90, 100)$ still find no node before $100$ , so they cross $0$ to node $0$ — the wrap is intact; F only shortened the walk for the $[75, 90)$ slice.

Verify: Both cases move exactly ONE arc. Interior (E): $40, 000$ . Wrap (F): $60, 000$ . The wrap case used the same clockwise rule — nothing new. Why is the benchmark $\frac{1}{N + 1}$ ? Because if all $N + 1$ nodes were spread perfectly evenly, they would cut the ring into $N + 1$ equal arcs, so the one new arc would be exactly $\frac{1}{N + 1}$ of the ring. Here $N = 4$ , so the ideal is $\frac{1}{5} = 0.20$ (i.e. $80, 000$ keys). Our two answers ( $40, 000$ and $60, 000$ ) differ from that only because the manual positions $0, 25, 50, 75, 90$ are not evenly spaced — proving the formula is the even-spacing ideal, not a hard law. ✓

C4 — Consistent hashing: remove a node (interior AND wrap)

Figure — the ring after a node dies. The left panel marks node $25$ with a red ✗ and colours its orphaned arc $[0, 25)$ green; a green arrow shows those keys flowing clockwise to the next survivor, node $50$ . The right panel marks the top node $75$ dead; its orphaned arc $[50, 75)$ (green) has no survivor before the top, so the green arrow curves clockwise across the yellow $0$ -marker to reach node $0$ . Both panels are the same clockwise rule — only the receiving node differs.

Worked example

Forecast: (cover the next line and guess first) — when the top node dies, do its keys wrap around past $0$ to node $0$ ? Answer to the forecast: yes — they walk clockwise, find nothing before $100$ , cross $0$ , and land on node $0$ . Same rule as always.

Recall the one rule: first surviving node clockwise, crossing $0$ if needed. Removal just deletes a node and re-runs the walk.

Step 1 — (a) interior: what did node-25 own? Why this step? By the rule, a node owns the arc from the previous node up to itself: node $25$ owned $[0, 25)$ . With $25$ gone, those keys walk clockwise to the next survivor. $first survivor clockwise = node 50. \frac{25 - 0}{100} = 0.25 \Rightarrow 100, 000 keys \to node 50.$

Step 2 — (b) wrap: what did node-75 own? Why this step? Node $75$ owned the arc from the previous node $50$ up to itself: $[50, 75)$ . $keys in [50, 75) are now orphaned — re-run the clockwise walk.$

Step 3 — (b) count and confirm the wrap. Why this step? The first live node clockwise from $[50, 75)$ is no longer $75$ ; continuing past $75, 76, \dots, 99$ we find nothing, so we cross $0$ and reach node $0$ . $\frac{75 - 50}{100} = 0.25 \Rightarrow 0.25 \times 400, 000 = 100, 000 keys \to node 0 (via the wrap).$

Verify: In both removals exactly one arc's worth ( $100, 000$ keys) relocates, and the only difference in the wrap case is that the receiving node is found by crossing $0$ . "First surviving node clockwise" is the single rule that covers interior and wrap, add and remove alike. ✓

C5 — Quorum: the healthy default

Worked example Ex 5 · Standard strong-read setup

$N = 5$ replicas. You pick $W = 3, R = 3$ . Is read-your-writes guaranteed? How many node failures survive?

Forecast: (cover the next line and guess first) — does $W + R > N$ hold, and by how much overlap? Answer to the forecast: yes, $6 > 5$ , and the read and write are forced to share at least $1$ replica.

Define the sets first. When you perform a write, you send it to some specific group of $W$ replicas — call that group $S_{W}$ (the "write set", size $W$ ). When you perform a read, you query some specific group of $R$ replicas — call that group $S_{R}$ (the "read set", size $R$ ). Both are just subsets of the $N$ replicas: $S_{W}$ is the ones that got the new value, $S_{R}$ is the ones we ask. The whole quorum question is: must these two groups overlap?

Step 1 — Test the quorum inequality. Why this step? The whole guarantee is $W+R>N$. $W + R = 3 + 3 = 6 > 5 = N . ✓$

Step 2 — Minimum overlap (pigeonhole). Why this step? The overlap $∣ S_{W} \cap S_{R} ∣$ — the count of replicas that are in both the write group and the read group — tells us how strongly the read is guaranteed to see the write. Pigeonhole forces: $∣ S_{W} \cap S_{R} ∣ \geq W + R - N = 6 - 5 = 1 replica shared.$ That one shared replica has the newest value, so the read can find it.

Step 3a — Write-side fault tolerance (derive separately). Why this step? A write succeeds only if it can gather $W$ live replicas. With $N$ total, at most $N - W$ can be dead while still leaving $W$ alive: $write survives N - W = 5 - 3 = 2 failures.$

Step 3b — Read-side fault tolerance (derive separately). Why this step? A read likewise needs $R$ live replicas, tolerating $N - R$ dead: $read survives N - R = 5 - 3 = 2 failures.$

Step 3c — Combine. Why this step? The system's both-ops tolerance is the smaller of the two, i.e. $min (N - W, N - R) = N - max (W, R)$ . $min (2, 2) = 2 = N - max (W, R) = 5 - 3.$

Verify: Overlap $\geq 1$ means at least one replica has both the write and answers the read → newest version wins. Write tolerates 2, read tolerates 2, so the whole system tolerates 2. ✓

C6 — Degenerate boundary: $W + R = N$

Worked example Ex 6 · The knife-edge that fails

$N = 4$ , $W = 2$ , $R = 2$ . Read-your-writes guaranteed?

Forecast: (cover the next line and guess first) — $2 + 2 = 4$ ; is "equal" good enough? Answer to the forecast: no — equality is the failure edge; stale reads become possible.

Step 1 — Test strictness. Why this step? The rule is a strict inequality $W + R > N$ , not $\geq$ . $W + R = 4 \neq > 4 = N .✗$

Step 2 — Show a stale read is possible. Why this step? At the boundary, minimum overlap is $W + R - N = 0$ — the write set $S_{W}$ and read set $S_{R}$ can miss entirely. Write to replicas ${1, 2}$ , read from ${3, 4}$ : no shared node.

Step 3 — Conclusion. Why this step? Zero guaranteed overlap ⇒ the read may see the old value. $NOT guaranteed — stale reads possible.$

Verify: This is the degenerate case the parent's $W = R = 1, N = 3$ example warned about, generalized: equality is the failure edge. Bump $R$ to $3$ → $2 + 3 = 5 > 4$ → fixed. ✓

C7 — Limiting values: $W = N$ and $R = N$

Worked example Ex 7 · Both extremes of the quorum dial

$N = 3$ . Compare (a) $W = 3, R = 1$ and (b) $W = 1, R = 3$ . Consistency and fault tolerance of each?

Forecast: (cover the next line and guess first) — which extreme kills write availability, which kills read availability? Answer to the forecast: (a) $W = N$ kills write availability; (b) $R = N$ kills read availability.

Step 1 — Both satisfy the rule. Why this step? Confirm consistency first. $(a) 3 + 1 = 4 > 3 ✓ (b) 1 + 3 = 4 > 3 ✓$

Step 2 — (a) $W = N = 3$ : write tolerance. Why this step? Needing all $3$ replicas to ack a write means any node down blocks writes. $write survives 3 - 3 = 0 failures — reads survive 3 - 1 = 2.$

Step 3 — (b) $R = N = 3$ : read tolerance. Why this step? Symmetric extreme — reads need all $3$ , so any node down blocks reads. $read survives 3 - 3 = 0 failures — writes survive 3 - 1 = 2.$

Verify: Both are consistent, but each sacrifices availability on one side. (a) is a "write-rarely, read-fast-and-robust" store; (b) is "write-fast-and-robust, read-rarely". The dial trades read vs write resilience. ✓

C8 — Range-shard hotspot (zero-spread input)

Worked example Ex 8 · Time-ordered keys, the degenerate distribution

Ranges: 2023-*→shard 0, 2024-*→shard 1, 2025-*→shard 2. During 2025 you insert $300, 000$ new rows keyed by created_at. How are writes distributed?

Forecast: (cover the next line and guess first) — even thirds, or a pile-up? Answer to the forecast: a total pile-up — all $300, 000$ hit one shard.

Step 1 — Where do 2025 keys fall? Why this step? Range sharding sends by key value; every 2025-* timestamp is $\geq$ 2025. $all 300, 000 \to shard 2.$

Step 2 — Load per shard. Why this step? Quantify the imbalance. $shard 0: 0, shard 1: 0, shard 2: 300, 000.$

Step 3 — The fix. Why this step? This is exactly the hotspot the parent warns of; hashing the key spreads it — expected $\approx 100, 000$ per shard.

Verify: A monotone (time-ordered) key has zero spread across ranges at any moment — the pathological input for range sharding. Hash sharding turns $300, 000$ into $\approx 3 \times 100, 000$ . ✓

C9 — Real-world word problem

Worked example Ex 9 · Design a global shopping cart store

A shop serves users in 3 continents. Writes must feel instant locally; a whole continent's datacenter can go dark; occasional cart merge conflicts are acceptable. Pick a topology and one quorum-ish knob.

Forecast: (cover the next line and guess first) — single-leader, multi-leader, or leaderless? Answer to the forecast: multi-leader, one leader per continent, with union-merge carts.

Step 1 — Rule out single-leader. Why this step? One leader means far-away continents pay cross-ocean write latency and the app dies if the leader's region dies. That fails both "instant local writes" and "survive a region outage".

Step 2 — Choose multi-leader. Why this step? One leader per continent → local writes are fast (no ocean crossing), and losing one region leaves the other two writable. The stated tolerance of "cart merge conflicts" matches multi-leader's known cost — it needs conflict resolution when the same cart is edited in two regions.

Step 3 — Pick the conflict-resolution knob. Why this step? We must say how conflicting cart edits merge. Carts combine naturally: take the union of items across regions (and last-writer-wins on any per-item quantity). So conflicts are cheap here, confirming multi-leader is safe for this domain. $Answer: multi-leader, one leader per continent, union-merge carts.$

Verify: Check every requirement against the design. Instant local writes ✓ (each continent writes to its own leader). Survive a region outage ✓ (the other leaders keep serving). Conflicts acceptable ✓ (union merge resolves them cheaply). All three met → design is sound. ✓

C10 — Exam twist: "more replicas = safer"

Worked example Ex 10 · The trap

You run $N = 3, W = 2, R = 2$ (consistent). To be "safer" you add 2 replicas → $N = 5$ but keep $W = 2, R = 2$ . Are you still consistent?

Forecast: (cover the next line and guess first) — did adding copies help or hurt? Answer to the forecast: it hurt — consistency breaks until you also raise $W$ or $R$ .

Step 1 — Re-test the inequality with the NEW $N$ . Why this step? $W, R$ didn't change but $N$ grew — the rule must be rechecked against the new $N$ . $W + R = 2 + 2 = 4 \neq > 5 = N .✗$

Step 2 — Why it broke. Why this step? More replicas means the write set $S_{W}$ (size $2$ ) and read set $S_{R}$ (size $2$ ) can now both hide inside the $5$ copies and never overlap — exactly the C6 boundary failure, pushed past the edge.

Step 3 — The correct fix. Why this step? Restore $W + R > N$ by raising the quorums: e.g. $W = 3, R = 3$ ( $6 > 5$ ✓) or $W = 4, R = 2$ ( $6 > 5$ ✓). $Fix: W = 3, R = 3 \Rightarrow 6 > 5 ✓ .$

Verify: This is the parent's "safety is governed by the quorum relation, not raw count" made concrete — see CAP Theorem for why you can't dodge the trade-off. Adding blind copies reduced consistency until $W, R$ caught up. ✓

Recall

Recall Every cell, one line each

Fraction moved, naive mod, $N \to N + 1$ ? ::: About $N / (N + 1)$ — nearly all keys. What does $f_{moved}$ mean in words? ::: The fraction of keys forced to change shards, between 0 (none) and 1 (all). Why is $P (stays) \approx 1/ (N + 1)$ ? ::: After the change there are $N + 1$ bins; a random hash lands back in its old bin only 1 time in $N + 1$ . Does a key move under mod reshard? ::: Only if $hash (k) mod N_{old} \neq = hash (k) mod N_{new}$ — check BOTH grow and shrink. The single rule for who owns a key on a ring? ::: First surviving node clockwise from the key, crossing position 0 if needed — same for add and remove. On a ring, adding a node moves which keys? ::: Only the one arc between the new node and its clockwise neighbor — including when that arc crosses $0$ . What is the half-open arc $[a, b)$ ? ::: Positions from $a$ included up to $b$ excluded, so no position is owned by two arcs. Why is $1/ (N + 1)$ the benchmark arc size? ::: With $N + 1$ evenly spaced nodes the ring splits into $N + 1$ equal arcs, so one new arc is exactly $1/ (N + 1)$ . What are $S_{W}$ and $S_{R}$ ? ::: The write set (the $W$ replicas that got the value) and the read set (the $R$ replicas we query) — both subsets of the $N$ replicas. The strict quorum rule for read-your-writes? ::: $W + R > N$ (equality is NOT enough). Write-side vs read-side fault tolerance? ::: Write survives $N - W$ down, read survives $N - R$ down; system tolerates $min$ of the two. Why does adding replicas alone break consistency? ::: It raises $N$ , so fixed $W, R$ may fail $W + R > N$ .