Consistent hashing ring with virtual nodes.
Hash nodes and keys onto a ring, walk clockwise with binary search, and prove that adding a node only moves the keys it takes over.
With hash(key) % N, changing N remaps almost every key. Day 1, section 3.2 puts nodes and keys on a ring instead: a key belongs to the first node position at or after its hash, walking clockwise and wrapping past the end. Adding a node only takes over the arc just before it. Each physical node gets many positions (virtual nodes) so the arcs even out.
Implement ConsistentHashRing(nodes=None, virtual_nodes=150):
| Method | Does |
|---|---|
add_node(node) |
puts virtual_nodes positions on the ring for node: position i is ring_hash(f"{node}:{i}"). Adding a node that is already on the ring changes nothing |
remove_node(node) |
takes all of the node's positions off the ring. Raises KeyError for a node that isn't on it |
get_node(key) |
the node owning key: the first position >= ring_hash(key), wrapping to the smallest position when the hash is past the last one. Raises LookupError on an empty ring |
nodes() |
the set of physical nodes |
Use the given ring_hash (MD5 as an integer, the same as the lesson's _hash) for both keys and positions, so the tests can check exact placements.
get_node runs on every request, so it should be O(log n) in the number of positions: keep the positions sorted and binary search them with bisect, as the lesson's implementation does.
The hidden tests check the property that makes consistent hashing worth it: when you add a node, every key that moves, moves to the new node, and only about 1/(N+1) of them move.
Write your code, then run 3 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and Python restarts, your code stays.