Retry with Backoff
Track: Load and timing. 6 stages. Languages: Go, Python, JavaScript, Rust.
A failed call often works if you just try it again, a little later. Trying again right away can make a struggling service even worse. This challenge asks you to build that retry logic well.
You implement two things, using your language's own names for them:
- A function that tells you how long to wait before the next try. The wait should grow after each failure, up to a limit, and it should be a random amount within that limit every single time, never the same number twice in a row.
- A function that keeps calling the real piece of work until it succeeds or you run out of tries, waiting between tries using the first function.
Your code will be called from many goroutines, threads, or calls that overlap, so it must stay correct when several callers are retrying at the same time. Standard library only.
The tester runs your code for real and measures how long your waits actually took. It does not use a fake or sped up clock, so you are judged against what really happened during your run, not against an idealized number.
There is more than one way to build this well. One way that works: start with a small wait, and roughly double it every time you fail again, but never let it go past a fixed upper limit. Then, instead of always waiting that exact amount, pick a random amount somewhere between zero and that limit, a different one every time. The random part matters because of what happens when many callers fail at the same moment: if they all wait the exact same length of time, they will all retry at the exact same moment too, hitting the struggling service all over again, together. Picking a random amount scatters their retries out, so they do not all land at once. For help with the ideas, read the notes. New to code that many callers run at the same time? Read Many callers at once first.
Where it is used
- The AWS SDKs, in their standard retry mode, retry failed calls with exponential backoff and "full jitter": a random wait between zero and a limit that doubles each time. That is the design described above.
- gRPC clients wait longer and longer before they reconnect to a server (by default from 1 second up to about 120 seconds) and add some randomness to the waits after the first one.
Without the randomness, a thousand clients that failed at the same moment all retry at the same moment, and a service that was just recovering falls over again.
Stages
rt1: hello, the first try succeeds (very easy)
Call the retry function with a piece of work that succeeds right away. It should be called exactly once. Example: New(8, 40, 5), then Do(an operation that succeeds immediately) -> ok=true, attempts=1.
The tester will verify: the first try succeeds, so Do reports success after exactly 1 attempt.
rt2: gives up after the limit (easy)
Call the retry function with a piece of work that always fails. It should be tried up to the limit you were given, 5 times here, and then report failure. Trying one time too many, or giving up one try too early, both fail this stage. Example: New(8, 40, 5), then Do(an operation that always fails) -> ok=false, attempts=5.
The tester will verify: an always-failing piece of work is tried exactly 5 times, then Do reports failure.
rt3: the wait grows, but only up to a limit (medium)
With a starting wait of 8 ms and a cap of 40 ms, the longest allowed wait before each attempt looks like this: about 8 ms, then about 16 ms, then about 32 ms, then about 40 ms, and it stays at about 40 ms after that, because doubling again would go past the cap. The tester asks your wait function for 200 waits at each attempt from 0 to 5 and checks that none of them ever goes over its attempt's own limit. It also checks that the longest of the 200 waits at attempt 5 reaches at least about 20 ms, half of the cap, to make sure the wait really does grow each time instead of getting stuck low.
The tester will verify: no sampled wait goes over its attempt's limit (8, 16, 32, 40, 40, 40 ms for attempts 0 through 5), and the longest wait sampled at attempt 5 is at least about 20 ms.
rt4: each wait is spread out, not stuck at one value (medium)
Ask your wait function for the same attempt 200 times in a row, at the attempt where the cap is about 40 ms. The 200 answers should not all land near the same number. The gap between the smallest and the largest of those 200 waits should be at least about 12 ms, and the waits should typically scatter by at least about 4 ms away from their average, not huddle close to it. A wait function that always returns the full 40 ms fails this stage, because every answer is identical.
The tester will verify: across 200 waits at the capped attempt, the smallest-to-largest gap is at least about 12 ms, and the waits scatter by at least about 4 ms from their average.
rt5: many callers retrying at once don't line up (hard)
64 callers all retry the same failing piece of work at the same time. For this stage the tester uses a starting wait of 100 ms, so each first wait should be a fresh random amount between 0 and 100 ms. Example: random waits like 7, 31, 52, 88 ms spread the retries out. Waits like 50, 50, 50, 50 ms make every caller retry at the same moment, and that is what this stage catches. Timing on a real machine is a little noisy, so the tester repeats the check up to 5 times and goes by the majority.
The tester will verify: after sorting the 64 first waits, the middle half (the 17th to the 48th shortest) spreads over at least 15 ms in most runs.
rt6: wait calculation speed (L2, hard)
Keep your wait function fast, and keep every answer correct. Note that rt1 to rt5 are timed too, so a wait function that is slow on its own can also cost you those earlier stages, not just this one. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.
The tester will verify: your wait function takes at most 1.5 times as long as our solution in the same language, and every answer stays correct. How many memory allocations you use is also shown, but it never decides a pass or a fail.
Rules
- Standard library only. No third-party packages.
- Every wait must be genuinely random within its bounds, picked fresh on every single call, never reused or precomputed.
- Your code will be called from many callers at once. Keep it safe for that, including whatever you use to produce random numbers.