Compliant Web Scraping

Adding Jitter to Exponential Backoff #

This page answers one precise question: how do you add randomness to exponential backoff delays so that many clients retrying at once stop retrying in lockstep? It is a detail page under Exponential Backoff and Retry Logic in the Network Resilience & Proxy Management section, and it walks through the three standard jitter algorithms — full, equal, and decorrelated — with their formulas, Python, and the tradeoffs that decide which to reach for.

Problem Framing #

Plain exponential backoff computes a deterministic delay: base * 2^attempt. The problem surfaces the instant more than one client fails at the same moment — which is exactly what happens when a server returns 503 or 429 under load, or when a shared dependency blips. Every client computes the same delay from the same attempt number, sleeps the same duration, and then fires again simultaneously. The retry itself becomes a synchronised wave — the thundering herd — that re-overloads the server and pushes everyone into the next identical backoff round. The system oscillates instead of recovering.

Jitter breaks the synchronisation by spreading retries randomly across the backoff window. It does not change the average delay much; it changes the distribution, turning a spike of simultaneous retries into a smear the server can absorb. In a distributed crawler where dozens of workers hit the same origin, jitter is not optional — it is the difference between a fleet that backs off gracefully and one that DDoSes its target on every hiccup.

Step-by-Step Implementation #

  1. Compute the capped exponential ceiling for this attempt: cap_delay = min(max_delay, base * 2^attempt).
  2. Choose a jitter algorithm and sample the actual sleep from within (or around) that ceiling.
  3. Honour a server Retry-After first — when present it overrides any computed delay verbatim.
  4. Sleep the jittered value, not the raw exponential.

The three algorithms, from AWS’s well-known analysis:

Algorithm Formula Property
Full jitter sleep = random(0, min(cap, base * 2^attempt)) Maximum spread; lowest collision rate
Equal jitter t = min(cap, base * 2^attempt); sleep = t/2 + random(0, t/2) Guarantees a minimum wait, still spreads
Decorrelated jitter sleep = min(cap, random(base, prev_sleep * 3)) Self-scaling; grows from the last actual sleep 
import random

def full_jitter(attempt: int, base: float = 1.0, cap: float = 30.0) -> float:
    # Uniformly random anywhere in [0, ceiling]. Best default for crawlers:
    # maximum decorrelation between workers retrying the same host.
    ceiling = min(cap, base * (2 ** attempt))
    return random.uniform(0, ceiling)

def equal_jitter(attempt: int, base: float = 1.0, cap: float = 30.0) -> float:
    # Half fixed, half random: retries never fire "instantly", but still spread.
    ceiling = min(cap, base * (2 ** attempt))
    return ceiling / 2 + random.uniform(0, ceiling / 2)

def decorrelated_jitter(prev: float, base: float = 1.0, cap: float = 30.0) -> float:
    # Feeds the previous sleep back in, so the window widens organically.
    # Seed the first call with prev = base.
    return min(cap, random.uniform(base, prev * 3))

A production retry loop wiring full jitter in, with Retry-After taking precedence:

import time
import random
import requests

def fetch_with_jittered_backoff(url: str, max_attempts: int = 5,
                                base: float = 1.0, cap: float = 30.0) -> requests.Response:
    for attempt in range(max_attempts):
        resp = requests.get(url, timeout=10)
        if resp.status_code < 400:
            return resp
        if resp.status_code not in (429, 500, 502, 503, 504):
            resp.raise_for_status()          # terminal: do not retry 4xx (except 429)

        # A server-declared delay always wins over our computed one.
        retry_after = resp.headers.get("Retry-After")
        if retry_after and retry_after.isdigit():
            time.sleep(int(retry_after))
            continue

        if attempt == max_attempts - 1:
            resp.raise_for_status()
        delay = random.uniform(0, min(cap, base * (2 ** attempt)))  # full jitter
        time.sleep(delay)
    raise RuntimeError("retries exhausted")

Decorrelated jitter, which many practitioners prefer for its slightly higher throughput at the same server load, threads the previous sleep through the loop:

def fetch_decorrelated(url: str, max_attempts: int = 5,
                       base: float = 1.0, cap: float = 30.0) -> requests.Response:
    sleep = base
    for attempt in range(max_attempts):
        resp = requests.get(url, timeout=10)
        if resp.status_code < 400:
            return resp
        if attempt == max_attempts - 1:
            resp.raise_for_status()
        sleep = min(cap, random.uniform(base, sleep * 3))   # carries state forward
        time.sleep(sleep)
    raise RuntimeError("retries exhausted")

Verification & Testing #

Prove that jitter actually spreads the delays — a good test asserts the variance, not a fixed value:

def test_full_jitter_spreads_and_caps():
    samples = [full_jitter(attempt=4, base=1.0, cap=30.0) for _ in range(10_000)]
    assert all(0 <= s <= 16 for s in samples)      # ceiling = min(30, 16) = 16
    assert len(set(round(s, 3) for s in samples)) > 1000   # genuinely spread
    assert 6 < sum(samples) / len(samples) < 10            # mean ~ceiling/2

To see the thundering herd disappear, simulate 500 clients failing on the same attempt and histogram their fire times. With deterministic backoff every client lands in one bucket; with full jitter they smear across the window:

from collections import Counter
buckets = Counter(int(full_jitter(3)) for _ in range(500))
print(sorted(buckets.items()))   # spread across seconds, not a single spike

Compliance & Operational Guardrails #

  • Jitter never overrides an explicit server signal. A Retry-After header — or the reset hints you read when adapting rate limits from response headers — is an instruction from the target and must be honoured verbatim; jitter only applies to your own computed delays.
  • Jitter reduces load but does not license more retries. Keep the attempt cap and per-host budget intact; spreading retries is about being a good neighbour during recovery, not extracting more requests.
  • Always cap the delay. An uncapped 2^attempt eventually sleeps for hours; a max_delay ceiling keeps recovery bounded and predictable for on-call.

Common Mistakes #

  1. Adding jitter but keeping a fixed floor equal to the full exponential, so every client still waits at least the deterministic delay and only the tail is randomised — the herd barely thins.
  2. Applying jitter on top of Retry-After, randomising a delay the server told you to honour exactly, which either wastes time or violates the stated limit.
  3. Forgetting the cap, letting decorrelated jitter’s prev * 3 growth run unbounded into multi-hour sleeps that stall the pipeline.

Frequently Asked Questions #

Which jitter strategy should I use by default? #

Full jitter is the safest default for crawlers because it maximises decorrelation — retries can fire anywhere in [0, ceiling], giving the widest spread and the lowest chance two workers hit the origin together. Choose decorrelated jitter when you want slightly higher throughput at equivalent server load, since it tends to recover faster while still avoiding synchronisation. Equal jitter is a middle ground when you want to guarantee a minimum wait between attempts.

Does jitter make my total retry time unpredictable? #

It makes any single retry’s delay random, but the aggregate stays bounded because you cap each delay at max_delay and cap the attempt count. The expected total is close to the deterministic version — full jitter averages about half the ceiling per attempt — so you can still reason about worst-case time as max_attempts * max_delay.

Do I still need jitter if I only run one crawler process? #

Yes, though the benefit is smaller. Even a single process shares the target with every other client of that server, and outages are correlated across clients. Jitter keeps your retries from synchronising with everyone else’s recovery wave, which matters most precisely when the server is already struggling.