Round-Robin Request Router with Health and Dynamic Membership
You are given a list of backend servers and an incoming stream of requests. Implement a round-robin request router that returns the next healthy server for each request.
Requirements
-
Round-robin across servers with correct wrap-around.
-
Only return healthy servers; skip unhealthy ones.
-
Support server add and remove at runtime.
-
Support health state changes at runtime.
-
Ensure fair rotation (no skipped or duplicated assignments when state changes happen).
-
If no healthy servers exist, the router should signal that state (e.g., by raising an exception or returning a sentinel).
Bug-Fix Prompt
You are given failing tests indicating incorrect routing order after server removal and during health flapping. Identify the likely bug causing skipped or duplicated assignments and fix it.
Deliverables
-
Implement the router with the following interface (or equivalent in your language):
-
add_server(id)
-
remove_server(id)
-
set_health(id, healthy: bool)
-
next() -> id (returns the next healthy server)
-
Fix the routing bug so that:
-
The rotation index is correctly advanced only after returning a server.
-
Removal of a server adjusts the rotation index to avoid skipping or duplicating assignments.
-
Write tests for:
-
Single server
-
Multiple servers
-
Removal during routing
-
Health flapping (servers toggling between healthy/unhealthy)
-
Analyze time/space complexity and discuss thread-safety considerations and mitigations.
Assumptions
-
Server IDs are unique and comparable (e.g., strings or integers).
-
If all servers are unhealthy (or there are none), the router returns a defined error or raises an exception.
-
New servers are appended to the rotation and should be included in subsequent calls to next().