Implement round-robin load balancer

Implement a load balancer that distributes incoming requests across N backend servers in strict round-robin order. Requirements: (1) Support addServer(id), removeServer(id), and nextServer() operations in O(1) average time; (2) Skip servers marked unhealthy via markHealthy(id, isHealthy) without breaking round-robin fairness; (3) Ensure thread-safe behavior under concurrent calls to nextServer and server updates; (4) Discuss failure scenarios (e.g., a server crashes mid-selection) and how you would design health checks; (5) Provide unit tests and analyze time/space complexity.

Round-Robin Load Balancer

Implement a load balancer that distributes requests across backend servers in strict round-robin order, supporting dynamic membership and health toggling.

Process a list of operations and return a list containing the result of every next operation, in order.

Each operation is a tuple:

• ('add', id) — register server id (appended to the end of the rotation; no-op if it already exists).
• ('remove', id) — remove server id from the rotation (no-op if absent).
• ('mark', id, isHealthy) — mark server id healthy/unhealthy. Unhealthy servers stay in the rotation but are skipped by next (no-op if id absent). New servers start healthy.
• ('next',) — return the next healthy server id in round-robin order, then advance. If there is no healthy server, the result is None.

Round-robin fairness must be preserved across membership and health changes: next always continues from where the previous selection left off, scanning forward and wrapping around, skipping unhealthy servers.

Return a list with one entry per next operation.

Example: [('add','a'),('add','b'),('add','c'),('next',),('next',),('next',),('next',)] -> ['a','b','c','a'].

Constraints

• 0 <= number of operations <= 10^5
• Server ids are unique strings; add of an existing id is a no-op
• remove/mark of an absent id is a no-op
• Newly added servers start healthy
• next returns None when there is no currently-healthy server

Hints

1. Keep an ordered list of server ids to define rotation order, plus a hash map id -> isHealthy so add/mark are O(1) average.
2. Store a single integer pointer for the next candidate. On next, scan forward (with modular wraparound) and pick the first healthy server, then set the pointer just past it.
3. To keep fairness across removals, when you delete a server before the current pointer, decrement the pointer; then re-normalize it modulo the new size so it never points out of range.
4. Thread-safety in a real system: guard the structure with a single mutex (or a read-write lock favoring next). For O(1) lock-free fairness you can use an atomic counter and a copy-on-write snapshot of the healthy-server array.