Interview frequency: …
Short answer
Consistent Hashing places servers and keys on a virtual circular ring. When a server is added or removed, only a small fraction of keys (roughly K/N) are reassigned instead of redistributing all data as with modulo hashing.
Explanation
With traditional hash(key) % N, changing from four servers to five changes the hash result for about 80% of keys (generally a fraction of N/(N+1)), emptying the cache and causing massive cache invalidation that overloads the database. Consistent Hashing arranges a ring from 0 to 2^32 - 1. Place servers on the ring and assign each key to the next server clockwise. Virtual nodes help distribute load evenly and avoid hotspots.
Code example
import bisect, hashlib
def h(key: str) -> int:
return int(hashlib.md5(key.encode()).hexdigest(), 16)
class Ring:
def __init__(self, nodes, vnodes=100): # virtual nodes spread each server around the ring
self.ring = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
self.points = [point for point, _ in self.ring]
def node_for(self, key: str) -> str:
i = bisect.bisect(self.points, h(key)) % len(self.ring) # first node clockwise from the key
return self.ring[i][1]
before = Ring(["A", "B", "C", "D"])
after = Ring(["A", "B", "C", "D", "E"])
keys = [f"user:{i}" for i in range(10_000)]
moved = sum(before.node_for(k) != after.node_for(k) for k in keys)
print(f"{moved / len(keys):.0%} of keys moved") # ≈ 1/5, versus ≈ 80% with hash % NCommon mistakes
- Implementing Consistent Hashing without virtual nodes, resulting in unfairly uneven load distribution across servers.