go-hash-ring

What it is#

Consistent hashing with virtual nodes, in Go, written to understand the problem and not just to use it. The goal is that every request for the same key lands on the same node, for caching, request collapsing with singleflight or session affinity.

Every number in the README is measured by go run ./cmd/demo, over 100,000 keys and 4 nodes, and the tests assert what the README claims.

Architecture#

The README frames it as a chain of three solutions, each fixing what the previous one left behind:

hash % N            →  splits evenly, but changing N breaks everything
consistent hashing  →  changing N is cheap now, but the split is terrible
+ virtual nodes     →  splits evenly AND changing N is still cheap

The ring is the uint32 hash space wrapped at the end. Each node is placed 200 times by hashing labels like A#0 … A#199; a key is hashed once and belongs to the first point clockwise. The lookup is a sorted slice plus a binary search. The ring indexes members, not keys, so it is derived state: two processes with the same node list build identical rings without talking to each other.

What I learned#

The measurements, growing from 4 nodes to 5 and splitting load:

• hash % N: 80.0 % of keys change node.
• Consistent hashing: 21.2 % change, close to the theoretical minimum of 1/5 = 20%. It optimises the movement, not the split.
• One point per node: A=32.5% B=6.2% C=7.0% D=54.3%, and when A dies its load goes 100% to C, a cascading failure.
• 200 virtual nodes: worst deviation 2.8 pp, and A’s load spreads to B=33% C=32% D=34%.

What it does not solve: hashing spreads keys, not traffic, so a hot key still lands whole on one node; the guarantee is suspended during a topology change; and every remap is a stampede against the origin. For few, stable nodes, the README recommends rendezvous hashing instead.

What’s next#