# Implement a Consistent Hash Ring Design a consistent-hashing component that maps arbitrary keys to backend nodes and minimizes remapping when nodes are added or removed. Provide pseudocode or code-level detail for at least: ```text add_node(node_id) remove_node(node_id) get_node(key) -> node_id or no node ``` Use virtual nodes to improve balance. Explain data structures, hash collisions, complexity, concurrency, and how clients agree on the same ring configuration. ### Constraints & Assumptions - The hash function maps node tokens and keys into the same fixed circular space. - Node identifiers are unique and virtual-node token generation is deterministic. - `get_node` returns no node when the ring is empty. - The number or weight of virtual nodes is configurable. - The component need not copy data itself, but it must identify ownership changes needed by a storage or routing layer. ### Clarifying Questions to Ask - Is the ring used only for routing, or must it coordinate data migration and replication? - Are node weights equal, and how quickly may membership change? - Must lookups continue during configuration updates? - How are ring versions distributed and ordered across clients? ### Solving Hints - A lookup needs the first token at or clockwise after the key hash, with wraparound. - Membership changes should publish a complete new view rather than expose a partially edited ring. - Define deterministic behavior when two tokens hash to the same position. ### What a Strong Answer Covers - A sorted token index plus token-to-physical-node ownership. - Correct wraparound, empty-ring, duplicate-add, removal, and collision behavior. - Virtual nodes or weights and their balance/remapping trade-offs. - Expected time complexity for membership changes and lookups. - Immutable snapshots or appropriate locking for concurrent reads. - Ring versioning, replication implications, and migration sequencing. ### Follow-up Questions 1. How would you support a node with twice the capacity of another? 2. What happens when clients briefly use different ring versions? 3. How would you assign replicas in distinct failure domains? 4. How can you test the balance and remapping properties statistically?