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

A load balancer spreads incoming requests over a pool of backend servers. This exercise has two parts: first debug a round-robin server selector, then implement consistent hashing as a selection strategy. ### Constraints and Clarifications - Servers are identified by unique strings, and the pool can change at runtime as servers are added or removed. - Assume the selector object is shared by all request-handling threads of one process. ### Clarifying Questions - What should happen when a request arrives and the pool is empty? - When a server is removed mid-rotation, which server should come next? - Is removing a server that is not in the pool an error or a no-op, and can the same server be added twice? - For consistent hashing, what is the routing key (for example, a user ID or session ID), and how evenly must load be spread across servers? - Should servers with more capacity receive proportionally more traffic? ### Part 1 — Debug the round-robin selector The implementation below is illustrative. It is meant to hand out servers in strict rotation (A, B, C, A, B, C, and so on) and to keep rotating correctly while servers are added or removed. ```python class RoundRobinBalancer: def __init__(self, servers): self.servers = servers self.index = 0 def add_server(self, server): self.servers.append(server) def remove_server(self, server): self.servers.remove(server) def next_server(self): server = self.servers[self.index] self.index = self.index + 1 if self.index > len(self.servers): self.index = 0 return server ``` Find every bug you can. For each one, give a short sequence of calls that exposes it, explain the root cause, and then write a corrected class. ```hint Trace a full rotation Call `next_server` by hand on a three-server pool and keep going past the point where the rotation should wrap around to the first server. ``` ```hint Change the pool mid-rotation Consider what the stored index means after the pool shrinks, depending on whether the removed server sat before, at or after the position it points to. ``` #### What This Part Should Cover - Each defect with a concrete call sequence that reproduces it and its root cause - A corrected implementation that keeps strict rotation across additions and removals - Behavior with an empty pool and under concurrent callers ### Part 2 — Implement consistent hashing Round robin ignores the request, so requests with the same key (for example, the same user) land on a different server each time, which defeats per-server caches and session state. Implement a consistent-hash ring so that a given key always maps to the same server while the pool is unchanged, and adding or removing one server moves only a small fraction of keys (about the share owned by that server) instead of reshuffling almost every key, as `hash(key) % number_of_servers` would. ```python class ConsistentHashRing: def add_server(self, server: str) -> None: ... def remove_server(self, server: str) -> None: ... def get_server(self, key: str) -> str: ... ``` ```hint One space for both Map servers and keys into the same hash space, and decide which server owns a key from their relative positions. ``` ```hint Check the balance With only a few servers, estimate how evenly your structure divides the key space, and think about what you could change to even it out. ``` #### Clarifying Questions for this Part - Must the key-to-server mapping be identical across processes and restarts, for example when several load-balancer instances route the same keys? #### What This Part Should Cover - The ring data structure and the cost of lookups and membership changes - The choice of a hash function that is stable and well distributed - Load balance across servers, including how uneven shares are evened out - Which keys move, and where, when a server joins or leaves ### What a Strong Answer Covers - A systematic debugging process: reproduce, explain the root cause, fix, and add a regression test - Thread-safe designs for both selectors - When round robin is the right choice and when consistent hashing is - Tests for both parts: rotation order, pool changes, stability of the key-to-server mapping, and the fraction of keys that move ### Follow-up Questions - Servers have different capacities. How do you weight both the round-robin selector and the ring? - With consistent hashing, one very popular key overloads its server. What can you do without losing affinity for all the other keys? - How does your ring compare with rendezvous (highest-random-weight) hashing in lookup cost, memory and key movement? - A server fails health checks for a few seconds and then recovers. How do you avoid moving its keys away and back repeatedly?