principlejavascriptTip
Consistent hashing minimizes key remapping when nodes are added or removed
Viewed 0 times
consistent hashingring hashdistributed cachenode additionload balancingvirtual nodes
Problem
Simple modulo hashing (key % n) requires remapping nearly all keys when n changes (adding or removing a server). This causes cache stampedes and hot spots during scaling events.
Solution
Consistent hashing maps both keys and nodes onto a ring (hash space 0..2^32). Each key is served by the first node clockwise on the ring. Adding/removing a node only remaps keys between the new/removed node and its predecessor — O(k/n) keys instead of O(k).
Why
On a modulo hash ring of n nodes, adding one node changes n to n+1, invalidating roughly n/(n+1) of all mappings. Consistent hashing bounds the remapping to 1/n of keys regardless of total node count.
Gotchas
- Raw consistent hashing produces uneven load — use virtual nodes (multiple ring positions per physical node) for even distribution
- The ring lookup (find next node clockwise) should use binary search on sorted virtual node positions — O(log n) not O(n)
- Used by DynamoDB, Cassandra, Riak, and CDNs for shard routing
Code Snippets
Consistent hash ring with virtual nodes
// Simplified consistent hash ring
class HashRing {
constructor(vnodes = 100) {
this.vnodes = vnodes;
this.ring = new Map(); // position -> node
this.sorted = [];
}
_hash(str) {
let h = 0;
for (const c of str) h = (h * 31 + c.charCodeAt(0)) >>> 0;
return h;
}
addNode(node) {
for (let i = 0; i < this.vnodes; i++) {
const pos = this._hash(`${node}:${i}`);
this.ring.set(pos, node);
}
this.sorted = [...this.ring.keys()].sort((a, b) => a - b);
}
getNode(key) {
const h = this._hash(key);
const idx = this.sorted.findIndex(p => p >= h);
const pos = this.sorted[idx === -1 ? 0 : idx];
return this.ring.get(pos);
}
}Context
Designing distributed caches, sharded databases, or load balancers that scale horizontally
Revisions (0)
No revisions yet.