Several independent proxies balance to the same backend pool, each using least-connection. Why can one backend still be overwhelmed, and what do power-of-two-choices and latency-aware (EWMA) balancing do about it?

## The herd effect Least-connection is only as good as its view. A single proxy in front of a pool has a complete view of its own traffic, and if it is the only proxy that is the whole truth. Put four proxies in front of the same pool and each one knows a quarter of the picture. Every proxy independently applies the same deterministic rule — send to the backend with the fewest outstanding requests — to information that is both partial and slightly stale. The pathological case is a backend that suddenly looks empty to everyone: one that has just been added, just finished a restart, just been un-ejected after failing health checks, or just drained a queue. Every proxy sees zero in flight, every proxy picks it, and it receives an N-fold burst while its cache is cold and its runtime unwarmed. It slows down, its in-flight count rises above everyone else's, all proxies abandon it at once, it empties, and the cycle repeats. That oscillation is the signature: load sloshing between backends rather than settling. The general lesson is worth stating explicitly, because interviewers are usually probing for it: **any greedy rule applied independently by many agents to shared, stale state converges on the same target.** It shows up as retry storms, as cache stampedes, and here as balancing herds. ## Power-of-two-choices The fix is to add randomness without giving up load-awareness. Sample two backends uniformly at random and send the request to whichever of the two has the lower load: ```python import random def pick(backends, inflight): a, b = random.sample(backends, 2) return a if inflight[a] <= inflight[b] else b ``` This is the classic "power of two choices" result: comparing just two random options gives a dramatically better worst-case load than picking one at random, and gets close to the behaviour of always choosing the true minimum — while costing only two lookups and, crucially, being immune to the herd. Two proxies choosing independent random pairs rarely collide, and a momentarily empty backend is only chosen when it happens to be sampled *and* wins its comparison, so it receives a share of the burst rather than all of it. It also degrades gracefully: with a stale view, sampling two means you avoid the badly loaded backends even if you do not find the very best one. ## EWMA: changing what "load" means In-flight count answers "how many requests have I sent that have not come back". That is a decent proxy for busyness and a poor proxy for health. Two cases break it. A backend that is slow but receiving little traffic looks fine on count. And a backend that fails instantly — returning errors, or refusing work — has the *lowest* count of all, so a count-based rule feeds it preferentially. Latency-aware balancing scores each backend by an exponentially weighted moving average of its observed response time, sometimes multiplied by the number of outstanding requests to give a cost estimate. The average is exponentially weighted so recent observations dominate and old ones decay, which is what lets it react to a garbage-collection pause or a noisy neighbour within seconds. The decay window is the tuning knob and the trap: too short and the score chases noise, oscillating as much as the greedy rule did; too long and it keeps sending traffic to a backend that went bad a minute ago. EWMA does not solve the fast-failure case by itself — a backend returning immediate errors has *excellent* latency. Pairing latency scoring with health checking and outlier ejection, which decide pool membership on success rate rather than speed, is what closes that gap; the balancing algorithm chooses among backends that another mechanism has already judged fit to receive traffic. ## Where you actually see this Proxies that expect to run in fleets tend to implement power-of-two-choices rather than strict least-connection precisely because of the herd problem: Envoy's least-request policy selects among randomly sampled hosts rather than scanning for the global minimum, and Linkerd's proxy combines the same sampling with an EWMA latency score. Plain least-connection is still the right default for a single proxy in front of a small pool, where the local view is the global view and the extra machinery buys nothing. ## What to say about choosing The decision is about how many independent deciders there are and how variable your backends are. One proxy, uniform backends, short requests: round-robin or least-connection, and do not over-engineer. Many proxies or many clients balancing independently, backends that vary in speed, request costs that vary widely: sample-two with a latency-derived score, and make sure something else is ejecting the backends that are fast because they are broken.