The request hedging pattern is introduced in the paper The Tail At Scale as a solution by Google to address the long tail effect in microservices. It is also one of the two retry modes in gRPC.

The hedging client sends the same request to multiple nodes, and once it receives the first result, it cancels the remaining in-flight requests. This pattern primarily aims to achieve predictable latency.
For instance, if our service’s call chain consists of 20 nodes, each with a P99 latency of 1 second, there is a statistically significant 18.2% chance that the request time will exceed 1 second.

Using the hedging pattern, we consistently obtain results from the fastest node, thus preventing unpredictable long tail latencies (service faults are not within the scope here).

In Golang, we can quickly implement the hedging request pattern using context. For example, in the code snippet below, we make five requests to the same backend service, but we only take the first one that returns:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func hedgedRequest() string {
	ch := make(chan string) // chan used to abort other requests
	ctx, cancel := context.WithCancel(context.Background())

	for i := 0; i < 5; i++ {
		go func(ctx *context.Context, ch chan string, i int) {
			log.Println("in goroutine: ", i)
			if request(ctx, "http://localhost:8090", i) {
				ch <- fmt.Sprintf("finsh [from %v]", i)
				log.Println("completed goroutine: ", i)
			}
		}(&ctx, ch, i)
	}

	select {
	case s := <-ch:
		cancel()
		log.Println("cancelled all inflight requests")
		return s
	case <-time.After(5 * time.Second):
		cancel()
		return "all requests timeout after 5 secs."
	}
}

You can find the complete code at: https://go.dev/play/p/fY9Lj_M7ZYE
The benefit of this approach is that we can mitigate long-tail latency in services and maintain the delays between services within a controllable range. However, directly implementing it can lead to multiple times the load, so careful design is necessary.

Why Does Long Tail Latency Occur?

There are several reasons for long tail latency, such as:

1. Hybrid deployments have become mainstream, meaning many users compete for critical resources on the same physical machine, potentially leading to long-term effects due to resource scheduling.
2. Garbage Collection (GC), which doesn’t require much explanation; Golang’s Stop-The-World (STW) can amplify long tail latency.
3. Queuing, including message queues, network delays, etc.

Is there a way to avoid the request amplification caused by the hedging request pattern? The blog post Go High-Performance Programming EP7: Use singleflight To Merge The Same Request discusses how to use SingleFlight to merge identical requests. In this scenario, using SingleFlight can partially alleviate duplicate requests.

Another approach is to initially send only one request. If the P95 threshold does not respond, immediately request the second node. This method limits duplicate requests to about 5% and significantly reduces long-tail requests.

In the paper The Tail At Scale, several other methods are suggested to address long tail requests:

1. Service differentiation and priority queues: Different service classes can be prioritized to schedule user requests over non-interactive requests. Short low-level queues allow faster execution of higher-level strategies.
2. Reducing head-of-line blocking: Transforming time-consuming requests into more minor, more manageable requests is also a standard web performance enhancement method.
3. Micro-partitioning: Fine-grained load adjustments to minimize the latency impact caused by uneven load distribution.
4. Implementing circuit breakers for poorly performing machines.
5. …
   Do you have other great ways to deal with long-tail requests?