Consistent Hashing with Virtual Nodes
Modulo sharding (`hash(k) % N`) forces almost 100% of keys to reshuffle when cluster nodes scale. Consistent Hashing places nodes on a circular hash ring so topology changes only remap $K/N$ keys. Virtual nodes eliminate hot-spots by spreading hash points uniformly 🎯🔄.
import hashlib
import bisect
class HashRing:
def __init__(self, vnodes=3):
self.vnodes = vnodes
self.ring = []
self.node_map = {}
def _hash(self, key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node):
for i in range(self.vnodes):
h = self._hash(f"{node}#VN{i}")
bisect.insort(self.ring, h)
self.node_map[h] = node
def get_node(self, key):
h = self._hash(key)
idx = bisect.bisect_right(self.ring, h)
if idx == len(self.ring):
idx = 0
return self.node_map[self.ring[idx]]
ring = HashRing()
ring.add_node("cache-east")
ring.add_node("cache-west")
print(f"Key routed to: {ring.get_node('user:1049')} 🚀")
# 43. Consistent Hashing with Virtual Nodes If you shard your cache using `hash(key) % server_count` and scale from 10 servers to 11, roughly 91% of your keys instantly hash to the wrong server, causing a total cache stampede that melts your primary database 🛑. ```python # Modulo sharding failure: # hash(k) % 10 != hash(k) % 11 (for ~91% of keys!) ``` ### The Ring Architecture 1. **The Hash Circle**: The hash function maps keys to an integer range between $0$ and $2^{128} - 1$. 2. **Server Placement**: Both physical nodes and data keys are mapped onto the identical ring. A key belongs to the first server encountered moving clockwise. 3. **Graceful Scaling**: When a new server joins the ring, it only takes a fraction of keys from its immediate clockwise neighbor. The other $N-1$ servers remain completely untouched! 4. **Virtual Nodes (Vnodes)**: Creating multiple virtual points (e.g. `node-A#0`, `node-A#1`) for each physical machine balances statistical distribution, preventing accidental clustering 🎯. --- ### Interactive Pop-Quiz 🧠#### Why are virtual nodes (vnodes) added to physical servers in a consistent hashing ring? - [ ] To prevent non-uniform clustering of hash positions and eliminate disproportionate hot-spot load 🎯 - [ ] To allocate additional swap space on the physical hard drive - [ ] To compress the memory footprint of the binary routing tree - [ ] To force incoming packets to pass through an SSL proxy --- ### Practical Challenge 🎯 Implement `SimpleRing` with `replicas` (default 3), `add_node(node)`, and `get_node(key)`. Use `bisect.insort` and `bisect.bisect_right` on MD5 integer hashes. Add `'Alpha'` and `'Beta'` with 5 replicas each. Route key `'order_999'`, assert the returned node is in `{'Alpha', 'Beta'}`, and print the assigned node. <details> <summary>Solution</summary> ```python import hashlib import bisect class SimpleRing: def __init__(self, replicas=3): self.replicas = replicas self.ring = [] self.node_map = {} def _hash(self, key): return int(hashlib.md5(key.encode()).hexdigest(), 16) def add_node(self, node): for i in range(self.replicas): h = self._hash(f"{node}:{i}") bisect.insort(self.ring, h) self.node_map[h] = node def get_node(self, key): h = self._hash(key) idx = bisect.bisect_right(self.ring, h) if idx == len(self.ring): idx = 0 return self.node_map[self.ring[idx]] ring = SimpleRing(replicas=5) ring.add_node("Alpha") ring.add_node("Beta") node = ring.get_node("order_999") assert node in ("Alpha", "Beta") print(node) ``` </details>