Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
Exponential Backoff with Full Jitter
When a customer’s API throws 503s, everyone retrying on the same doubling schedule stampedes it in sync. Full jitter spreads the retries randomly across the window so the herd disperses. Compute the delay schedule. (Random draws are supplied, so it’s deterministic.) Solve it in Python or TypeScript, with hidden tests.
The problem
Implement backoff_jitter(base, cap, attempts, rand). For attempt i (0-indexed), the exponential ceiling is min(cap, base * 2^i). With full jitter, the actual delay is a uniform random value in [0, ceiling]: here that random fraction is supplied as rand[i] in [0, 1], so the delay is rand[i] * ceiling. Return the list of attempts delays, each rounded to 4 decimals.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or Reveal solution is one click away.
Implement backoff_jitter(base, cap, attempts, rand): for each attempt compute the clamped exponential ceiling, multiply by the supplied random fraction, round to 4 decimals, and collect the delays.
Examples and constraints 4 examples
base = 1.0, cap = 10.0, attempts = 5, rand = [1.0, 0.5, 1.0, 0.5, 0.0][1.0, 1.0, 4.0, 4.0, 0.0]base = 10.0, cap = 3.0, attempts = 3, rand = [1.0, 0.5, 0.25][3.0, 1.5, 0.75]base = 0.1, cap = 5.0, attempts = 3, rand = [0.7, 0.7, 0.7][0.07, 0.14, 0.28]base = 1.0, cap = 10.0, attempts = 0, rand = [][]- Ceiling for attempt
iismin(cap, base * 2^i)— exponential growth, clamped atcap. - Full jitter: delay =
rand[i] * ceiling(a fraction of the ceiling, not the ceiling itself). - Round each delay to 4 decimal places.
randhas at leastattemptsentries.
Hints 3 ideas
- Ceiling:
min(cap, base * (2 ** i))foriin0 … attempts-1. - Full jitter multiplies that ceiling by
rand[i](in [0,1]) — so a retry lands anywhere in the window, not on a synchronized tick. - Round to 4 decimals so floating-point noise doesn’t leak into the result.
Approach, complexity & discussion — open after you solve
Start from brute force
The obvious first draft computes the full exponential, multiplies by the random fraction, and clamps last: min(cap, rand[i] * base * 2**i). It even passes the first example, because the only attempt past the cap there has rand = 0.0. It costs O(attempts) time and O(attempts) space for the list, the same as the right answer, so the problem is not speed: it is wrong. Once base * 2**i passes cap, every draw above cap / (base * 2**i) is clamped to exactly cap. At attempt 6 with base = 1 and cap = 10 that is any draw above 10/64, about 84% of clients, all landing on the same instant again.
The approach
The key insight is the order of operations: clamp the window first, then pick a point inside it. For attempt i the window is [0, ceiling] with ceiling = min(cap, base * 2**i), and full jitter draws the delay from that whole window, so the invariant is 0 ≤ delay ≤ ceiling ≤ cap on every attempt. The exponent spreads one client's retries out over time; the jitter spreads different clients out within each window, so two callers that failed at the same moment are unlikely to retry at the same moment.
The reference solution is one loop. For each i in range(attempts) it computes ceiling = min(cap, base * (2 ** i)), scales it with delay = rand[i] * ceiling, and appends round(delay, 4) to delays. Passing rand in is what makes it testable; production code would call random.uniform(0, ceiling) on that line. The rounding matters because 0.7 * 0.1 is 0.06999999999999999 in binary floating point, and the tests compare exact values.
[0, ceiling], and the marker is where rand[i] puts the delay inside it. The ceilings double (1, 2, 4, 8) until the fifth would be 16, which the cap clamps to 10 (dashed). The algorithm keeps no state between attempts: each window depends only on i, base and cap.Walk through an example
Trace backoff_jitter(1.0, 10.0, 5, [1.0, 0.5, 1.0, 0.5, 0.0]): the ceiling doubles until the cap stops it at attempt 4, and each delay is that ceiling scaled by rand[i].
| step | base * 2**i | ceiling | rand[i] | delay | delays |
|---|---|---|---|---|---|
| i = 0 | 1.0 | 1.0 | 1.0 | 1.0 | [1.0] |
| i = 1 | 2.0 | 2.0 | 0.5 | 1.0 | [1.0, 1.0] |
| i = 2 | 4.0 | 4.0 | 1.0 | 4.0 | [1.0, 1.0, 4.0] |
| i = 3 | 8.0 | 8.0 | 0.5 | 4.0 | [1.0, 1.0, 4.0, 4.0] |
| i = 4 | 16.0 | 10.0 (capped) | 0.0 | 0.0 | [1.0, 1.0, 4.0, 4.0, 0.0] |
Complexity
Optimal: O(attempts) time, because each attempt is a fixed handful of arithmetic operations, and O(attempts) space for the returned list (O(1) beyond it). Brute force (clamp after jitter) has the same O(attempts) time and space; its flaw is the delays it produces, not what it costs to produce them.
Edge cases to test
attempts = 0→[]. The loop never runs andrandmay be empty, so never readrand[0]up front.capbelowbase:base = 10.0, cap = 3.0, rand = [1.0, 0.5, 0.25]→[3.0, 1.5, 0.75]. Every ceiling is3.0from the first attempt.rand[i] = 0.0→ a delay of0.0. Full jitter allows an immediate retry; do not add a floor the spec does not ask for.- Float noise:
base = 0.1, cap = 5.0, rand = [0.7, 0.7, 0.7]gives raw products such as0.06999999999999999; after rounding the answer is[0.07, 0.14, 0.28]. - A huge attempt count: in Python
1.0 * 2**1024raisesOverflowError(the integer is too large to convert to a float), while in JavaScript2 ** 1024isInfinityandMath.minclamps it tocap. Production code stops doubling once the ceiling reachescap.
Common mistakes
- Exponential growth with no cap — delays explode into minutes or hours.
- No jitter — every client retries on the same doubling schedule and stampedes the recovering service in lockstep (a thundering herd).
- Jittering the wrong range:
rand[i] * basenever grows, andceiling + rand[i]leaves every client on the same doubling schedule, offset by at most one time unit. - Resetting the attempt counter before a call has actually succeeded, so a flapping dependency is retried at the shortest delay forever.
Follow-ups an interviewer asks next
- How do equal jitter and decorrelated jitter differ from full jitter?
- Equal jitter keeps half the window fixed:
delay = ceiling / 2 + rand * ceiling / 2, so a client always waits at least half the ceiling. Decorrelated jitter drops the attempt number and grows from the previous delay:delay = min(cap, uniform(base, previous * 3)). Full jitter has the widest spread; equal jitter gives some of that spread up in exchange for a guaranteed minimum wait. - The server sends a Retry-After header. Now what?
- Treat it as a floor: wait at least that long, and keep jitter on top (for example
retry_after + rand * ceiling) so every client told “30 seconds” does not return on the same tick. If the requested wait is longer than the operation’s overall deadline, fail fast instead of sleeping through it. - How do you stop retries from making an outage worse?
- Bound them three ways: a maximum attempt count, an overall deadline for the operation, and a retry budget shared by the whole client (retries may be at most a fixed fraction of recent requests). Retry only failures that can succeed later, such as timeouts, 429 and 503, and only operations that are safe to repeat or carry an idempotency key.
- How would you test this with real randomness?
- Inject the random source, as this signature does with
rand, or seed it. Then assert properties instead of exact values: every delay is between 0 and its ceiling, ceilings double until they reachcap, and over many draws the mean delay approachesceiling / 2, which is what a uniform draw on[0, ceiling]predicts.
Where this shows up
Exponential backoff with jitter is the standard retry strategy for any flaky dependency — APIs, databases, queues. The jitter is the crucial part: when a service returns 503s, un-jittered retries all fire together and re-stampede it in sync, so spreading them randomly across the window is what actually lets it recover. The AWS Architecture Blog post “Exponential Backoff And Jitter” compares this full-jitter formula with equal and decorrelated jitter in a simulation of clients contending for one resource.
One rule matters as much as the formula: retry at one layer of a call chain, not at every layer. If a frontend, a service and its database client each make up to 3 attempts, one failing request at the bottom can be tried 3 × 3 × 3 = 27 times, and jitter does not undo that multiplication. The usual design is to retry close to the failure (the client that talks to the flaky dependency), give the layers above a deadline instead of their own retry loop, and propagate that deadline downward so an inner retry never sleeps past the point where the outer caller has already given up.
Check yourself
Predict backoff_jitter(2.0, 20.0, 5, [0.5, 0.5, 0.5, 0.5, 0.5]).
[1.0, 2.0, 4.0, 8.0, 10.0]. The ceilings are 2, 4, 8, 16 and then 32 clamped to 20, and a draw of 0.5 lands in the middle of each window.
With base = 1.0, cap = 10.0 and rand = [0, 0, 0, 0, 0.5, 0.5], compare the reference with the clamp-last draft min(cap, rand[i] * base * 2**i).
The reference gives [0.0, 0.0, 0.0, 0.0, 5.0, 5.0]; the draft gives [0.0, 0.0, 0.0, 0.0, 8.0, 10.0]. At attempt 4 the draft scales the unclamped 16, and at attempt 5 the product 16 is cut to exactly 10, the shared instant every client with a draw above 10/32 also lands on.
At attempt i = 3 with base = 1 and cap = 10, what is the average delay under full jitter, and under equal jitter?
The ceiling is 8. Full jitter is uniform on [0, 8], so it averages 4.0 seconds. Equal jitter waits 4 + rand · 4, uniform on [4, 8], averaging 6.0 seconds: a guaranteed minimum wait bought with a longer average and half the spread.
With base = 0.1, cap = 30 and 12 attempts, at which attempt does the ceiling stop growing, and what is the expected total wait?
At i = 9: attempt 8 has a ceiling of 25.6 and attempt 9 would be 51.2, clamped to 30. The twelve ceilings sum to 141.1 seconds, and each uniform delay averages half its ceiling, so the expected total wait is about 70.55 seconds. Totals like this are what an overall deadline has to be checked against.
Reference solution
Reference solution — Python
def backoff_jitter(base, cap, attempts, rand):
delays = []
for i in range(attempts):
ceiling = min(cap, base * (2 ** i)) # exponential, clamped at cap
delay = rand[i] * ceiling # full jitter: uniform [0, ceiling]
delays.append(round(delay, 4))
return delays
print(backoff_jitter(1.0, 10.0, 5, [1.0, 0.5, 1.0, 0.5, 0.0])) # -> [1.0, 1.0, 4.0, 4.0, 0.0]Reference solution — TypeScript
function backoffJitter(base: number, cap: number, attempts: number, rand: number[]): number[] {
const delays: number[] = [];
for (let i = 0; i < attempts; i++) {
const ceiling = Math.min(cap, base * 2 ** i); // exponential, clamped
const delay = rand[i] * ceiling; // full jitter
delays.push(Math.round(delay * 1e4) / 1e4);
}
return delays;
}
console.log(JSON.stringify(backoffJitter(1.0, 10.0, 5, [1.0, 0.5, 1.0, 0.5, 0.0]))); // -> [1,1,4,4,0]Questions about Exponential Backoff with Full Jitter
What is full jitter in exponential backoff?
Full jitter means the retry delay is a uniformly random value between zero and the current exponential ceiling, instead of the ceiling itself. The ceiling for attempt i is the smaller of cap and base times 2 to the power i, so the window still doubles on every failure and stops growing at the cap. Picking a random point anywhere in that window means clients that failed at the same moment spread out across the whole window when they retry, rather than firing again on the same tick. In this challenge the random fraction is passed in as rand[i], so the delay is rand[i] times the ceiling and the output is deterministic.
Why is jitter needed if the delays already grow exponentially?
Exponential growth spaces one client’s retries out over time, but it does nothing to separate clients from each other. If a thousand clients fail at the same moment, plain exponential backoff has every one of them retry at exactly 1 second, then 2, then 4, so the recovering service receives the same spike again and again. That synchronized pattern is called a thundering herd. Adding a random component breaks the lockstep: each client lands at a different point within the window, so the load arrives spread out and the service has room to recover between requests.
Should the cap be applied before or after the jitter?
Before. Compute the ceiling as the smaller of cap and base times 2 to the power i, then multiply by the random fraction. If you multiply first and clamp afterwards, every random draw that would have exceeded the cap is pushed to exactly the cap. With base 1 and cap 10, the uncapped value at attempt 6 is 64, so any draw above 10 divided by 64 lands on exactly 10 seconds, which is about 84 percent of clients. The herd you just spread out reassembles at the cap, which is the outcome jitter exists to prevent.
Is a delay of zero a bug when using full jitter?
No. A uniform draw over the window from zero to the ceiling can land at or near zero, and the formula returns 0.0 whenever the random fraction is 0.0, as the first example shows on its last attempt. An occasional immediate retry is harmless because the other clients are spread across the rest of the window. If you need a guaranteed minimum wait, that is a different scheme, usually called equal jitter, which keeps half of the ceiling fixed and randomizes only the other half.
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Challenges
- Retry with Exponential BackoffTools time out and APIs rate-limit — a production agent retries without hammering. Exponential backoff waits longer after each failure (1s, 2s, 4s, 8s…) up to a cap. Compute the delay schedule: delay[i] = min(cap, base·2ⁱ). Solve it in Python or TypeScript.Read →
- Verify a Webhook SignatureEvery real integration sends signed webhooks — and every FDE has to verify them. Recompute the signature over the payload, compare in constant time, and reject stale events to stop replay attacks. Solve it in Python or TypeScript, with hidden tests.Read →
- Idempotency Key HandlerNetworks retry. A webhook fires twice; a payment is re-sent after a timeout. Without idempotency you double-charge or double-write. The fix: dedupe by a client-supplied key and always return the first result. Solve it in Python or TypeScript, with hidden tests.Read →
- CSV → Schema MapperEvery customer hands you a messy export. Before it flows into your system, each row must be coerced to a schema — strings to ints, "true" to booleans — and the rows that don’t fit quarantined, not silently dropped. Solve it in Python or TypeScript, with hidden tests.Read →
- Data Reconciliation DiffThe customer swears the migration worked. You reconcile: compare source records against what landed in the target, keyed by id, and report exactly what was added, removed, or changed. Solve it in Python or TypeScript, with hidden tests.Read →
- PII RedactorBefore customer data touches a log line — or a third-party LLM — the personal bits have to go. Mask emails, SSNs, credit cards, and phone numbers with pattern matching, leaving the rest readable. Solve it in Python or TypeScript, with hidden tests.Read →