Load balancing and resilience, simulated

The diagram. Clients on the left (or top on a phone), the load balancer, and the servers. Each server card shows its workers as squares (filled when busy) and its queue as small bars, oldest on the left, coloured by what they are: blue a first attempt, orange a retry, violet a hedge, amber a breaker probe, grey an attempt whose client has already given up (work that will be wasted). Badges show a server that is down, slowed (×0.25), in a GC pause, failing (500s), or whose circuit breaker is OPEN or HALF-OPEN. The line under it gives the queue, completed requests, cache hit ratio (when servers cache keys), concurrency limit (when a limiter is on), the balancer’s latency estimate (EWMA algorithms) and the outstanding requests the balancer counts. A wire’s thickness is the request rate to that server; a ✕ marks one that gets nothing. Tap the clients, the balancer or a server to inspect it and act on it.

Counters for the last two simulated seconds: requests offered, goodput (the share answered successfully), attempts per request, p50 and p99 latency, and totals of timeouts, errors and rejections, retries, hedges, wasted work and failed requests.

Over time: latency p50/p95/p99 of successful requests; offered load, attempts and goodput; timeouts, rejections, retries and failures per second; and requests in each server (or each server’s concurrency limit) — the last 20 simulated seconds, one point per 250 ms. Hover or tap for values.

Do something: the request rate, the algorithm, per-server kill / restart / slow / GC pause / fail, slow everything down, add a server; client retries, a retry budget, hedging at the current p95, a 100 ms timeout; circuit breakers, a bounded queue, LIFO, dropping expired requests and a concurrency limiter (Gradient2 or AIMD).

Event log: breaker transitions, failures and changes.

Fleet and resilience settings rebuild the fleet with any of the parameters below.

Round robin and a slow server (rr-slow) — follow single requests, then 400/s; one server slows to a quarter speed and round robin builds an endless queue on it; least outstanding and power of two choices route around it.

Stale load information makes a herd (herd) — four balancers share load numbers refreshed every 500 ms: least-loaded sends everything to one server at a time; two choices spread it; plain random does best on information that old; fresh, local counts fix least-loaded.

GC pauses: load-aware balancing dodges them (gc-ewma) — a 300 ms pause every 2 s on one server: round robin’s p99, then least outstanding and Finagle’s peak-EWMA with two choices.

Consistent hashing and bounded loads (ch-bounded) — key affinity keeps server caches warm but hot keys overload one server; bounded loads (ε = 0.25) even the load and keep most of the hits; two choices balance but cool the caches; adding a server moves about 1/6 of keys.

Retry storm and metastable failure (retry-storm) — a 1.5 s slowdown at 70% load; timeouts and three retries keep the fleet overloaded after the slowdown ends; a retry budget stops the amplification and dropping expired work clears the dead backlog.

Circuit breaker (breaker) — a server that fails fast attracts least-outstanding traffic; its breaker opens, probes half-open, re-opens, and closes once it recovers.

Hedged requests trim the tail (hedging) — a lognormal service-time tail; hedging at the p95 cuts p99 from about 125 to 75 ms for about 5% more attempts; hedging too early doubles the work.

Adaptive concurrency limits find the knee (adaptive) — 25% overload with no limit, then Gradient2 and AIMD limits that reject the excess at once.

Load shedding keeps goodput (shedding) — 1.4× overload with a 200 ms timeout: an unbounded FIFO answers nobody in time; a bounded queue, LIFO and dropping expired requests compared.

Playground — no script.

Servers: a number of workers each (concurrency), an unbounded or bounded queue (FIFO or LIFO), service times that are exponential, constant or lognormal with a chosen coefficient of variation, a speed factor, periodic stop-the-world pauses (running work stops too), an error rate (fast HTTP 500s), and optionally an LRU cache of keys that makes a cached request cheaper.

Clients: open-loop Poisson arrivals, or a closed loop of users with exponential think time. Each request has a key drawn from a Zipf distribution.

The network: every hop takes the same time (5 ms by default), client → balancer → server and back.

Balancing (each balancer keeps its own outstanding counts and latency averages; with shared load information every balancer instead sees the servers' real loads as of the last refresh): round robin; smooth weighted round robin (nginx’s algorithm; weights default to server speeds); random; least outstanding requests (ties broken at random); least EWMA latency (time-decayed, 1 s); peak-EWMA with two random choices — the latency average jumps to any higher sample and decays otherwise, and the cost is average × (outstanding + 1), as Finagle’s p2cPeakEwma; power of two choices on outstanding requests (Mitzenmacher 2001); consistent hashing with virtual nodes (Karger et al. 1997); and consistent hashing with bounded loads (Mirrokni, Thorup & Zadimoghaddam 2018): capacity ⌈(1 + ε)(in flight + 1) / servers⌉, walking clockwise past full servers.

Timeouts are per attempt, at the balancer, which answers the client 504; the server keeps working on the attempt unless drop expired is on.

Retries happen at the client after an error or timeout, up to the retry count, after exponential backoff base × 2^(i−1) (capped at 10 s) with full jitter — a random wait between 0 and that (Brooker 2015) — or none. A retry budget is a token bucket: every request deposits budget tokens (0.1 = 10%), a retry spends one, the bucket holds at most max(10, 100 × budget); without a token the request fails instead — like Finagle’s RetryBudget and Envoy’s retry budget.

Circuit breakers sit at the balancer, one per server: closed while fewer than the threshold share of the last cbWindow results (at least 10) failed; open (no traffic) for cbOpenMs; then half-open, letting cbProbes requests through — all succeed → closed, one fails → open again. Errors and timeouts count as failures.

Hedging: if a request has no answer after hedge ms, the client sends one more copy to a different server and takes the first answer; the loser is skipped if it is still queued.

Load shedding: with a bounded queue a full server answers 503 at once (FIFO), or drops its oldest queued request to make room (LIFO).

Adaptive concurrency limits, per server, on requests in service plus queued (excess rejected with 503). AIMD after Netflix’s AIMDLimit: +1 while the limit is in use, ×0.9 on a response slower than 5 × the mean service time, at most once per round of admitted requests. Gradient after Gradient2: a short-term response-time average (about 10 samples) against a long-term baseline, gradient = clamp(1.5 × baseline / short, 0.5, 1), new limit = limit × gradient
√limit, smoothed. Gradient2 keeps its baseline as a 600-sample average; here the baseline is learned from requests that did not queue — what that average stands for — because a plain average creeps upward during a long overload in a simulation this small. Limiters learn only from requests they admitted.

Charts and Little’s law: a 250 ms bin collects offered requests, attempts, successes, failures, timeouts, rejections and the latencies of successful requests. The time-average number of requests in the system equals arrival rate × mean time in system (checked in the tests).

A model, not a benchmark: one network hop time, no connection set-up, no TCP, no CPU or memory contention beyond the workers and queues, and servers whose only state is a key cache. Numbers in the narration come from this simulation with its default seed.

The balancer never fails and never becomes a bottleneck; there is one service, not a call graph (retry layers are on the Retry maths tab).

No active health checks: a dead server is only noticed through refused connections and the circuit breaker. Least outstanding therefore keeps sending to a server that fails fast — a real effect, sharper here than with health checks.

The concurrency limiters are simplified (see above), and the retry budget is a token bucket rather than Finagle’s time-windowed one.

Hedges are not budgeted, and the hedged copy is cancelled only while it is still queued.

M. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing (IEEE TPDS 2001), and The Power of Two Random Choices: A Survey (with Richa and Sitaraman), which covers stale information; Y. Azar, A. Broder, A. Karlin and E. Upfal, Balanced Allocations (SIAM J. Computing 1999).

Finagle, load balancing (P2C, peak EWMA, aperture) and retry budgets; Linkerd, Beyond round robin.

D. Karger et al., Consistent hashing and random trees (STOC 1997); V. Mirrokni, M. Thorup and M. Zadimoghaddam, Consistent Hashing with Bounded Loads (SODA 2018).

M. Brooker, Exponential Backoff and Jitter (AWS Architecture Blog, 2015); AWS Builders' Library, Timeouts, retries and backoff with jitter and Using load shedding to avoid overload.

N. Bronson, A. Aghayev, A. Charapko and T. Zhu, Metastable Failures in Distributed Systems (HotOS 2021); L. Huang et al., Metastable Failures in the Wild (OSDI 2022).

M. Nygard, Release It! (Pragmatic Bookshelf, 2nd ed. 2018), stability patterns; M. Fowler, CircuitBreaker; Envoy, circuit breaking and load balancers.

J. Dean and L. A. Barroso, The Tail at Scale (CACM 2013) — hedged and tied requests.

Netflix, concurrency-limits (AIMDLimit, Gradient2Limit) and Performance Under Load.

Google SRE book, Handling Overload and Addressing Cascading Failures; B. Maurer, Fail at Scale (ACM Queue 2015) — adaptive LIFO.

J. D. C. Little, A Proof for the Queuing Formula L = λW (Operations Research, 1961).