Lesson 8: Sharding & Consistent Hashing

Lesson 7 solved the read tier very cheaply. But it does nothing for two things: write throughput — every write still funnels into one primary — and capacity — every replica holds the complete dataset. When either of those exceeds what one machine can take, there is no option left but to split the data: sharding.

This is the most expensive step in the whole series, and the price is not money but permanent complexity: no cross-shard transactions, no JOINs, pagination becomes hard, and every query that does not carry the shard key turns into a full sweep.

Two measurements in this lesson stand out. First, the share of data that must migrate when you add a shard: modulo hashing going from 4 to 5 shards moves 79.97% of the data, while consistent hashing moves only 18.78% — and both match the theoretical formula almost perfectly. Second, a skewed shard key makes p99 10.3 times worse while p50 actually gets better — the hotspot lives entirely in the tail.

8.1 When you are forced to shard — and why it should be the last step

The correct order of priority, cheapest to most expensive. Take each step only once the previous one has run out:

Three signs that you genuinely need to shard, rather than just feeling that you do:

8.2 Choosing a shard key — and a measurement that nearly inverted the conclusion

A good shard key has to satisfy all three of these, and the third is the one most often forgotten:

Measured for real: a good shard key versus a skewed one

The lab stands up two completely independent PostgreSQL shards — no replication, no knowledge of each other — and a router inside the app decides which key goes to which shard. The skew mode reproduces the "one giant tenant" situation exactly: 95% of requests use the same shard key.

24 connections, 12 seconds, 20,000 distinct keys, each shard limited to 1 CPU, two repetitions:

The good shard key gives +32% throughput. But read the three percentile rows carefully: the skewed key has a better p50 and a better p95, and then p99 suddenly gets 10.3 times worse. A hotspot does not slow most requests down — it concentrates the entire damage in the tail.

This is the third time the same pattern has appeared in this series: in Lesson 3 round robin produced a balanced chart but a p95 340 times worse; in Lesson 5 single-flight made p50 worse but cut the tail 11-fold; here a skewed shard key wins on p50 and p95 and then loses 10-fold on p99. If your dashboard only has the mean and p95, you would draw the wrong conclusion all three times.

The lab's shard router, exactly as the running code has it:

// FNV-1a, then mixed with MurmurHash3's fmix32.
// Why the mixing step is needed: FNV-1a has POOR avalanche for short, similar strings
// ('user:1', 'user:2'...), so consecutive keys land on the same shard in clumps.
// The fmix32 step is cheap and removes that effect entirely.
function shardHash(key) {
  let h = 2166136261;
  for (let i = 0; i < key.length; i++) {
    h ^= key.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  h ^= h >>> 16;
  h = Math.imul(h, 2246822507);
  h ^= h >>> 13;
  h = Math.imul(h, 3266489909);
  h ^= h >>> 16;
  return h >>> 0;
}

// WARNING: this is modulo hashing. Simple, but read section 8.3 before using it for
// real — adding one shard means migrating nearly all of the data.
function pickShard(shardKey) {
  return shardHash(String(shardKey)) % pgShards.length;
}

8.3 Modulo hashing and the resharding disaster

The simplest way to divide is hash(key) % N, where $N$ is the shard count. It is short, easy to understand, evenly distributed, and it is exactly what the lab's router does. The problem shows up on the day you add shard number $N+1$.

A key stays where it is only if $h \bmod N = h \bmod (N+1)$. By the Chinese remainder theorem, when $N$ and $N+1$ are coprime — and two consecutive integers always are — the pair $(h \bmod N,\ h \bmod (N+1))$ is uniformly distributed over $N(N+1)$ possibilities. The number of pairs satisfying the stay condition is $N$, so:

$$P(\text{stay}) = \frac{N}{N(N+1)} = \frac{1}{N+1} \quad\Rightarrow\quad P(\text{move}) = \frac{N}{N+1}$$

Note that this figure is $N/(N+1)$, not $(N-1)/N$ as it is often quoted. Run for real over 100,000 keys, comparing both algorithms, with consistent hashing using 150 virtual nodes:

Modulo matches theory to two decimal places on every row. And the number worth remembering is the 4 → 5 row: adding one shard to a four-shard system forces 80% of the data to move. With 16 shards the figure is 94% — the more shards you have, the worse adding one more becomes.

Consistent hashing tracks $1/(N+1)$ closely but deviates more visibly at small $N$ (37.19% against a theoretical 33.33% at 2 → 3). The reason: with few nodes, the positions of the hash points on the ring have high variance, so the actual ratio fluctuates around the expected value. The more nodes and the more virtual nodes, the closer the match.

8.4 Consistent hashing and virtual nodes

The idea: instead of hashing the key into a shard index, hash both the key and the shard name into the same space — a 32-bit ring. Each key belongs to the first shard it meets going clockwise. Adding a shard only takes over the arc immediately before it, so only the keys inside that arc have to migrate.

The full table, with the same 8 nodes and 100,000 keys (the ideal is 12,500 keys per node):

The first row is the reason virtual nodes exist: with one hash point per node, one shard receives 66 keys while another receives 25,465 — a 386-fold difference, for an algorithm still routinely introduced as "evenly distributed".

Both tables above can be reproduced in seconds, with no Docker. One small note so it does not alarm you: Node will first print a MODULE_TYPELESS_PACKAGE_JSON warning — that is only because the repo's package.json does not declare "type": "module"; the results below it are still correct.

# No Docker needed — just node
cd blog/sysdesign
node --input-type=module -e "
import { compareAddNode, makeKeys, HashRing } from './sysdesign-hashring.js';
const keys = makeKeys(100000);
for (const n of [2,3,4,8,16]) {
  const nodes = Array.from({length:n},(_,i)=>'s'+(i+1));
  const r = compareAddNode(keys, nodes, 's'+(n+1), 150);
  console.log(n+'->'+(n+1),
    'modulo', (r.modulo.ratio*100).toFixed(2)+'%',
    '(theory', ((n/(n+1))*100).toFixed(2)+'%)',
    '| consistent', (r.consistent.ratio*100).toFixed(2)+'%',
    '(theory', ((1/(n+1))*100).toFixed(2)+'%)');
}
for (const v of [1,2,10,150,500]) {
  const ring = new HashRing({ vnodes: v });
  for (const n of ['s1','s2','s3','s4','s5','s6','s7','s8']) ring.addNode(n);
  const d = ring.loadDistribution(keys);
  console.log(v+' vnode: min', d.min, 'max', d.max,
    'spread', (d.spread*100).toFixed(1)+'%');
}
"

# And the self-test suite of 42 assertions, which covers the hash ring too
node sysdesign-engine-selftest.mjs

8.5 The consequences at the application layer — the genuinely expensive part

Choosing a good shard key and using consistent hashing only solves the infrastructure part. The expensive part is at the application layer, because four things you have always taken for granted are gone.

There is one more thing that no advice makes easy: pagination across shards. To get "the 20 most recent rows" across 8 shards you have to fetch the 20 most recent from each shard (160 rows), merge, sort, then cut to 20. The second page needs 40 per shard, and page 100 needs each shard to return 2,000 rows so that 20 can be used. The cost grows with the page number, not with the number of rows you want.

The usual escape is to drop page-number pagination in favour of cursor (keyset) pagination: "give me 20 rows after this marker". That removes the per-page cost growth, but in exchange the user can no longer jump to page 100 — a product change, not just a technical one. This is a very characteristic sharding trade-off: an infrastructure limit travels back up and shapes the feature set.

Reproduce the shard measurements yourself

cd blog/sysdesign/sysdesign-lab
docker compose --profile shard up -d   # two INDEPENDENT PostgreSQL shards + the app router

# Check that the router really does distribute
for k in a b c d e f; do curl -s "http://localhost:3001/shard?key=$k&mode=good"; echo; done

# --- GOOD shard key ---
./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/shard?mode=good" \
  -c 24 -d 12 -w 2 --json --key-space 20000
./tools/cache-stats.sh          # look at the SHARD line + the spread

# --- SKEWED shard key (95% of requests share one shard key) ---
./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/shard?mode=skew" \
  -c 24 -d 12 -w 2 --json --key-space 20000
./tools/cache-stats.sh

# IMPORTANT: if you drop the `cpus: '1.0'` limit on the two shards in docker-compose.yml
# the result INVERTS — the skewed key will look faster. The reason is in section 8.2.

In summary

Sharding is the last step because it is the only one with a permanent cost: no JOINs, no cross-shard transactions, pagination as a project of its own. Four cheaper steps come before it, and the test question is always "have you measured, and do you know exactly what is saturating".

Modulo hashing is simple, but adding one shard forces $N/(N+1)$ of the data to migrate — measured at 79.97% going from 4 to 5 shards, matching theory to two decimal places. Consistent hashing brings that down to 18.78%, but only with virtual nodes: without them, one shard receives 66 keys while another receives 25,465.

And the measurement lesson repeats for the third time in this series: a skewed shard key has a better p50 and a better p95 than a good one, and then a p99 10.3 times worse. Plus a new lesson: the first run of section 8.2 produced the exact opposite result, because both shards shared one machine's CPU — the measurement environment had cancelled out the very phenomenon being measured.

Lesson 9 formalises the question section 7.4 left open: when the network is cut, and neither node knows whether the other has died or has merely lost contact, what do you choose? That is CAP — and the part that matters more than CAP itself, which fewer people talk about: the choice you face every single day, while the network is perfectly healthy.