Exponential backoff and jitter

Exponential backoff is the rule that a client waits longer after each successive failure, doubling a base delay: one second, then two, then four. It is the default in every HTTP retry library, and on the retryable failure classes — a 429 saying you exceeded your own allowance, a 529 saying the provider is out of capacity — it is the right shape of answer. Waiting longer after repeated rejections concedes capacity to whatever is short of it, and doing so geometrically means a client stops hammering quickly without giving up after one try.

What most implementations of it drop is the random draw that the mechanism was originally specified with. A delay computed purely from the attempt number is a deterministic function, which means every caller in a fleet that has failed the same number of times waits the identical interval and returns to the wire in the same instant. On a single-process script that costs nothing and is invisible. On four hundred workers it reinstates precisely the collision that backing off was invented to avoid, and the symptom is a fleet that keeps failing long after the provider has recovered.

The mechanism is worth taking one step at a time, because the conclusion is stronger than it first looks: a fixed schedule does not merely fail to break the synchronisation, it deepens it. A delay computed as a base multiplied by two to the power of the attempt number takes exactly one input, which is the attempt number. Workers rejected in the same second all carry the same attempt number. The same function applied to the same input returns the same value, so they sleep for the same interval, and the only thing separating them when they wake is whatever spread their clocks and timers happened to have — milliseconds, against a delay measured in seconds. They arrive together. The allowance admits a few and rejects the rest, and the rejected ones now share an attempt number with each other and with nobody else, which is a tighter grouping than the one they started in. Each round selects for the workers that are in step and hands them back to the wire still in step.

The randomness was in the original specification#

Backing off exponentially after a collision is older than the web by two decades and did not originally come without randomisation. ALOHAnet in the early 1970s and then Ethernet's CSMA/CD — carrier sense multiple access with collision detection — in 1976 faced the same structural problem: two stations transmit at once, both detect the collision at the same instant, and if both wait the same interval they collide again forever. The solution Metcalfe and Boggs specified was binary exponential backoff, and the operative word in the specification is not "exponential" — a station that has collided k times picks a random integer in the range 0 to 2^k − 1 and waits that many slot times. The exponent widens the range of choices; the random draw inside that range is what decorrelates the stations. Two colliding Ethernet stations pick from two slots on the first retry and have a 50% chance of separating immediately, from four slots on the second, and so on.

That 50% is small enough to check by hand, and checking it shows exactly where the randomness does its work. After one collision each station draws an integer from the range 0 to 1 — two choices each, so four equally likely pairs of choices between them. In two of those four the stations draw different numbers and separate. In the other two they draw the same number and collide again. Half the pairs separate, which is the 50%. After a second collision the range is 0 to 3: four choices each, sixteen pairs, and only the four pairs where both picked the same number collide, so three quarters of them separate. The exponent is not making a station wait more politely as it fails more often. It is enlarging the set of values the draw can return, and two independent draws from a larger set are less likely to agree.

What survived into HTTP client libraries is the exponent, frequently without the draw. wait_exponential(multiplier=1, max=8) and its equivalents compute a delay from the attempt number and nothing else. The randomisation can be added back in several ways, and they are not equivalent. Writing base = 1s and cap = 8s, with d the deterministic delay min(cap, base × 2^attempt), and taking a fleet of 400 workers against an allowance of 4,000 requests per minute — about 67 per second:

Every entry in the last two columns is one division, and doing that division once makes the table readable rather than something to memorise. Take the fleet size and divide it by the width of the window the delay is drawn from. That gives the average arrival rate, and it is legitimate because a uniform draw puts an equal share of the fleet into every equal slice of the window — that is what uniform means. Full jitter on the third attempt draws from zero to four seconds, so four hundred workers spread across four seconds arrive at about a hundred a second. Equal jitter draws from two to four seconds, a window half as wide, so the same four hundred arrive at about two hundred a second. Decorrelated jitter can reach out to eight seconds, and four hundred across eight seconds is about fifty.

The fixed row is the same division with a window nobody chose. Nothing in that schedule spreads the workers at all, so the only thing separating their arrivals is the residual difference in when each one started sleeping: clock skew between machines, timer granularity, the order in which the rejections came back. That comes to something like fifty milliseconds across a fleet, and four hundred requests inside fifty milliseconds is eight thousand a second. The fixed schedule is not eighty times worse than full jitter because it waits differently — the delay is four seconds either way. It is eighty times worse because the window its arrivals land in is eighty times narrower, and the schedule never picked that window. It inherited it from the hardware.

Full jitter is the one to reach for by default. AWS published a simulation of exactly this comparison in 2015 and found that drawing uniformly from zero to the full computed delay both completed the work in the fewest total attempts and produced the least contention, because it spreads callers across the entire window rather than across half of it. Equal jitter exists because engineers dislike the possibility of a near-zero wait, and it buys that comfort by halving the spread, which doubles the peak arrival rate for no benefit the simulation could find. Decorrelated jitter, where each delay is drawn relative to the previous one rather than to the attempt number, spreads the widest and is worth having when the contention is between your own workers rather than with other tenants.

Equal jitter deserves to be taken seriously as an instinct even though the simulation went against it, because the instinct is pointing at something real. A worker that draws a near-zero delay retries almost immediately, and retrying immediately is the behaviour this whole chapter argues against. What defuses the objection is that it is about one caller while the failure is about all of them. The provider never observes a delay; it observes an arrival rate. One worker arriving early is one worker, and under a uniform draw the share of the fleet landing in any slice of the window is the same as the share of the window that slice occupies — a tenth of a second out of four seconds is a fortieth of the fleet. Forbidding the first half of the window removes no arrivals at all. It relocates them into the second half, which is precisely why the peak rate doubles. The comfort is paid for by making the crowd denser.

Sizing the base delay against the fleet#

Jitter is necessary and, on a large fleet with a small base, not sufficient. Run the arithmetic for those 400 workers with full jitter and a one-second base: the first retry round spreads them uniformly across one second, giving an arrival rate of about 400 per second against a capacity of 67 per second. Still six times over. The second round spreads the survivors across two seconds, the third across four, and only by the fourth round — an eight-second window — does the arrival rate fall to roughly 50 per second and drop under the allowance. Jitter converts a burst into a series of decreasing plateaus and the fleet drains in four rounds instead of never, which is the whole of its contribution, and the fleet still overshoots the limit for the first three of them.

Each of those rounds is the division from the table, run again with a wider window. The allowance is quoted per minute while the collisions happen per second, so the first move is to put both on one clock: 4,000 requests a minute over the sixty seconds in a minute is about 67 a second. The first retry round then spreads four hundred workers across a one-second window, which is four hundred a second, and 67 goes into 400 about six times — the "six times over" in the sentence above. The second round draws from a two-second window and the rate halves to about two hundred. The third halves again to about a hundred. The fourth draws from eight seconds and reaches roughly fifty a second, which is the first round that fits under 67. The rate halves each time because the window doubles each time and the number of callers arriving into it does not. Workers that get through stop retrying, so the real rates are somewhat lower than these; the sequence is here to show that it is the width of the window doing the work.

The lever that fixes the overshoot is the relationship between the base delay and the fleet size. Four hundred workers sharing a 67-per-second allowance need their retries spread across at least six seconds to fit, so a base of one second is simply too small for that fleet, and a base of eight with full jitter puts the very first retry round inside the allowance. The general form is base ≥ concurrent_callers / allowance_per_second, and it is the reason a retry configuration copied from a tutorial written for a single-process script tends to be wrong by an order of magnitude in a fleet.

That formula is the condition for the first round, written out and rearranged. Full jitter spreads N callers uniformly across a window whose width is the base delay, so the arrival rate is N divided by the base. Requiring that rate to fit under an allowance of A per second is the statement that N divided by base is at most A. Multiply both sides by the base and divide both by A, and it becomes base ≥ N ÷ A, which is base ≥ concurrent_callers / allowance_per_second with the names filled in. Both of those steps are allowed without reversing the inequality because a delay and an allowance are positive quantities, and only multiplying by a negative one would flip it. Putting the fleet's own figures in: four hundred callers divided by 67 a second is just under six seconds, which is where the six-second requirement comes from, and eight is the next value anybody would actually type into a configuration file.

The two bounds, and the queue behind them#

A schedule with a growing delay and no ceiling reaches absurd numbers quickly: 2^10 seconds is seventeen minutes, and a worker asleep for seventeen minutes is a worker that has stopped consuming its queue while still holding a connection, a database transaction if someone was careless, and a slot in the pool. Capping the delay somewhere in the range of eight to sixty seconds keeps the spread wide enough to be useful and keeps the resource held per attempt bounded.

Seventeen minutes is a startling number to arrive at from a one-second base, and the reason it arrives is that the growth is in the exponent rather than in the delay. Doubling ten times multiplies by a bit over a thousand, so a one-second base becomes a bit over a thousand seconds, and a thousand seconds is about seventeen minutes. Ten failures is not an exotic condition during a provider incident. The schedule that produced this looked entirely reasonable at every step, which is the argument for a ceiling: the ceiling is not there to make the common case better, it is there because nothing in a doubling schedule stops on its own.

The attempt cap is the more consequential of the two, and the reason is what happens to the work that is not being done. Through a long rejection episode the queue keeps receiving items at its normal rate while the workers spend their time asleep. With five attempts and a cap of eight seconds, a worker gives up after about twenty-three seconds of waiting and the item goes to a dead-letter queue — the side channel a queue system keeps for messages it has stopped trying to deliver, so they can be inspected and replayed later — or to a delayed retry. With unbounded attempts the worker never gives up, queue depth grows monotonically, and the recovery, when it comes, has to serve both the live traffic and the entire backlog accumulated during the outage. That backlog then arrives as its own thundering herd — the standing term for a mass of clients released onto a resource at the same instant when it can serve only a few of them — which is how a service recovers from one incident by immediately causing a second.

The twenty-three seconds in that paragraph is the schedule added up. A one-second base doubles to two, then four, then eight, and the ceiling holds the fifth delay at eight rather than letting it reach sixteen, so the waiting is one plus two plus four plus eight plus eight. Under full jitter each of those is the top of a range rather than the delay itself, which makes twenty-three seconds the longest a worker can wait before giving up and puts the typical total at around half of it. Both readings are worth having, because they answer different questions: the upper bound is what sizes the resource a stuck worker is holding, and the typical figure is what the queue behind that worker actually experiences.

A useful third bound sits alongside them, expressed in wall-clock rather than in attempts. Each call carries a total retry deadline, and no attempt is started that cannot plausibly finish before it. Without that, an interactive request can spend forty seconds retrying on behalf of a user who closed the tab after four, and every second of that is a connection held for an answer nobody will read.

import random, time

def full_jitter_delays(base=8.0, cap=60.0, attempts=5, deadline_s=45.0):
    """Yield the delay before each retry, stopping at the deadline."""
    started = time.monotonic()
    for attempt in range(attempts):
        d = min(cap, base * (2 ** attempt))
        delay = random.uniform(0.0, d)          # full jitter
        elapsed = time.monotonic() - started
        if elapsed + delay > deadline_s:        # third bound
            return
        yield delay

def decorrelated_delays(base=1.0, cap=60.0, attempts=5):
    prev = base
    for _ in range(attempts):
        prev = min(cap, random.uniform(base, prev * 3))
        yield prev

Two details in that first function matter more than the formula. The sleep is drawn fresh on every attempt rather than once per call, because a single draw reused across attempts keeps a worker in the same relative position in every round and reconstructs the lockstep at a fixed offset. And the deadline check happens before the sleep rather than after it, so a call abandons the attempt it cannot afford instead of discovering the fact once the time is already spent.

Sustained demand above the allowance#

Spreading arrivals in time changes when load lands and not how much of it there is. If sustained demand genuinely exceeds the allowance — a batch job that wants 8,000 requests per minute against a 4,000 limit — then every schedule, jittered or not, is redistributing a deficit. The retries will fail, the queue will grow, and the correct interventions are concurrency limits at the source, batching, or a higher quota. A retry policy that looks like it is coping in this situation is usually converting a throughput shortfall into latency and then into timeouts, and the symptom will move without the cause changing.

The arithmetic in that case is a subtraction rather than a schedule. A job that wants 8,000 requests a minute against a 4,000 limit gets half of what it wants, so each minute ends with four thousand requests undone, and undone requests do not evaporate — they sit somewhere. Ten minutes of that is forty thousand items waiting, and no arrangement of delays reduces the figure by one, because a delay decides when a request is sent and not whether there is room for it when it arrives. Every schedule in this chapter is a policy for allocating a fixed throughput among competing callers. None of them is a source of throughput.

Jitter is also a fleet property rather than a request property, which means it does nothing measurable for a single-process job and everything for four hundred. That asymmetry is why the problem survives load testing: a test harness with eight concurrent callers produces eight-way collisions that clear in one round, and nothing in the results hints at the behaviour at four hundred. Seeing it before production does requires running the test at the concurrency production runs at, against a limit low enough to trip.

The same division explains why the small test looks clean. Eight callers retrying into a one-second window arrive at eight a second, which is a long way under 67, so every one of them gets through on the first round and the schedule is never asked to spread anything. The test is not a smaller version of the production failure. It is a system in a different regime, where arrivals fit inside the allowance and the only property being exercised is that a delay happens at all. Nothing about the shape of that result extrapolates, because the quantity that decides the outcome — fleet size divided by window width against the allowance — is not being varied at all.

The last thing to be honest about is that jitter costs predictability. A fixed schedule gives a call a deterministic worst case, whereas full jitter gives a distribution, and a p99 latency target computed on the assumption of fixed delays will be wrong. That is a fair trade when the alternative is a fleet that cannot recover, and it is a real change to the latency profile that belongs in the conversation about a service's objectives to its own callers rather than being discovered in it.

A retry schedule is therefore three numbers and a draw: a base sized to the fleet, a ceiling on the delay, a cap on attempts, and a uniform random sample taken fresh each time from zero to the computed delay. The draw is the part that distinguishes a fleet which recovers from one which reproduces its own burst indefinitely, and it is the part libraries most often leave to the caller.

All of this concerns a delay computed from an attempt counter, with no information about the thing being waited for. On a rate-limit rejection you frequently do not have to guess, because the response arrived carrying the provider's own statement of when capacity returns, and that number beats any schedule derived from an exponent.