p99 and load testing.

Send the same request to the same server a thousand times and you get a thousand different answer times. Most land close together. A handful take ten or a hundred times longer, for reasons that have nothing to do with your code. Those few slow ones are what people mean by “the tail”, and they decide how fast a system feels.

That matters the moment you make a claim about speed. When you say your inference server on the Spark holds up against Fireworks, the claim lives or dies on the slowest 1 request in 100, and on whether your test sent traffic the way real users do. An agent step that calls five tools at once waits for the slowest of the five. And “what happens to response times if we run fewer machines?” is a question interviewers love, because most people guess wrong.

You’ve already built the pieces this needs: a load generator (a program that fires requests at a server and times them) and the rule that ties “how many requests are in flight” to “how long each takes” in Waiting vs working, and a benchmark harness in Baseline: my Spark vs Fireworks. Here you learn to point them at a server without fooling yourself. After this come Rate limits and backpressure (what to do when more traffic arrives than you can serve), Load balancers and state, and Batching, which trades a little waiting for a lot more work per GPU pass.

Today

• Read latency numbers like p50 and p99 (the time that 50, or 99, out of every 100 requests beat), say why the average misleads, and why you can’t average two p99s together.
• Explain why a few requests are always far slower than the rest, and why a page that has to wait for many servers turns each server’s rare bad moment into most users’ normal experience.
• Predict, with one short formula, how waiting time grows as a server gets busier, and find the point on a real server where it suddenly shoots up.
• Tell a load test that waits for each answer before sending the next from one that sends on a fixed schedule the way real users do; catch the first kind hiding slow requests from you; and record latencies in a compact tally that keeps the slow ones.
• Build “if the first copy is slow, send a second copy elsewhere” and measure how much it helps the slowest requests and how much extra traffic it costs.

You’ll want Waiting vs working first (your async loadgen.py, and Little’s Law, the rule linking requests in flight, request rate and time per request) and Baseline: my Spark vs Fireworks (your benchmark harness, and why 20 samples can’t tell you about the slowest 1 in 100). Budget two evenings.

The Problem

You run your load generator from lesson 4 against a service before you ship it. Sixteen workers, a few thousand requests. The summary says p50 83 ms, p99 136 ms. Clean. You ship it.

A week later someone shows you the dashboard from the real thing. At about the same request rate, p99 is over a second, and every few minutes there’s a cliff where it touches ten. Nothing changed in the code. The server is the same. So which number was the lie?

The load test was. Not because of a bug in your arithmetic, but because of how it sent requests. Your sixteen workers each waited politely for an answer before sending the next request. Real users don’t. When the server slowed down, your load test slowed down with it and stopped sending exactly the requests that would have been slow. The test measured a gentler world than the one you shipped into.

That’s one of three ideas in this lesson. The other two explain why it matters: latency is a lopsided pile in which the rare bad requests decide how a big system feels, and as a server gets busier those bad requests don’t grow politely, they explode, at a point you can find on a chart.

The Idea

A pile, not a number

Time a thousand requests to the same endpoint. You don’t get one number; you get a thousand different ones. Sort them and you get a shape like this.

You already got the key fact right in the diagnostic: p99 tells you about the bad experiences, the mean doesn’t. Let’s make that precise.

A percentilepercentileThe value below which that fraction of measurements fall. p99 = 120 ms means 99% of requests took 120 ms or less, and 1% took longer. answers “how slow is the request that only N% of requests are worse than?” Sort the samples; p50 (the medianmedianThe middle value once sorted. Half the requests were faster, half slower. Same thing as p50.) is the one in the middle, p99 is the one 99% of the way along, p99.9 is 999 out of 1,000 of the way along. At 100 requests a second, your p99 happens every second. A user whose 10 page views make 300 requests meets it about three times.

Why not the mean? Because it describes nobody. Take 99 requests at 10 ms and one at 10 seconds. The mean is about 110 ms: eleven times worse than what 99% of requests saw, ninety times better than what the unlucky one saw. In a long-tailed pile the mean is a tug-of-war between the hump and the tail, and it won’t tell you who’s winning.

Two rules follow, and people break both all the time.

You can’t average percentiles. If server A’s p99 is 50 ms and server B’s is 500 ms, the p99 of both together is not 275 ms; it depends on how many requests each served and the whole shape. Same for time: the average of sixty per-second p99s is not the p99 of the minute, and it can be wrong in either direction (you’ll see both in Break It). To combine, you need the underlying counts. Hold that thought until the HDR histogram.

Report p99 next to n. With 20 samples, “p99” is just your slowest request. You’ll put numbers on this later.

Why the pile is lopsided

In Figure 001 the left edge is a wall: a request can’t be faster than its work. The right edge is open, because there are dozens of ways to be slower, and they only ever add time.

• Waiting in line. If another request is being served when yours arrives, you wait. This one is so important it gets its own section below.
• Pauses. A garbage collectorgarbage collectorThe part of a language runtime (Python, Java, Go) that finds and frees memory nobody uses. Some collectors briefly stop all the program’s threads while they work, and every request in flight waits. stopping the world for 50 ms.
• The machine doing something else. A backup, a cron job, another container stealing CPU (the “noisy neighbour”).
• Cold caches. After a deploy or an eviction, a request goes to disk instead of RAM: up to 1,000x, from How slow is slow?.
• The network. A lost packet makes TCP wait before resending, and on Linux that wait has a floor of about 200 ms, more than most whole requests take.
• Locks. Two requests want the same row or mutex. One waits.

Each is rare and adds a lot. Stack rare-but-large delays on a fixed floor and you get Figure 001. That’s not a bug in your server; it’s what latency looks like on every computer ever measured.

Fan-out: when the tail becomes the body

Here’s where rare stops being rare. Most real requests aren’t one call. A search goes to many index shardsshardsSlices of a big dataset (an index, a table, a vector store), each held by a different server. A query that needs all the data asks every shard.. A RAG pipeline queries several vector-store shards and a reranker. An agent step calls three tools in parallel. In each case the answer can’t come back until every piece has. That’s fan-outfan-outOne incoming request triggering many outgoing requests (to shards, replicas, tools), whose answers must all come back before it can finish., and it means the user doesn’t see a backend’s typical latency. They see the worst of N draws.

Now play with it. Push the backends up, and switch between “slow” meaning past p90, p99 or p99.9.

That second readout is the one to sit with. If a request needs N backends and you want to know what the median user sees, ask: what latency do all N backends beat half the time? If each beats latency x with probability q, all N do with probability q^N. Set q^N = 0.5 and q = 0.5^(1/N). For N = 100 that’s 0.9931. The typical user of a 100-way fan-out sees each backend’s p99.3. The backend’s tail has become the product’s median.

So a backend team that says “our p99 is fine, it’s only 1%” is watching the wrong number. The paper’s measurements make the same point from the other end: in one Google service, with a root server waiting on 100 leaves, the slowest 5% of leaf requests accounted for about half of the root’s 99th-percentile latency. (The formula assumes backends are slow independently. Shared causes, like one overloaded switch, break that, but fan-out still amplifies the tail.)

Queues: why busy servers have huge tails

The biggest single source of tail latency is waiting in line. Picture a coffee shop with one barista. Each drink takes about a minute. If one customer walks in every ten minutes, you almost never wait. If customers come every 1.1 minutes, on average the barista keeps up, but people don’t arrive evenly. Three show up together, the line forms, and before it clears two more arrive. Some customers wait ten minutes for a one-minute drink.

Three names. The arrival ratearrival rateHow many requests show up per second, on average. Written λ (lambda). λ, how often requests show up. The service timeservice timeHow long the server spends actually working on one request, not counting waiting. Its inverse, the service rate μ (mu), is the most requests per second the server could ever finish. S, how long each takes to serve, so the server can finish at most μ = 1/S per second. And the utilizationutilizationThe fraction of time the server is busy: arrival rate times service time, written ρ (rho). ρ = 0.9 means busy 90% of the time. Must stay below 1 or the line grows forever. ρ = λ × S: the fraction of time the server is busy.

Queueing theorists name the simplest useful model M/M/1M/M/1Kendall’s notation: arrivals are Markovian (random, Poisson), service times are Markovian (exponential), and there is 1 server. The “hello world” of queueing theory.: requests arrive at random, each takes a random amount of work (exponentially distributed, mean S), and there’s one server. You don’t need the derivation. You need two results, at cartoon level.

The average time a request spends in the system, waiting plus being served, is

T = S / (1 − ρ)

and in M/M/1 that total time has an exponential distributionexponential distributionThe shape of “waiting for a random event that is equally likely at every moment”. Many short values, a few long ones; its p99 is 4.6 times its mean., so its percentiles are fixed multiples of the average: p50 = 0.69 × T, p99 = 4.6 × T (that’s ln 100).

Put numbers on it for S = 10 ms. I checked these by simulating 400,000 requests in Python; the simulation lands within a few percent of the formula.

That 1 / (1 − ρ) is the whole story. From 50% to 90% busy, the server does 1.8x more work and p99 gets 5x worse. From 90% to 99%, 10% more throughput costs a 10x worse p99.

Now drive it yourself. Slide the arrival rate. Watch the histogram stretch to the right, and watch where your dot sits on the curve below it. Then switch the service times between constant, exponential, and “rare 100 ms”: mostly quick requests with an occasional slow one, the same 10 ms average.

Three things to take from the simulator.

The hockey stick. Latency against utilization is flat, then bends, then goes nearly vertical. The bend is the kneekneeThe point on a latency-vs-load curve where latency stops growing slowly and starts growing fast. Past it, small increases in load cause large increases in latency. of the curve. Below it, extra load is almost free; above it, you pay in tail latency. Real servers often have a sharper knee than M/M/1, because overloaded servers also do more work per request (cold caches, lock contention, retries).

Variability is the enemy, not just load. The three service-time settings have the same average, so the same utilization, yet very different tails. A rule called Kingman's formulaKingman's formulaAn approximation for the average wait in a single-server queue with any arrival and service distributions: wait ≈ (ρ / (1 − ρ)) × ((Ca² + Cs²) / 2) × S, where Ca and Cs measure how variable arrivals and service times are. says the average wait is roughly (utilization term) × (variability term) × (service time). You can attack either factor: lower utilization (more servers) or lower variability (cap request sizes, split big jobs, move the slow 1% to a separate queue).

Why people run servers at 50-70%. Because the knee is there and traffic is bursty. At a normal 60%, a spike of 30% takes you to 90% and p99 goes up 4x. At a normal 85%, the same spike takes you past 100% and the queue grows until something times out. In the baseline lesson the naive Spark server had to stay near 1% utilization for 99% of requests to see no wait. That was this curve at its most brutal.

Closed loop and open loop

Now back to the lie in The Problem. There are two ways to generate load, and they answer different questions.

A closed-loopclosed-loopA load generator with a fixed number of workers (or “virtual users”). Each sends a request, waits for the answer, then sends the next. The next request depends on the previous one finishing. generator has c workers that each send, wait, send again. Your loadgen.py from lesson 4 is one: the semaphore lets at most c requests be in flight, and a new one starts only when one finishes.

An open-loopopen-loopA load generator that sends requests on a schedule (say 100 per second, at random times), whether or not earlier requests have finished. Like real users, who don’t wait for each other. generator decides when each request goes out before the test starts, then sticks to the schedule no matter how the server is doing.

Little’s Law (L = λW, from lesson 4) says what each one controls. A closed loop fixes L, the number in flight, at c, so throughput is λ = c / W. When the server slows down, W rises and the generator sends fewer requests per second. It backs off exactly when the server struggles, so it can never push the server past its knee. An open loop fixes λ. When the server slows down, L, the pile of unfinished requests, grows. That’s what real traffic does: users on the internet don’t know your server is slow; they keep clicking.

That’s why the test in The Problem looked fine. On my Mac, closed-loop c = 16 drove the server to about 185 requests per second with p99 136 ms. An open loop at 190 per second, a hair more, got p99 of ten seconds: 190 was just past capacity, so the queue grew for the whole test. One test asked “how fast is it when we’re careful?” The other asked “what happens when traffic doesn’t care?”

Coordinated omission

Figure 004 is the bug Gil Tene named. Say your server freezes for 500 ms every 5 seconds (a GC pause, a stalled disk), so it’s frozen about 9% of the time. A closed-loop worker caught mid-request records one 500 ms sample, then nothing for the rest of the freeze, because it’s waiting. Generator and server have “coordinated”: the generator omitted exactly the requests that would have seen the freeze. That’s coordinated omissioncoordinated omissionA measurement error where the load generator stops sending while the server is slow, so the slow periods are under-sampled and the reported tail looks far better than what real users would see..

There are two fixes, and they’re the same idea.

1. Generate load open-loop and measure from the intended send time. Decide the schedule up front, t_intended = start + i / rate (or random gaps with that average), and compute latency as t_done − t_intended, not t_done − t_actually_sent. If your generator was late sending a request, maybe because it was itself stuck, that lateness counts. A real user would have experienced it.
2. Or correct afterwards. If a closed-loop worker meant to send every 5 ms and one request took 500 ms, it knows it skipped about 99 sends. You can back-fill them: one sample at 495 ms, one at 490 ms, and so on down to 5 ms, the latencies those skipped requests would have seen. That’s what HdrHistogram’s record_corrected_value(value, expected_interval) does. It’s an estimate, and it needs you to say what the intended rate was, but it’s far better than nothing.

It also hides where you wouldn’t look. The wrk HTTP benchmark has it (Tene wrote wrk2, which sends at a fixed rate and measures from the intended time). So does any tool that starts the stopwatch after waiting for a free connection, worker, or semaphore. Your own loadgen.py starts it inside async with sem:. That’s honest for a closed-loop tool, and coordinated omission the moment you treat it as a schedule. You’ll reproduce exactly that in Break It.

Counting the tail: samples and HDR histograms

Two practical problems remain: how many samples you need, and how to store them.

Samples. You can’t measure p99 with 100 requests. You can barely measure it with 1,000. Here’s a simulation: sample from a distribution whose true p99 is 46 ms, estimate p99, repeat 2,000 times, and see how much the estimate wanders.

At 100 samples, p99 is the slowest or second-slowest request, and two runs can differ by almost 2x. You want at least ten samples past the percentile, so 1,000+ for p99 and 10,000+ for p99.9. A 10-minute test at 100 requests per second gives 60,000, plenty. The corollary: a p99.9 from a 30-second test is a max with extra steps.

Storage. A Python list of every latency is fine for a test. It’s not fine for 10,000 requests a second, all day, on 50 machines, when you want p99 per minute per endpoint. You need a summary, and the naive ones fail: a mean loses the tail, and fixed linear buckets (0-10 ms, 10-20 ms…) either need millions of buckets or lose all detail at the low end.

An HDR histogramHDR histogramHigh Dynamic Range histogram (Gil Tene). Buckets that grow exponentially in width, each split into many equal sub-buckets, so every recorded value is kept to a fixed relative precision (say 3 significant digits) across a huge range, in a fixed amount of memory. solves this by making bucket width grow with the value. The buckets are powers of two (1-2 µs, 2-4 µs, 4-8 µs, …), and each one is split into the same number of equal sub-buckets, enough to keep, say, 3 significant digits. So a 1.234 ms latency is stored as “somewhere in 1.234 ms ± 0.05%”, and so is 12.34 s. A histogram covering 1 microsecond to an hour at 3 significant digits takes about 185 KB with 64-bit counters (I checked with the Python package), however many values you record, and recording a value is a couple of arithmetic operations and one counter increment.

The killer feature: histograms add. Two with the same layout combine by adding counts bucket by bucket. Record one per machine per minute, add them up, and ask the sum for its p99: the true p99 of all those requests, to 3 significant digits. That’s the fix for “you can’t average percentiles”: keep histograms, compute percentiles at the end. Prometheus histograms and OpenTelemetry’s exponential histograms use versions of the same idea.

Cutting the tail

You can’t make every machine fast every time. Dean and Barroso’s argument: treat slowness like failure. Expect it and route around it.

Timeouts. A timeouttimeoutThe longest a client will wait for an answer before giving up. It caps how long one request can hurt you, and turns “slow” into “failed”, which you then have to handle. caps the damage of one stuck call. Set it from measured data (a bit above your p99.9), not a round number, and decide what happens after it fires.

Retries. After a timeout, try again, ideally on a different replicareplicaOne of several identical copies of a service, any of which can answer a request.. But a retry is extra load, and you’ve seen what extra load does near the knee. If a server is slow because it’s overloaded, retries double its load and make it slower: a retry stormretry stormA feedback loop where slowness causes timeouts, timeouts cause retries, and retries add load that causes more slowness. Can keep a service down after the original problem is gone.. Real systems cap retries with a budget (at most, say, 10% extra traffic) and back off randomly between attempts; see the rate limits lesson.

Hedged requests. The clever one. Send to one replica. If it hasn’t answered within some delay, send the same request to a second, use whichever answers first, and cancel the other.

The trick is the delay. Two copies of every request doubles your load to fix a 1% problem. Waiting until the request has been out longer than your p95 means only 5% ever get a second copy, about 5% extra load, aimed exactly at the requests headed for the tail. The paper reports a Google BigTable benchmark where hedging after 10 ms cut the 99.9th-percentile latency for a 1,000-key read from 1,800 ms to 74 ms while sending only 2% more requests.

Hedging works because tail slowness is often about the machine, not the request: replica A is in a GC pause, replica B isn’t. That gives the two cases where it fails:

• When the slowness is the request. If the query is slow because it’s a huge query, sending it twice gets you two slow answers and double the work.
• When the slowness is load. If every replica is slow because they’re all near the knee, hedging adds load to a system that’s slow because of load. You’ll measure this in Break It, and it isn’t subtle.

And only hedge requests that are safe to do twice. A read, a search, a rerank, an LLM completion: fine. “Charge this card”: not without an idempotency key, a unique ID the server uses to recognise and ignore a duplicate.

Refinements. Tied requestsTied requestsDean and Barroso’s refinement of hedging: send the request to two servers at once, each told about the other. Whichever starts working on it first tells the other to cancel, so the duplicate rarely costs real work. send to two servers at once but let them cancel each other as soon as one starts, so you get the latency benefit with almost none of the duplicated work. Backup tasksBackup tasksMapReduce’s version of hedging (Dean and Ghemawat, 2004): near the end of a job, re-launch the still-running “straggler” tasks on other machines and take whichever copy finishes first. are the batch-job version: MapReduce re-runs the last few straggling tasks of a job on other machines, and the MapReduce paper reported that one large sort took 44% longer with the feature turned off. In your world: an LLM request stuck behind a giant prompt on one replica, a vector-index shard on a sick machine, a flaky tool API. Same shape.

Build It

Everything goes in one folder, say ~/workbench/tail/. The server and the generators run on the same machine at first, which is fine as long as you remember the generator itself costs CPU. On my Mac, one httpx AsyncClient adds about 3 ms per request and tops out somewhere around a thousand requests a second, so keep the server’s capacity well below that.

mkdir -p ~/workbench/tail && cd ~/workbench/tail
python3 -m venv .venv && source .venv/bin/activate
pip install httpx numpy matplotlib hdrhistogram

# tail_server.py: a tiny HTTP server with a knob for every kind of slowness.
import argparse, asyncio, random, time

p = argparse.ArgumentParser()
p.add_argument("--port", type=int, default=8090)
p.add_argument("--workers", type=int, default=1, help="requests served at once; 0 = unlimited")
p.add_argument("--service-ms", type=float, default=5.0, help="mean service time")
p.add_argument("--dist", choices=["exp", "const"], default="exp")
p.add_argument("--slow-prob", type=float, default=0.0, help="chance a request is a straggler")
p.add_argument("--slow-ms", type=float, default=100.0)
p.add_argument("--stall-every", type=float, default=0.0, help="seconds between whole-server freezes")
p.add_argument("--stall-ms", type=float, default=0.0)
args = p.parse_args()

sem = asyncio.Semaphore(args.workers) if args.workers > 0 else None
BODY = b"ok\n"
RESP = (b"HTTP/1.1 200 OK\r\nContent-Length: %d\r\nContent-Type: text/plain\r\n\r\n" % len(BODY)) + BODY


def service_time() -> float:
    if args.slow_prob and random.random() < args.slow_prob:
        return args.slow_ms / 1000
    m = args.service_ms / 1000
    return random.expovariate(1 / m) if args.dist == "exp" else m


async def work():
    if sem is None:
        await asyncio.sleep(service_time())
    else:
        async with sem:
            await asyncio.sleep(service_time())


async def handle(reader: asyncio.StreamReader, writer: asyncio.StreamWriter):
    try:
        while True:
            await reader.readuntil(b"\r\n\r\n")  # we only serve GETs with no body
            await work()
            writer.write(RESP)
            await writer.drain()
    except (asyncio.IncompleteReadError, ConnectionError):
        pass
    finally:
        writer.close()


async def staller():
    # Freeze the whole event loop, like a stop-the-world GC pause or a noisy neighbour.
    while True:
        await asyncio.sleep(args.stall_every)
        time.sleep(args.stall_ms / 1000)


async def main():
    server = await asyncio.start_server(handle, "127.0.0.1", args.port, backlog=4096)
    if args.stall_every > 0:
        asyncio.create_task(staller())
    print(f"listening on :{args.port} workers={args.workers or 'inf'} "
          f"service={args.service_ms}ms {args.dist}")
    async with server:
        await server.serve_forever()


asyncio.run(main())

async def closed_loop(url: str, conc: int, duration: float) -> tuple[list[float], float]:
    """Run `conc` workers for `duration` seconds. Return (latencies in seconds, wall time)."""

def summary(lat_s: list[float], wall: float, label: str) -> None:
    """Print n, achieved req/s, mean, p50, p99, p99.9 and max, in ms. Use numpy.percentile."""

async def open_loop(url: str, rate: float, duration: float) -> tuple[list[float], list[float], float]:
    """Send about rate * duration requests at random (Poisson) times.
    Return (latency from intended send time, latency from actual send time, wall time)."""
    # 1. Build the whole schedule BEFORE starting: gaps = random.expovariate(rate), cumulative sum.
    # 2. start = time.perf_counter(). For each scheduled offset s:
    #       sleep until start + s (skip the sleep if you're already late),
    #       then asyncio.create_task(one(start + s)).
    # 3. one(t_intended): t_sent = now; await client.get(url); t_done = now;
    #       record t_done - t_intended AND t_done - t_sent.
    # 4. gather all the tasks, return.

from hdrh.histogram import HdrHistogram

h = HdrHistogram(1, 60_000_000, 3)        # values in microseconds: 1 µs to 60 s, 3 significant digits
h.record_corrected_value(latency_us, expected_interval_us)
h.get_value_at_percentile(99.0)           # back in microseconds

python tail_server.py --port 8101 --workers 0 --dist const --service-ms 5 --slow-prob 0.03 --slow-ms 100 &
python tail_server.py --port 8102 --workers 0 --dist const --service-ms 5 --slow-prob 0.03 --slow-ms 100 &

async def plain(client, delay):
    """Pick one replica at random and send."""

async def hedged(client, delay):
    """Send to one replica. If no answer within `delay` seconds, send to the other.
    Return whichever finishes first; cancel the loser."""
    # asyncio.wait({t1}, timeout=delay) tells you whether t1 finished in time.
    # Then asyncio.wait({t1, t2}, return_when=asyncio.FIRST_COMPLETED).

async def both(client, delay):
    """Send to both at once, take the first. (The 'always hedge' baseline.)"""

Measure

Fill in your numbers. Use runs of at least 20 seconds, and put n next to every percentile.

For reference, my runs on an M-series MacBook, Python 3.14, httpx 0.28, client and server on the same machine. Yours will differ in the details; the shape should not.

Closed vs open, default server (1 worker, 5 ms exponential):

The closed loop never breaks. At c = 16 the server is as busy as it gets, yet p99 is 136 ms: with sixteen in flight, at most fifteen are ahead of you. More workers just means linearly more latency. It can’t show you the cliff.

The open loop finds the cliff. p99 roughly doubles from 50/s to 130/s, triples again by 165/s, and at 185-190/s the backlog grows for the whole test, so p99 is set by how long the test ran. A p99 that grows with test duration is the signature of being past capacity. My knee was around 130-150 per second, 70-80% of capacity, about where M/M/1 says it should be.

Runs near the knee are noisy. Two runs at 150/s gave p99 118 and 156 ms, and 175/s once beat 165/s. Near the knee one unlucky burst builds a queue that drains slowly, so a run may catch several or none. The variance explodes along with the mean; run those points longer.

Coordinated omission (server freezes 500 ms every 5 s):

The closed loop sees the freezes only in its max. The corrected histogram lands within 10% of the open-loop answer, but its count was about double the requests sent, because correction also back-fills for ordinary slow requests over the expected interval. It’s an estimate.

Hedging (2 replicas, 5 ms constant, 3% of requests 100 ms; open loop 100/s, 30 s, n = 3,000):

(About 3 ms of every number is the client: an httpx request on localhost costs that much on its own.)

p99 dropped from 105 ms to 21 ms for 4% more requests: roughly the hedge delay plus one normal request, as Figure 005 predicts. Always sending both is better still, at double the cost. Ignore the p99.9 column: with 3,000 samples it’s the third-slowest request, decided by whether both copies of some request were stragglers (about 1 in 1,000).

Break It

1. Hedge a server that’s slow because it’s busy. Restart the two replicas as plain queues (--workers 1 --service-ms 5, no stragglers) and drive them at 140 requests per second in total, about 40% busy each. Now the tail comes from queueing, and queueing is caused by load. On my run, plain gave p99 39 ms. hedged with a 12 ms delay, below the p95 of 27 ms, sent 34% extra requests and made p99 worse: 58 ms. Sending to both every time made it worse again: 64 ms, with each replica now about 75% busy. Each extra request pushed both replicas further up the hockey stick. Hedging is a fix for random bad luck on one machine, not for not having enough machines. And always set the delay from the measured p95, not from a guess.

2. Put coordinated omission back into an open loop. In open.py, wrap the request in an asyncio.Semaphore(4) and stamp t_sent after acquiring it, so at most four requests are in flight, which is what lots of real load tools quietly do with a fixed connection pool. Run it at 100 per second against the stalling server. On mine, latency measured from the semaphore said p99 52 ms; measured from the schedule, 515 ms. The generator is sending “on a schedule”, but it’s measuring from when it got around to it. This is also what your lesson-4 loadgen.py does with its semaphore. Lesson: where you start the stopwatch decides which question you’re answering.

3. Average your p99s. Have open.py also compute p99 per one-second window, and compare the average of those to the p99 of the whole run. Against the stalling server they disagree badly. It can go either way: in a quick simulation of 20 windows, a stall window with few requests in it gave an average-of-p99s of 47 ms against a true p99 of 26 ms; a stall window with as many requests as the others gave 46 ms against a true 402 ms. Then record per-window HDR histograms, add them, and ask the sum for its p99. It matches the whole-run number to 3 digits.

4. Make the load generator the bottleneck. Point open.py at a server with --workers 0 --service-ms 1 and ask for 3,000 requests per second. Watch top: the Python process running the generator sits near 100% of a core. Compare the achieved rate to the target, and “from intended” to “from sent” latency: they finally come apart, because the generator falls behind its own schedule. What you’re measuring now is your load generator. Real load tests use several generator processes or a generator written in something faster (wrk2, k6, vegeta), and always check that achieved rate equals target rate.

Explain It Back

Answer out loud, as if in an interview, then check.

Go Deeper

• Jeffrey Dean and Luiz André Barroso, “The Tail at Scale”, Communications of the ACM, February 2013. Eight pages, and the reason everyone in the industry says “p99”. The fan-out arithmetic, hedged and tied requests, micro-partitions, and the “tolerate it like failure” argument, with Google measurements.
• Gil Tene, “How NOT to Measure Latency” (talk; the Strange Loop 2015 recording is the usual one to find). The talk that named coordinated omission, with the best explanation of why percentiles and averages mislead. Watch it after this lesson; it’ll feel like a replay with more war stories.
• HdrHistogram (hdrhistogram.org) and wrk2 (github.com/giltene/wrk2). The data structure and the coordinated-omission-free load generator, both by Tene. The wrk2 README is itself a short, clear lesson in measuring from the intended send time.
• Bianca Schroeder, Adam Wierman and Mor Harchol-Balter, “Open Versus Closed: A Cautionary Tale”, NSDI 2006. A careful study of how the choice of open vs closed load generation changes your conclusions about a system, including which scheduling tricks look good.
• Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Cambridge, 2013). The friendliest real queueing-theory book: M/M/1, Kingman, the variability effects you saw in Figure 003, and why server farms are designed the way they are.
• Jeffrey Dean and Sanjay Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters”, OSDI 2004. Read the “backup tasks” section for the batch-world ancestor of hedging, with numbers.
• Brendan Gregg, Systems Performance (2nd edition, 2020), the chapters on methodology and on benchmarking. How to do load testing without fooling yourself, from someone who has seen every way it goes wrong.
• Marc Brooker’s blog (brooker.co.za/blog), especially his posts on tail latency, retries and backoff, and metastable failures. Short, mathematical, and written by an engineer who runs very large systems at AWS.

Connections

This lesson leans on Waiting vs working (your load generator is the closed loop here, and Little’s Law is how you tell the two kinds apart) and on Baseline: my Spark vs Fireworks, where you first met “20 samples can’t give a p99” and the server that can only stay fast at 1% utilization.

It feeds straight into Rate limits and backpressure, which is what to do when offered load goes past the knee you found here, and Load balancers and state, where the way you pick a replica changes the tail. Batching is the inference version of the same trade-off: wait a little to fill a batch, so the GPU does more per pass, and watch what that does to p99. And when you build observability, you’ll record HDR-style histograms, not averages.