Adding one node to a mod N placement does not move a small share of the keys; it moves N/(N+1) of them, which is nearly all. A consistent-hash ring moves 1/(N+1), which is the rest of the same whole. The two fractions add to exactly one, and that single line is the entire argument for consistent hashing.
Core ideas
The counting is easy once the object being counted is right, and the object is a complete cycle of hash values rather than a sample of keys.
A key sits on shard h mod N. Change N to N + 1 and h mod (N+1) is a different residue for almost every h: the two agree only when both equal the same value below N. Adding one node does not perturb the placement, it replaces it, and the keys that happen to stay are a coincidence rather than a design.
On a consistent-hash ring each node owns the arc ending at its token, and a key belongs to the first token at or after its position. Adding a node adds tokens and moves nothing else, so the keys that relocate are exactly the keys in the arcs the newcomer claimed — 1/(N+1) of the ring in expectation, and whatever the newcomer's arcs actually measure on a given placement.
N/(N+1) + 1/(N+1) = 1. The keys that mod N moves and the keys that a ring moves are the entire key set between them, so the comparison is not “somewhat better” — one scheme moves all but a sliver and the other moves the sliver. At N = 7 that is 87.50% against 12.50%, and the ratio only widens as the fleet grows.
The material
The misconception first, then the enumeration that refutes it, then the ring and the identity the two fractions satisfy.
The expectation almost everybody brings to this is that adding one node to a fleet of seven moves about a seventh of the keys — the share the new node will end up owning. Under mod N assignment that is wrong, and it is wrong by a factor of about N: the true figure at N = 7 is seven eighths, which is 6.13 times the one-seventh prediction.
Assigning key k to shard h(k) mod N and then to h(k) mod (N+1) moves a fraction N/(N+1) of a complete cycle of hash values. At N = 7 that is 7/8; at N = 100 it is 100/101.
Take the hash values h = 0, 1, …, N(N+1) − 1, one complete cycle. A key stays exactly when h mod N = h mod (N+1). Write v for that common value; since v is a residue mod N it satisfies v ≤ N − 1, and every such v is also its own residue mod N + 1, so the pairs that agree are exactly (v, v) for v = 0, 1, …, N − 1.
Because N and N + 1 are consecutive integers their greatest common divisor is 1, so by the Chinese Remainder Theorem each of the N(N+1) possible residue pairs occurs exactly once as h runs over the cycle. The N agreeing pairs therefore correspond to exactly N values of h, and the remaining N(N+1) − N = N² values move.
The moved fraction is N²/(N(N+1)) = N/(N+1), with no sampling and no approximation anywhere in the argument. The lab performs this enumeration for the N you choose: at N = 7 it reports 49 of 56.
□
The Chinese Remainder Theorem step is the only piece of machinery here, and it is “The Chinese Remainder Theorem” on the Discrete Mathematics path; the residue arithmetic under it is “Modular Arithmetic” on the same path. Everything else is counting.
Under consistent hashing, nodes and keys are both placed on a ring of hash values. Each node holds one or more tokens on the ring, and a key belongs to the first token at or after the key's position, going clockwise and wrapping. Adding a node adds tokens; it changes no existing token's position, so the only keys that move are those in the arcs the new tokens claimed.
The 7/8 is a count over a complete cycle of hash values, so it is exact for that object. A real key set is a finite sample of hashes, and the 600 keys the lab draws moved 519 times — 86.50%, near 87.50% and not equal to it. Neither figure is a correction of the other. The lab prints both because a reader who has only seen the exact fraction will believe their own measurement is a bug.
The ring's numbers work the same way with one extra wrinkle: what moves is the arc the joining node actually took, which on this seed was 12.89% of the ring rather than the 12.50% its expectation predicts. The 82 keys that moved are the keys in that arc. The expectation is a property of the scheme; the arc is a property of the placement, and “Virtual Nodes” is about how far apart those two can be.
7/8 and 1/8 are not two independent measurements that happen to be different. They partition the same key set: every key either changes shard under mod N or does not, and the ones a ring leaves alone are precisely the complement. So the choice between the schemes is not a tuning decision, and a system that reshards regularly under mod N is copying its entire dataset every time it grows. The identity is verified by enumeration at eleven shard counts from 1 to 100 rather than asserted once.
One thing the ring does not fix is the imbalance of the previous lesson. It changes what moves when N changes; it does not make the arcs equal, and with one token a node they are wildly unequal. That is the next lesson.
Interactive
Count the keys that move, both ways, and watch the two fractions add to one
Method
Two fractions, and the check that they add to one. The check is the part that catches an arithmetic slip before it becomes a migration plan.
Not 1/N, and not 1/(N+1). At seven shards going to eight it is 7/8. The quickest sanity check is that the fraction should be close to 1 and get closer as the fleet grows, which is the opposite of what intuition offers.
It is the share of the ring the joining node takes in expectation. On any particular placement the keys that move are the ones in the arcs it actually took, which will be near that fraction rather than on it.
N/(N+1) + 1/(N+1) = 1. If your two fractions do not sum to one, one of them is wrong, and it is almost always the first: 1/N and 1/(N+1) do not add to one with anything.
A fraction is not yet a cost. 7/8 of a 48 TB dataset is 42 TB to move, and “Rebalancing Cost” turns that into a duration and a utilisation. The argument for a ring is that the same growth step moves 6 TB instead.
The exact enumeration first, then the seeded sample of 600 keys, then the identity as a check on both.
The line worth memorising is 49 = 7². The count of moved hashes over a complete cycle is N² out of N(N+1), which is where the whole result comes from, and it is a fact about consecutive integers rather than about hashing.
For a faded rehearsal, take N = 12 going to 13. The supplied first move is the cycle length, 12 × 13 = 156. Produce the count that stays, the count that moves, both fractions as exact ratios, and their sum; then predict the sampled figure the lab will report for 600 keys — not the exact fraction, but the range you would accept — and check it. Say which of your five numbers is exact and which is a draw.
You should be able to state both fractions for any N, justify the mod-N one by the cycle argument, check the pair sums to one, and say why a sampled measurement of either will be near its fraction without matching it.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.