Implement the policy that retries only what is safe for the operation, jitters its waits from injected draws, and stops at the budget a run can afford.
codemediumExercise · 4 min · 46 of 75
On this page
A retry is a second copy of a request, and whether that is safe depends on what the first copy may already have done. The deterministic schedule over a status table is llm-dev's retry-with-backoff policy; this one adds the operation, the jitter and a budget, and it is the last mechanism on the path in why we write these five by hand. Its budget is time for one call; the fleet-wide retry budget, a share of all calls in a minute, sits a level above it, as rate limits, retries and backoff sets out.
The 40-person wholesaler this module uses in place of the agency supplies 900 cafés. Its connector makes three kinds of call to the accounting API: reads such as get_invoice; send_invoice, which accepts an idempotency key; and record_payment, an older endpoint that does not. Every call ran with one setting: retry on failure, three times, 1 second apart.
In March a record_payment for a $4,200 invoice timed out after the payment had been recorded. The retry recorded it again, and the café showed $4,200 in credit until month end. Untangling it took the bookkeeper 3 hours and you 1, at an assumed $30 and $100 an hour: $190. The same setting retried a 400 caused by a malformed date three times, and on Friday it sent 429s back into an empty bucket in lockstep.
The run that makes these calls stops after 5 minutes, so each call may spend at most 120 seconds waiting between attempts.
Implement the policy so the examples below hold, with policy = {"base": 2, "cap": 60, "budget": 120}. The random draws are an argument, so the schedule is a pure function a test can fix.
def solve(outcomes, op, policy, draws):
"""outcomes: what each attempt returns, in order: "ok", "timeout", an HTTP status
int, or (429, retry_after_s). op: "read", "keyed_write", or "write" (a write with
no idempotency key). policy: {"base": s, "cap": s, "budget": s}, integer seconds.
draws: the caller's random numbers as whole percentages 0..99, one per retry.
Retry k waits c // 2 + (c - c // 2) * draws[k - 1] // 100, where
c = min(cap, base * 2 ** (k - 1)); that wait, not c, is raised to retry_after_s
when the server sent it.
Returns (waits, verdict). waits: seconds before each retry, in order. verdict:
"ok"; "failed" (a 4xx other than 429); "unknown" (a timeout or 5xx on a "write",
never resent); or "gave_up" (the next wait would take the total past the budget,
or the outcomes ran out while the call was still failing)."""
Classify before waiting. A 429 was refused before the server did anything, so it is safe to resend for any call (example 3). A timeout or a 5xx may have been applied, so it is safe to resend only a read or a keyed write; on a write the policy returns unknown and stops (example 2). That branch is the $4,200: the caller hands an unknown to a person, or to a get_invoice that checks whether the payment landed, never to a blind resend. Any other 4xx fails at once, since the malformed date fails the same way every time.
Retry k starts from the ceiling c = min(cap, base × 2^(k−1)) and splits it: a fixed half, c // 2, plus a random half scaled by the caller's draw. The fixed half means every retry spends budget, so the budget bounds the attempts. With every draw at 0 the waits are 1, 2, 4, 8, 16, 30, 30, a total of 91; the next 30 would pass 120, so seven retries at most. The random half spreads calls that failed in the same second instead of resending them together. A Retry-After raises the wait, because the server knows when capacity returns, but never past the budget: a 429 asking for 200 seconds gives up now rather than holding a run that dies at 5 minutes.
The function never sleeps and never calls random, so a failing schedule reproduces exactly. The evidence that would change the budget is calls that routinely succeed only on the sixth attempt: that says a rate limiter is missing upstream, not that 120 seconds is short.
"Retry every failure three times, 1 second apart." That is the setting that recorded $4,200 twice, retried a 400 three times, and sent 70 calls back into an empty bucket in the same second.
"Full jitter: a random wait between 0 and the ceiling, from random.uniform." The schedule can no longer be tested or reproduced, and draws near 0 spend no budget, so the budget stops bounding the attempts.
"A timeout is transient, so retry it." Transient for the network, not for the ledger. The timeout says nothing about whether the payment was recorded; only a key or a read can.
Python 3 · standard library53 lines · 11 of 11 tests passing
"""A retry policy — which failures earn another attempt, jittered backoff, and a time budget per call."""
SAFE_ANY_OP = {429} # refused before the server did anything: safe to resend any call
SAFE_IF_IDEMPOTENT = {"timeout"} # plus every 5xx: the first attempt may have landed
def classify(outcome, op):
"""One attempt's outcome -> "ok", "retry", "unknown" or "failed"."""
if outcome == "ok":
return "ok"
status = outcome[0] if isinstance(outcome, tuple) else outcome
if status in SAFE_ANY_OP:
return "retry"
if status in SAFE_IF_IDEMPOTENT or (isinstance(status, int) and 500 <= status <= 599):
# A read or a keyed write can be resent; a write with no key may have been applied,
# and resending it is how a payment is recorded twice.
return "retry" if op in ("read", "keyed_write") else "unknown"
return "failed" # any other 4xx fails the same way on every attempt
def solve(outcomes, op, policy, draws):
"""outcomes: what each attempt returns, in order: "ok", "timeout", an HTTP status
int, or (429, retry_after_s). op: "read", "keyed_write", or "write" (a write with
no idempotency key). policy: {"base": s, "cap": s, "budget": s}, integer seconds.
draws: the caller's random numbers as whole percentages 0..99, one per retry.
Retry k waits c // 2 + (c - c // 2) * draws[k - 1] // 100, where
c = min(cap, base * 2 ** (k - 1)); that wait, not c, is raised to retry_after_s
when the server sent it.
Returns (waits, verdict). waits: seconds before each retry, in order. verdict:
"ok"; "failed" (a 4xx other than 429); "unknown" (a timeout or 5xx on a "write",
never resent); or "gave_up" (the next wait would take the total past the budget,
or the outcomes ran out while the call was still failing)."""
waits, spent = [], 0
for k, outcome in enumerate(outcomes, 1):
verdict = classify(outcome, op)
if verdict != "retry":
return waits, verdict
if k == len(outcomes):
return waits, "gave_up" # no attempt left to wait for
c = min(policy["cap"], policy["base"] * 2 ** (k - 1))
# Equal jitter: the fixed half means every retry spends budget, so the budget bounds
# the attempts; the random half spreads callers that failed in the same second.
wait = c // 2 + (c - c // 2) * draws[k - 1] // 100
if isinstance(outcome, tuple):
wait = max(wait, outcome[1]) # the server's Retry-After wins over the backoff...
if spent + wait > policy["budget"]:
return waits, "gave_up" # ...but never over the budget
waits.append(wait)
spent += wait
return waits, "gave_up" # no outcomes at all: nothing was attempted
P = {"base": 2, "cap": 60, "budget": 120}
The cases that ran
TESTS = [
# the examples on the page
(([500, 500, "ok"], "keyed_write", P, [50, 50]), ([1, 3], "ok")),
((["timeout", "ok"], "write", P, [50]), ([], "unknown")),
(([(429, 30), "ok"], "write", P, [0]), ([30], "ok")),
(([503] * 10, "read", P, [99] * 9), ([1, 3, 7, 15, 31, 59], "gave_up")),
# a 400 or a 401 fails at once, for any op
(([400, "ok"], "read", P, [0]), ([], "failed")),
(([401], "keyed_write", P, []), ([], "failed")),
# the fixed half bounds the attempts: draws of 0 still spend the budget
(([500] * 10, "read", P, [0] * 9), ([1, 2, 4, 8, 16, 30, 30], "gave_up")),
# a Retry-After longer than the budget gives up now instead of holding the run
(([(429, 200), "ok"], "read", P, [0]), ([], "gave_up")),
# an unkeyed write survives a 429 but stops at the first timeout
(([429, "timeout", "ok"], "write", P, [0, 0]), ([1], "unknown")),
# the outcomes run out while still failing
(([500, 500], "read", P, [0, 0]), ([1], "gave_up")),
# a keyed write retries a timeout
((["timeout", 502, "ok"], "keyed_write", P, [99, 99]), ([1, 3], "ok")),
]
