Retry with jitter

A server went down for ten seconds, and two thousand clients had a request fail at once. The server will come back and answer 500 times a second, so four seconds would be enough for everyone. But the clients do not know when it will come back, and they retry. Exactly how decides whether they get an answer in half a minute or never. Choose a retry rule and watch how many clients knock on the server every 100 ms.

“At once” is the fastest option as long as a refusal costs the server nothing: everyone is served in 13.9 s, but each client sent 120 requests on average. A one-second pause and a pause that doubles cut the number of requests but turn the clients into a marching column: all two thousand arrive in the same tick, the server takes fifty, the rest go off to wait together and come back together again. The exponential pause without randomness serves the last client after 13 minutes. Now turn on “a refusal costs the server a tenth of an answer”: accepting a connection and answering “busy” is work too. Two thousand refusals per tick eat everything the server can do, and all three rules without randomness let not a single client through in a minute. And with jitter, a random share of the pause, the peak load after the outage is 44–94 requests per tick against a capacity of 50, and everyone is served in 23–30 seconds.

The idea

After every failure the pause before a retry grows, usually twofold but not above a cap, and is taken not whole but at random: full jitter picks it uniformly from zero to the current limit. The growth of the pauses lowers the overall pressure: the longer the server does not answer, the less often it is knocked on. The randomness spreads the clients out in time: even if all the failures happened in one instant, the retries scatter over a growing window, and the server sees not waves but an even stream.

Growth and randomness are needed together, and the scene shows why. Growth alone, without randomness, keeps the column: two thousand clients refused in one tick all wait exactly two seconds, then exactly four. Randomness alone, without growth, a pause of say zero to a second, spreads everyone over ten ticks, two hundred clients per tick, while the server handles fifty: the overload is simply smeared. A growing window, though, sooner or later becomes wider than needed: with N clients and a server of C requests per tick, a window of N/C ticks is enough, and full jitter reaches such a window after log₂(N/C) failures. In the model N/C = 2000/50 = 40 ticks: a window of 64 ticks opens after the seventh failure, and from then on fewer requests arrive per tick on average than the server can serve.

Four pause rules

Let the limit after the k-th failure be g = min(cap, base·2^k−1): an initial pause base, doubling, a cap cap. Four ways of choosing the pause are common.

• No jitter: the pause is exactly g. Clients that failed together come back together.
• Full jitter: the pause is uniform from 0 (in the model, from one tick) to g. The widest spread.
• Equal jitter: half of g is guaranteed, the other half random, from g/2 to g. Nobody retries too early.
• Decorrelated jitter: the pause is random from base to three times the previous pause, but not above the cap. The window grows not with the attempt number but with what came up last time.

A hundred clients whose request failed at the same instant, a dot for each and a row for each failure:

Without jitter all hundred dots in each row merge into one. Full jitter scatters them over the whole window, equal jitter over its right half, decorrelated wider and more unevenly: each client has its own history. On the storm model the three rules with jitter are close: full serves half the clients by 14.9 s and all by 29.6 s with 9.2 requests per client, equal by 16.7 and 23.1 s with 8.7, decorrelated by 12.2 and 26.8 s with 12.2. Marc Brooker compared them in 2015 on another model, clients competing to update the same database row, and there equal jitter lagged noticeably in time while full and decorrelated were close. The conclusion is the same on any model: the main thing is that there is randomness, and which of the three is secondary.

Why a marching column ruins the server

The server in the model serves as many per tick as it manages and refuses the rest. While a refusal is free, the column only wastes time: each wave lets fifty clients through, and the others wait for the next. But a refusal is not free. The server has to accept the connection, parse the request, perhaps check authorisation, and only then answer “busy”. If a refusal costs a tenth of an answer, two thousand refusals are the work of two hundred answers, and the server can do only fifty. The whole wave goes on refusals, no client gets an answer, and they all come back in the next wave, just the same. The server is healthy, the load is manageable on average, and yet the system does not get out of the overload by itself.

Such states have been named metastable failures: Nathan Bronson and co-authors described in 2021 how a system knocked out by a brief fault stays overloaded after the cause is gone, because a feedback loop holds it there, here the retries. The only way out is to break the loop: drop the queues, refuse faster than it serves, or make the clients spread out in time by themselves. The last is what jitter does.

How much to retry, and where

The pause is half the job. The other half is how many times to retry. Google's book on site reliability advises always retrying with a randomised exponential pause, limiting the number of retries per request, and keeping an overall retry budget per process, for example no more than 60 retries a minute. And above all, not retrying at every layer. If a service retries a call four times, its caller four times too, and a layer above that as well, the database under them gets 4³ = 64 requests from one user action, just when it is struggling anyway. Computing this avalanche over a graph of services is the second problem.

Only what is safe to repeat can be retried. A read can be retried. A request to “charge the money” cannot, if it is unknown whether the first one arrived: the server may have charged and failed to answer. Such requests carry an idempotency key, a number by which the server recognises a repeat and does not carry it out a second time.

Code

The listing is the storm model of the first scene: thousands of clients, a server with a work budget per tick, six retry rules and two kinds of refusal, free and costing a tenth of an answer. The clients are sorted into buckets by the tick in which they will knock, as in the first problem, and the random number generator is shared by Python, Go and the scene, so the numbers agree.

What it costs

The rule itself is a few arithmetic operations and one random number per failure: O(1) time and O(1) memory per client, plus the previous pause for decorrelated jitter. It is paid for with latency: with growing pauses a client learns that the server is back not at once but, on average, after half the current window. In the model this shows in the median: “at once” serves half the clients by 12.0 s, full jitter by 14.9 s. Three seconds is the price of not sending hundreds of thousands of extra requests and not ending up in an overload with no way out.

Where it is used

Ethernet. In the old Ethernet all stations shared one cable, and if two started transmitting at once, the frames collided. After the k-th collision a station waited a random number of slots from 0 to 2^{min(k, 10)} − 1, and after sixteen attempts it dropped the frame. This is exponential backoff with full jitter, only in slots of the cable. The trick itself, a random pause whose mean doubles after every collision, was described by Robert Metcalfe and David Boggs in their 1976 paper on Ethernet and named binary exponential backoff; the exact numbers, up to 2¹⁰ slots and at most sixteen attempts, were fixed later by the standard.

TCP. If an acknowledgement does not arrive, the retransmission timer doubles after every loss. There is no randomness here, but there is less need for it: connections do not lose packets at the same instant.

Client libraries. gRPC, when retrying a connection, starts with a one-second pause, multiplies it by 1.6 up to a cap of 120 seconds and adds a random spread of ±20 %. The client libraries of cloud services can retry requests with an exponential pause and jitter; after Brooker's article this became the usual choice.

History

A random pause after a collision appeared in the radio networks of the early 1970s, where stations shared one channel. The Ethernet of 1976 added growth to it: a station does not know how many rivals it has, and doubling the window after every collision adapts the pause to their number. For servers and their clients the same thing came up later, when synchronised retries became a common cause of outages. Marc Brooker's 2015 article “Exponential Backoff And Jitter”, with the formulas for full, equal and decorrelated jitter, became the standard reference for it; its main conclusion is “The solution isn't to remove backoff. It's to add jitter.”

Problems

In the first problem you model a storm exactly with a given random number generator, and so that the long tests, where not everyone waits for an answer, do not drag a scan of all clients through every tick. In the second you count how many requests each service gets if retries are set up at every layer and something at the bottom is broken.