Tail Latency: Hedged Requests and Load Shedding Guide

Tail latency is the response time of your slowest requests, and hedged requests plus load shedding are the two standard ways to tame it. A hedged request sends a backup copy to another replica when the first one is slow. Load shedding rejects some work quickly when a server is saturated so everyone else stays fast. Used together, they cut your p99 without buying more hardware. Used badly, they melt your system faster than the original slowness would have.

Why the tail matters more than the average

Say each backend call is slow 1% of the time. That sounds fine. Now build a page that makes 100 of those calls in parallel and waits for all of them. The chance every call is fast is 0.99 to the power of 100, about 37%. So roughly 63% of page loads hit at least one slow call. This is the central example in Jeff Dean and Luiz Barroso’s paper The Tail at Scale, and it’s why a rare event at the component level becomes the common case for users.

Fan-out is everywhere now: a search over many shards, a GraphQL resolver calling ten services, an AI feature that makes several model and retrieval calls before answering. The more calls you wait for, the more your p99 becomes your typical user’s experience.

Averages hide this completely. Track p95, p99 and p99.9 per endpoint, and look at the histogram, not just one number. If you’re setting targets, SLOs and error budgets should be expressed in percentiles for exactly this reason.

Hedged requests: pay a little to skip the slow path

Slowness is usually transient and local: a garbage collection pause, a noisy neighbour, a cold cache, a disk hiccup on one replica. A different replica is probably fine. So:

1. Send the request to one replica.
2. If no answer arrives within a short delay, send the same request to a second replica.
3. Use whichever answers first. Cancel the other.

The delay matters. Hedge immediately and you double your load. Wait for your p95 latency and only about 5% of requests ever send a second copy. The paper reports a striking result for a benchmark reading 1,000 values from a Bigtable cluster: hedging after a 10 ms delay cut the 99.9th percentile for retrieving all values from 1,800 ms to 74 ms, while sending only about 2% more requests.

Here’s a minimal version in TypeScript. It assumes fetch and replicas that answer the same query.

async function hedgedFetch(
  urls: string[],          // same data, different replicas
  hedgeAfterMs: number,    // set near your p95
  init: RequestInit = {},
): Promise<Response> {
  const controllers = urls.map(() => new AbortController());

  const attempt = async (i: number): Promise<{ i: number; res: Response }> => {
    const res = await fetch(urls[i], { ...init, signal: controllers[i].signal });
    if (!res.ok) throw new Error(`replica ${i} returned ${res.status}`);
    return { i, res };
  };

  const first = attempt(0);
  const second = new Promise<{ i: number; res: Response }>((resolve, reject) => {
    const timer = setTimeout(() => attempt(1).then(resolve, reject), hedgeAfterMs);
    // If the first call finishes early, we never send the hedge.
    first.then(() => clearTimeout(timer), () => {});
  });

  const winner = await Promise.any([first, second]);
  controllers.forEach((c, i) => { if (i !== winner.i) c.abort(); });
  return winner.res;
}

Three details people get wrong. First, Promise.any ignores a fast failure from one replica and waits for the other, which is what you want. Second, cancelling the loser matters: without the abort, you pay for both calls in full. Third, if the first call fails quickly, a smarter version sends the second immediately instead of waiting out the timer.

What you must not hedge

Hedging is retrying in a hurry, so the same rule applies as for any retry: only duplicate calls that are safe to run twice. Reads are fine. Idempotent writes carrying an idempotency key are fine (how idempotency keys work). A plain POST /charges is not, and neither is anything that sends an email.

The other trap is hedging into a failing system. If every replica is slow because the whole cluster is overloaded, a second copy of each request just adds load. Which brings us to the other half.

Load shedding: say no early

When a server receives more work than it can handle, queues grow, latency climbs for everyone, and eventually requests time out after the server already spent effort on them. The work was wasted and the user got an error anyway.

Load shedding rejects some requests immediately, with a fast 503 (or 429), so the server’s capacity goes to requests it can finish in time. It’s different from rate limiting. Rate limiting enforces a quota per client, whether the server is healthy or not (see API rate limiting patterns). Shedding looks at the server’s own state.

A simple shedder tracks in-flight requests and rejects above a limit:

const MAX_IN_FLIGHT = 200;   // tune from load tests, not guesswork
let inFlight = 0;

app.use((req, res, next) => {
  if (inFlight >= MAX_IN_FLIGHT) {
    res.set("Retry-After", "1").status(503).send("overloaded");
    return;
  }
  inFlight++;
  res.on("close", () => { inFlight--; });
  next();
});

Better signals than a fixed count: queue wait time (reject anything that has already waited longer than its deadline), CPU saturation, or event-loop lag in Node. Prioritize too. Shed health-check-adjacent and background traffic before interactive user requests, and shed the cheapest-to-retry work first. This pairs with backpressure: shedding is what a server does when backpressure has nowhere left to go.

Putting them together safely

Hedging and shedding fight each other unless you set rules:

• Use a retry budget. Allow hedges only up to a small percentage of traffic, say 5%. When the budget is spent, stop hedging. This keeps the extra load bounded, and it’s what stops a slow cluster from getting a second wave of requests.
• Treat a shed response as a final answer. A 503 from a shedding server should not trigger a hedge or a retry storm. Combine it with exponential backoff and jitter on the client.
• Add a circuit breaker. If a replica keeps failing, stop sending it traffic entirely (circuit breaker pattern).
• Propagate deadlines. If the caller will give up in 200 ms, pass that along so downstream services can drop work that’s already too late.

A rollout order that doesn’t hurt

1. Measure p95, p99 and p99.9 per endpoint, plus fan-out count.
2. Add shedding first. It protects you from the worst failure mode.
3. Hedge one read-only, high-fan-out call behind a flag, with a budget.
4. Compare tail latency and total request volume for a week. If extra load is well under your budget and p99 dropped, widen it.

If your team is wrestling with slow, fan-out-heavy backends and wants a second pair of eyes, our engineering team does this kind of performance review.

The takeaway

Don’t chase the average. Pick the one endpoint with the highest fan-out, measure its p99, and add a load shedder before you add a hedge. The shedder is ten lines and prevents outages. The hedge is the optimization.