tail-latency-lab

One slow server in a hundred makes most requests slow

A search or a feed page often waits on 100 backends in parallel and is only as fast as the slowest. If each backend has a 1% chance of a one-second hiccup, 63% of page loads hit one. This page simulates that effect and three fixes from the literature: hedged requests, hedging under real load, and picking the shorter of two queues. Every number is computed in this tab from a seeded run.

1. Fan-out turns a leaf's p99 into the request's median

Each request waits on leaves at once. A leaf is slow with probability p, so a request is slow with probability 1 - (1 - p)^n. The line is that formula, the dot is the simulation.

2. Hedged requests

Send to one replica. If nothing has come back by the delay, send the same request to a second replica and take whichever answers first, cancelling the other. Dean and Barroso set the delay at the p95, so the backup fires on about 5% of requests. Replicas here are idle; section 3 adds load.

3. Hedging when replicas are busy

Now 10 replicas serve a Poisson stream in FIFO order and a one-second hiccup blocks everyone queued behind it. A backup waits in another replica's queue and holds that replica until one copy answers, so hedges cost capacity. Duplicating every request is the best policy at low load and the worst near saturation.

4. The power of two choices

Jobs arrive at 100 servers. Sending each to a random server makes every server an M/M/1 queue, with mean time 1 / (1 - load). Sampling two servers and joining the shorter queue cuts that exponentially; a third sample adds only a constant factor. The theory line is Mitzenmacher's fixed point.

5. In code

Five small modules with no dependencies. Each simulation is checked by node --test against its closed form: the fan-out formula, the two-replica survival product for hedging, and the supermarket-model fixed point for d choices.

  1. Dean, Barroso, The Tail at Scale, CACM 56(2), 2013
  2. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE TPDS 2001
import { slowShare } from "./src/fanout.js";
import { simulateHedge } from "./src/hedge.js";
import { simulateLoaded } from "./src/loaded.js";
import { simulateBalance } from "./src/balance.js";

slowShare(0.01, 100);              // 0.634
simulateHedge({ delayQ: 0.95 });   // p99.9 and extra work
simulateLoaded({ load: 0.6, delay: 0 });
simulateBalance({ lambda: 0.9, policy: "two" });