Hedged Requests in Go: Reducing Tail Latency Without Overloading Dependencies

Most requests in a distributed system finish quickly.

A few don't.

Your API might have a median response time of 40ms, while its p99 latency reaches 900ms. Most users get a fast response, but a small percentage experience significantly longer waits.

These slow requests are particularly problematic in systems that depend on multiple services.

A single slow dependency can delay an entire operation, even when every other component is responding normally.

One way to address this problem is request hedging.

Instead of waiting indefinitely for an unusually slow request, the client starts another copy after a configured delay. Whichever request succeeds first wins, and the remaining requests are canceled.

This technique can significantly reduce tail latency, but it comes with an important trade-off: it generates additional traffic.

If every slow request triggers another request without limits, the mechanism designed to improve latency can overload the dependency it's trying to protect.

In this article, we'll explore:

• What tail latency is and why averages hide it
• How hedged requests work
• The difference between hedging and retries
• How to implement hedged requests in Go
• How to cancel losing requests safely
• How to integrate hedging with retry budgets and adaptive concurrency
• When hedging helps and when it makes things worse
• What to monitor and test in production

1. The Problem: Tail Latency

Let's say an API receives 10,000 requests.

Its response-time distribution looks like this:

Looking only at the average or median would suggest that the service is performing well.

But 1% of 10,000 requests means 100 requests take at least 900ms.

For latency-sensitive applications, these outliers matter.

Consider an API that aggregates data from five independent services:

 API Request | +-----------+-----------+ | | | Service A Service B Service C | | | Service D Service E | | | | +-----------+-----------+ | Final Response 

If the API needs all five responses, its total latency is constrained by the slowest dependency.

Even if four services respond in 30ms, one service taking 800ms can delay the entire operation.

This is one reason tail latency becomes increasingly important as distributed systems grow.

Jeff Dean and Luiz André Barroso discuss this problem in their influential paper, The Tail at Scale. They describe techniques for building responsive services despite unpredictable latency in individual components.

Reference: https://research.google/pubs/the-tail-at-scale/

2. What Are Hedged Requests?

A hedged request is a duplicate request sent while the original request is still in progress.

The client does not immediately send multiple copies.

Instead, it waits for a configurable period.

If the original request hasn't completed, the client sends another request, ideally to a different replica.

The first successful response wins.

Time | | Primary request | ────────────────────────────────> | | Wait: 100ms | | Hedge request | ─────────────────────> | | Hedge response: 160ms | Primary response: 450ms | | Return hedge response | Cancel primary request | 

The important detail is that the second request starts before the first one fails.

This is fundamentally different from a traditional retry.

A retry waits for an unsuccessful attempt before trying again.

A hedge assumes that an unusually slow request might be an outlier and starts another attempt proactively.

Why does this work?

Imagine two replicas:

• Replica A is experiencing temporary contention.
• Replica B is healthy.

The primary request goes to A.

After 100ms, it still hasn't completed, so the client sends a hedge to B.

If B responds in 60ms, the client returns that response instead of waiting for A.

The total latency becomes approximately 160ms instead of 450ms.

The original request might still finish later, but its result is no longer needed.

3. Hedging vs. Retrying

These mechanisms are related, but they solve slightly different problems.

A retry responds to failure.

A hedge responds to excessive waiting.

This distinction matters because hedging can increase downstream load even when the original request would eventually succeed.

For that reason, hedging should generally be limited to safe, idempotent operations, especially reads.

4. Choosing the Hedging Delay

The hedging delay is one of the most important configuration decisions.

If the delay is too short, the client duplicates too many requests.

If it is too long, the hedge provides little latency improvement.

A reasonable starting point is to use a measured latency percentile for a particular operation.

For example:

A 100ms hedging delay means that requests exceeding the p95 threshold become candidates for hedging.

Under stable conditions, approximately 5% of requests may reach that threshold.

This does not mean exactly 5% of requests will generate a hedge: requests can complete at the threshold boundary, and actual behavior depends on the latency distribution and scheduling.

The important principle is to trigger hedging in the tail, not in the middle of normal traffic.

The original Tail at Scale paper discusses using a high-percentile latency threshold to limit duplicate traffic while reducing extreme latency. Its examples demonstrate why carefully selected hedging delays can achieve substantial tail-latency improvements with relatively modest additional load.

Source: https://www.andrew.cmu.edu/user/gaurij/18-847F-Readings/tail_at_scale.pdf

5. Implementing Hedged Requests in Go

Let's build a small hedging executor.

Our implementation will support:

• An immediate primary request
• A configurable hedging delay
• A maximum number of attempts
• Context cancellation
• First-successful-response semantics
• Retryable error classification
• An optional shared retry budget

We'll use Go generics so the executor can return any response type.

Step 1: Define the policy

package hedge import ( "context" "errors" "fmt" "time" ) var ( ErrInvalidPolicy = errors.New("invalid hedging policy") ErrBudgetDenied = errors.New("hedging budget exhausted") ) type Budget interface { TryTake() bool } type Policy struct { Delay time.Duration MaxAttempts int Budget Budget ShouldHedge func(error) bool } type result[T any] struct { value T err error } 

The Budget interface allows us to reuse the retry budget implementation from the previous article.

The original request does not consume a hedge token.

Every additional request does.

We also use ShouldHedge to distinguish errors that should terminate the operation from errors that may allow another attempt.

For example, a validation error should not trigger another request.

Step 2: Implement the executor

func Do[T any]( ctx context.Context, policy Policy, operation func(context.Context, int) (T, error), ) (T, error) { var zero T if policy.Delay <= 0 || policy.MaxAttempts < 1 || policy.MaxAttempts > 3 || operation == nil || policy.ShouldHedge == nil { return zero, ErrInvalidPolicy } if err := ctx.Err(); err != nil { return zero, err } hedgeCtx, cancel := context.WithCancel(ctx) defer cancel() results := make(chan result[T], policy.MaxAttempts) launched := 0 inFlight := 0 var lastErr error startAttempt := func() { launched++ inFlight++ attempt := launched go func() { value, err := operation(hedgeCtx, attempt) results <- result[T]{ value: value, err: err, } }() } // The primary request starts immediately. startAttempt() var timer *time.Timer var timerC <-chan time.Time if policy.MaxAttempts > 1 { timer = time.NewTimer(policy.Delay) timerC = timer.C defer timer.Stop() } for { select { case <-ctx.Done(): return zero, ctx.Err() case res := <-results: inFlight-- if res.err == nil { // First successful response wins. return res.value, nil } lastErr = res.err if !policy.ShouldHedge(res.err) { return zero, res.err } if inFlight == 0 && launched == policy.MaxAttempts { return zero, lastErr } case <-timerC: if launched >= policy.MaxAttempts { timerC = nil continue } if policy.Budget != nil && !policy.Budget.TryTake() { // No more additional requests. timerC = nil if inFlight == 0 { if lastErr != nil { return zero, lastErr } return zero, ErrBudgetDenied } continue } startAttempt() if launched < policy.MaxAttempts { timer.Reset(policy.Delay) } else { timerC = nil } } } } 

Let's examine the important decisions.

The primary request starts immediately.

We don't wait for a timer before sending the first request.

Additional requests start only after the configured delay.

If the primary finishes successfully before the delay expires, the executor returns without sending a hedge.

The first successful response wins.

As soon as a successful result arrives, the function returns and cancels the shared context.

Errors are classified.

A fatal error can terminate the operation immediately. A retryable error can be treated as non-final while another attempt is still running.

The number of attempts is bounded.

The implementation intentionally limits the example to three total attempts, including the original request.

This is a conservative default for the example, not a universal limit.

Step 3: Use the executor

Imagine a service that reads market data from multiple replicas.

type Price struct { Symbol string Value float64 } func fetchPrice( ctx context.Context, attempt int, ) (Price, error) { replica := selectReplica(attempt) return replica.Fetch(ctx, "AAPL") } 

We can now use the hedging executor:

policy := hedge.Policy{ Delay: 100 * time.Millisecond, MaxAttempts: 2, Budget: retryBudget, ShouldHedge: isRetryableError, } price, err := hedge.Do( ctx, policy, fetchPrice, ) if err != nil { return err } fmt.Printf( "%s: %.2f\n", price.Symbol, price.Value, ) 

The primary request goes to the first replica.

If it hasn't completed after 100ms, the executor checks the budget and starts another request.

If the second replica responds first, the result is returned and the first request is canceled.

The example assumes that selectReplica routes attempts to distinct, suitable replicas. Sending both copies to the same overloaded instance may provide little benefit.

6. Cancellation Is Not the Same as Stopping Work

This is one of the most important details in a hedging implementation.

When the winning request completes, the executor calls cancel() on the shared context.

The losing requests receive cancellation through their contexts.

But cancellation is cooperative.

It does not forcibly terminate a goroutine, an HTTP request, a database query, or server-side processing.

For example, a dependency may continue executing a query even after the client disconnects.

A correct operation should propagate its context:

func fetch( ctx context.Context, client *http.Client, ) error { req, err := http.NewRequestWithContext( ctx, http.MethodGet, "https://api.example.com/prices/AAPL", nil, ) if err != nil { return err } resp, err := client.Do(req) if err != nil { return err } defer resp.Body.Close() return nil } 

The server should also respect request cancellation where possible.

Otherwise, the client may stop waiting while the dependency continues doing unnecessary work.

This is especially important for expensive database queries and CPU-intensive operations.

7. Why a Hedge Budget Matters

Hedging creates additional traffic.

Imagine a service receiving 10,000 requests per second.

If 5% reach the hedging threshold, that could mean approximately 500 additional attempts per second.

Now imagine the dependency is already degraded.

More concurrent requests may increase queueing, which increases latency, which triggers more hedges.

The mechanism can create the same kind of amplification problem that we discussed in the Retry Budgets article.

This is why the hedge budget should be shared across requests.

A simple rule:

• The original request is always allowed, subject to normal admission controls.
• Each additional hedge requires a token.
• Successful normal traffic replenishes the budget.
• If the budget is exhausted, no new hedges are launched.

For example:

budget := retry.NewRetryBudget( 20, 0.1, ) 

The exact budget should be tuned according to the dependency's spare capacity and the service's traffic patterns.

The important part is that hedging is not an unlimited permission to duplicate requests.

It is an additional workload that must be controlled.

8. Hedging and Adaptive Concurrency

Hedging and adaptive concurrency work particularly well together, but they need to share a consistent view of downstream capacity.

Adaptive concurrency adjusts how many requests are allowed in flight based on observed dependency behavior.

Hedging creates additional in-flight requests.

If the adaptive limiter counts only original requests, hedged requests can bypass the intended concurrency ceiling.

That defeats the purpose of the limiter.

A safer integration is:

1. The primary request acquires a concurrency permit.
2. A hedge must acquire its own permit.
3. If no permit is available, the hedge is skipped.
4. The winning request returns its result.
5. Every attempt releases its own permit when it actually completes.

There is an important implementation detail here.

Do not release the losing request's concurrency permit merely because the caller stopped waiting for it.

The permit must remain held until the underlying operation actually completes or otherwise confirms that the protected work has stopped.

Otherwise, the limiter undercounts active downstream work.

This is also why a shared cancellation context alone is not enough to guarantee that hedged work has disappeared.

9. Hedging Requires Idempotency

Sending the same operation more than once is not always safe.

Consider these operations:

A hedge can reach two different servers before either has completed.

Both servers may execute the operation.

Canceling one request does not guarantee that its side effects are rolled back.

For operations with side effects, use an idempotency key or another server-side deduplication mechanism.

Even then, the server must correctly enforce the idempotency contract.

Hedging should generally be introduced first for read-only operations where duplicate execution is safe.

10. Where Should Hedged Requests Be Sent?

Sending a duplicate request to the same server is often ineffective.

If that server is experiencing CPU contention, a long queue, or an overloaded database connection pool, the second request may suffer from the same problem.

Ideally, the hedge should target an independent replica.

But independence is not guaranteed.

Two replicas may share:

• The same database
• The same network path
• The same cache
• The same storage system
• The same overloaded region

This is called correlated failure or correlated latency.

If both requests depend on the same struggling resource, hedging may increase load without meaningfully reducing latency.

Replica selection should consider failure domains and actual dependency topology.

11. Observability: Measure the Cost of Hedging

A hedging system needs more than a request-latency dashboard.

You need to understand whether the reduction in tail latency justifies the additional work.

Useful metrics include:

A useful derived metric is the hedge win rate:

[
HedgeWinRate =
\frac{HedgeWins}{HedgedRequests}
]

If hedges rarely win, you may be generating additional traffic without much benefit.

Also compare:

• p50 latency
• p95 latency
• p99 latency
• Downstream request volume
• Dependency CPU and memory usage
• Cancellation effectiveness
• Error rate

The goal is not to minimize p99 at any cost.

It is to improve tail latency while keeping the additional workload within the dependency's capacity.

12. Testing Hedged Requests

Concurrency behavior needs deterministic tests.

At minimum, test these scenarios:

• The primary request succeeds before the hedging delay.
• The primary request is slow and the hedge wins.
• The primary request fails with a retryable error.
• A fatal error cancels outstanding attempts.
• The hedge budget prevents additional requests.
• The parent context is canceled.
• The maximum number of attempts is respected.
• Losing operations receive cancellation.
• A losing operation that ignores cancellation does not release its concurrency permit prematurely.

A simple test for the winning hedge could use controlled channels instead of arbitrary sleeps:

func TestHedgeWins(t *testing.T) { primaryStarted := make(chan struct{}) hedgeStarted := make(chan struct{}) ctx, cancel := context.WithTimeout( context.Background(), time.Second, ) defer cancel() policy := Policy{ Delay: 20 * time.Millisecond, MaxAttempts: 2, ShouldHedge: func(error) bool { return true }, } result, err := Do( ctx, policy, func( ctx context.Context, attempt int, ) (string, error) { if attempt == 1 { close(primaryStarted) <-ctx.Done() return "", ctx.Err() } close(hedgeStarted) return "hedge response", nil }, ) if err != nil { t.Fatal(err) } if result != "hedge response" { t.Fatalf( "unexpected result: %s", result, ) } <-primaryStarted <-hedgeStarted } 

The test verifies that the second request can win and that the operation completes successfully.

In a complete test suite, also verify that the primary operation observes cancellation.

Run the race detector:

go test -race ./... 

Finally, use load tests with a dependency that deliberately introduces variable latency.

A useful experiment compares:

1. Hedging disabled.
2. Hedging enabled with a conservative delay.
3. Hedging enabled with an aggressive delay.
4. Hedging enabled with a shared budget.
5. Hedging enabled with adaptive concurrency.

Compare both latency improvements and additional downstream traffic.

13. Production Checklist

Before introducing hedged requests into a production service:

• [ ] Hedge only safe, idempotent operations.
• [ ] Select a delay from measured latency distributions.
• [ ] Use a strict maximum attempt count.
• [ ] Require a shared budget for additional attempts.
• [ ] Ensure hedges target independent replicas where possible.
• [ ] Apply concurrency limits to every attempt.
• [ ] Propagate context cancellation.
• [ ] Ensure permits remain held while work is still active.
• [ ] Respect the original request deadline.
• [ ] Measure hedge win rate and additional traffic.
• [ ] Test correlated latency and dependency overload.
• [ ] Roll out gradually and compare against a no-hedging baseline.

Conclusion

Tail latency is one of the most difficult problems in distributed systems because a small number of unusually slow operations can dominate the response time of an entire request.

Hedged requests provide a way to reduce that impact.

By launching a second request after a carefully selected delay, a client can avoid waiting for an unusually slow replica and use the first successful response.

But hedging is not free.

Every additional request consumes capacity, and uncontrolled duplication can make an already degraded dependency even slower.

The right approach combines measured hedging delays, idempotent operations, cancellation, retry budgets, and adaptive concurrency limits.

The goal isn't to send more requests. It's to get the response sooner without making the system slower for everyone else.

References

• The Tail at Scale — Google Research
• Request Hedging — gRPC Documentation
• gRPC Retry and Hedging Design