Explain Consistent Hashing with Routing Pseudocode

Explain consistent hashing and sketch pseudocode for routing a key to a server. Show how the routing rule behaves when the lookup reaches the end of the hash space, and explain why changing the server set need not remap every key. The exercise asks for an algorithm explanation and pseudocode. It does not prescribe a callable API, hash function, token format, or exact output for a supplied input. ### Constraints & Assumptions - State the hash-space model you choose and use it consistently for keys and server positions. - Distinguish a server's identity from its position in the hash space. - Resolve empty membership and hash collisions explicitly rather than silently assuming they cannot occur. - Virtual nodes, replication, and concurrent membership changes are design choices to discuss; they are not mandatory features of the initial sketch. ### Clarifying Questions to Ask - Is the goal to explain the routing algorithm or to implement a particular interface? - Is membership fixed during a lookup, and how is a new membership view distributed? - Should each server have one position or multiple virtual-node positions? - What should happen when no server is available, and how should equal hash positions be handled? ```hint Compare the part of the key space assigned to a server before and after adding one new position. Also trace a key whose hash lies beyond the last stored position. ``` ### What a Strong Answer Covers The explanation should define one complete routing rule, give readable pseudocode consistent with that rule, and handle wraparound and empty membership. It should identify which keys move when a server position is added or removed, distinguish limited remapping from balanced load, and state lookup and membership-update costs for the chosen data structure. ### Follow-up Questions - What changes when one physical server owns several virtual-node positions? - Why can a hot key overload a server even if the number of keys is evenly distributed? - What can go wrong if two clients temporarily use different membership views?