Every consistent-hashing explainer starts with a circle. The circle was never the part that confused me.
What confused me was why anyone needed it. Because the obvious approach looks fine. You have N servers. You hash the key and take it modulo N. Done. It is O(1), it is deterministic, and it needs no coordination.
Then you add a server, and 75% of your keys move.
Not because anything crashed. Because of one character in that formula: the N.
Here is the one-sentence version up front: Consistent hashing is not a better hash function. It is a way to stop the size of your cluster from deciding where every key lives.
Why hash % N looked fine
The setup everyone reaches for first:
server = hash(key) % N
Three servers. A key hashes to 9410. 9410 % 3 = 2. It lives on server 2. Next key, same idea. Perfectly reasonable.
It works for exactly as long as N never changes. And N always changes. Servers crash. You add capacity during peak. You decommission old boxes. Every one of those events rewrites the modulus in that formula.
The subtle part is that N is not a detail of the lookup. It is inside the lookup. Change it, and you have changed the answer for every key at once.
Here is the scale of it.
3 servers -> 4 servers ~75% of keys move
10 servers -> 11 servers ~91% of keys move
99 servers -> 100 servers ~99% of keys move
The bigger the cluster, the worse a single addition gets. At 100 nodes, adding one machine invalidates essentially the whole cache.
And the failure is not graceful. Every moved key becomes a cache miss, and they all arrive together. The database that the cache was shielding now takes the full request rate in one burst. That is the cache stampede, and it is how a routine scaling operation takes down production.
Why 75%?
Forget the algebra for a second and just count.
Three servers, adding a fourth. A key's fate depends only on hash(key) mod 3 versus hash(key) mod 4, so the pattern repeats every 3 × 4 = 12 values. Line up the first twelve:
hash value 0 1 2 3 4 5 6 7 8 9 10 11
mod 3 0 1 2 0 1 2 0 1 2 0 1 2
mod 4 0 1 2 3 0 1 2 3 0 1 2 3
same? Y Y Y . . . . . . . . .
Three of the twelve keep their server. The other nine move.
Three out of twelve is 1/4. And 1/4 is exactly 1/(N+1) with N = 3.
The survivors are always the first N values in each cycle, so with N servers the stayed fraction is 1/(N+1) and the moved fraction is N/(N+1). At three servers that's 75%. At 99 servers it's 99%. The cycle is N × (N+1) values long, which is why the odds get worse as the cluster grows.
The ring
The fix starts by refusing to index servers.
Instead of asking "which number is this server," give every server a fixed position on a circle that represents the full range of the hash function, 0 to 2^32 - 1. Hash the server's name to place it. That position is called a token.
Then hash the keys onto the same circle with the same function.
To find the owner of a key, start at the key's position and walk clockwise. The first token you hit owns it.
owner(key) = first token with hash >= hash(key)
If the key hashes past the highest token, you wrap around to the lowest one. A token's partition is the arc behind it, exclusive of the previous token:
(previous token, this token]
Because the tokens are sorted, finding that first token is a binary search.
function getNode(key, tokens) {
const h = hash32(key);
let low = 0, high = tokens.length - 1;
let idx = 0; // wrap-around default
while (low <= high) {
const mid = (low + high) >>> 1;
if (tokens[mid].hash >= h) { idx = mid; high = mid - 1; }
else { low = mid + 1; }
}
return tokens[idx].nodeId;
}
The important thing is what is missing from that function: N.
The lookup asks "which token is next," not "how many servers are there." Only one of those questions changes when you add a machine.
What that buys you
When you add a server, you drop one new token onto the circle. It splits one existing arc in two and takes the part in front of it. Every other arc keeps its boundaries and its keys.
The numbers flip.
add a node remove a node
hash % N N/(N+1) (N-1)/N
consistent hashing 1/(N+1) 1/N
At three nodes, adding one moves about 25% instead of 75%. At 100 nodes, it moves about 1% instead of 99%. The disaster line and the acceptable line are the same number, just inverted.
That was the first real win. It also exposed a second problem.
The ring's ugly seam
Three servers on a circle are three random points. Random points do not divide a circle into fair thirds. One server can end up owning a huge arc and quietly become the busiest machine in the cluster, while another gets a sliver and sits idle.
The ring is balanced on average, which is a polite way of saying it is not balanced.
The fix is to give every server many positions instead of one. Hash each server with a list of suffixes, and each one becomes a token:
hash("server-1#0") -> token
hash("server-1#1") -> token
hash("server-1#2") -> token
...
These are virtual nodes. Now each machine owns many small arcs scattered around the circle instead of one lumpy slice. It wins some and loses others, and the total lands near its fair share almost every time.
The effect is large and easy to verify. Running the same keys against three nodes:
tokens per node load split std dev
1 76% / 8% / 15% ~30pp
10 47% / 28% / 25% ~10pp
100 34% / 32% / 34% ~1pp
Same three machines. Same hash function. The only change is how many points each one holds, and the imbalance goes from severe to negligible. ("pp" is percentage points.)
There is a free feature hiding in this. If load tracks the number of tokens, you can give the big machine more tokens and it takes more traffic. No new algorithm, just more points.
Reality shows up
Two things break the clean picture.
First, real systems keep copies, usually three, so a dead machine does not lose data. That means the owner is not one node; it is the next R nodes clockwise. Because each machine now holds many tokens, you have to skip duplicates as you walk:
for (let step = 0; list.length < R; step++) {
const node = tokens[(start + step) % tokens.length].nodeId;
if (!chosen.has(node)) { // skip a machine we already picked
chosen.add(node);
list.push(node);
}
}
Without that check, the next three tokens might all belong to the same physical machine, and your three "replicas" live on one box.
Second, none of this fixes a single hot key. The ring spreads out different keys. It does nothing for one key that suddenly gets all the traffic. A viral post or a celebrity stream still lands on exactly one machine. You salt the key, or cache it closer to the client, or add replicas for it. The ring cannot help, and no amount of balance fixes a key that is genuinely popular.
Redis Cluster is worth knowing here because it solves the same problem a different way. It does not use a ring at all. It maps every key to one of 16,384 fixed slots with CRC16(key) % 16384, then assigns slots to nodes. A key never changes slot, so adding a node only moves a few slots. Same goal, different mechanism.
The honest gap
Where this still bites:
The metadata is not free. Each node holds k tokens, so a ring of N nodes stores N × k entries. At 5,000 nodes with 256 tokens each, that is 1.28 million entries to hold and search, and clients have to keep them in sync.
Hot keys remain a real problem. If your workload has one key carrying a large share of traffic, consistent hashing will not save you. That is a caching problem, not a sharding problem.
And weights are static. Token counts encode capacity when you configure the cluster. A machine that gets hot at runtime does not get more load automatically.
What I actually took away
For a while I thought the hard part was the hash function. It was not. The hash was fine from the start.
- The ring does not make hashing better. It makes ownership independent of cluster size.
1/(N+1)instead ofN/(N+1)is the entire payoff, and it comes from removingNfrom the lookup, not from a cleverer function.- Virtual nodes are not an optimization of the ring. They are what makes the ring usable, because random arcs are not fair.
- The one thing it does not fix is a popular key. That is a different problem with different answers.
The hash was never the problem. Carrying the size of the cluster into every lookup was.