Part 3 · System design · Data, caching and scale
Consistent hashing
Spreads keys across servers so that adding or removing a server moves about 1/n of the keys, not nearly all of them.
How it works
Hash every server onto a circle, many times each (virtual nodes) so the slices even out. Hash the key onto the same circle and walk clockwise to the first server point: that server owns the key. A new server only takes over the arcs just before its own points. Compare hash(key) % n: going from 3 to 4 servers moves about 3 in 4 keys, which empties every cache at once.
| lookup | O(log points), binary search on the sorted ring |
| add or remove a server | moves about 1/n of the keys |
| virtual nodes | more points per server = more even spread |
| hash % n instead | moves about (n-1)/n of the keys on resize |
Reach for it when
- Sharding a cache across servers
- Choosing the partition for a key in a distributed store
- Sticky routing: the same user to the same worker
Implementation (JavaScript, tested)
// FNV-1a plus a final mix so similar keys ("user:1", "user:2") land far apart
const hash32 = s => {
let h = 2166136261;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 16777619);
}
h ^= h >>> 16;
h = Math.imul(h, 0x85ebca6b);
h ^= h >>> 13;
h = Math.imul(h, 0xc2b2ae35);
return (h ^ (h >>> 16)) >>> 0;
};
class HashRing {
constructor(vnodes = 100) {
this.vnodes = vnodes; // points per server; more points = more even slices
this.ring = []; // sorted [hash, server]
}
add(server) {
for (let v = 0; v < this.vnodes; v++) this.ring.push([hash32(`${server}#${v}`), server]);
this.ring.sort((a, b) => a[0] - b[0]);
}
remove(server) {
this.ring = this.ring.filter(([, s]) => s !== server);
}
get(key) {
const h = hash32(key), r = this.ring;
let lo = 0, hi = r.length; // first point clockwise with hash >= h
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (r[mid][0] < h) lo = mid + 1;
else hi = mid;
}
return r[lo % r.length][1]; // past the last point: wrap to the first
}
}Traps
- Without virtual nodes one server can own a huge arc and take most of the traffic.
- It spreads keys, not load per key. A hot key still lands on one server: replicate it or cache it locally.
- Moved keys are cold on the new server. Expect a short spike on the database.
In real systems: Cassandra and DynamoDB place data on a token ring. Redis Cluster uses 16384 fixed hash slots, the same idea with a lookup table. Envoy and Nginx offer ring hash load balancing.
Say out loud: hash mod n reshuffles almost everything when n changes. A ring with virtual nodes moves only about 1/n of the keys, and a lookup is a binary search.