Tail latency: how hedged requests cut p99 at scale

Tail latency is the response time of your slowest requests, usually measured as p99 or p99.9. It matters at scale because a single user action often fans out to many backend calls, and the action is only as fast as the slowest of them. Hedged requests cut tail latency by sending a second copy of a slow request to another replica after a short delay and using whichever answer arrives first.

Averages hide this problem. A service can report a median of 10 ms and still make a noticeable share of page loads feel slow, because those page loads each touch dozens of servers.

What is tail latency?

A percentile is the value below which a given share of measurements fall. p50 is the median; p99 is the latency that 99% of requests beat. The "tail" is everything past p99: the rare requests that take ten or twenty times longer than usual.

Slow outliers come from ordinary causes:

• a garbage collection pause in the process handling the request,
• a cache miss that falls through to disk or another service,
• a noisy neighbor on the same host using the CPU or network,
• a background job such as compaction, a backup or log rotation,
• a request that lands in a queue behind a burst of other work.

None of these are bugs you can fix once. They are the normal background noise of shared machines, and they show up as a long tail no matter how well the code is written.

Why does fan-out make the tail worse?

Fan-out is when one incoming request triggers many downstream requests, like a search query that hits 100 index shards or a feed that loads data from 40 services. The response cannot be sent until every downstream call returns.

If each call has a 1% chance of being slow, the chance that at least one of N calls is slow is 1 - 0.99^N:

At 100 calls, the p99 of a single server becomes the experience of most users. A server's tail turns into the system's median. That is why large systems care about p99.9 on individual components even when p99 looks fine.

How do hedged requests work?

The idea is simple. Send the request to one replica. If it hasn't answered within a short delay, send the same request to a second replica. Take the first response and cancel the other.

The delay is what makes this cheap. If you sent two copies of every request, you would double your load. Instead, set the hedge delay near the p95 latency of that call. Then only about 5% of requests ever trigger a second copy, so extra load stays around 5%, while the slow ones get a fresh chance on a different machine that is probably not having a bad moment at the same time.

A small simulation shows the effect. Model a call where 98% of requests take 5 to 15 ms and 2% take 150 to 250 ms, then hedge at 20 ms:

import random
random.seed(1)

def latency():
    return random.uniform(5, 15) if random.random() < 0.98 else random.uniform(150, 250)

def pct(xs, p):
    xs = sorted(xs)
    return xs[int(len(xs) * p) - 1]

N, HEDGE = 100_000, 20
plain = [latency() for _ in range(N)]
hedged, extra = [], 0
for _ in range(N):
    a = latency()
    if a > HEDGE:
        extra += 1
        a = min(a, HEDGE + latency())
    hedged.append(a)

print("plain  p99:", round(pct(plain, .99)))
print("hedged p99:", round(pct(hedged, .99)), "extra load:", f"{100 * extra / N:.1f}%")

Running it prints a plain p99 of about 202 ms and a hedged p99 of about 30 ms, for roughly 2% extra requests. The median doesn't move. The real gain will depend on your latency distribution, but the shape of the result is typical: hedging attacks the tail and leaves the common case alone.

Here is a minimal hedging helper in JavaScript. It starts one attempt, schedules a backup, returns the first success, and aborts whatever is still running:

async function hedged(fn, delayMs) {
  const controllers = [];
  const attempt = () => {
    const c = new AbortController();
    controllers.push(c);
    return fn(c.signal);
  };
  let timer;
  const backup = new Promise((resolve, reject) => {
    timer = setTimeout(() => attempt().then(resolve, reject), delayMs);
  });
  try {
    return await Promise.any([attempt(), backup]);
  } finally {
    clearTimeout(timer);
    controllers.forEach((c) => c.abort());
  }
}

// usage: each attempt can go to a different replica
const user = await hedged(
  (signal) => fetch(nextReplica() + "/users/42", { signal }).then((r) => r.json()),
  25
);

Promise.any resolves with the first attempt that succeeds, so a fast failure on one replica doesn't hide a success on the other. If the first call finishes before the delay, the timer is cleared and no backup is ever sent.

When should you use hedged requests?

Hedging fits when three things are true:

• The operation is safe to run twice. Reads are the natural case. For writes, you need the server to recognize duplicates, which is exactly what idempotency keys are for. Without that, two copies of a payment request are two payments.
• Replicas are interchangeable. The second copy has to go somewhere else. Hedging to the same overloaded server just adds to its queue.
• Slowness is mostly random, not systemic. Hedging helps when one machine is having a bad moment. If the whole cluster is slow because it's overloaded, every hedge adds load to a system that is already struggling.

That last point is the main risk. Protect against it with a budget: cap hedges at a small share of total traffic, such as 5%, and stop hedging when the cap is reached. This keeps hedging from amplifying an outage, the same concern that drives backoff with jitter for retries.

How is hedging different from retries and tied requests?

These techniques are related but solve different problems.

A retry waits for a failure, often with a timeout far longer than p99, so it doesn't help with slowness. A hedge gives up waiting on one server without giving up on the request. A tied request goes further: it enqueues the request on two servers at once, each copy knowing about the other, and whichever server starts working on it first tells the other to drop its copy. That removes most duplicate work, but it needs support in the server, not just the client.

Some databases and RPC frameworks support hedging directly. gRPC, for example, defines a hedging policy in its service config with a maximum number of attempts, a hedging delay, and a list of status codes that count as non-fatal. Check whether your client library offers it before writing your own.

Key takeaways

• Tail latency, not the average, decides how fast a fan-out request feels.
• With 100 downstream calls, a 1% slow rate per call slows about 63% of requests.
• Hedged requests send a backup after roughly p95 delay and take the first answer.
• Only hedge idempotent operations, and send the backup to a different replica.
• Cap hedges with a budget so they can't amplify overload.

FAQ

How do I choose the hedge delay?

Start near the p95 latency of that specific call and measure. A shorter delay cuts more tail but sends more duplicate requests; a longer one is cheaper but rescues fewer slow calls.

Do hedged requests double server load?

No, if the delay is set well. Only requests slower than the delay trigger a backup, so with a p95 delay the extra load is around 5%, and cancelling the losing copy recovers some of that.

Can I hedge write requests?

Only when the server can safely deduplicate them, usually through an idempotency key. Otherwise both copies may apply, and you get the same write twice.