Retry with exponential backoff and jitter

Why is jitter required for retries to converge?

What it is. Call again. Retry is the simplest case of recomputation: the "dependency graph" has one node, and it lives in the caller's stack frame. This is also why it is the only recovery available to a stateless caller (one that stores nothing between requests): its artifact costs nothing to keep.

Why it converges, and the exact condition

If each attempt fails with probability ε, independently, then n attempts all fail with probability εⁿ. With ε = 0.01 and three attempts: 10⁻⁶. Everything depends on the word independent.

• Against a deterministic fault (the same input always fails), the success probability is zero for every n. Retry is pure waste.
• Against an overloaded server, the failure is not only dependent on the previous attempt. It is caused by it: every retry adds load. The sign flips, and retry becomes harmful. This is the clearest example of the independence assumption being violated in a way that reverses the purpose of the mechanism. It is Wanjiru's first symptom.

Why the waiting time grows exponentially

The caller is searching for an unknown recovery time T and has no prior information about it. If you knew T, you would retry once, at time T. Not knowing it, you want a schedule of probes where the overshoot (time wasted after the service has recovered) is at most a constant factor of T, using only a logarithmic number of probes. Geometric growth gives that. With base b the wasted time is at most b × T and the number of probes is log_b(T). Base b = 2 is the usual compromise. This is the same argument as array doubling and TCP's slow start.

The common explanation, "exponential backoff reduces load", is true but is the secondary effect. The primary effect is that you are doing a doubling search for a deadline you cannot observe.

Why jitter is not optional

The clients did not all retry at the same moment by chance. They retried together because a shared event (the failure) synchronized them. So the failure itself creates the correlation that breaks the independence the retry needs.

Jitter means adding randomness to each wait. It replaces coordination: instead of the clients talking to each other to spread out, each one picks a random delay. The best-known empirical result (an analysis by AWS) is that full jitter, sleep = random(0, min(cap, base × 2ⁿ)), minimizes both the contended work and the total completion time. Adding randomness made the whole population finish sooner, not just more politely.

import random, time

def call_with_retry(op, base=0.1, cap=10.0, attempts=5):
    for n in range(attempts):
        try:
            return op()
        except TransientError:
            if n == attempts - 1:
                raise
            # full jitter: wait a random time between 0 and min(cap, base * 2^n)
            time.sleep(random.uniform(0, min(cap, base * 2 ** n)))

The parameter everyone forgets: the retry budget

Retry limits are set per request and per hop, and they multiply down a call tree: three attempts at each of three tiers is 3 × 3 × 3 = 27 requests arriving at the bottom for one user request. A per-hop policy becomes an exponential policy in a layered system. The bound is a retry budget (retries limited to a fraction of successes), retrying at exactly one layer, and a propagated deadline.

Boundary. Retry is safe only where the operation is idempotent or where ambiguity is acceptable. It does not create that property; it consumes it. Making a repeat harmless is where it is made.