Back
+20 XP
Concept

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

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

Checkpoint

Why are virtual nodes (vnodes) added to physical servers in a consistent hashing ring? 🧠

Practice

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

Terminal
01
Tap code blocks below to assemble
Available Blocks