# Exponential Backoff

> Space repeat attempts at base times two raised to the attempt, capped, with random jitter - so retries spread out instead of arriving in a synchronized herd.

- kind: pattern
- category: resilience
- aliases: Backoff, Jittered Backoff
- canonical: https://aipatterns.dev/design-patterns/exponential-backoff
- inspired-by: https://learn.microsoft.com/en-us/azure/architecture/best-practices/transient-faults

## Intent

When an operation is repeated, double the wait each time: 100 ms, 200 ms, 400 ms, capped at a few seconds. Then randomize each wait within its range (jitter), because a thousand clients that all failed together will otherwise all retry together - reproducing the exact spike that caused the failure.

## Forces

- **Retry now** vs **thundering herd**: synchronized retries hit the recovering dependency as a second outage.
- **Back off** vs **never finish**: pure doubling eventually schedules multi-minute waits; a cap keeps retries finishable.
- **Fairness** vs **starvation**: without jitter, the client that failed first always retries first, every round.
- **Compute a schedule** vs **obey the server**: a `Retry-After` header is a fact; the computed delay is a guess.

## Therefore

**Wait `random(0, min(cap, base × 2^attempt))` before each repeat - full jitter over a doubling, capped range - and stop when attempts or the deadline run out.**

The doubling matches how outages actually recover: most blips clear in the first second, so early attempts come quickly; genuine outages need the later, longer gaps. The jitter converts one synchronized spike into a spread. Fixed delays and zero jitter are the two defaults that turn a retry policy into a self-inflicted denial of service.

## Structure

```mermaid
flowchart TD
  A["attempt"] --> B{"succeeded?"}
  B -- "yes" --> C["return"]
  B -- "no" --> D{"attempts or deadline exhausted?"}
  D -- "yes" --> E["fail with last error"]
  D -- "no" --> F["delay = random(0, min(cap, base x 2^n))"]
  F --> G["sleep, honouring Retry-After if sent"]
  G --> A
```

### Participants

- **Schedule** (`backoffDelay`): a pure function from attempt number to delay. Deterministic given its RNG, so tests can assert it.
- **Loop**: the [Retry](https://aipatterns.dev/design-patterns/retry.md) policy that consults the schedule, checks its budget, and sleeps.
- **Dependency**: the failing call; ideally it sends `Retry-After`, which overrides the computed delay.

## Use it when

- Any automatic retry loop spans more than one attempt - this is the default spacing for [Retry](https://aipatterns.dev/design-patterns/retry.md).
- A job or queue consumer re-runs failed work on a schedule.
- You poll a not-yet-ready resource (a job status endpoint, a deployment).
- Many clients call one rate-limited or capacity-limited API.

## Do not use it when

- The server sent `Retry-After`. Obey it; the server knows its own recovery better than your formula does.
- The caller is interactive with a 1–2 s budget. The schedule outgrows the budget after the first doubling; retry once or fail instead.
- The error is permanent. No spacing fixes a 400; do not schedule retries for it.
- There is exactly one caller and no contention: the jitter buys nothing, though the doubling still helps.
- You are the dependency being hammered. Backoff in clients does not fix your capacity; throttle or shed load at the source.

## Application grill

**Inspect first:** every retry site and its current spacing; whether the HTTP client or SDK already retries with its own backoff - a second layer multiplies attempts silently; the platform's own retries (load balancers, service meshes, queue redeliveries).

**Missing pieces:** none beyond a helper: delay = min(cap, base * 2^attempt) with jitter. No library is needed; if the codebase adopts one (p-retry, tenacity), keep exactly one.

**Ask before you build:**

- **Scale:** what total attempt count across all callers can the recovering dependency absorb (cap times callers)?
- **Performance:** does the backoff sequence fit the caller's own deadline - timeouts shorten the room backoff has?
- **Reliability:** full jitter or decorrelated jitter - is a synchronized herd acceptable during recovery windows?
- **Budget:** is the policy one shared helper or drifting per call site - who audits when an incident needs a global change?
- **Implementation:** are attempt numbers logged so retry storms are visible in the metrics that already exist?

## Implementation steps

1. Pick `base` near the dependency's normal response time - 100 ms for APIs, seconds for batch systems.
2. Compute the raw delay as `base × 2^attempt` and cap it (1–5 s for interactive paths, minutes for batch).
3. Apply full jitter: sleep `random(0, min(cap, raw))`. Decorrelated jitter (`random(base, last_delay × 3)` capped) is an alternative when delays should not shrink across attempts.
4. Bound the loop with max attempts (3–5 interactive) and an overall deadline; the cap plus the deadline decides when to stop, not the exponent.
5. Let `Retry-After` override the computed delay, capped by the deadline.
6. Keep each attempt's own [Timeout](https://aipatterns.dev/design-patterns/timeout.md): the schedule bounds the gaps, not the attempts.
7. Seed the RNG in tests so schedules are assertable; inject the sleep in tests so they do not actually wait.

## Example

Three workers hit a rate-limited API and fail together. With a fixed delay they would all retry on the same millisecond, every round. Full jitter spreads them; the cap keeps every wait finishable. The output below shows the schedule each worker computes for its first five attempts.

```ts title="backoff.ts"
// Full jitter: uniform over the capped doubling range.
export function backoffDelay(
  attempt: number, // 0-based
  baseMs: number,
  capMs: number,
  rand: () => number,
): number {
  return Math.floor(rand() * Math.min(capMs, baseMs * 2 ** attempt));
}

// Deterministic MINSTD generator so the demo output is reproducible.
// In production: Math.random. (48271 keeps the math exact in 64-bit floats.)
const rng = (seed: number) => () =>
  (seed = (seed * 48271) % 2147483647) / 2147483647;

const BASE = 100;
const CAP = 2_000;

const raw = [0, 1, 2, 3, 4].map((n) => Math.min(CAP, BASE * 2 ** n));
console.log(`no jitter, every worker: ${raw.join(", ")} ms`);
for (const [i, worker] of ["worker-1", "worker-2", "worker-3"].entries()) {
  const rand = rng((i + 1) * 7919); // one stream per worker
  const waits = [0, 1, 2, 3, 4].map((n) => backoffDelay(n, BASE, CAP, rand));
  console.log(`${worker}: ${waits.join(", ")} ms`);
}
// worker-1: 17, 74, 44, 535, 385 ms
// worker-2: 35, 148, 89, 271, 771 ms  <- never in lockstep with worker-1
// worker-3: 53, 23, 133, 7, 1157 ms   <- waits may shrink; only the range is fixed
```

```python title="backoff.py"
def backoff_delay(attempt: int, base_ms: int, cap_ms: int, rand) -> int:
    """Full jitter: uniform over the capped doubling range."""
    return int(rand() * min(cap_ms, base_ms * 2**attempt))

class Minstd:
    """Deterministic generator so the demo output is reproducible.

    In production pass random.random.
    """

    def __init__(self, seed: int) -> None:
        self._state = seed

    def __call__(self) -> float:
        self._state = (self._state * 48271) % 2147483647
        return self._state / 2147483647

BASE, CAP = 100, 2_000

raw = [min(CAP, BASE * 2**n) for n in range(5)]
print(f"no jitter, every worker: {', '.join(map(str, raw))} ms")
for i in range(3):
    rand = Minstd(seed=(i + 1) * 7919)  # one stream per worker
    waits = [backoff_delay(n, BASE, CAP, rand) for n in range(5)]
    print(f"worker-{i + 1}: {', '.join(map(str, waits))} ms")
# worker-1: 17, 74, 44, 535, 385 ms
# worker-2: 35, 148, 89, 271, 771 ms  <- never in lockstep with worker-1
# worker-3: 53, 23, 133, 7, 1157 ms   <- waits may shrink; only the range is fixed
```

```go title="backoff.go"
package main

import "fmt"

// Deterministic MINSTD generator so the demo output is reproducible.
type minstd struct{ state int64 }

func (l *minstd) next() float64 {
	l.state = (l.state * 48271) % 2147483647
	return float64(l.state) / 2147483647
}

// Full jitter: uniform over the capped doubling range.
func backoffDelay(attempt int, baseMs, capMs int64, r *minstd) int64 {
	raw := baseMs << attempt // base * 2^attempt
	if raw > capMs || raw <= 0 {
		raw = capMs
	}
	return int64(r.next() * float64(raw))
}

func main() {
	const baseMs, capMs = int64(100), int64(2_000)

	fmt.Print("no jitter, every worker: ")
	for n := 0; n < 5; n++ {
		raw := baseMs << n
		if raw > capMs || raw <= 0 {
			raw = capMs
		}
		fmt.Printf("%d ms ", raw)
	}
	fmt.Println()
	for i := 1; i <= 3; i++ {
		r := &minstd{state: int64(i) * 7919} // one stream per worker
		fmt.Printf("worker-%d: ", i)
		for n := 0; n < 5; n++ {
			fmt.Printf("%d ms ", backoffDelay(n, baseMs, capMs, r))
		}
		fmt.Println()
	}
	// worker-1: 17 ms 74 ms 44 ms 535 ms 385 ms
	// worker-2: 35 ms 148 ms 89 ms 271 ms 771 ms  <- never in lockstep
	// worker-3: 53 ms 23 ms 133 ms 7 ms 1157 ms
}
```

```java title="Backoff.java"
public class Backoff {
    /** Deterministic MINSTD generator so the demo output is reproducible. */
    static final class Minstd {
        private long state;
        Minstd(long seed) { this.state = seed; }
        double next() {
            state = (state * 48271L) % 2147483647L;
            return (double) state / 2147483647L;
        }
    }

    /** Full jitter: uniform over the capped doubling range. */
    static long backoffDelay(int attempt, long baseMs, long capMs, Minstd rand) {
        long raw = baseMs << attempt; // base * 2^attempt
        if (raw > capMs || raw <= 0) raw = capMs;
        return (long) (rand.next() * raw);
    }

    public static void main(String[] args) {
        long BASE = 100, CAP = 2_000;
        StringBuilder rawLine = new StringBuilder("no jitter, every worker: ");
        for (int n = 0; n < 5; n++) {
            long raw = BASE << n;
            if (raw > CAP || raw <= 0) raw = CAP;
            rawLine.append(raw).append(" ms ");
        }
        System.out.println(rawLine);
        for (int i = 1; i <= 3; i++) {
            Minstd rand = new Minstd((long) i * 7919); // one stream per worker
            StringBuilder line = new StringBuilder("worker-" + i + ": ");
            for (int n = 0; n < 5; n++)
                line.append(backoffDelay(n, BASE, CAP, rand)).append(" ms ");
            System.out.println(line);
        }
        // worker-1: 17 ms 74 ms 44 ms 535 ms 385 ms
        // worker-2: 35 ms 148 ms 89 ms 271 ms 771 ms  <- never in lockstep
        // worker-3: 53 ms 23 ms 133 ms 7 ms 1157 ms
    }
}
```

The three workers share a raw schedule but never retry in the same millisecond, and no wait exceeds the cap.

## Trade-offs

**Gains**
- Retry load spreads instead of arriving as a synchronized second spike.
- The doubling curve matches how quickly transient failures actually clear.
- The cap guarantees the loop stays finishable within the deadline.

**Costs**
- Added latency: the median caller waits longer than with an immediate retry.
- Two knobs to tune per dependency (`base`, `cap`), both wrong more often than absent.
- Without a cap, exponential growth schedules multi-minute waits nobody approved.
- Jitter makes runs non-reproducible unless the RNG is seeded.

## Relations

- [Retry](https://aipatterns.dev/design-patterns/retry.md) owns what to repeat and when to stop; this pattern owns only the spacing between repeats.
- [Timeout](https://aipatterns.dev/design-patterns/timeout.md) bounds each attempt; the backoff bounds the gaps between attempts.
- [Circuit Breaker](https://aipatterns.dev/design-patterns/circuit-breaker.md) is the next step when spaced retries keep failing: stop calling entirely.
- [Command](https://aipatterns.dev/design-patterns/command.md): when waits grow to minutes, move the repeat into a scheduled queue instead of a sleeping caller.

## Agent checklist

- [ ] The delay is randomized (full jitter), and the RNG is seeded where tests assert schedules.
- [ ] The doubling range has a cap; no wait can exceed it.
- [ ] `Retry-After` overrides the computed delay when the server sends one.
- [ ] Attempts and overall deadline still bound the loop; the schedule does not decide alone.
- [ ] Each attempt keeps its own timeout.