How to avoid "retry storms" in distributed services?

Question

A "retry storm" is caused when clients are configured to retry a set number of times before giving up, a retry policy is necessary because of packets loss will occur in normal operation of a service.

Take this example:

If for example the services as a whole were scaled to support 80,000 requests per seconds and run at about 80% of capacity, a spike in traffic that caused the service to receive 101,000 requests per second would cause 1,000 of those requests to fail.

When the retry policies kick in, you end up with additional 1,000+ requests, depending on where the failure was detected which would push the service as a whole up to 102,000 requests per second - from there your service goes into a death spiral doubling the number of failed requests every second.

Other than massive over-provisioning of services beyond the projected peak transaction, which would be inefficient. What strategies can you employ to avoid "retry storms"?

Answer 1

It depends on what you're trying to avoid.

If you are trying to avoid any service interuption of something which is a genuinely critical service (I'm thinking in terms of "people will die if my API call is not appropriately served") the you need to just budget for the huge inefficiencies that come from vastly over provisioning dedicated resources. And yes they have to be dedicated, none of this allowing for traffic spikes stuff, multiple services spiking would thus cause an outage.

In the far more likely scenario that you're service going down would be inconvenient you can tackle the problem both from the client and server sides. Although it's worth noting that it's logically impossible to actually solve the problem of to much traffic because without processing the traffic (which consumes resources) you can't know if it's a retry, if it's a retry for a request that was successful but incorrectly handled by the client, if it's a DDOS, etc. But you can mitigate impact.

In the client code write sensible retry logic which has an upper limit and a mechanism for gracefully failing. That way you don't stick your users in an infinite loop of failing requests and you just give them an error telling them to try whatever they just did in little while.

For your server side infrastructure the simplest solution is to throttle. Hard limits on requests, especially if you can try and spread them logically based on your specific use case (ie. If you have a centralised service make some hard decisions, do you want to start blocking geographically distant requests which might be resulting in threads hanging server side? Or do you want to distribute your inevitable yet minor outage evenly? etc) It basically boils down to the fact that returning a 503 intentionally from a gateway is a hell of a lot cheaper than letting the request go through and sending a 504 anyway. Basically force clients to behave based on what you can currently provide and provide the correct responses so that clients can react appropriately.

Answer 2

One way of preventing these retry storms is by using backoff mechanisms.

From the Implement backoff on retry section of Google App Engine Designing for Scale guide:

Your code can retry on failure, whether calling a service such as Cloud Datastore or an external service using URL Fetch or the Socket API. In these cases, you should always implement a randomized exponential backoff policy in order to avoid the thundering herd problem. You should also limit the total number of retries and handle failures after the maximum retry limit is reached.

Most of the GAE APIs already have such backoff mechanisms/policies enabled by default.