Tail latency and hedged requests: an interactive fan-out simulator

Tail latency is how long the slowest requests take: the p99, the p99.9. It matters more than the average because of fan-out. When one user request calls many backends in parallel and waits for all of them, a slowdown that hits 1 call in 100 hits most user requests. Hedged requests, sending a second copy of a call that is running late and taking whichever answers first, cut that tail for a few percent more load.

In the playground, a backend answers in about 10 ms but stalls for 200 ms to a second 1% of the time. Change how many backends each user request calls, and when to hedge.

Why fan-out makes the tail the common case

If each backend is slow with probability p, a request that calls n of them and waits for all is slow with probability 1 − (1 − p)ⁿ. With p = 1%, that is 10% for 10 backends and 63% for 100. In the playground, every backend’s p99 is under 30 ms, yet with 100 backends per request the median user request takes 436 ms. The backends’ rare tail has become the user’s typical experience. Search, feeds, recommendation and any page assembled from many services all fan out like this.

Where the tail comes from

Slow calls are usually not slow servers but slow moments: a garbage-collection pause, a request queued behind a large one, a cache miss to disk, a noisy neighbour on the same machine, a background compaction, a network retransmit. They are short and random, which is exactly why retrying elsewhere works: the replica you ask second is unlikely to be in the same moment.

Hedged requests

Send the call to one replica. If it has not answered by about the 95th percentile of its normal latency, send the same call to another replica, use whichever answers first and cancel the other. Only the slowest few percent of calls get a second copy, so the extra load is small: hedging after 20 ms adds 2% more calls in the playground and brings the median request with 100 backends from 436 ms to 29 ms. Hedge too early and you double the load instead, as the last preset does after 5 ms, and the extra load makes every server slower.

The idea comes from Jeffrey Dean and Luiz Barroso’s 2013 paper The Tail at Scale, which also describes tied requests: send both copies at once, each telling its server about the other, so whichever starts first cancels its twin. Hedge only calls that are safe to run twice, reads or idempotent writes.

Other ways to cut the tail

• Fan out less: fewer, larger partitions, or answering from a cache or precomputed result.
• Do not wait for everyone: return results from the backends that answered within a deadline, if a slightly incomplete answer is acceptable, as search often is.
• Route around slow servers: least connections or power of two choices avoid sending work to a server that is already behind.
• Remove the cause: smaller GC pauses, separate queues for big and small requests, isolating background work.

A hedged request in code

// hedged request: if the first replica is slow, ask a second and take whichever answers first
func hedged(ctx context.Context, replicas []Client, req Request, hedgeAfter time.Duration) (Response, error) {
    ctx, cancel := context.WithCancel(ctx)
    defer cancel()                                  // the loser is cancelled when we return
    results := make(chan result, 2)
    send := func(c Client) { r, err := c.Do(ctx, req); results <- result{r, err} }

    go send(replicas[0])
    select {
    case res := <-results:
        return res.resp, res.err                     // answered in time: no hedge needed
    case <-time.After(hedgeAfter):                   // about the p95 of this call
        go send(replicas[1])
    }
    res := <-results                                 // first of the two to answer
    return res.resp, res.err
}

In a system design interview

When a request fans out, do the arithmetic out loud: “The search page queries 100 index shards. If each is slow 1% of the time, 63% of searches would wait on a slow shard, so the shards’ p99 is our median. Each shard call is hedged to a second replica after its p95, about 20 ms, which costs a few percent more load, and the page returns whatever shards answered within 200 ms.” Expect the follow-ups: what the hedge does to load during an incident, which calls are safe to duplicate, and how you measure p99 and p99.9.

Read the guide to tail latency, see queueing and Little’s law for why busy servers have long tails, or watch a strong candidate design typeahead search.

Questions people ask