Consistent Hashing Ring
Problem
A sharded store places keys on database nodes with a consistent hashing ring. Every node is hashed onto the ring 100 times, as "node#0" to "node#99", to spread its share evenly. A key belongs to the first node point at or after the key's own hash, going clockwise and wrapping around past the top. Use the first 8 hex digits of MD5 as the hash so the placement is identical on every machine. Build the ring and its owner(key) lookup, then show the property that makes it worth using: when a fourth node joins, only the keys it takes over move, and they all move to it.
Examples
Input: nodes = db-a, db-b, db-c; owner("user:42") before and after db-d joins
Output: db-c db-cInput: keys user:0 to user:999, then db-d joins
Output: 251 {'db-d'}
Why: about a quarter of the keys move, and every one of them moves to the new nodeInput: a ring with the single node "solo"; owners of user:0, user:1, user:2
Output: ['solo', 'solo', 'solo']
Why: edge case, every lookup wraps around to the only nodeHints
0 / 3
With hash(key) mod n, adding a node changes n and moves almost every key. A ring avoids that by comparing hashes with each other instead of taking a remainder.
Store the ring as a sorted list of (hash, node) points. Finding the first point at or after a key's hash is a binary search.
Build every virtual point with the stable hash and sort them. owner(key) uses bisect on the list of hashes and takes the index modulo the number of points, so a key past the last point wraps to the first.
Solution
A ring compares hashes instead of dividing by the node count, so a new node only claims the arcs just before each of its own points, and every key that moves goes to the new node while all others stay put. The ring is a sorted list of virtual points, and bisect finds the first point at or after a key's hash in O(log p); taking the index modulo the number of points handles the wrap past the top. Virtual nodes matter because three points would split the ring into very uneven arcs, while a hundred per node averages the shares out. MD5 is used only as a stable, well-spread hash, not for security, and Python's built-in hash would not do because it is randomised for strings on every run. Building the ring is O(p log p) for p points, and each lookup is O(log p).
import bisect, hashlib
def h(text):
return int(hashlib.md5(text.encode()).hexdigest()[:8], 16) # stable across runs
class Ring:
def __init__(self, nodes, vnodes=100):
self.points = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
self.hashes = [p for p, _ in self.points]
def owner(self, key):
i = bisect.bisect_left(self.hashes, h(key)) % len(self.points) # next point clockwise
return self.points[i][1]
keys = [f"user:{i}" for i in range(1000)]
before = Ring(["db-a", "db-b", "db-c"])
after = Ring(["db-a", "db-b", "db-c", "db-d"])
moved = [k for k in keys if before.owner(k) != after.owner(k)]
print(before.owner("user:42"), after.owner("user:42")) # -> db-c db-c
print(len(moved), {after.owner(k) for k in moved}) # -> 251 {'db-d'}
print([Ring(["solo"]).owner(k) for k in keys[:3]]) # -> ['solo', 'solo', 'solo']Stuck on the idea rather than the code? Database Sharding covers it.