The problem with modulo hashingCore idea
With modulo hashing, server = hash(key) % N. Change N and the answer changes for nearly every key, which means moving nearly all your data. At scale, that is unacceptable.
| Key (hash) | 4 servers: hash % 4 | 5 servers: hash % 5 | Moved? |
|---|---|---|---|
| key1 (7) | server 3 | server 2 | ✗ moved |
| key2 (12) | server 0 | server 2 | ✗ moved |
| key3 (19) | server 3 | server 4 | ✗ moved |
| key4 (25) | server 1 | server 0 | ✗ moved |
The hash ringHow it works
Consistent hashing places both keys and servers on a circle of hash values (0 to 2³² − 1). To find a key's server, hash the key and walk clockwise until you reach a server.
When a server is added, only the keys between it and the server before it move. When a server is removed, only its own keys move, to the next server clockwise.
ImplementationHow it works
class ConsistentHashRing {
private ring = new Map<number, string>();
private sortedKeys: number[] = [];
addServer(server: string) {
const h = this.hash(server);
this.ring.set(h, server);
this.sortedKeys.push(h);
this.sortedKeys.sort((a, b) => a - b);
}
getServer(key: string): string {
const h = this.hash(key);
// First server clockwise (binary search would make this O(log n))
for (const ringKey of this.sortedKeys) {
if (ringKey >= h) return this.ring.get(ringKey)!;
}
// Past the last server: wrap around to the first
return this.ring.get(this.sortedKeys[0])!;
}
private hash(s: string): number {
let h = 2166136261; // FNV-1a, 32-bit
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 16777619);
}
return h >>> 0;
}
}Virtual nodesPattern
With only a few servers, the gaps between them on the ring are uneven, so some servers get far more keys. Virtual nodes fix this: each physical server is placed on the ring many times (say 150), and the load evens out statistically.
Adding and removing serversScale
Adding a server only moves the keys between it and its neighbour. With 3 servers and 1M keys, adding a 4th moves about 250K keys (25%), compared with about 750K (75%) under modulo hashing.
| Approach | Keys moved when a server is added | Balance |
|---|---|---|
| Modulo hashing | ~all keys | Even (while N is fixed) |
| Consistent hashing | ~1/N of keys | Uneven without virtual nodes |
| Consistent + virtual nodes | ~1/N of keys | Even (150+ vnodes) |
Where it is usedReal world
Amazon DynamoDB
Spreads data across storage nodes.
Apache Cassandra
Partitions data using a ring with virtual nodes.
CDNs
Akamai and Cloudflare route requests to edge servers.
Memcached clients
Spread keys across cache nodes.
Load balancers
Session affinity by hashing the client IP.
Common interview mistakesPitfalls
In the interviewIn the interview
Frequently asked questionsFAQ
What problem does consistent hashing solve?
It distributes keys across a ring of nodes so that adding or removing a node remaps only a small fraction of keys. Naive modular hashing remaps nearly everything when the node count changes, causing mass cache misses; consistent hashing bounds the movement to about 1/n of the keys.
What are virtual nodes and why add them?
Virtual nodes replicate each physical server at many positions on the ring, smoothing out skew caused by uneven hash positions or different machine capacities. More virtual slots mean a server leaving or joining shifts only a balanced slice of keys, and heavier machines map to proportionally more slots.
Where is consistent hashing used in real systems?
Distributed caches like Memcached and DynamoDB-style stores use it to assign data to nodes, and load balancers use it for stable IP hashing so clients keep reaching the same server. It is the standard answer for any horizontally scaled keyed lookup tier.
Now explain consistent hashing to me out loud
I'll give you a design problem and push on the trade-offs, like a real interviewer.