LESSON 24.2
Rendezvous, jump hash and bounded loads
The alternatives to a hash ring and when each wins, plus consistent hashing with bounded loads for keeping popular keys from overloading one server.
7 min read
The ring isn't the only way to get stable key placement. Two other algorithms are simpler in important cases, and a refinement of the ring tackles a problem none of them solve on their own: uneven popularity.
Rendezvous hashing
Also called highest random weight (HRW). For a key, score every node with hash(key, node) and choose the highest. For replicas, take the top N.
- Nodes A, B, C. For key "photo42": score(A) = 0.71, score(B) = 0.93, score(C) = 0.12.
- B owns it; with 2 replicas, B then A.
- If C leaves, nothing changes for this key. If B leaves, the key moves to A, its next choice.
It gives perfectly even distribution with no virtual nodes, minimal movement, and natural replica lists. The cost: each lookup computes a hash per node, O(n). With tens or a few hundred nodes that's negligible; with thousands, use a ring or a hierarchical scheme.
Jump consistent hash
A few lines of code that map a 64-bit key to a bucket number from 0 to n−1 using a pseudo-random sequence. It needs no memory for a ring, is very fast, distributes keys almost perfectly evenly, and when buckets grow from n to n+1, only 1/(n+1) of keys move.
The catch: buckets are numbered. You can add or remove the last bucket, but not an arbitrary one. That fits data shards, which are themselves replicated and never disappear, and not raw servers, which fail at random.
Comparing them
Hash ring + virtual nodes
- Arbitrary joins and leaves
- O(log n) lookups
- Weighted nodes
- Ring state to store and sync
- Imbalance unless many tokens
Pick it when: Large dynamic clusters: Cassandra, cache clients.
Rendezvous (HRW)
- Even without vnodes
- Simple replicas
- No state but the node list
- O(n) per lookup
Pick it when: Up to a few hundred nodes: CDN edge selection, small caches.
Jump hash
- No memory
- Fastest
- Near-perfect balance
- Only add or remove the last bucket
Popular keys break every scheme
All these algorithms balance keys, not load. If one video is a thousand times more popular than average, whichever server owns it is overloaded.
Consistent hashing with bounded loads (published by Google researchers in 2016, used in HAProxy and at Vimeo) fixes this for request routing:
- Set a cap: no server may take more than (1 + ε) times the average load, for example ε = 0.25.
- Route each request to its consistent-hash owner, unless that server is at its cap.
- If it is, walk clockwise to the next server under its cap.
Assignment stays mostly stable, so caches stay warm, while no server exceeds 125% of average. Other tools for hot keys: replicate the key under several names, add a small local cache in front, or split it, as the partitioning module described.
- ε = 0.1more keys pushed off their home server
- tight balance
- ε = 0.25
- a common default
- ε = 1.0almost no movement
- loose balance
Try it
Content Delivery Network HLD
Design a CDN that keeps caches warm and survives viral content.