Support for backup requests / hedge requests

[ewilde]

Summary

Add support to linkerd to enable backup requests also known at hedge requests.

Context

Backup requests can be used to reduce the overall latency of a system, specifically tail latency. If a request starts to take longer than the n-th percentile, you can choose to issue the same request again, and use the response of the request which replies first to send to the client. This may work well for read requests without requiring modification of downstream systems.

Further reading and context:

• Software techniques that tolerate latency variability are vital to building responsive large-scale Web services
• The Tail at Scale discusses the above article
• Finagle already has implemented a BackupRequestFilter
• Simple implementation of hedge requests in go: hedged

Possible Implementation

I've never used linkerd before so this might be way off!

Looking at the configuration documenation it seems like retires might be a good place to configure backup requests. Whilst a backup request isn't exactly a 'retry' it feels close enough?

Retry backup request

Key	Default Value	Description
quantile	95	The response latency quantile, above which a backup request will be issued. Must be between 0 and 100, exclusive.
clipDurationSec	60	The maximum duration to measure. Used to create the latency histogram. Requests that take longer than clipDurationSec will be added to the histogram using this upper bound.
historySec	3600	The length of time to keep latency information, used when calculating the quantile

Tasks

• Decide on implementation
• Create pull request
• Code review

[wmorgan]

Thanks for the detailed writeup, @ewilde!

[adleong]

I know @olix0r has been thinking a lot about this and the API around it.

[gsogol]

This is a great request. Something I've been thinking about as well. Would be an awesome feature.

[jacktuck]

@ewilde Those links are great. I think hedged requests would give an edge over istio/envoy since they do not have this yet. 😍

[amitsaha]

@ewilde I am curious to know how would one approach adopting this for requests which has a side-effect? (

[jacktuck]

@amitsaha You'd probably only want to hedge idempotent requests.

[ewilde]

@amitsaha as @jacktuck mentioned I'm not sure this approach would work for apis that are not idempotent. Perhaps we could include a response classifier section in the configuration similar to https://linkerd.io/config/1.3.5/linkerd/index.html#http-response-classifiers, this then allows the linkerd user to determine which types of requests can be hedged