Routing by the most recent latency sample can overreact to one unusually fast or slow request. An exponentially weighted moving average, or EWMA, smooths observations while still giving recent measurements more influence.
Design an EwmaLatencyBalancer class:
EwmaLatencyBalancer(int backendCount, double alpha) creates backends with no latency measurements.double recordLatency(int backend, double observedMs) records one completed request and returns that backend's updated EWMA.int pick() returns the backend preferred by the current measurements.
For the first observation of a backend:
For every later observation:
Selection rules:
- If any backend is unmeasured, return the smallest unmeasured index.
- Otherwise return the backend with the smallest EWMA.
- Break equal-EWMA ties by smaller index.
Keep full floating-point precision in stored estimates. Floating results are accepted within 10^-5.
Example 1:
Input:
Output:
Explanation: Every backend receives an initial measurement. Backend 1 later ties backend 2 at 80 ms and wins by index, then rises to 140 ms after a 200 ms observation.
Example 2:
Input:
Output:
Explanation: The smaller alpha dampens changes. Backend 0 moves from 100 to 90 rather than immediately becoming 60.
Constraints
1 <= backendCount <= 10^50 <= alpha <= 10 <= backend < backendCount0 <= observedMs <= 10^9- At most
10^5 calls are made to each method. - Floating-point answers are accepted within
10^-5.
Balance by Smoothed Latencymedium