Debug a round-robin load balancer, then extend it to consistent hashing

In a debugging round you receive a small round-robin load balancer, which hands out the servers of a pool in turn, together with test cases that it currently fails. Find and fix the bugs. The final step of the round is to change how the balancer assigns requests so that it uses consistent hashing. The report does not include the original code. The version below is a practice stand-in of the same shape: a round-robin balancer with bugs and a test file. It must follow these rules: - The balancer keeps its own copy of the server list it is given; later changes to the caller's list do not affect it. Server names in the list are distinct. - `next_server()` returns the servers in list order, starting with the first, and wraps around after the last. It returns `None` when the pool is empty. - `add_server(s)` puts `s` at the end of the rotation. Adding a server that is already in the pool does nothing. - `remove_server(s)` takes `s` out of the pool. Removing a server that is not in the pool does nothing. After a removal, the rotation continues with the server that would have come next among the remaining servers. - Keep the given tests and their inputs as they are: fix the code, not the tests. ```python # balancer.py class RoundRobinBalancer: def __init__(self, servers): self.servers = servers self.index = 0 def next_server(self): server = self.servers[self.index] self.index = self.index + 1 % len(self.servers) return server def add_server(self, server): self.servers.append(server) def remove_server(self, server): position = self.servers.index(server) self.servers.remove(server) if position <= self.index: self.index -= 1 ``` ```python # test_balancer.py from balancer import RoundRobinBalancer def test_rotation_wraps(): lb = RoundRobinBalancer(["a", "b", "c"]) assert [lb.next_server() for _ in range(5)] == ["a", "b", "c", "a", "b"] def test_remove_next_server(): lb = RoundRobinBalancer(["a", "b", "c"]) assert lb.next_server() == "a" lb.remove_server("b") assert [lb.next_server() for _ in range(3)] == ["c", "a", "c"] def test_remove_unknown_and_add_duplicate_are_noops(): lb = RoundRobinBalancer(["a", "b"]) lb.remove_server("z") lb.add_server("a") assert [lb.next_server() for _ in range(4)] == ["a", "b", "a", "b"] def test_caller_list_is_copied(): pool = ["a", "b"] lb = RoundRobinBalancer(pool) pool.append("c") assert [lb.next_server() for _ in range(3)] == ["a", "b", "a"] def test_empty_pool(): lb = RoundRobinBalancer(["a"]) lb.remove_server("a") assert lb.next_server() is None ``` ### Clarifying Questions - Must the public method names and return values stay exactly as the tests use them? - Is the balancer called from several threads at once? - Should an unhealthy server be skipped, or is health checking out of scope? ### Part 1 — Fix the round-robin balancer Make every given test pass by fixing the balancer, explain each bug you find and why it caused a failure, and add any test you think is missing. ```hint Reproduce before you restyle Run the tests unchanged and work from the first failure's error message and line before touching anything that is only a matter of style. ``` ```hint Follow the pointer For each operation, write down where the stored index should point afterwards, especially when the removed server is the next one or the last one in the list. ``` #### What This Part Should Cover - A systematic loop: reproduce, isolate, explain the root cause, make the smallest fix, rerun everything - Every defect, including those that only appear after removals or on an empty pool - Index bookkeeping that keeps the rotation fair after additions and removals - The given tests left unchanged, plus regression tests for cases they miss ### Part 2 — Switch to consistent hashing Requests now carry a key, such as a user id, and each key must go to the same server as long as the pool does not change. Add `get_server(key)` based on consistent hashing, keeping `add_server` and `remove_server`, so that adding or removing one server moves only the keys that have to move. ```hint One circle for keys and servers Picture servers and keys placed on the same circle of hash values, and ask which keys change owner when one server joins. ``` #### Clarifying Questions for this Part - How many servers and keys must it handle, and how even must the load be? - Do servers have different capacities that the assignment should respect? - Must the mapping be identical across processes and restarts? #### What This Part Should Cover - A ring of sorted positions with a fast lookup of the next position - Virtual nodes for an even spread, and a hash function that is stable across processes - Behavior on add, remove and an empty pool, with the complexity of each operation - Tests that show stability and minimal key movement ### What a Strong Answer Covers - A structured search for bugs driven by the failing tests, not rewrites for style - A correct root-cause explanation for each fix - The original tests and inputs untouched, with focused new tests added - A correct consistent hashing implementation with virtual nodes and a stable hash - The complexity and trade-offs of both assignment schemes, with time managed so the second step is reached ### Follow-up Questions - Make the balancer safe when many threads call it at once. What exactly must be atomic? - Add server weights so that a larger server gets proportionally more traffic, in both the round-robin and the consistent hashing versions. - How many virtual nodes per server would you choose, and how would you measure whether the load is even? - A server drops out briefly and comes back. How do you avoid moving its keys away and back?