When you shard data across N servers with hash(key) % N, changing N remaps almost every key — a catastrophe for a cache or database, because nearly all data suddenly lives on the wrong node. Consistent hashing solves this: adding or removing a node moves only a small fraction of keys (roughly 1/N), leaving the rest untouched.
The idea: hash both nodes and keys onto a circular space (the "ring"). A key is owned by the first node encountered walking clockwise from the key's position. To keep the load balanced, each physical node is placed at many positions using virtual nodes (replicas).
Implement ConsistentHashRing. A hash function is provided — call self._hash(...); you never implement hashing yourself.
__init__(self, virtual_nodes: int = 100)add_node(self, node: str) -> None — place virtual_nodes positions for node on the ring (at self._hash(f"{node}#{i}") for i in 0..virtual_nodes-1).remove_node(self, node: str) -> None — remove all of that node's positions.get_node(self, key: str) -> str | None — return the node owning key (first position clockwise from self._hash(key), wrapping around the ring). Return None if the ring is empty.Requirements:
virtual_nodes ring positions.Constraints:
get_node must be O(log R) where R is the number of ring positions (binary search)Official solution locked
Give the problem a real attempt before peeking — revealing it affects your credit for this problem for 4 hours.