Taming the tail

Slow servers are normal. The goal is a system that keeps answering on time while some of its parts are slow. This is the same idea as fault tolerance: build something reliable out of parts that aren't. The main tools are timeouts, hedged requests, tied requests and graceful degradation.

The big idea

Don't wait on one server that might be stuck. Plan for the wait. Set a deadline. If the first reply is late, ask someone else. If someone is still late when the deadline passes, answer without them.

Timeouts are the foundation. Without one, a hung dependency holds your threads and connections forever.

Walking through it

Timeouts. Set each one from the dependency's measured latency, usually a bit above its p99. A common starting point is p99 × 1.5. Don't pick a round number someone chose years ago.

Hedged requests. Send the request to one replica. If it hasn't answered after a short delay, such as the p95 latency, send a second copy to another replica. Use whichever answers first, and cancel the other.

Because the hedge fires only for the slowest few percent of requests, the extra load stays small. In a Bigtable benchmark from the Tail at Scale paper, hedging after 10 ms cut the p99.9 from 1,800 ms to 74 ms, while sending only about 2% more requests.

// Sketch: `fetch` and the replica URLs are assumed. Hedge one replica after a delay.
async function hedgedGet(key: string, replicas: string[], hedgeAfterMs = 20) {
  const controllers: AbortController[] = []
  const attempt = (replica: string) => {
    const ctl = new AbortController()
    controllers.push(ctl)
    return fetch(`${replica}/kv/${key}`, { signal: ctl.signal }).then((r) => r.json())
  }
  let timer: ReturnType<typeof setTimeout> | undefined
  const first = attempt(replicas[0])
  const hedge = new Promise((resolve, reject) => {
    timer = setTimeout(() => attempt(replicas[1]).then(resolve, reject), hedgeAfterMs)
  })
  try {
    return await Promise.any([first, hedge])
  } finally {
    clearTimeout(timer) // the hedge never fires if the first reply already won
    controllers.forEach((c) => c.abort()) // cancel the loser
  }
}

Tied requests. Send the request to two servers at once, and tag each with the other's identity. When one server starts working on it, it tells the other to cancel. This removes most of the duplicated work, while still avoiding a busy server's queue.

Graceful degradation. Often a partial answer on time beats a full answer late. A search can return results from 98 of 100 shards. A product page can leave out recommendations. Decide in advance which parts are optional.

Common mistakes

• Hedging writes. Only hedge idempotent reads, or writes that carry an idempotency key.
• No cap on hedges. A struggling cluster that receives double traffic gets slower. Limit the hedge rate.
• Forgetting to cancel the loser. An unanswered duplicate still costs the server work.

Check yourself

1. Why should a hedge wait for a delay such as p95 instead of firing at once? Hedges then fire only for the slowest few percent of requests, so the extra load stays small.
2. Why accept partial results? A slightly incomplete answer that arrives on time often serves users better than a complete answer that arrives late.

Key takeaways

• Set timeouts from measured latency, not from a round number.
• Hedge slow idempotent reads after a delay, and cancel the slower copy.
• Tied requests remove most duplicate work while still avoiding busy queues.
• Decide ahead of time which parts of a response can be left out.

Further learning

The Amazon Builders' Library article on timeouts, retries and backoff with jitter covers the retry side in detail.

Next, read about latency budgets, which split a target across every hop.