EWMA Least-Response-Time

Connection counts measure how much work a backend holds, not how well it's doing. Two backends with 3 in-flight requests each look identical to least-connections — even if one answers in 10 ms and the other has been grinding through a GC storm at 900 ms. Least-response-time balancing routes on the signal users actually feel: observed latency.

Raw latency is far too noisy to use directly — one slow request would exile a healthy backend. So we smooth it with an exponentially weighted moving average:

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

alpha is the weight of the newest sample. Small alpha (0.1) = heavy smoothing: stable, but slow to notice a backend going bad. Large alpha (0.5) = reactive but jittery. This exercise uses alpha = 0.3.

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

Watch it move. RECORD a 100 three times from a starting ewma of 0:

0.3*100 + 0.7*0    = 30.0
0.3*100 + 0.7*30   = 51.0
0.3*100 + 0.7*51   = 65.7      # converging toward 100

And decay: a backend that recorded 1000 once, then 10 twice, sits at 152.1 — the old spike fades but hasn't vanished.

In production this idea ships as P2C + EWMA: pick two random backends, take the one with the lower EWMA latency. Linkerd's default load balancer works this way, following Twitter's Finagle (whose "peak EWMA" variant also inflates the estimate while requests are in flight, punishing slow backends even faster). O(1) selection, latency-aware, herd-proof — close to the state of the art for service meshes.

The cold-start trap

We initialize every backend's EWMA to 0.0, which reads as "infinitely fast." Any backend with no samples will win every pick until it gets scored. In this exercise that's deliberate — it makes tests deterministic (PICK on a fresh pool returns the lexicographically first name, and after RECORD a 100 the next PICK jumps to b, still unsampled at 0). Production systems must not do this naively: a brand-new backend would soak traffic precisely while its caches are coldest. Real balancers initialize the estimate high (a penalty) or ramp the newcomer with slow start (a later lesson).

Your exercise

Implement record() and pick() in the starter's EwmaPicker. RECORD <backend> <ms> applies the formula with ALPHA = 0.3 (print OK comes from the harness). PICK prints the backend with the lowest EWMA, ties broken by lexicographically smaller name. STATUS prints <name>:<rounded> per backend sorted by name, where the value is Python's round() of the float.

Grader traps:

• Reversed alpha. 0.7 * sample + 0.3 * old gives a:70 after RECORD a 100; the test demands a:30. First visible test, instant fail.
• Rounding, precisely. Three RECORD a 100 must yield a:66 (65.7 rounds up). Don't truncate; the starter's status_lines already uses round() — leave it.
• The pick after one sample. POOL a b c, PICK → a (all tied at 0); RECORD a 100, PICK → b (0 beats 30, and b < c). If your tie-break isn't lexicographic you'll print c and fail the hidden tests.