Implement a Consistent Hashing Ring From Scratch

Implement a consistent hashing ring from scratch. The ring assigns keys, such as cache keys or request IDs, to a changing set of server nodes. When a node joins or leaves, only a small fraction of the keys may change owner, unlike `hash(key) % node_count`, which reassigns almost every key whenever the node count changes. A possible interface (adjust it as you clarify): ```python class ConsistentHashRing: def __init__(self, nodes: list[str] | None = None): ... def add_node(self, node: str) -> None: ... def remove_node(self, node: str) -> None: ... def get_node(self, key: str) -> str | None: ... ``` Implement the ring, then explain the cost of each operation, how evenly it spreads keys across the nodes, and how many keys move when a node is added or removed. ```hint Find the owner quickly Think about how to store the nodes' positions on the ring so that "the first position at or after this hash" is a fast lookup, including when the hash is past the largest position. ``` ```hint Few nodes, uneven arcs With only a handful of nodes at random positions, the arcs between neighboring positions can differ a lot in length. Consider what would make each node's total share of the ring more even. ``` ### Constraints and Clarifications - Keys and node IDs are strings, and node IDs are unique. - Every process that builds the ring from the same node list must map each key to the same node, so the hash must be deterministic across processes and restarts. Python's built-in `hash()` for strings is randomized per process and does not qualify. - Write the ring yourself; standard-library helpers such as `bisect` and `hashlib` are fine. ### Clarifying Questions - How many nodes and how many lookups per second are expected, and how often does membership change? - Do all nodes have the same capacity, or should some receive proportionally more keys? - Does a caller need several distinct nodes per key, for example for replication? - What should `get_node` return when the ring has no nodes? - Will lookups run concurrently with `add_node` and `remove_node`? ### What a Strong Answer Covers - A sorted structure of ring positions with binary-search lookup and wrap-around past the largest position - A deterministic, well-distributed hash and a defined behavior when two positions collide - Several positions per node to balance load, with the cost in memory and update time - Correct add and remove, including removing every position of a node, and the empty-ring case - The complexity of each operation and the fraction of keys that move when one node joins or leaves, compared with modulo hashing ### Follow-up Questions - Return `R` distinct nodes for a key for replication. How do you walk the ring when one node owns many positions? - One node has twice the capacity of the others. How do you give it twice the keys? - After adding a node, how do you determine which key ranges must be copied to it and from which nodes? - Compare the ring with rendezvous (highest random weight) hashing and with jump consistent hashing. When would you pick each?