Algorithm
Consistent hashing spreads keys across servers so that adding or removing a node moves only the keys that must move; used in caches, stores and load balancers.
Consistent hashing is a way to distribute keys across many servers, introduced by Karger et al. in 1997 for distributed web caching. It treats the hash space as a ring, places both servers and keys on it, and assigns each key to the first server found clockwise from it. Giving each server many points on the ring, called virtual nodes, evens out the load.
With hash(key) % N, changing the server count relocates almost every key, wiping out cache hit rates and forcing massive data movement. Consistent hashing moves on average only 1/(N+1) of the keys when a server joins, and only onto the new server, so clusters can grow and shrink while running. Ketama in Memcached clients, the Amazon Dynamo paper, Cassandra, and the consistent hash options in Nginx and HAProxy all build on this idea.
Start by computing how many keys mod-N sharding moves, then implement a hash ring with a sorted array and binary search. Next, measure how the load spread shrinks as you add virtual nodes, and compare replica selection, rendezvous hashing and jump consistent hash. That foundation also lets you explain the trade-offs clearly in system design interviews.
Adding or removing a node moves about 1/(N+1) of the keys in expectation, and existing nodes never trade keys with each other.
The hash space is a circle and a key belongs to the first node clockwise from it. A lookup is a binary search over sorted positions.
Many points per node reduce load imbalance, and the number of points expresses differences in server capacity.
Replicas go to the next R distinct nodes clockwise; rendezvous hashing and jump hash reach the same goal by other means.
The first 8 bytes of an MD5 digest serve as the ring position, and each node gets 100 virtual nodes inserted into a sorted list with bisect.insort. get uses bisect_left to find the first point at or after the key and wraps around past the end. Adding node D moves only about a quarter of the keys, and removing it again sends every key back to its original node.
consistent_hashing.py
import bisect
import hashlib
def h(key: str) -> int:
return int.from_bytes(hashlib.md5(key.encode()).digest()[:8], "big")
class HashRing:
def __init__(self, nodes=(), vnodes=100):
self.vnodes = vnodes
self.points = [] # sorted hash positions on the ring
self.owner = {} # position -> physical node
for node in nodes:
self.add(node)
def add(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
bisect.insort(self.points, p)
self.owner[p] = node
def remove(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
self.points.pop(bisect.bisect_left(self.points, p))
del self.owner[p]
def get(self, key):
if not self.points:
raise LookupError("ring is empty")
i = bisect.bisect_left(self.points, h(key)) % len(self.points)
return self.owner[self.points[i]]
ring = HashRing(["A", "B", "C"])
keys = [f"user:{n}" for n in range(10_000)]
before = {k: ring.get(k) for k in keys}
ring.add("D")
moved = sum(before[k] != ring.get(k) for k in keys)
print(f"moved {moved / len(keys):.1%} of keys") # about 25%
ring.remove("D")
print(all(ring.get(k) == before[k] for k in keys)) # True
python consistent_hashing.pySix chapters that take you from installation to the core ideas of Consistent hashing.
Ask questions, share experience and trade opinions about Consistent hashing.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.