Skip to content

Hedged Requests

1. What is it? (2-3 lines)

Hedged Requests is a tail-latency reduction pattern where a client issues a primary request to Node A, and if no response is received within a tight deadline (e.g. P95 latency threshold), issues a duplicate "hedged" request to Node B, using whichever response arrives first and canceling the outstanding request.

2. Why does it exist?

In large-scale distributed systems operating across thousands of servers, long-tail latency (P99 / P99.9 latency spikes) is inevitable due to background JVM Garbage Collection, network packet loss, disk I/O queuing, or noisy neighbors. Hedged Requests tame tail latency by eliminating long-tail outliers.

3. Where is it used?

  • Distributed Search & Analytics: Google Search (Dean & Barroso's "The Tail at Scale" paper), Apache Lucene / Elasticsearch, BigTable.
  • Distributed Storage & SQL: CockroachDB (Hedged Reads), Cassandra (Speculative Execution), gRPC Hedging policies.
  • Client Microservices: Finagle, Envoy Proxy (hedging policy).

4. How does it work? (simple flow)

  1. Primary Request: Client sends read request \(R_1\) to Node A (Primary replica) at time \(T=0\text{ms}\).
  2. Timer Window: Client sets a Hedging Delay timer equal to the expected P95 latency (e.g. \(10\text{ms}\)).
  3. Trigger Hedged Request: If Node A has NOT responded by \(T=10\text{ms}\), Client immediately fires duplicate request \(R_2\) to Node B (Secondary replica).
  4. Race Resolution:
  5. Client waits for whichever response (\(R_1\) or \(R_2\)) returns FIRST.
  6. Client processes the winning response and sends a Cancelation Signal (CANCEL) to the losing node.
Time 0ms:    Client --- (R1) ---> Node A (Stalled by GC pause!)
Time 10ms:   [Timer Fires! No Response]
Time 10ms:   Client --- (R2) ---> Node B (Healthy)
Time 12ms:   Client <--- (ACK) -- Node B (Winner!)
Time 12ms:   Client --- (CANCEL) -> Node A

5. Advantages

  • Dramatically compresses tail latency (\(P99.9\) drops from \(1,000\text{ms}\) to \(15\text{ms}\)).
  • Guarantees high consistency and fast response SLAs for user-facing search and read queries.
  • Hides transient node hiccups, GC pauses, and disk I/O stalls transparently.

6. Limitations

  • Traffic Amplification Penalty: Issuing duplicate requests increases overall network and server load by 2-5%.
  • MUST BE READ-ONLY: Hedged requests must NEVER be used for non-idempotent mutation queries (POST /pay!) due to risk of double execution.

7. Common interview questions (10)

  1. Explain how Hedged Requests solve the "Tail at Scale" problem described by Jeffrey Dean (Google).
  2. How does Cassandra's speculative_retry configuration implement Hedged Requests?
  3. How do you select the optimal Hedging Delay threshold (e.g. P90 vs P95 vs P99 latency)?
  4. Why must Hedged Requests be strictly restricted to Idempotent Read operations?
  5. What is the difference between Hedged Requests and Parallel Dual-Reads (Tied Requests)?
  6. How does gRPC natively configure Hedging policies (maxAttempts, hedgingDelay) in JSON configs?
  7. What is the network and CPU load penalty of Hedged Requests under heavy cluster load?
  8. How does a client cancel the losing outstanding request to prevent wasted downstream server CPU?
  9. How does Envoy Proxy implement Request Hedging at the Service Mesh layer?
  10. What happens if you enable Hedged Requests when the downstream system is already suffering from 100% CPU saturation?

8. Common misconceptions

  • Misconception: Hedged Requests send 2 requests simultaneously at \(T=0\). Fact: Sending 2 requests immediately doubles total traffic (\(100\%\) load penalty). Hedged Requests wait for a P95/P99 delay before sending the 2nd request, adding only 2-5% extra traffic!
  • Misconception: Hedged Requests can be used for database writes. Fact: Hedged requests are strictly for Idempotent Read Operations.

10. 30-second cheat sheet

  • Purpose: Eliminate P99 / P99.9 Tail Latency spikes caused by GC pauses or network hiccups.
  • Flow: Send \(R_1 \to\) Wait for P95 Latency Timer (e.g. 10ms) \(\to\) Send \(R_2 \to\) Take 1st Response \(\to\) Cancel loser.
  • Traffic Overhead: Minimal (~2-5% extra traffic) because only 5% of requests trigger hedging.
  • Golden Rule: STRICTLY READ-ONLY / IDEMPOTENT QUERIES ONLY! Never hedge unsafe mutations.