Partitioning and Sharding: What Moves When You Add a Node

Range against hash, consistent hashing, virtual nodes and hot keys — measured by placing a million keys four ways and counting what moves, plus what partitioning costs a query inside one PostgreSQL 18 database.

Splitting data across machines is two questions. Which machine does this key live on, and what happens to that answer when the number of machines changes. The first is easy. The second is the reason consistent hashing exists, and the reason people are frightened of resharding.

This part places a million keys four ways and counts exactly what moves. Then it asks a partitioned PostgreSQL what a query costs when it names the partition key and when it doesn’t.

Try this first

You have four nodes and a million keys, placed by hash(key) % 4. You add a fifth node.

How many of the million keys end up on a different node? Write the number down before scrolling.

Modulo: the obvious answer, and why nobody uses it

Change	Keys moved	Share of the million	Times the ideal
4 nodes to 5	799,897	79.99%	4×
100 nodes to 101	990,073	99.01%	100×

The ideal for four-to-five is 200,000 keys — the new node’s own share, and not one more.

Eighty per cent. A scheme that moved only what it had to would move 200,000 keys — a fifth of them, which is exactly the share the new node has to end up holding. Modulo moved four times that. In fact the fifth node ended up holding 199,612 keys, so modulo moved 799,897 keys to place 199,612: four keys moved for every one that needed a new home, three of them for nothing.

And it gets worse as the cluster grows, which is the opposite of what you want. Going from a hundred nodes to a hundred and one moves 99.01% of the keys — 100 times the ideal. The bigger the cluster, the more total havoc one new machine causes.

The reason is that % 5 and % 4 have almost nothing to do with each other. Changing the divisor re-derives every key’s answer from scratch. Nothing about the scheme knows that most keys were fine where they were.

Consistent hashing, and what it actually guarantees

The fix is to stop asking “which of N buckets” and start asking “which point on a circle”. Nodes are placed at positions on a ring; a key hashes to its own position and belongs to the first node clockwise from it. Adding a node inserts one new point, which claims only the arc between itself and the point before it. Nothing else moves.

That is the 1997 paper’s own summary of the idea, in one sentence:

Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes.

It is worth knowing what that paper proves, because it is not the thing everyone quotes. The guarantee is structural, not a count. From the proof of its main theorem:

Monotonicity is immediate. When a new bucket is added, the only items that move are those that are now closest to one of the new bucket’ s associated points. No items move between old buckets.

Read that carefully. No key moves between two nodes that both already existed — that is the whole promise, and it is a promise about which keys move, not how many. The familiar line that adding the (n+1)-th node moves 1/(n+1) of the keys is a different result later in the paper, and it needs an extra hypothesis the paper calls “rather stringent” and never claims for the construction everyone actually implements. The section it lives in opens by describing itself as “unneccessary for the remainder of the paper” — the typo is the paper’s.

So the famous fraction is closer to folklore than to a citation, which is a good reason to go and measure it rather than repeat it. Here is what our lab found:

Scheme	4 → 5 nodes	100 → 101 nodes
modulo	79.99%	99.01%
consistent hashing, 1 point per node	30.78%	0.15%
consistent hashing, 16 points per node	14.55%	1.16%
consistent hashing, 256 points per node	18.6%	0.99%

Every ring beats modulo by a mile, which is the expected part. The unexpected part is that the ring column has no pattern in it. Going from four nodes to five, more points per node does not mean less movement, or more: it goes 30.78%, down to 14.55%, back up to 18.6%. Two of those are under the 20% ideal and one is well over it.

I spent a while trying to explain that ordering before realising there is nothing to explain. It is noise. And the reason it is noise is the most useful thing in this part.

The one number that is always exactly right

Alongside the count of what moved, the lab records what the new node ended up holding once the dust settled. Put them side by side:

Scheme	Keys moved	What the fifth node ended up holding
modulo	799,897	199,612
consistent hashing, 1 point per node	307,824	307,824
consistent hashing, 16 points per node	145,452	145,452
consistent hashing, 256 points per node	185,966	185,966

Every ring row is the same number twice. Not approximately — exactly, to the key, in all three.

That is the whole guarantee, and it is the theorem from the paper showing up in a column of integers. The ring moves the keys the new node ends up owning, and it moves nothing else. No key is ever shuffled between two nodes that both stayed. Modulo, on the same line, moved 799,897 keys to hand the newcomer 199,612 — the other 600,285 went from one old node to a different old node, for nothing.

Removing a node is the same identity from the other side:

Scheme	Keys moved	What the departing node was holding
modulo	749,824	250,352
consistent hashing, 1 point per node	516,164	516,164
consistent hashing, 16 points per node	230,472	230,472
consistent hashing, 256 points per node	246,728	246,728

Again: exact, on every ring row. When a node leaves the ring, its keys go to its neighbours and nobody else’s move at all.

Which node leaves is therefore the whole story. The lab always removes the highest-numbered one, and at one point per node that happened to be the node holding half the ring — hence 51.62%. Remove a different node and you get a different number, entirely because that node was holding a different amount. There is nothing to tune here and nothing to get wrong; there is only how lopsided the ring was to begin with.

So “how much does consistent hashing move?” turns out to be the wrong question. The answer is always exactly what it must. The right question is the one hiding behind it: how much is that? Which is the same as asking how big the departing or arriving node’s share was. And that is what virtual nodes are about.

Scheme	Busiest node	Smallest	Largest	Std dev (% of mean)
modulo	1× the mean	249,787	250,352	0.08%
consistent hashing, 1 point per node	2.06× the mean	77,841	516,164	71.32%
consistent hashing, 16 points per node	1.28× the mean	217,093	319,315	16.19%
consistent hashing, 256 points per node	1.02× the mean	244,840	255,785	1.76%

Four nodes, one million keys, before anything is added.

With one point per node, the four arcs are wildly different sizes, because four positions drawn at random from a circle do not divide it into quarters. The busiest node held 2.06 times the mean — one node holding 516,164 of the million keys while another held 77,841.

Now look back at the removal table. One point per node moved 516,164 keys when a node left. It is the same number, because it is the same keys: that node was holding a quarter of the ring’s points and half of its space.

So the erratic movement column resolves. Adding a node to a one-point ring moved 30.78% not because the ring is wasteful but because the new point happened to land in a big arc and inherit a big share. Add it somewhere else and you would get a different number. The movement is always exactly right; what varies wildly is how much “exactly right” happens to be.

At 256 points each, the busiest node holds 1.02 times the mean — 244,840 to 255,785 keys across four nodes — and adding a fifth moves 18.6%, just under the fifth share it ends up with. Both numbers stop being interesting, which is the point of them.

That is the actual trade, and it is not the one usually stated:

Virtual nodes do not reduce how much moves. The ring already moves the minimum. What they fix is how lopsided the minimum is.

The mechanism is in the 1997 paper, though the name is not: the construction gives each bucket many points around the circle rather than one, and the proof uses exactly that to get balance. “Virtual node” is Dynamo’s word, and Dynamo names a second reason the retellings drop:

The basic consistent hashing algorithm presents some challenges. First, the random position assignment of each node on the ring leads to non-uniform data and load distribution. Second, the basic algorithm is oblivious to the heterogeneity in the performance of nodes.

That second reason is why the count is per node and tunable rather than one global constant. A bigger machine gets more tokens and takes more data. Cassandra documents a third reason — “we can make small clusters look larger” — so a single new machine can take a little from many neighbours instead of splitting one arc.

And they are not free, in a way our lab cannot see. Cassandra is blunt about it:

Every token introduces up to 2 * (RF – 1) additional neighbors on the token ring, which means that there are more combinations of node failures where we lose availability for a portion of the token ring. The more tokens you have, the higher the probability of an outage.

Cassandra ships num_tokens: 16, and documents that same default as “Not recommended for clusters over 50 nodes”. Delete the line entirely and you get 1, “for legacy compatibility”. Version 2.x defaulted to 256, and the drop to 16 is documented as the result of a better token-allocation algorithm rather than a change of mind about balance.

Modulo, for contrast, divides the keys almost exactly evenly — 249,787 to 250,352 across four nodes — and moves nearly all of them. The ring is the other way round. There is no scheme that balances perfectly and moves nothing, because balance is what forces the movement.

One ring is an anecdote

Everything above came from one ring. Whether four points happen to carve a circle into reasonable arcs is luck, and quoting one draw of that lottery as “what consistent hashing does” would be exactly the sort of claim this series is supposed to avoid.

So the lab builds the ring 20,000 times, with different node names each time, and records how much of the circle the busiest node owns — the arc it is responsible for, before a single key is placed:

Points per node	Typical ring	Worse than this 1 time in 100	Worst of 20,000
1	2×	3.45×	3.96×
16	1.25×	1.67×	1.95×
256	1.06×	1.16×	1.23×

That is the honest version of the claim, and it is sharper than the single-ring table. With one point per node, the busiest of four nodes typically owns 2 times its share, and one ring in a hundred is worse than 3.45 times — which is a machine holding most of your data because of what you called it. At 256 points the typical ring is 1.06× and the one-in-a-hundred case is 1.16×.

Note what the last column is and is not. 1.23× is the worst of 20,000 tries, not a bound — build enough rings and you will beat it. That is exactly why the percentile column is the one to quote.

Virtual nodes improve the typical ring. What they really do is shrink the range — and the tail is what you have to buy hardware for.

Both halves of that matter. The typical ring does get better, from 2× to 1.06×. But the tail improves faster: at one point per node, one ring in a hundred is worse than 3.45×, and the worst seen was 3.96×. At 256 points, one in a hundred is worse than 1.16× and the worst seen was 1.23×. You provision for the bad case, not the median, so the column that decides your hardware bill is the right-hand one.

And the mechanism is not that the ring learned to divide. It is that you asked it to divide 1,024 times instead of 4, and the law of large numbers did the rest. Virtual nodes are a sampling trick.

The ring is only as even as its hash

One more thing the lab measured, because it nearly fooled me. The first version of this lab hashed keys with FNV-1a — a perfectly good hash for a hash table, and the wrong tool here. Every balance number it produced was wrong, and wrong in a direction that made consistent hashing look worse than it is.

The ring positions are what give it away, measured before a single key exists:

where each node's single point lands, as a % of the hash space
  node-0#0  node-1#0  node-2#0  node-3#0  node-4#0  node-5#0

  FNV-1a         0.48     3.83     6.89    10.29    14.01    17.37
  step                     3.35     3.06     3.40     3.72     3.36

  SHA-256       71.26    11.90    81.01    63.51    42.63    75.36
  step                   -59.35    69.11   -17.49   -20.87    32.73

Look at the step rows. Under FNV-1a every node name lands a near-constant distance further round the circle than the last — 3.35, 3.06, 3.4, 3.72, 3.36 per cent, over and over. The points are not scattered; they are an arithmetic progression. Under SHA-256 the steps jump around by design, which is the only thing a ring ever wanted from a hash.

That single fact explains everything the first lab reported. The points came out in name order, evenly spaced, and bunched — four steps of about three per cent span only ten per cent of the circle, so the first node owned everything from the fourth point round to the first, which was 90.19% of the ring:

how much of the ring each node then owns, one point each
  FNV-1a     90.19%   3.35%   3.06%   3.39%
  SHA-256     7.74%  30.89%   9.76%  51.61%

It is worth being precise about the cause, because the obvious explanation is wrong. FNV-1a is often described as mixing poorly into its high bits, and it does — for the final byte of the input. These names end in #0, so the digit that varies is third from the end and gets two more rounds of multiplication; flip it and the top bits really do change. The problem is not that the hash ignores the difference. It is that it responds to it linearly: one more in that digit means roughly one more constant added to the output. A hash can avalanche and still be useless on structured, near-sequential names, which is exactly the shape node names have.

Even at 256 points per node FNV-1a was still 1.32× off, where SHA-256 gives 1.02×.

Nothing about the ring algorithm was wrong. The circle was fine; the dart-thrower was not.

A consistent-hashing ring inherits the quality of its hash. If near-identical node names land at near-identical positions, you do not have a ring — you have a queue.

This is why the systems that ship this use MD5, SHA-1 or MurmurHash and not whatever was nearest to hand. It is also a good reminder that a lab can reproduce perfectly and still measure the wrong thing: those FNV numbers were stable to the key across every run.

The ring is not where this story ended

Dynamo published the random-token ring in 2007 and, in the same paper, reported that it had moved off it. Section 6.2 compares three strategies. Strategy 1 is the textbook one: “T random tokens per node and partition by token value: This was the initial strategy deployed in production (and described in Section 4.2).” Its problem is stated plainly:

The fundamental issue with this strategy is that the schemes for data partitioning and data placement are intertwined. For instance, in some cases, it is preferred to add more nodes to the system in order to handle an increase in request load. However, in this scenario, it is not possible to add nodes without affecting data partitioning. Ideally, it is desirable to use independent schemes for partitioning and placement.

Strategy 3, the one they moved to, cuts the hash space into Q equal-sized partitions and gives each node Q/S of them. A joining node “steals” whole partitions from the nodes that have them. No key ever changes partition; only partitions change machines. Their evaluation, for a thirty-node cluster: “strategy 3 achieves the best load balancing efficiency … Compared to Strategy 1, Strategy 3 achieves better efficiency and reduces the size of membership information maintained at each node by three orders of magnitude.”

Fixed, equal-sized partitions decoupled from placement is what most systems you will actually operate ship — Kafka partitions and Elasticsearch shards both fix their count when you create the thing. Learn the ring because it explains why any of this works. Expect to run the pre-split version.

Cassandra adds a related warning about letting the ring heal itself. It will not remove a failed node from the ring without a human saying so, and the reason is not politeness:

This choice is intentional to allow Cassandra nodes to temporarily fail without causing data to needlessly re-balance. This also helps to prevent simultaneous range movements, where multiple replicas of a token range are moving at the same time, which can violate monotonic consistency and can even cause data loss.

Automatic rebalancing is documented there as a hazard, not a feature.

Range or hash: it depends what arrives next

Hash partitioning spreads keys by their hash. Range partitioning keeps neighbours together — all of January on one node, February on the next.

Over a whole dataset they look equally good. Our lab split 100,000 events by both, and both filled every node evenly — range by construction, since cutting a sequence into eight equal blocks is what it does, and hash because that is what hashing gives you. The totals are not the finding. The difference only shows up when you ask where the newest data went:

	Range partitioning	Hash partitioning
busiest node, all 100,000 events	1× the mean	1.01× the mean
of the most recent 10,000, how many on one node	10,000	1,316

Of the ten thousand most recent events, range partitioning put all ten thousand on one node. Hash put 1,316 there.

That is the whole argument. If your key is a timestamp, an auto-increment id, or anything else that goes up, range partitioning means every new write lands on the same machine — while the other machines hold history nobody is writing to. The overall balance looks perfect on a dashboard, and one node is on fire.

MongoDB documents exactly this failure, and names the chunk it happens to:

Since the value of X is always increasing, the chunk with an upper bound of MaxKey receives the majority incoming writes. This restricts insert operations to the single shard containing this chunk, which reduces or removes the advantage of distributed writes in a sharded cluster.

It also names the price of the fix in the same breath: hashed sharding “provides a more even data distribution across the sharded cluster at the cost of reducing Targeted Operations vs. Broadcast Operations.” There is no free version of this choice anywhere in the vendor documentation, which should tell you something.

Range earns its place when you need ranges back: give me everything from last Tuesday, in order. Hash destroys that — a range query has to ask every partition. You are choosing which query shape is cheap.

The thing partitioning cannot fix

A hot key is the failure no partitioning scheme can rescue, and it is worth seeing what that looks like on a placement that is doing everything right:

1,000,000 requests, zipf s=1.07, over 1,000,000 keys
8 nodes, spread by 256 points each

distinct keys touched        158,866
the hottest key alone        105,312 requests (10.53%)

keys per node                1.13x the mean  (120,414 to 141,141)
requests per node            1.75x the mean  (86,663 to 218,189)
the hottest key alone        48.27% of the busiest node's traffic

Those last three lines are the whole section. The keys are spread almost perfectly — 1.13 times the mean, which is as even as anything in this part. The requests are not: 1.75 times. And nearly half of the busiest node’s traffic is a single key — one key alone took 10.53% of all requests.

No partitioning scheme fixes this, and it is important to see why: a key lives on one node. You can spread keys, and the requests follow the keys. If one key is hot, its node is hot, and adding machines does not divide it.

Dynamo — the paper usually cited for hash partitioning — is careful here in a way the folklore is not. It states a condition:

A uniform key distribution can help us achieve uniform load distribution assuming the access distribution of keys is not highly skewed.

And then it measures its own production clusters against a 15% band: “during low loads the imbalance ratio is as high as 20% and during high loads it is close to 10%.” That is a real system, hashing its keys correctly, with between one node in five and one node in ten more than 15% away from the average load.

AWS makes the same point as a table. Two consecutive rows of DynamoDB’s partition-key guidance read “Device ID, where each device accesses data at relatively similar intervals” and “Device ID, where even if there are many devices being tracked, one is by far more popular than all the others.” Same column, same cardinality. The first is rated Good and the second Bad, and the only difference between them is access skew. High cardinality is necessary and nowhere near sufficient.

The answers are all outside partitioning. Cache it, so most requests never reach the node. Split the key artificially — celebrity:123#0 through #9 — and merge on read. Or replicate that key to several nodes and read from any. Each has a cost, and each is a different design, not a setting.

AWS documents the middle one and is honest about the bill. Its worked example widens the key with a random suffix from 1 to 200, and then: “to read all the items for a given day, you would have to query the items for all the suffixes and then merge the results.” One logical read becomes two hundred queries and an application-side merge. You have not removed the hot spot. You have converted it into a scatter-gather — often the right trade, and one to make with your eyes open.

There is also a hard floor on what any of this buys for a single key. DynamoDB’s adaptive capacity might, in the best case, “rebalance your data so that a partition contains only that single, frequently accessed item” — and that partition is still capped at 3,000 read units and 1,000 write units a second. (A read unit is one strongly consistent read of an item up to 4 KB, or two eventually consistent ones, so it is not quite 3,000 reads.) The very best case for one hot key is one machine’s worth of one key.

Inside one database: the same question, exactly measurable

A sharded cluster is hard to measure honestly on a laptop. PostgreSQL’s declarative partitioning is the same idea one level down — rows split by a key, and a query that either names that key or doesn’t — and EXPLAIN answers exactly.

One thing to notice before the numbers, because it closes the loop on the first half of this part. PostgreSQL’s hash partitioning is documented as specifying “a modulus and a remainder for each partition” — it is plain modulo hashing, not a ring. Which is precisely why changing the number of hash partitions on a live table is so unpleasant, and why the systems that do want to change their node count went to the trouble of building something else.

Query	Partitions scanned	Blocks	Time
with the partition key	1 of 8	3	0.07 ms
on an indexed non-key column	8 of 8	30	2.78 ms
with the partition key, on an unindexed column	1 of 8	202	1.91 ms
without the partition key	8 of 8	3,337	40.76 ms

400,000 rows, 8 hash partitions. Tenant 42 has 200 rows.

The first and last rows are the ones everybody quotes: 3 blocks against 3,337, a factor of about 1,112. It is a real comparison of two real queries, and it is not the cost of failing to name the partition key — because those two queries differ in two ways, not one. The first prunes to a single partition and is answered from an index. The last scans all eight and has no index to use, because note has none.

Two things at once is how you get a number that flatters your argument. So the lab asks a third question: name the partition key and filter on that same unindexed column. It prunes to one partition and then reads it the hard way — 202 blocks.

Even that is not clean, because PostgreSQL quietly used the tenant index to find the rows. To isolate pruning properly both halves have to be forced to sequential scans, and then the comparison finally holds still:

both forced to Seq Scan, same predicate, one names the partition key
  with the partition key        1 of 8 partitions      467 blocks     5.45 ms
  without the partition key     8 of 8 partitions    3,337 blocks    36.30 ms

Pruning on its own is worth 7.15×. That is the honest number, and it is two orders of magnitude smaller than the headline.

It is also a little under the 8× that reading one partition out of eight suggests, and the reason is the subject of the next section. Tenant 42 lives in events_p2, which holds 56,000 of the 400,000 rows — 14%, not the even 12.5%. Hash partitioning spreads tenants evenly, not rows, and eight partitions of two thousand tenants do not come out equal. 14% of 3,337 blocks is 467 — exactly what it read.

The other 150-fold is the index, and the middle row proves it from the other direction. A query on an indexed non-key column touched all eight partitions and cost 30 blocks — nearly seven times less than the pruned-but-unindexed query. Touching every partition is not automatically expensive; touching every row is. Eight index lookups are still just eight index lookups.

That reordering is worth sitting with. Of the two levers, the index is the bigger one here, and the one people reach for last.

Two more things the lab found worth knowing.

Pruning can happen at run time, not just at planning time. When the key came from a subquery the planner couldn’t evaluate, all 8 partitions stayed in the plan and only one was ever executed. If you read a plan and panic at the number of partitions listed, check how many actually ran.

There is a third moment, and it misleads in the opposite direction. PostgreSQL prunes at planning, at executor initialization, and during execution — and of the middle one the docs say that partitions “pruned during this stage will not show up in the query’s EXPLAIN or EXPLAIN ANALYZE“, and that “any partitions removed by the partition pruning done at this stage are still locked at the beginning of execution”. A plan that looks beautifully pruned may have taken a lock on every partition on its way there.

Partitionwise aggregation is worth turning on and is off by default. The same group-by went from 3,337 blocks to 353 — because once each partition may group its own rows, the planner can satisfy each one from the tenant index instead of reading the heap at all. Grouping per partition is the enabler; the index-only scan is where the blocks actually go. The clue is in the timings, which improved only 1.9× against a 9.5× drop in blocks: that is the shape of the I/O changing, not the work disappearing.

select tenant, count(*) from events group by tenant
enable_partitionwise_aggregate = off     3,337 blocks    153.65 ms
enable_partitionwise_aggregate = on        353 blocks     81.41 ms

It is off by default for a documented reason rather than by oversight: with it on, “the number of nodes whose memory usage is restricted by work_mem appearing in the final plan can increase linearly according to the number of partitions being scanned”. You are buying blocks with memory. The same warning governs enable_partitionwise_join, which is the setting that stops a join between two partitioned tables being a scatter-gather — and which only applies “when the join conditions include all the partition keys”. A co-located join is neither free nor automatic, in one database or across a cluster.

And one restriction that shapes schemas more than anything else here:

alter table events add constraint events_id_unique unique (id);
ERROR:  unique constraint on partitioned table must include all partitioning columns
DETAIL:  UNIQUE constraint on table "events" lacks column "tenant" which is part of the partition key.

alter table events add constraint events_id_tenant_unique unique (id, tenant);
accepted

A unique constraint on a partitioned table must include the partition key. PostgreSQL states the rule and its reason in one sentence:

To create a unique or primary key constraint on a partitioned table, the partition keys must not include any expressions or function calls and the constraint’s columns must include all of the partition key columns. This limitation exists because the individual indexes making up the constraint can only directly enforce uniqueness within their own partitions; therefore, the partition structure itself must guarantee that there are not duplicates in different partitions.

That is two restrictions, and people remember one. The constraint’s columns must be a superset of the partition key — and the partition key must not contain an expression or a function call at all, or you get no unique constraint whatsoever.

It is not something you can engineer around inside the database: it follows from the partitions being separate tables with separate indexes. The distributed version of the same rule is why sharded systems struggle with globally unique constraints that aren’t the shard key, and why so many of them hand you a UUID instead. PostgreSQL is candid that the tail can wag the dog here. Having advised you to partition on the columns your queries filter by, it adds: “However, you may be forced into making other decisions by requirements for the PRIMARY KEY or a UNIQUE constraint.”

The skew that partitioning creates and cannot solve

One more measurement, because it catches people who think hash partitioning is a guarantee:

400,000 rows over 8 hash partitions, one tenant dominating
biggest partition   331,600 rows (6.63x the mean)
smallest partition  7,800 rows
the busy tenant     320,000 rows, all of them in one partition

Eight hash partitions, 400,000 rows, and one partition holding 331,600 of them — 6.63 times the mean. Nothing is broken. One tenant simply has 320,000 rows, and hash partitioning spreads tenants evenly; it cannot split one tenant across partitions.

If your partition key has a value that dominates, the partition holding it dominates. This is the multi-tenant version of the hot key, and it is the reason “shard by tenant” fails exactly when it matters — when one tenant gets big enough to be worth having.

Explain it like I’m ten

A library with four rooms, and you need to know which room a book is in.

• By the number of rooms: count the letters in the title, divide by four, use the remainder. Fast. But open a fifth room and almost every book has to move, because you’re now dividing by five.
• By a circle: imagine the rooms standing at spots around a circular corridor, and every book walks clockwise until it reaches a room. Add a new room and only the books between it and the room before it have to move. Everyone else stays put.
• But four spots on a circle aren’t evenly spaced, so one room ends up with most of the books — and how bad it gets depends on luck. The fix is to give each room many spots instead of one, so the gaps average out and you stop needing luck.
• By date: all of January in one room, February in the next. Lovely for “show me January”. Terrible for today’s books — they all go in the same room, and the January room is empty of visitors.
• And none of it helps if everyone wants the same one book. That book is in one room, and that room is busy.

The precise version

• Dividing by the number of rooms is modulo hashing, and changing the count re-derives every answer.
• The circle is consistent hashing; the many spots per room are virtual nodes. They exist to make the room sizes predictable, not to reduce how many books move — the circle already moves only the books it must.
• All-of-January-together is range partitioning; its failure on new data is a write hot spot.
• Everyone wanting one book is a hot key, and it is not a partitioning problem — it is a caching or key-splitting problem.
• Where the analogy breaks: real systems move books while people are reading them, which is the part that makes resharding frightening rather than merely slow.

Trade-offs

• Modulo is simple and unshardable. Perfect balance, and a hundred-node cluster moves 99% of its keys to gain one machine.
• A ring always moves exactly the right keys. Measured: keys moved equalled what the joining node ended up holding, to the key, at every points-per-node. Virtual nodes change how big that is, not whether it is minimal.
• Virtual nodes shrink the tail faster than the average. Over 20,000 rings the busiest of four owned typically 2× the even share at one point each, and 3.45× at the 99th percentile; at 256 points those become 1.06× and 1.16×.
• The ring inherits its hash. FNV-1a mapped consecutive node names to evenly spaced positions, handing one node 90.19% of the ring before a key was placed; SHA-256 in the same code gives 1.02× balance at 256 points.
• Range gives you range queries and write hot spots. Hash gives you spread writes and scatter-gather reads. Pick by which query you run most.
• The partition key decides what is cheap forever after. Queries that name it are one partition; queries that don’t are all of them.
• Uniqueness that isn’t the partition key is the constraint you will miss. PostgreSQL says so outright; distributed stores say it by not offering it.
• Hot keys and dominant tenants are not partitioning problems, and no key choice solves them.

Common mistakes

• Sharding by an auto-increment id or a timestamp with range partitioning. Every write goes to the newest shard.
• Choosing the shard key from the entity rather than from the queries. Same mistake as Part 17, one level up.
• Assuming hash partitioning prevents hot spots. Measured: one partition at 6.63× the mean, because one tenant is big.
• Quoting one ring as though it were the scheme. Build it 200 times before you believe a balance number; at one point per node the spread across rings is 1.18× to 3.61×.
• Using a hash that isn’t uniform on structured names. FNV-1a is a fine hash table hash and a bad ring hash: node names differing by one digit hashed to an arithmetic progression, giving one node 90.19% of the ring, reproducibly.
• Reading “8 partitions” in a plan and panicking. Check how many were executed; run-time pruning is real.
• Forgetting partitionwise aggregation is off by default. Ours was a 9.5× reduction in blocks for one setting — though only 1.9× in time, which is the tell that it changed the I/O shape rather than removing work.
• Planning a resharding that doubles the shard count without checking what fraction of keys move — and whether the system can move them while serving.
• Adding shards to fix a hot key. It cannot help; the key is on one shard.
• Thinking the balance on a dashboard is the whole story. Range partitioning balances perfectly on total rows while one node takes every write. MongoDB’s balancer, for the same reason, triggers on data volume and not on load — a shard that is small and hot will never move a thing.
• Quoting “consistent hashing moves K/n keys” as though the paper proved it. What it proves is that no key moves between two nodes that both already existed. The fraction is a separate result under a stricter assumption.
• Expecting more shards to be faster. Elasticsearch, on the same data: “Searching a thousand 50MB shards will be substantially more expensive than searching a single 50GB shard containing the same data.”

Interview questions

Try to answer each one before opening the model answer.

1. Why not just use hash(key) % number_of_nodes?

Show a strong answer

• Because changing the node count re-derives every key. Our lab: adding a fifth node to four moved 80% of a million keys; the ideal is 20%.
• And it gets worse with scale, which is backwards: 100 to 101 nodes moved 99%.
• Consistent hashing fixes it by mapping keys and nodes onto a ring, so a new node only claims the arc before it. Measured: the ring moved exactly the keys the fifth node ended up holding, and modulo moved 799,897 to place 199,612.
• It is still fine when the node count genuinely never changes, or when “moving” is cheap because the store is a cache that can miss.
• That last case is worth naming: for a cache, a mass remapping is a thundering herd of misses rather than a data migration.

Likely follow-up: “When is modulo actually right?” Fixed-size partition counts — pre-create 1,024 logical partitions and map those to nodes. Then the divisor never changes; only the mapping does.

2. What are virtual nodes for?

Show a strong answer

• Predictable balance. A handful of points divide a circle very unevenly. Our lab: one point per node left the busiest of four holding 2.06× the mean, 516,164 keys against another’s 77,841.
• Many points per node average that out: 1.28× at sixteen, 1.02× at 256.
• Quote a percentile, not one ring. Over 20,000 independently built rings, one point per node was worse than 3.45× one time in a hundred; at 256 points that figure is 1.16×. The narrow tail is the product.
• They do not reduce movement, because there is nothing to reduce. The ring already moves exactly the keys the arriving node ends up holding — measured exact at every setting. Virtual nodes change how lopsided that amount is.
• They also make failure smoother: a dead node’s load spreads over many neighbours instead of landing entirely on one.

Likely follow-up: “How many?” Take the shipped default rather than inventing one — but know that the defaults come with conditions. Cassandra ships num_tokens: 16 and documents that as “Not recommended for clusters over 50 nodes”; it was 256 in 2.x, and it came down because the token allocator got smarter, not because the balance argument changed.

3. Range or hash partitioning?

Show a strong answer

• Hash spreads writes evenly and makes range queries scatter-gather.
• Range keeps neighbours together, so range scans are cheap — and puts every new write on one node if the key increases.
• Measured: of the ten thousand most recent events, range put all ten thousand on one node; hash put 1,316.
• So the question is which query you run most, and whether your key is monotonic.
• The hybrid is common: hash on a tenant or user, range within it, so each tenant’s data is range-scannable but tenants are spread.

Likely follow-up: “What about the balance dashboard looking fine?” Total rows per node can be perfectly even while one node takes 100% of the writes. Look at write rate per node, not size.

4. A single key is getting a huge share of your traffic. What do you do?

Show a strong answer

• Accept first that partitioning cannot fix it. A key lives on one node. Our lab: keys spread 1.13× the mean, requests 1.75×, and one key was 48.27% of the busiest node’s traffic.
• Cache in front of it, so most reads never reach the store. Usually the cheapest fix by far.
• Split the key into key#0…key#N and merge on read, if it’s a counter or a list you can decompose.
• Replicate that key to several nodes and read from any of them, if reads dominate and staleness is acceptable.
• Or move it out — a hot key is sometimes a sign it should be a different kind of object entirely.

Likely follow-up: “How do you find hot keys?” Sampling at the proxy or client, and per-key counters on the hot path — by the time you see it in node-level metrics you only know which node, not which key.

5. How would you choose a shard key?

Show a strong answer

• From the queries, exactly as Part 17 argued for data models: the key you can name in your hottest queries is the key to shard on.
• Check its cardinality and its distribution. High cardinality is necessary and not sufficient — one dominant value ruins it.
• Check it isn’t monotonic if you’re range-partitioning.
• Check what you lose: any uniqueness or transaction that spans shards gets much harder, and PostgreSQL will refuse a unique constraint that doesn’t include the key.
• Then check growth: the distribution that’s fine today is the one that produces a 6.63× partition when one tenant takes off.

Likely follow-up: “What if two query shapes need different keys?” Duplicate the data with a second key, and accept that you now own the consistency between them.

6. What does resharding actually involve?

Show a strong answer

• Moving a fraction of the data while still serving it, which is the hard part — not the arithmetic.
• The fraction depends on the scheme: 79.99% for modulo going four to five; for a ring it is whatever the arriving node ends up holding, which with enough virtual nodes converges on the 1/(n+1) share — ours moved 18.6% against a 20% ideal.
• You need the routing to be correct during the move, so reads either follow the key to its old home or the new one, never neither.
• That is why pre-splitting is popular: create many more logical partitions than nodes up front, and resharding becomes reassigning partitions rather than rehashing keys.
• And rehearse it, because the failure modes are operational — a half-migrated key space is a much worse outage than a full one.
• The vendors document the real bill. MongoDB can reshard a live collection and still requires twice the storage, a two-second write block, a disabled balancer, and a minimum duration of five minutes. Elasticsearch can only split an index that is read-only, into a multiple of its current shard count, bounded by a setting fixed when the index was created — and an index with a prime number of shards can only ever be shrunk to one.

Likely follow-up: “Why does pre-splitting help so much?” The expensive part is recomputing which keys move. If the logical partition count is fixed, no key ever changes partition — only partitions change machines. That is exactly the move Dynamo made from Strategy 1 to Strategy 3, and it is what Vitess does too. It reshards by splitting existing shards; you can contrive a split that puts no existing rows in the new shard, but the docs say of that “it’s not natural for Vitess”.

7. What does a query that doesn’t name the shard key cost?

Show a strong answer

• It has to ask every shard — scatter-gather — and wait for the slowest one.
• Measured inside one database: naming the key read 3 blocks from one partition; not naming it read 3,337 across all eight.
• But most of that gap is the index, not the pruning. With both queries forced to scan, pruning alone was worth 7.15× — 467 blocks against 3,337. The rest was that the pruned query also had an index to use.
• So “every partition” isn’t automatically ruinous. A query on an indexed non-key column touched all eight and cost 30 blocks — nearly seven times less than a pruned query with no index.
• Across a network it’s worse than the block count suggests, because you add the slowest shard’s latency and a fan-out that grows with the cluster.
• And naming the key does not guarantee a targeted query. MongoDB’s own wording: the router “may still perform a broadcast operation to fulfill these queries”, depending on data distribution and selectivity.
• The fix is usually a second copy keyed differently, or a search index, not a cleverer query.

Likely follow-up: “What about aggregates?” If the store can aggregate per shard and merge — PostgreSQL’s partitionwise aggregation, off by default, took our group-by from 3,337 blocks to 353 — it’s far cheaper than shipping rows.

8. When should you shard at all?

Show a strong answer

• Later than people think, and for a named reason: write throughput a single leader can’t take, a dataset that won’t fit, or a regulatory need to keep data in places.
• “The database is big” is not a reason on its own. Part 18 measured how far indexes go inside one machine, and this part measured what partitioning buys there. The only documented size threshold I could find anywhere is PostgreSQL’s, it is about partitioning a single server, and it is modest: “the size of the table should exceed the physical memory of the database server”. MongoDB’s own “Considerations Before Sharding” gives no number at all.
• Try the cheaper things first: read replicas, caching, archiving cold data, one-machine partitioning.
• Because sharding costs you cross-shard transactions, cross-shard joins, global uniqueness, and an operational burden that never goes away.
• And once you shard on a key, that key is very hard to change. It is closer to a schema decision than a configuration one.

Likely follow-up: “How would you know you’re close?” Watch the single-writer limits — commit latency under load, replication lag, vacuum keeping up — and forecast against growth rather than waiting for the wall.

Sources

• Labs: system-design/checks/part21_partitioning/run.py — a million keys placed by modulo and by a consistent-hashing ring at 1, 16 and 256 points per node, measuring what moves when the cluster changes, how evenly each scheme fills its nodes, a Zipf workload against a balanced placement, and range against hash for keys that arrive in order; and postgres.py, which measures partition pruning, run-time pruning, partitionwise aggregation, the unique-constraint rule and partition skew against PostgreSQL 18 in a container
• Karger, Lehman, Leighton, Levine, Lewin and Panigrahy, Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, STOC 1997 — the definition, the monotonicity proof, the replication trick that later became virtual nodes, and the original motivation: clients that disagree about which machines exist. Quotations here are from the authors’ preprint, verbatim including its own typos
• Dynamo: Amazon’s Highly Available Key-value Store, SOSP 2007 — §4.2 for virtual nodes and the heterogeneity argument, §6.1 for the measured load imbalance in production, §6.2 for the three partitioning strategies and why Dynamo left the random-token ring
• Apache Cassandra: Dynamo architecture for vnode costs and why failed nodes are not auto-rebalanced, production recommendations for token-count guidance, and cassandra.yaml for num_tokens
• PostgreSQL 18: Table Partitioning for the three methods, the pruning phases, the unique-constraint rule and the partition-count advice; Planner Method Configuration for enable_partition_pruning, enable_partitionwise_aggregate and enable_partitionwise_join
• Amazon DynamoDB: partition key design, distributing your workload, write sharding and burst and adaptive capacity for the per-partition ceiling and what adaptive capacity can and cannot do for one key
• MongoDB: hashed sharding, the query router, the balancer and resharding a collection
• Elasticsearch: sizing your shards, split and shrink; and Vitess on resharding and vindexes

What to remember

• Modulo re-derives every key when the node count changes: 79.99% moved adding a fifth node, 99.01% adding a hundred-and-first.
• A consistent-hashing ring moves exactly the keys the arriving node ends up holding, and nothing else. Measured exact, at every points-per-node.
• So the question is never how much a ring moves. It is how lopsided that amount is — and with one point per node it is a lottery, 1.18× to 3.61× across 200 rings.
• Virtual nodes shrink the tail: at 256 points the busiest node owned 1.06× the even share typically and 1.16× at the 99th percentile, over 20,000 rings.
• A ring is only as even as its hash — and “it avalanches” is not enough. FNV-1a sent consecutive node names to evenly spaced positions and gave one node 90.19% of the circle, reproducibly.
• Range partitioning puts every new write on one node when the key increases, while the dashboard looks balanced.
• A hot key cannot be partitioned away. It lives on one node.
• Hash partitioning spreads tenants, not tenants’ rows: one big tenant still makes one big partition.
• A query that names the partition key is one partition; one that doesn’t is all of them. But pruning alone was worth 7.15× here, and the index was worth far more — every partition with an index is still cheap.

Choosing a shard key is choosing which questions stay cheap for the rest of the system’s life.