Hedged Requests

A tail-latency mitigation strategy where a client issues the same logical request to multiple replicas or backends and consumes the first response, cancelling the losers. It trades a controlled increase in resource consumption for a bounded reduction in P99/P999 latency in high-fanout distributed systems.

Hedged requests exist because latency distributions in large fleets are rarely Gaussian; they are heavy-tailed due to GC pauses, page faults, network jitter, noisy neighbors, and lock contention on a small subset of nodes at any given moment. A single slow replica can dominate a fan-out operation’s total latency even if 999 out of 1000 backends respond instantly. Instead of waiting on a single request path and hoping it doesn’t hit that tail, the client (or an RPC layer like gRPC or Finagle) issues a second identical request after a threshold delay, typically set near the P95 latency of the endpoint, rather than firing both simultaneously. Firing both at t=0 is wasteful; firing the hedge after a delay bounds the additional load to only those requests that are already trending slow.

There are two dominant flavors: hedged requests (independent, uncorrelated retries with no coordination between replicas) and tied requests (a Google-internal refinement described in the Tail at Scale paper, where each replica is made aware of its sibling via a shared request ID). In the tied variant, once one replica begins execution, it broadcasts a cancellation signal to the others, preventing wasted CPU cycles on the loser. Without this coordination, naive hedging can amplify load precisely during periods of degradation — the exact moment you can least afford it — creating a feedback loop where hedge-induced load pushes more nodes into the slow tail.

Correctness is the primary architectural constraint: hedging is only safe for idempotent operations. A duplicated write, payment authorization, or non-idempotent RPC executed twice can corrupt state unless de-duplicated via an idempotency key or fencing mechanism upstream. Read-heavy workloads (cache lookups, quorum reads, search shard queries) are the canonical use case. Systems must also handle cancellation propagation correctly — if the underlying transport doesn’t support mid-flight cancellation (e.g., a blocking synchronous call to a legacy backend), the ‘losing’ request still consumes a thread, socket, or connection pool slot until it naturally completes, meaning hedging without cancellation support can silently exhaust connection pools under load.

Operationally, tuning the hedge delay is a live control-loop problem, not a static config value. Set it too aggressively low and you 2x your effective QPS against every backend, potentially triggering the very saturation that causes tail latency in the first place; set it too high and you lose the latency benefit entirely. Production systems typically compute the hedge delay adaptively from a rolling percentile of recent latencies per endpoint (e.g., dynamically pegged to P90/P95) and cap the maximum number of concurrent hedges system-wide as a circuit breaker, since hedging is fundamentally a latency-for-throughput trade that must be load-shed away during genuine overload rather than genuine outlier events.