Distributed databases — sharding strategies, replication: Exercises

Everything here builds on the parent note. If a term feels shaky, the prerequisite is linked the first time it appears.

L1 — Recognition

You should be able to name the right concept without any calculation.

Exercise L1.1

A table of 50 TB cannot fit on one server. You cut it into disjoint pieces, each row living on exactly one node. What is this called, and what problem does it solve?

Recall Solution

This is sharding (also called horizontal partitioning — see Horizontal vs Vertical Partitioning). Problem solved: scale — one machine cannot hold the whole dataset or serve all the traffic. We split distinct data across many nodes. It is not replication: replication would copy the same data, not split it.

Exercise L1.2

For each phrase, say whether it describes sharding or replication: (a) "keep three copies of every row so a crash loses nothing" (b) "users A–H on node 0, I–P on node 1" (c) "serve reads from many machines to spread read load" (d) "each row lives on exactly one primary node chosen by a key"

Recall Solution

(a) Replication — copies of the same data (durability). (b) Sharding — distinct rows split by range. (c) Replication — read scaling comes from having copies to read from. (d) Sharding — a shard key routes each row to one owner.

Memory anchor: Sharding = split (scale). Replication = copy (safety).

Exercise L1.3

In the quorum rule $W + R > N$ , name what each of $N$ , $W$ , $R$ stands for.

Recall Solution

$N$ = total number of replicas (copies) of the data.
$W$ = number of replicas a write must reach before it is acknowledged.
$R$ = number of replicas a read must contact. See Quorum Consensus and Paxos/Raft for the machinery behind it.

L2 — Application

Now plug numbers into the formulas.

Exercise L2.1

You run $N = 7$ shards with shard = hash(key) mod N holding 2,100,000 keys. You add a shard (now $N + 1 = 8$ ). About how many keys must migrate?

Recall Solution

Under naive mod, the moved fraction is $f_{moved} \approx \frac{N}{N + 1} = \frac{7}{8} = 0.875.$ Keys moved $\approx 0.875 \times 2, 100, 000 = 1, 837, 500$ . Why so many? Changing the modulus from 7 to 8 changes the residue class of almost every key, so almost every key gets a new home.

Exercise L2.2

Same starting point ( $N = 7$ , 2,100,000 keys, add one node) but you use consistent hashing with evenly placed virtual nodes. About how many keys move now?

Recall Solution

$f_{moved} \approx \frac{1}{N + 1} = \frac{1}{8} = 0.125.$ Keys moved $\approx 0.125 \times 2, 100, 000 = 262, 500$ . Why so few? The new node steals exactly one arc of the ring — the arc between it and its clockwise neighbour. Everyone else keeps their keys.

Exercise L2.3

$N = 5$ replicas. You want strong consistency (read always sees the latest write) while tolerating 1 replica down for writes. Give a valid $(W, R)$ and check it.

Recall Solution

Tolerating 1 node down for writes means we can only require $W = N - 1 = 4$ . Strong consistency needs $W + R > N$ : $4 + R > 5 ⟹ R > 1 ⟹ R \geq 2.$ Smallest read set: $R = 2$ . Check: $4 + 2 = 6 > 5$ ✓. So $(W, R) = (4, 2)$ works. This also tolerates up to $N - R = 3$ replicas down for reads.

L3 — Analysis

Reason about why a configuration behaves as it does.

Exercise L3.1

$N = 3$ . A team picks $(W, R) = (1, 1)$ "for speed." Show precisely when a read can return stale data, and fix it with the minimum change.

Recall Solution

Check the rule: $W + R = 1 + 1 = 2 \neq > 3$ . Fails. Why staleness happens (pigeonhole): the write lands on some single replica $S_{W}$ (size 1), the read hits some single replica $S_{R}$ (size 1). Overlap is forced only when $W + R > N$ ; here $2 \leq 3$ , so the two singletons can be completely different replicas — the reader may hit a copy that never saw the write. Minimum fix: bump one of them so the sum exceeds 3. E.g. $(W, R) = (2, 1)$ : $2 + 1 = 3 \neq > 3$ — still fails! You need $> 3$ , so $(2, 2)$ : $2 + 2 = 4 > 3$ ✓. Overlap $\geq W + R - N = 1$ replica guaranteed.

Exercise L3.2

For $N = 3$ , someone chooses $(W, R) = (3, 1)$ . It satisfies $W + R > N$ . Explain the hidden cost and when writes will simply fail.

Recall Solution

$3 + 1 = 4 > 3$ ✓ — reads are super fast (any 1 replica is enough, since a write touched all 3). Hidden cost: $W = N = 3$ means a write must reach every replica. Write fault tolerance is $N - W = 0$ . If even one replica is down or slow, the write cannot complete. So this trades write availability for cheap reads — good only for read-heavy, rarely-written data.

Exercise L3.3

A time-ordered key (created_at) is used as the shard key with range sharding across 4 shards. Predict the load pattern and explain the mechanism; then say which single change removes the hotspot without losing all range-query ability.

Recall Solution

Prediction: a hotspot — every new write lands on the last range (the newest timestamps), so one shard absorbs ~100% of write traffic while three sit idle. Mechanism: ranges are contiguous and time is monotonically increasing, so the "current" time always falls in the highest range. See the two panels in the figure below. Fix: use a compound / hashed prefix shard key (e.g. hash(user_id) as the leading component, created_at secondary). This spreads writes across shards (Load Balancing) while still letting you range-scan within a user. Pure hash(created_at) would kill all range queries, so we keep time as a secondary sort key.

Figure — Distributed databases — sharding strategies, replication

L4 — Synthesis

Combine sharding and replication in one design.

Exercise L4.1

You shard 12,000,000 rows across $N_{s} = 6$ shards using consistent hashing, and replicate each shard $N = 3$ times. (a) How many physical data copies exist in total? (b) How much data (rows) does one physical node hold, assuming even spread and one shard-replica per node?

Recall Solution

(a) Each of the 6 shards is stored 3 times: $6 \times 3 = 18$ physical shard-replicas (copies). (b) Rows per shard $= 12, 000, 000/6 = 2, 000, 000$ . Each physical node holds one shard-replica $= 2, 000, 000$ rows. Reading it: sharding cut the 12M rows into 6 disjoint 2M pieces (scale); replication then made 3 copies of each piece (safety). The two axes multiply: $6 \times 3 = 18$ boxes.

Exercise L4.2

On the same system ( $N = 3$ replicas per shard), you want a read to see your own latest write with the cheapest reads possible, while still surviving 1 replica failure during writes. Give $(W, R)$ per shard and justify each number.

Recall Solution

Survive 1 replica down on write ⇒ $W = N - 1 = 2$ .
Cheapest reads that still guarantee overlap: $W + R > N \Rightarrow 2 + R > 3 \Rightarrow R \geq 2$ , so $R = 2$ . Wait — can we get $R = 1$ ? That needs $W + 1 > 3 \Rightarrow W \geq 3 = N$ , which loses write fault tolerance. So with the "survive 1 write failure" constraint, the cheapest read is $R = 2$ . Answer: $(W, R) = (2, 2)$ per shard. This is the classic strong-consistency default. (See Replication Lag and Read-Your-Writes for why $R$ must overlap the write set to beat lag.)

Exercise L4.3

During a network partition, one half of your leaderless cluster can only reach 1 of the 3 replicas of a shard, with $(W, R) = (2, 2)$ . What happens to reads and writes in that half, and which side of CAP did this configuration choose?

Recall Solution

With only 1 replica reachable and $W = R = 2$ , both reads and writes fail in that half (cannot assemble a quorum of 2). By refusing to answer rather than returning possibly-stale/unconfirmed data, this configuration chose Consistency over Availability. The rule $W + R > N$ enforces consistency; the price under partition is that the minority side goes unavailable.

L5 — Mastery

One open-ended design problem tying every idea together.

Exercise L5.1

A global social app: 900,000,000 rows, write-heavy timeline feeds, users clustered by region (US, EU, APAC), must survive a whole-region outage, and users must read their own posts immediately after posting. Design the sharding + replication scheme and justify every choice against a specific concept.

Recall Solution

1. Shard key & strategy. Use hash(user_id) as the leading shard-key component (consistent hashing).

Why not range on user_id or created_at? Time-ordered keys create a write hotspot (L3.3). Hashing spreads write-heavy timelines evenly (Load Balancing).
Why consistent hashing not mod N? A global app grows; mod N would force $\frac{N}{N + 1}$ of 900M rows to migrate every time we add capacity (L2.1). Consistent hashing moves only $\frac{1}{N + 1}$ .

2. Replication topology. Multi-leader, one leader per region (US/EU/APAC), each region's leader replicating to the others.

Why multi-leader? Low-latency local writes and — crucially — survival of a whole-region outage (the other regions keep accepting writes).
Cost accepted: cross-region write conflicts need resolution (last-write-wins with version vectors, or app-level merge).

3. Read-your-writes. Route a user's reads to the same region/leader that took their write, or within a shard's replicas use a quorum with $W + R > N$ .

Why? Otherwise replication lag lets a user post and then not see their own post. Overlapping read/write sets (or sticky routing to their leader) guarantees they read the newest value.

4. Per-shard replica count. $N = 3$ replicas per shard, defaulting to $(W, R) = (2, 2)$ where strong consistency is needed, degrading to async/eventual for non-critical feeds.

Why $(2, 2)$ ? $2 + 2 = 4 > 3$ guarantees overlap and tolerates 1 replica down on each path (L4.2).

5. CAP stance. Under partition, timeline reads favour Availability (a slightly stale feed is fine), but "did my post save?" favours Consistency. Choose CAP per operation — exactly the parent note's point.

Summary of the mapping:

Scale → consistent-hash sharding on hash(user_id).
Region survival → multi-leader replication.
No hotspots → hashed key, not time-ordered.
Read-your-writes → sticky routing / quorum overlap.
Copies × pieces → $N_{s} \times 3$ shard-replicas total.