Least-Connections Load Balancer
Problem
A load balancer routes each request to the server with the fewest requests in flight, breaking ties by the order the servers are listed. Requests arrive as (arrive, duration) pairs sorted by arrival time, and a request that finishes at time t has already left before one arriving at time t is routed. Return the server chosen for each request, and the peak number of requests each server held at once. There are up to 100,000 requests and a handful of servers.
Examples
Input: servers = ["a", "b"], requests = [(0, 10), (1, 2), (2, 5), (3, 1), (4, 1)]
Output: (['a', 'b', 'a', 'b', 'b'], {'a': 2, 'b': 1})
Why: the long request pins a; b keeps emptying just in time for the next short oneInput: servers = ["a", "b", "c"], requests = [(0, 1), (1, 1), (2, 1)]
Output: (['a', 'a', 'a'], {'a': 1, 'b': 0, 'c': 0})
Why: each request is gone before the next arrives, so the tie always goes to aInput: servers = ["x"], requests = [(0, 5), (1, 5), (2, 5)]
Output: (['x', 'x', 'x'], {'x': 3})
Why: edge case, with one server the balancer has no choiceHints
0 / 3
Routing needs the live connection count of each server at the moment a request arrives, so requests that have finished by then must be removed first.
The requests in flight finish in end-time order, not in arrival order. A min-heap of (end time, server) always has the next one to finish on top.
For each request: pop every heap entry ending at or before its arrival and decrement that server's count. Pick the server with the smallest count, taking the first listed on a tie, then increment its count, update its peak and push (arrive + duration, server).
Solution
Least-connections routing only needs each server's current in-flight count, and the counts only change when a request arrives or finishes. Arrivals are processed in order, and before each one a min-heap of end times releases every request finished by then, which is what makes the "finishes at t leaves before t" rule hold. The pick is a min over the servers with the listed order as the tie-breaker, since min returns the first of equal keys. Unlike round robin, this adapts to uneven request lengths, which the first example shows when one long request keeps server a busy. Each request is pushed and popped once and the pick scans s servers, so time is O(n (log n + s)) and space is O(n + s).
import heapq
def least_connections(servers, requests):
active = {s: 0 for s in servers}
peak = {s: 0 for s in servers}
ends, picks = [], [] # ends: min-heap of (end time, server)
for arrive, duration in requests:
while ends and ends[0][0] <= arrive: # finished requests leave first
active[heapq.heappop(ends)[1]] -= 1
best = min(servers, key=lambda s: active[s]) # ties go to the earlier server
active[best] += 1
peak[best] = max(peak[best], active[best])
heapq.heappush(ends, (arrive + duration, best))
picks.append(best)
return picks, peak
print(least_connections(["a", "b"], [(0, 10), (1, 2), (2, 5), (3, 1), (4, 1)])) # -> (['a', 'b', 'a', 'b', 'b'], {'a': 2, 'b': 1})
print(least_connections(["a", "b", "c"], [(0, 1), (1, 1), (2, 1)])) # -> (['a', 'a', 'a'], {'a': 1, 'b': 0, 'c': 0})
print(least_connections(["x"], [(0, 5), (1, 5), (2, 5)])) # -> (['x', 'x', 'x'], {'x': 3})Stuck on the idea rather than the code? Load Balancing covers it.