Back
+20 XP
Concept

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')} ⭕")

# 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>

Checkpoint

Why is modulo hashing (`hash(k) % N`) unacceptable for dynamically auto-scaled cache clusters? 🧠

Practice

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. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks