Fix a Round-Robin Load Balancer, Then Implement Consistent Hashing

In a debugging-format onsite round, you work on the component that decides which backend server handles each incoming request. The round has two pieces. First comes a classic round-robin load balancer that has to be made to behave correctly. Then you write an implementation of consistent hashing yourself. The original code from the round was not reported, so practice it as follows. Build the round-robin balancer yourself, and for each defect you would hunt for in an existing implementation, explain how it shows up and which test would expose it. Then write the consistent-hashing router. Use Python or another language you are comfortable with, and keep both components runnable and testable. ### Clarifying Questions - Is the balancer called by many threads at once, or by a single event loop? - Can servers be added or removed while traffic is flowing? - Should the balancer skip servers that are unhealthy, and who tells it that a server is unhealthy? - For consistent hashing, what is the routing key (for example a user or order identifier), and is any hash function acceptable? ### Part 1 — Make the round-robin balancer correct Implement a balancer over an ordered list of server identifiers. It needs `next_server()`, which hands out servers in rotation, plus `add_server(server)` and `remove_server(server)`. Then list the defects you would look for when an existing round-robin implementation misbehaves. For each one, give the symptom it causes and a test that reproduces it deterministically. ```hint Watch the position Trace the stored rotation position when the list shrinks below it, and when a server that comes before it in the list is removed. ``` ```hint Two callers at once Ask whether reading the current position and advancing it happen as one step when two requests arrive together. ``` #### Clarifying Questions for this Part - After a server is removed mid-rotation, must the next server be exactly the removed server's successor, or is one skipped or repeated turn acceptable? - What should `next_server()` do when the pool is empty? #### What This Part Should Cover - Rotation semantics, including wraparound and an empty or single-server pool - How the rotation position stays valid when servers join or leave mid-rotation - Atomicity of the read-and-advance step under concurrent callers - A deterministic test for each defect named ### Part 2 — Implement consistent hashing Requests now carry a key, and every request with the same key should reach the same server. When a server joins or leaves, only a small fraction of keys may change servers. Implement a router with `add_server(server)`, `remove_server(server)` and `get_server(key)`, and state the time complexity of each operation. ```hint Lookup speed Avoid examining every server on each lookup. Think about how the server positions could be stored so that the right one is found quickly. ``` ```hint Uneven shares With only a few servers, check how evenly the key space is divided among them, and what you could change to even it out without adding machines. ``` #### What This Part Should Cover - How servers and keys are mapped into one hash space, and how a key finds its server, including at the top of the range - How evenly load is spread with few servers, and how that is improved - Exactly which keys move when a server joins or leaves - The choice of hash function, and the complexity of add, remove and lookup ### What a Strong Answer Covers - Defects found by reproducing them with failing tests before fixing them, not by rewriting blindly - Correct behavior at the boundaries of both components: empty pool, single server, wraparound - Thread safety and runtime membership changes handled in both parts - A clear contrast between round robin (even spreading, no affinity) and consistent hashing (key affinity, minimal movement) - Accurate complexity for every operation ### Follow-up Questions - How would you add weights so that a server with twice the capacity receives twice the traffic, first in round robin and then in the hash ring? - If a server is unhealthy but still on the ring, where should its keys go, and how do you avoid overloading a single neighbor? - How would you verify, with tests or metrics, that keys are spread evenly and that only the expected keys move when a server is added? - If several balancer instances run in separate processes, how do they agree on the rotation or on the ring?