Loading page…
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.
In JavaScript and TypeScript the class is new ConsistentHashRing(nodes = [], virtualNodes = 150) with addNode, removeNode, getNode and nodes() (a Set). ringHash(key) returns a BigInt: an MD5 is 128 bits, far past the 2^53 that a Number holds exactly, and the given code returns the same values as Python's. BigInts compare with < and > like numbers, but JavaScript has no bisect, so write the binary search yourself. Both KeyError and LookupError become a RangeError (removing a node that isn't on the ring, or looking up a key on an empty ring).
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 4 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and the runtime restarts, your code stays.