Consistent-Hashing-Ring

Consistent hashing decides which node stores which key without a central directory, and without reshuffling everything when the cluster changes size. It is the placement rule behind Dynamo, Cassandra, Riak, memcached client libraries, many CDN caches and most sharded proxies.

How it works. The hash output is treated as a circle from 0 to 1. Every node places virtual nodes (tokens) on that circle at positions hash("node#0"), hash("node#1"), and so on. A key hashes to its own position and belongs to the first token clockwise from it. Each coloured arc in the ring is one such stretch of ownership.

Why virtual nodes. With one token per node the arcs come out wildly uneven — some node ends up owning three times its fair share. Because each node holds many independent tokens, the relative spread of the load falls roughly as 1/√V with V tokens per node. Slide the virtual-node control from 1 upward and watch the spread readout collapse: 1 token is chaos, 16 is tolerable, 100–200 is production practice.

Why not modulo. The obvious scheme, node = hash(key) mod n, is perfectly balanced but catastrophic to resize: going from 5 to 6 nodes moves about 83% of all keys, because every remainder changes. Consistent hashing moves only the keys of the arcs that changed hands — about 1/n of them. Add or remove a node here and compare the two numbers directly.

Reading the numbers

• Peak load — the busiest node as a multiple of the fair share. Anything above about 1.25× means a hot node.
• Spread — the standard deviation of the per-node key counts, relative to the fair share.
• Keys moved — measured exactly by re-assigning every key after the membership change, next to the theoretical 1/n and to what modulo hashing would have cost.

Lookup: enter any key to see its ring position, its primary node, and the next distinct nodes clockwise — that is exactly how a replication factor of 2 or 3 picks the replica set. Click the ring to ask who owns an arbitrary position.

Details and limits: the hash is 32-bit FNV-1a followed by the MurmurHash3 avalanche step. The finalizer matters: without it the high bits of FNV-1a barely change between “node-1#0” and “node-1#1”, the tokens clump, and the load spread comes out two to three times worse than theory. That is the practical reason real systems reach for MD5 or MurmurHash here. Keys are synthetic ("key-0", "key-1", …) and uniform, so this shows placement skew, not the hot-key skew you get from real traffic. Weighted nodes (more tokens for bigger machines) and bounded-load variants are not modelled.