Consistent Hashing for Distributed Caches
Modulo sharding (`hash(k) % N`) reshuffles almost all keys when cluster nodes scale, triggering cache stampedes. Consistent Hashing arranges nodes on a $360^\circ$ circle; adding or removing a node affects only its immediate neighbors ⭕.
import bisect
import hashlib
class HashRing:
def __init__(self, nodes):
self.ring = []
self.node_map = {}
for n in nodes:
h = int(hashlib.md5(n.encode()).hexdigest(), 16)
bisect.insort(self.ring, h)
self.node_map[h] = n
def get(self, key):
h = int(hashlib.md5(key.encode()).hexdigest(), 16)
idx = bisect.bisect_right(self.ring, h)
if idx == len(self.ring):
idx = 0
return self.node_map[self.ring[idx]]
ring = HashRing(["node_1", "node_2", "node_3"])
print(f"Key assigned to: {ring.get('session:user_123')} ⭕")
# 88. Consistent Hashing for Distributed Caches Modulo sharding (`hash(k) % N`) reshuffles almost all keys when cluster nodes scale, triggering cache stampedes. Consistent Hashing arranges nodes on a $360^\circ$ circle; adding or removing a node affects only its immediate neighbors ⭕. ```python import bisect import hashlib class HashRing: def __init__(self, nodes): self.ring = [] self.node_map = {} for n in nodes: h = int(hashlib.md5(n.encode()).hexdigest(), 16) bisect.insort(self.ring, h) self.node_map[h] = n def get(self, key): h = int(hashlib.md5(key.encode()).hexdigest(), 16) idx = bisect.bisect_right(self.ring, h) if idx == len(self.ring): idx = 0 return self.node_map[self.ring[idx]] ring = HashRing(["node_1", "node_2", "node_3"]) print(f"Key assigned to: {ring.get('session:user_123')} ⭕") ``` To eliminate hot spots caused by uneven ring distributions, real systems (like Cassandra and DynamoDB) generate hundreds of "virtual nodes" per physical server (e.g. `node_1#1`, `node_1#2`), distributing keys evenly 🚀! --- ### Question Why is modulo hashing (`hash(k) % N`) unacceptable for dynamically auto-scaled cache clusters? 🧠 - [ ] a. Changing N reshuffles virtually every key across the fleet, wiping out cache hit rates ⭕ - [ ] b. Modulo calculations are computationally too slow for network routers - [ ] c. It limits the maximum number of servers in a cluster to 256 - [ ] d. Cache keys must be integers rather than strings --- ### Challenge Implement `HashRing(nodes)` with MD5 hashes and `bisect_right`. Query for `key = 'user:99'` on `['cache_1', 'cache_2', 'cache_3']`. Print the assigned node. 🎯 <details> <summary>Solution</summary> ```python import bisect import hashlib class HashRing: def __init__(self, nodes): self.ring = [] self.nmap = {} for n in nodes: h = int(hashlib.md5(n.encode()).hexdigest(), 16) bisect.insort(self.ring, h) self.nmap[h] = n def get(self, key): h = int(hashlib.md5(key.encode()).hexdigest(), 16) idx = bisect.bisect_right(self.ring, h) if idx == len(self.ring): idx = 0 return self.nmap[self.ring[idx]] ring = HashRing(['cache_1', 'cache_2', 'cache_3']) print(ring.get('user:99')) ``` </details>