In a search cluster that fans each query out to 100 shards, how do hedged requests tame tail latency caused by rare per-shard slowness?

## Tail-latency amplification A single shard is fast most of the time, but every server has occasional slow requests. Causes include background compaction, a memory-management pause, a noisy neighbour, a cold cache or a retransmitted packet. Suppose each shard independently takes longer than 1 s on `p = 1%` of requests. A scatter-gather query that waits for **all** `N` shards is slow if **any** of them is slow: `P(query slow) = 1 − (1 − p)^N` | Shards waited on (N) | Share of queries slower than 1 s | |---|---| | 1 | 1.0% | | 10 | 9.6% | | 50 | 39.5% | | 100 | 63.4% | | 1,000 | effectively 100% | At 100 shards, most queries (about 63%) pay the per-shard p99. Improving the *average* shard latency does not help. The fix has to target the tail directly, or stop waiting for it. These figures assume shards slow down independently. Correlated slowness, such as cluster-wide overload, behaves differently and is covered below. ## Hedged requests A **hedged request** duplicates only the sub-requests that are already late: 1. Send the sub-request to one replica of the shard. 2. Wait for a **hedge delay**, typically about that shard's p95 latency. 3. If no reply has arrived, send the same sub-request to a **different replica**. 4. Use whichever response arrives first and **cancel** the other copy. 5. Enforce a **hedge budget**, for example no more than a few percent of sub-requests hedged, so that a widespread slowdown cannot double traffic. ```pseudocode function callShard(shard, req, hedgeDelay, deadline): first = send(shard.replica(0), req) if waitFor(first, hedgeDelay): return first.result pending = [first] if hedgeBudget.tryAcquire(): pending.add(send(shard.replica(1), req)) winner = waitAny(pending, until = deadline) cancelAllExcept(pending, winner) return winner == null ? TIMED_OUT : winner.result ``` ## What hedging costs - **Extra load.** With the delay at the p95, only about 5% of sub-requests are still pending when the timer fires, so the extra sub-requests are at most about 5%. The real figure is lower when cancelled losers stop early. - **Latency bound.** When the first replica stalls, a hedged sub-request typically finishes within the hedge delay plus a normal response time from the second replica. - **Duplicate work.** Both replicas may run the query until the cancellation reaches one of them. Search reads have no side effects, so duplicates are safe, but they still consume CPU. Sending two copies of every sub-request immediately would also cut the tail, but it doubles the load for a benefit that comes almost entirely from the few slow cases. ## When hedging backfires or does not help - **Query-intrinsic slowness.** An expensive query, such as a huge wildcard expansion or a very common term, is slow on every replica. The backup is just as slow and only adds load. - **Cluster-wide overload.** When the slowness comes from saturation, hedges push more traffic into queues that are already full and deepen the incident. The budget and an overload signal (queue depth, rejection rate) should switch hedging off. - **Correlated replicas.** If two replicas share a disk, a host or a network path, the backup inherits the stall. - **No cancellation.** If the losing copy is not cancelled, the extra work runs to completion and hedging costs more than planned. ## Related techniques | Technique | Idea | Trade-off | |---|---|---| | Tied requests | send to two replicas at once; whichever starts executing first tells the other to drop its copy | almost no duplicate work, but replicas must message each other | | Latency-aware replica selection | route to replicas with low recent latency and short queues | avoids known-slow replicas, but can herd traffic onto a few | | Deadline with partial results | stop waiting at a deadline and answer from the shards that replied | bounded latency, possibly incomplete answers | | Fewer, larger shards | reduce `N` | each shard is slower and less parallel | | Result caching | answer repeated queries with no fan-out | helps only popular queries and must be invalidated when the index refreshes | In practice these techniques are layered: replica selection first, hedging within a budget, and a deadline as the final backstop.