Consistent Hashing

Simple approach: server = hash(key) % N

When N=4:
  key: "user:42" → hash = 7 → 7 % 4 = 3 → Server 3
  key: "user:99" → hash = 15 → 15 % 4 = 3 → Server 3
  key: "user:100" → hash = 22 → 22 % 4 = 2 → Server 2

When N=4 → N=5 (add one server):
  key: "user:42" → hash = 7 → 7 % 5 = 2 → Server 2 (MOVED!)
  key: "user:99" → hash = 15 → 15 % 5 = 0 → Server 0 (MOVED!)
  key: "user:100" → hash = 22 → 22 % 5 = 2 → Server 2 (same)

Result: ~80% of keys map to a different server
  = 80% cache miss storm
  = potential cascading failure

Hash Ring (0 to 2^32-1)

        ┌─── Server B
        │
   ─────●────────────●────────────●─────
       /            /            /
      /            /            /
     /            /            /
    ●            ●            ●
Server A      Key X        Server C

To find which server owns a key:
1. Hash the key to a position on the ring
2. Walk clockwise until you hit a server
3. That server is the owner

Before:  A ──────── B ──────── C
After:   A ──────── B ── E ─── C

Only keys between B and C (now between B and E and between E and C)
need to move. Approximately 1/N of total keys.

With 1000 keys and 3 servers:
  Simple hashing: ~800 keys move (80%)
  Consistent hashing: ~333 keys move (33%)

Before:  A ── B ── C ── D
After:   A ── B ─── D   (C removed)

Only keys that were on C need to move to D.
Approximately K/N keys move.

Without vnodes:
  Server A placed at position 100
  Server B placed at position 500
  Server C placed at position 900

  Ring coverage:
  A: 0-100, 900-1000 → 20% of ring
  B: 100-500 → 40% of ring
  C: 500-900 → 40% of ring

  A gets 20% of traffic
  B gets 40% of traffic
  C gets 40% of traffic
  → Unbalanced!

With vnodes (100 per server):
  Server A: vnodes at positions 5, 15, 25, 35, 45, ...
  Server B: vnodes at positions 10, 20, 30, 40, 50, ...
  Server C: vnodes at positions 8, 18, 28, 38, 48, ...

  Ring coverage:
  A: ~33% of ring (scattered)
  B: ~33% of ring (scattered)
  C: ~33% of ring (scattered)
  → Balanced!

import hashlib
import bisect
 
class ConsistentHash:
    def __init__(self, nodes=None, vnodes=100):
        self.vnodes = vnodes
        self.ring = {}
        self.sorted_keys = []
        
        if nodes:
            for node in nodes:
                self.add_node(node)
    
    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def add_node(self, node):
        for i in range(self.vnodes):
            key = self._hash(f"{node}:{i}")
            self.ring[key] = node
            bisect.insort(self.sorted_keys, key)
    
    def remove_node(self, node):
        for i in range(self.vnodes):
            key = self._hash(f"{node}:{i}")
            del self.ring[key]
            self.sorted_keys.remove(key)
    
    def get_node(self, key):
        if not self.ring:
            return None
        
        h = self._hash(key)
        idx = bisect.bisect_right(self.sorted_keys, h)
        
        if idx == len(self.sorted_keys):
            idx = 0
        
        return self.ring[self.sorted_keys[idx]]
 
# Usage
ch = ConsistentHash(["server1", "server2", "server3"])
print(ch.get_node("user:42"))  # Returns a server
 
ch.add_node("server4")  # Only ~25% of keys move
print(ch.get_node("user:42"))  # Likely same server