EWMA Least-Response-Time

Connection counts measure how much work a backend holds, not how well it is doing. Two backends with three requests in flight each look identical to least-connections, even if one answers in 10 ms and the other is grinding through a GC storm at 900 ms. Least-response-time balancing routes on the signal users actually feel: observed latency. After this lesson your balancer measures every response and prefers the backend that has recently been quick.

Smoothing with an EWMA

Raw latency is far too noisy to use directly: one slow request would exile a healthy backend. So it is smoothed with an exponentially weighted moving average, one number per backend:

ewma_new = alpha * sample + (1 - alpha) * ewma_old

alpha is the weight of the newest sample. A small alpha (0.1) smooths heavily: stable, but slow to notice a backend going bad. A large alpha (0.5) reacts fast but jitters. This exercise uses alpha = 0.3, written as 3/10 so that integer arithmetic gives the same answer in every language.

Why not a plain mean or a percentile? A mean never forgets: a backend that was slow an hour ago carries it forever, and one that just turned slow is averaged out by ten thousand old fast samples. Percentiles are the gold standard for reporting but need a buffer or a sketch (t-digest). An EWMA is one number per backend, O(1) per update, and recency-weighted: old samples decay geometrically, so degradation shows within a handful of requests.

Watch it move. The first sample starts the average (there is nothing to blend with yet), then each new sample is blended in:

samples (ms):   100,  200,  1000
after 100:      100.000
after 200:      0.3 * 200  + 0.7 * 100.000  = 130.000
after 1000:     0.3 * 1000 + 0.7 * 130.000  = 391.000      one bad request, not exile

Fixed point, not floats

Keep each average in thousandths of a millisecond as an integer: a sample of ms milliseconds is ms * 1000. The update is

ewma_new = (3 * sample + 7 * ewma_old) / 10        integer division, rounding down

and you print ewma / 1000 and ewma mod 1000 (three digits) to show milliseconds. Floats would print differently in different languages; integers cannot.

Choosing: latency times load

The lowest average alone is dangerous: the fastest backend would receive every request until it slowed down. Real implementations (Finagle's peak EWMA, Linkerd's default balancer) multiply by load. The cost of a backend here is

cost = ewma * (in_flight + 1)

A backend that answers in 10 ms but already holds 9 requests costs 10 * 10 = 100, the same as an idle backend averaging 100 ms. PICK takes the lowest cost, ties broken by the lexicographically smaller name, and counts the request as in flight at once. DONE <backend> <ms> finishes a request: it decrements the in-flight count (never below 0) and feeds the measured latency into the average. Linkerd and Finagle pair this with power of two choices: sample two random backends and take the cheaper.

The cold-start trap

A backend with no samples has an EWMA of 0, and 0 * anything is 0, so it looks infinitely fast and wins every pick until it is scored. This exercise keeps that behaviour on purpose, because it makes the output deterministic and shows the problem: on a fresh pool the first backend takes every request until its first DONE. A production balancer must not do this, since a brand-new backend would soak up traffic exactly while its caches are coldest. Real systems start the estimate at a high penalty value or ramp the newcomer with slow start, which is a lesson of its own.

Common mistakes

• Reversed alpha: 0.7 * sample + 0.3 * old reacts too fast and fails the very first blend.
• Blending the first sample with 0. The first sample is the average; blending gives 30% of it and understates a new backend for dozens of requests.
• Rounding instead of truncating the integer division, and dividing before multiplying.
• Forgetting in_flight + 1: a busy fast backend must lose to an idle slower one.
• Tie-breaking by pool order instead of by name.

Your exercise

The starter holds the pool and parses commands. You write the average update (DONE) and the choice (PICK). STATUS prints <name> ewma=<ms>.<3 digits> inflight=<n> per backend, sorted by name.