Cost, latency and routing · Latency and retries

Retry-with-backoff policy

Implement the pure function that turns a sequence of API replies into the exponential-backoff wait schedule, retrying only what a retry can fix.

codemediumExercise · 3 min · 29 of 77

On this page

A client that retries the wrong things, or retries the right things at a fixed interval, turns a vendor's bad minute into your bad hour. The policy is a pure function, and this exercise writes it.

The situation

During a vendor incident a team's agent client retried every failure five times at a fixed one-second interval, including a batch of 400s caused by a tool schema that had failed validation since the morning deploy. Two hundred workers retried in lockstep, the 529s kept coming, and the 400s were retried 1,000 times before anyone read a response body. The incident review asked for one function that decides the wait schedule, testable without a network.

The contract: given the reply each attempt will receive, return the waits in milliseconds before each retry. Retry 408, 429 and any 5xx; never retry any other 4xx; stop on a 2xx. The k-th retry waits min(cap_ms, base_ms × 2^(k−1)), raised to the server's retry-after when one was sent. At most max_attempts attempts in total. Jitter is applied by the caller, on top of any retry-after, which is a floor — the function returns the deterministic wait, which is what makes it testable, as retries, timeouts and rate limits argues.

The question

Implement the schedule so that the four examples below hold, with the 400 branch producing no retry and the attempt cap ending the schedule without a trailing wait.

def solve(statuses, base_ms, cap_ms, max_attempts):
    """statuses: the reply each attempt will receive, in order — an int status
    code, or a (status, retry_after_ms) tuple when the server sent Retry-After.
    Returns the list of waits in ms before each retry. Retry 408, 429 and 5xx;
    never retry any other 4xx; stop on 2xx. The k-th retry waits
    min(cap_ms, base_ms * 2 ** (k - 1)), raised to retry_after_ms when the
    server sent one. At most max_attempts attempts in total. Jitter is the
    caller's job, so the schedule is deterministic."""

solve([500, 500, 200], 100, 10000, 5)             -> [100, 200]
solve([429, 429, 429, 429, 200], 100, 400, 5)     -> [100, 200, 400, 400]
solve([400, 200], 100, 10000, 5)                  -> []
solve([(429, 1500), 200], 100, 10000, 3)          -> [1500]

A strong answer · Rubric · Where answers go wrong · Solution

Write your answer first, then open

A strong answer

One for over range(1, max_attempts + 1). Each iteration reads the reply for that attempt — unpacking a tuple into a status and a retry-after — and classifies it with a small predicate: 408, 429 or 500 ≤ status ≤ 599 is retryable; anything else, success or client error alike, ends the loop. A retryable reply on the last permitted attempt also ends the loop, because there is no attempt left to wait for: a schedule never has more entries than max_attempts − 1. Otherwise the wait is min(cap_ms, base_ms × 2 ** (attempt − 1)), raised to retry_after_ms where the server sent one — the header is the server's own estimate and wins over the cap, since retrying earlier only earns another 429 — and appended.

The function never sleeps, never calls random, and never raises on an unexpected status; a status it does not recognise is treated as final, which is the safe default for a client whose retry can cost money. Running out of scripted replies before the attempts are exhausted ends the schedule too, so a short statuses list is a complete script, not an error. Twelve lines, and a test for every row of the status table: a 5xx run, a 429 run against the cap, a 400 that stops at once, an exhausted cap, a header above the backoff, a header below it, a single permitted attempt, and a cap below the base.

Rubric

retries 408, 429 and 5xx only; a 400 or 401 produces an empty schedule
doubles from the base and caps, with the cap applied before the header is considered
honours a retry-after above the computed wait and ignores one below it
ends the schedule when attempts run out, with no wait after the final attempt
stays pure: no sleeping, no randomness, no state outside the function

Where answers go wrong

while True with a break on success: passes the first example and never terminates on a script of endless 503s, which is the production incident restated. The cap on attempts is the exit, and it has to be the loop bound.

Applying jitter inside the function with random.uniform: the schedule becomes untestable and the caller cannot tell a jittered wait from a bug. The contract puts jitter on the caller for that reason; the function returns the deterministic wait.

Retrying everything that is not a 200: the 400 example returns [100] instead of [], and a validation error that will fail identically five times is retried five times. The status table is the whole point of the exercise.

Solution

Python 3 · standard library33 lines · 12 of 12 tests passing

"""Retry-with-backoff policy — the wait schedule for one request, as a pure function."""

TRANSIENT = {408, 429}


def retryable(status):
    """Timeouts, rate limits and server errors retry; any other 4xx will fail the same way again."""
    return status in TRANSIENT or 500 <= status <= 599


def unpack(reply):
    """A scripted reply is a status code, or a (status, retry_after_ms) tuple."""
    if isinstance(reply, tuple):
        return reply[0], reply[1]
    return reply, None


def solve(statuses, base_ms, cap_ms, max_attempts):
    waits = []
    for attempt in range(1, max_attempts + 1):
        # Invariant: len(waits) == attempt - 1 — one wait for every retry already decided.
        if attempt > len(statuses):
            break                                   # the script ran out: nothing more happens
        status, retry_after = unpack(statuses[attempt - 1])
        if not retryable(status):
            break                                   # 2xx is done; a 400 would fail identically again
        if attempt == max_attempts:
            break                                   # the last permitted attempt failed; no wait follows
        wait = min(cap_ms, base_ms * 2 ** (attempt - 1))
        if retry_after is not None:
            wait = max(wait, retry_after)           # the server's estimate wins over the cap
        waits.append(wait)
    return waits

The cases that ran

TESTS = [
    (([500, 500, 200], 100, 10000, 5), [100, 200]),
    (([429, 429, 429, 429, 200], 100, 400, 5), [100, 200, 400, 400]),
    (([400, 200], 100, 10000, 5), []),
    (([(429, 1500), 200], 100, 10000, 3), [1500]),
    (([503, 503, 503], 100, 10000, 3), [100, 200]),      # cap on attempts: no wait after the last one
    (([200], 100, 10000, 3), []),
    (([500], 100, 10000, 1), []),                        # one attempt permitted: nothing to schedule
    (([502, 200], 100, 50, 4), [50]),                    # cap below base
    (([(429, 30), 200], 100, 10000, 3), [100]),          # retry-after below the backoff is ignored
    (([401, 200], 100, 10000, 3), []),                   # not every 4xx is a 400, none retry
    (([408, 529, 200], 1000, 30000, 5), [1000, 2000]),
    (([503, 503], 100, 10000, 5), [100, 200]),           # script shorter than the attempt cap
]