hash ring
You have keys and you have servers, and something has to decide which server owns which key. The obvious answer is hash(key) % serverCount. It is one line and it is uniform, and it falls apart the moment the server count changes: nearly every key moves at once, so every cache is cold and every replica is in the wrong place.
A hash ring puts the servers on the same circle as the keys and gives each key to the first server clockwise of it. Adding a server then takes one arc from one neighbour and leaves everything else alone. About 170 lines, no dependencies, and no clock or random source anywhere: a ring is a pure function of its node set, which is what lets the tests assert exact key movement instead of a percentage.
Running live in this tab. Source in lib/hashring.
The ring
The band is the hash space, 0 at the top running clockwise. Small outlined dots are the servers. Filled dots are keys, coloured by whoever owns them. Hover a key to watch it walk clockwise to its owner.
What a node change costs
Both strips hold the same keys in the same order, coloured by owner. Add or remove a node and watch them: the ring recolours one arc's worth of dots, modulo recolours nearly everything. Keys that just changed owner are outlined.
Why modulo moves everything
Not because the hash is bad. Because the node count is baked into the answer.
With four nodes, a key hashing to 17 lands on 17 % 4 = 1. Add a fifth and the same key computes 17 % 5 = 2. Nothing about the key changed and nothing about node 1 changed, but the answer did, because the divisor is part of the arithmetic. Work through a few keys and you find only the ones where the remainder happens to agree stay put, which is about 1 in N of them.
The ring never divides by the node count. A key's position is fixed forever the moment you hash it, and so is every node's. All that changes when a node arrives is that a new boundary appears on the circle, so the only keys affected are the ones in the arc it landed in. This is the property worth remembering, and it is stronger than the percentage people quote:
- Removing a node moves only the keys that node owned. Nothing else is touched.
- Adding a node moves keys onto the new node only, never between two existing ones.
Both are exact, not statistical, so hashring/test.mjs asserts them directly: after a removal it checks that zero keys belonging to surviving nodes changed hands, and after an addition it checks that every moved key landed on the newcomer. The familiar "only 1/N of keys move" is a consequence of those two, and since arc widths are random it is only true on average, so that one is tested with a tolerance.
One point per node is not enough
Consistent hashing has a second problem, and it shows up immediately. Node positions are just hashes, so they land unevenly, so the arcs come out uneven too.
Drag that to 1 and one node is usually carrying two or three times its share. The fix is to stop treating a node as one point. Hash it under alpha#0, alpha#1, alpha#2 and so on, and it occupies many small arcs scattered around the circle instead of one arbitrary large one. Many small random arcs average out; one does not.
Virtual nodes buy two other things. Memory becomes the only cost of a node's weight, so a machine with twice the capacity can simply take twice the points. And when a node dies its load spreads across every remaining node rather than dumping entirely onto its one clockwise neighbour, which is the difference between a degradation and a second outage.
The slider stops at 32 to keep the drawing readable. Real systems use 128 to 256 per node, where the skew settles near 1.05x. At 10,000 keys the test suite measures 2.09x with one point per node and 1.07x with 128.
Trade-offs
| scheme | state | lookup | keys moved when N changes |
|---|---|---|---|
| hash % n | the node list | O(1) | about (N-1)/N, nearly all of them |
| ring, 1 point per node | N points | O(log N) | about 1/N, but load is lumpy |
| ring, v points per node | N×v points | O(log Nv) | about 1/N, load close to even |
| lookup table | one entry per key | O(1) | whatever you decide, if you can store it |
The ring with virtual nodes is the usual answer because the state is small, the lookup is a binary search, and nobody has to coordinate: two servers holding the same node list compute the same owner without talking to each other. That last property is why this shows up in Dynamo, Cassandra, Riak, and most memcached clients.
Usage
import { createRing } from "./lib/hashring/ring.mjs";
const ring = createRing({ vnodes: 128 });
ring.addNode("cache-1");
ring.addNode("cache-2");
ring.addNode("cache-3");
ring.lookup("user:1042"); // -> "cache-2"
ring.lookupN("user:1042", 3); // -> ["cache-2", "cache-1", "cache-3"], for replicas
ring.removeNode("cache-2"); // only cache-2's keys are reassigned
node hashring/test.mjs # 39 tests, no clock, no seedlookupN is how replication falls out of this for free: keep walking clockwise past the owner and the next distinct nodes are the replica set, with no placement table to keep in sync. A shorter replica set is always a prefix of a longer one, so raising the replication factor adds a copy rather than reshuffling the existing ones.