Say you have ten cache servers and you pick one for each key with hash(key) % 10. It spreads load evenly and it's one line of code. Then traffic grows and you add an eleventh server. Now it's % 11, and almost every key maps to a different server than it did a second ago. Every one of those lookups misses, and all of that traffic falls through to the database at the same moment.
I built a consistent-hash ring for the Lab on this site so I could measure that instead of quoting it. All the numbers below come from that code, over 10,000 keys, averaged across five random key sets.
How bad modulo actually is
With % N, a key stays put only if its hash gives the same remainder for both N and N+1. For most keys it doesn't. Going from N to N+1 servers moves about N/(N+1) of everything, and it gets worse as the cluster grows:
servers modulo moved ring moved ideal
3 → 4 74.8% 26.7% 25%
4 → 5 80.1% 19.6% 20%
9 → 10 89.9% 10.4% 10%The ideal is 1/(N+1): the new server should end up with its fair share, and only that share should move. The ring gets within a point or two of it. Modulo moves nine keys out of ten to add one server to ten.
The ring
Consistent hashing puts servers and keys on the same circle. Hash every server to a point on a 232 ring. Hash a key to a point, then walk clockwise until you hit a server; that server owns the key. In code, the ring is a sorted array and the walk is a binary search:
getNode(key) {
const h = hash(key);
let lo = 0, hi = ring.length;
while (lo < hi) { // first point with hash >= h
const mid = (lo + hi) >> 1;
if (ring[mid].hash < h) lo = mid + 1; else hi = mid;
}
return ring[lo % ring.length].nodeId; // wrap around past the top
}Add a server and it lands somewhere on the circle, taking over only the arc just behind it. Keys everywhere else don't notice. The tests check this directly: after adding a server, every key that moved must have moved to the new server, never between two old ones. Removing a server is the mirror image: only its keys move, to its neighbours.
One point per server isn't enough
With a single point each, five servers carve the circle into five arcs of random length. In my run, one server owned 1.7% of the keys and another owned 35.7%. The fix is virtual nodes: hash each server many times (node-0#0, node-0#1, and so on) so it owns lots of small arcs instead of one big one, and the random lengths average out.
vnodes per server smallest share largest share (ideal 20%)
1 1.7% 35.7%
10 13.3% 26.5%
50 18.8% 21.5%
100 18.4% 21.1%
200 16.9% 22.1%Most of the benefit arrives by about 50. After that it stops improving in any way a single run can show, and the 200 row being slightly worse than 100 is noise from one key set, not a trend. More virtual nodes also means a bigger ring to search and more work on every membership change, so there's no prize for going higher than you need.
The hash function matters more than you'd expect
The code has two hash functions: FNV-1a, which is small, fast and what the modulo mode uses, and MurmurHash3. Build the ring with FNV-1a instead and, with 50 virtual nodes across five servers, the shares come out anywhere from 11.8% to 35.3%. That's not much better than having no virtual nodes at all.
The reason is the virtual node names. node-0#0, node-0#1, node-0#2 differ in one trailing character, and FNV-1a doesn't scramble a change at the end of the input very thoroughly, so a server's points end up bunched together instead of scattered. MurmurHash3 mixes every input bit into every output bit much more aggressively, and the same setup comes out at 18.5% to 21.6%. Same ring, same keys, different hash, which is why the ring uses Murmur.
When you don't need any of this
If the number of servers never changes, or you can afford to rebuild everything when it does, % N is simpler and perfectly even. The ring earns its keep when membership changes while traffic is flowing: caches scaling up and down, nodes failing, a database adding shards. There are other answers to the same problem too, like rendezvous hashing, which skips the ring and scores every server for every key. The ring just happens to be the one that's easiest to draw.