Offered by Dead Brands
How rate limiters actually work under the hood — token bucket, leaky bucket, fixed and sliding windows — and how a well-behaved client survives them: exponential backoff with full jitter, `Retry-After
Use it over MCP: connect to https://mcp.deadbrands.co/hub/mcp and call skills_get with slug rate-limiting-and-backoff.
# Rate Limiting and Backoff Credit: SteTy — published free in the Skills Hub How rate limiters actually work under the hood — token bucket, leaky bucket, fixed and sliding windows — and how a well-behaved client survives them: exponential backoff with full jitter, `Retry-After`, retry budgets, and circuit breakers. Master both sides and you stop causing outages and stop being surprised by 429s. ## Overview A rate limiter enforces a quota: so many requests per key (user, API key, IP) per period. When you exceed it, the server returns **429 Too Many Requests** (RFC 6585; caches must not store it). Limits exist to protect shared capacity, enforce pricing tiers, and blunt abuse. Every serious API has one, whether documented or not, so every serious client needs a retry strategy — and every retry strategy is a load multiplier if written carelessly. This skill covers the server-side algorithms so you can predict behavior, and the client-side discipline so you cooperate instead of colliding. ## Core Principles - **429 is information, not failure.** It tells you the exact rule you broke and usually when to come back. Read it. - **Retries amplify load.** If each layer of a stack retries 3 times, one user action can become 27 upstream calls. Retry at one layer only — ideally the edge closest to the caller. - **Never retry blindly.** Retry only transient failures (429, 5xx, timeouts, connection resets). A 400/404/401 will fail identically forever; retrying it just delays the real error. - **Only retry idempotent operations automatically.** A retried POST may execute twice. Use idempotency keys for unsafe operations or don't retry them. - **The server's signal beats your schedule.** `Retry-After` and rate-limit headers override whatever backoff you computed. - **Fail fast when the dependency is dead.** That's the circuit breaker's job: stop spending latency and threads on a known-bad call. ## Techniques **Token bucket (the default).** A bucket holds up to `C` tokens, refilled at `r` tokens/second. Each request spends one token; empty bucket = reject. State is just two numbers per key (`tokens`, `last_refill`), refilled *lazily* on each request: `tokens = min(C, tokens + (now − last_refill) × r)`. Allows bursts up to `C` while enforcing average rate `r`. Used by Stripe and AWS API Gateway. GCRA (Generic Cell Rate Algorithm) is the same math expressed as a single "theoretical arrival time" timestamp — one int64 of state. **Leaky bucket.** Requests enter a queue and drain at a strictly constant rate; overflow is dropped. Output is perfectly smooth, which protects fragile downstreams, but bursts are *queued or lost*, never absorbed. NGINX `limit_req` is the queue flavor; Shopify's is the meter flavor (mathematically a token bucket viewed in reverse). **Fixed window counter.** Count requests in calendar-aligned windows (e.g., 12:01:00–12:01:59), reset at the boundary. One counter per key — cheapest possible. Fatal flaw: the **boundary burst**. 100 requests at 12:00:59 plus 100 at 12:01:00 = 200 requests in 2 seconds, fully "legal." **Sliding window log.** Store a timestamp per accepted request; count entries inside the trailing window. Exact, no boundary exploit, but O(n) memory and query cost. Reserved for low-volume, high-stakes limits: login attempts, MFA, password resets. **Sliding window counter (Cloudflare's hybrid).** Keep counters for the current and previous fixed windows and weight the previous one by how much of it still overlaps the trailing window: `estimate = prev × (1 − elapsed_fraction_of_current) + curr`. Two counters per key, O(1), ~1% error under uniform traffic. Kills the boundary burst at fixed-window cost. **Exponential backoff.** Wait `min(cap, base × 2^attempt)` between tries: base 100 ms, cap 10 s gives 100 ms, 200, 400, 800 … 10 s, 10 s. Gives a struggling service geometrically decreasing pressure. **Jitter (AWS Architecture Blog canon, Marc Brooker).** Backoff alone keeps clients synchronized — everyone who failed together retries together, forever (the thundering herd). Randomize: - *Full jitter (default):* `sleep = random(0, min(cap, base × 2^attempt))`. In AWS's simulation it did the least total work and finished soonest. - *Equal jitter:* `sleep = t/2 + random(0, t/2)` where `t` is the capped exponential — guarantees a minimum wait. - *Decorrelated jitter:* `sleep = min(cap, random(base, prev_sleep × 3))` — stateful, good for long retry chains. **Retry-After.** Sent on 429 (and 503). Two legal forms per RFC 9110: delay-seconds (`Retry-After: 120`) or an HTTP-date. If present, it is a floor: sleep at least that long, plus a little jitter on top so a thousand told-to-wait clients don't return in lockstep. **Rate-limit headers.** Many APIs report standing on every response: `X-RateLimit-Limit`, `X-RateLimit-Remaining`, `X-RateLimit-Reset` (epoch seconds). A polite client slows down as `Remaining` approaches 0 instead of waiting to be rejected. (An IETF draft standardizes these as `RateLimit` / `RateLimit-Policy`.) **Circuit breaker (Fowler / Nygard's *Release It!*).** Wrap a dependency. **Closed:** calls pass; failures count. At a threshold (e.g., 5 consecutive failures, or 50% errors over a rolling window) it trips **Open:** calls fail immediately, no network attempt, for a reset timeout (e.g., 30 s). Then **Half-open:** a small number of trial calls probe; success closes the breaker, failure re-opens it. Converts 30-second timeout cascades into microsecond rejections and gives the dependency silence to recover. ## Worked Examples *Token bucket, capacity 10, refill 2/s.* Client fires 15 requests instantly: 10 pass (bucket 10→0), 5 get 429. After 3 idle seconds the bucket holds 6. Sustained rate can never exceed 2/s, but saved-up capacity funds legitimate bursts. *Full jitter, base 100 ms, cap 10 s.* Attempt ceilings: 100 ms, 200, 400, 800, 1.6 s, 3.2 s, 6.4 s, 10 s. Actual sleeps are uniform draws *under* those ceilings — e.g., 37 ms, 190 ms, 88 ms, 640 ms… Two clients on the same schedule almost never collide twice. *Thundering herd.* An API dies for 60 s; 5,000 clients fail at t=0. Fixed 1 s backoff: retries land as 5,000-request spikes at t=1, 3, 7, 15… and re-kill the recovering service. Full jitter over the same windows: the same retries smeared evenly — the service survives its own recovery. *Retry budget.* "Retry at most 3 times AND stop after 20 s total elapsed, whichever comes first." Attempt 4's computed sleep would cross the deadline, so the client surfaces the error at 20 s instead of hanging for a minute. ## Common Pitfalls - **Retrying 4xx.** Only 429 (and occasionally 408) among client errors is retryable. Retrying a 403 burns budget and can escalate throttling or lockouts. - **Retry storms from layered retries.** Client library retries × gateway retries × service-mesh retries multiply. Audit the whole path; set budgets per layer that shrink toward the core. - **Ignoring `Retry-After`** and retrying sooner — many APIs punish this with longer bans. - **No cap, no attempt limit.** Uncapped exponential backoff with unlimited attempts is a slow-motion self-DoS and a hung worker pool. - **Synchronized jitter seeds.** Using the same PRNG seed (or wall-clock second) across a fleet re-synchronizes the herd. Seed from real entropy. - **Breaker counting the wrong failures.** If client errors (400s) trip the breaker, a bad deploy of *your* requests takes the dependency offline for everyone. Count server/timeout failures. ## Practice Drills 1. Implement a lazy-refill token bucket keyed by user ID. Unit-test: burst of C passes, C+1th fails, exactly r more pass after 1 s idle. 2. Simulate 1,000 clients against a service that fails for 30 s. Graph request volume for no-backoff, plain exponential, and full jitter. Measure total calls and time-to-drain. 3. Write a retry wrapper with base 200 ms, cap 5 s, max 4 attempts, 15 s total deadline, full jitter, and `Retry-After` honored as a floor. Feed it scripted 429/500/400 responses and assert behavior for each. 4. Add a circuit breaker (threshold 5, reset 10 s) around drill 3's call. Kill the fake service mid-run and watch calls fail in microseconds instead of timing out. ## When to Use and Limits - **Use it when:** a task calls for rate limiting and backoff, as laid out in the Techniques and Worked Examples above. - **Watch first for:** Retrying 4xx.; Retry storms from layered retries.; Ignoring `Retry-After` (see Common Pitfalls). - **Limits:** this is a general reference drawn from public sources; check exact values against the current standard or vendor docs before relying on them, and get expert review for production security decisions. ## Quick Reference | Algorithm | State per key | Bursts | Exact? | Reach for it when | |---|---|---|---|---| | Token bucket | 2 numbers | Up to capacity, on purpose | Average rate | General-purpose API limits | | Leaky bucket | Queue or 1 timestamp | Smoothed away | Yes, on output | Fragile downstream, traffic shaping | | Fixed window | 1 counter | 2× at boundaries | Per window | Coarse quotas, internal APIs | | Sliding log | 1 timestamp/request | Never over | Exact | Logins, MFA, low volume | | Sliding counter | 2 counters | Near limit | ~1% error | High-volume, accuracy matters | Retry defaults that rarely hurt: base 100–500 ms, multiplier 2, cap 5–30 s, max 3–5 attempts, full jitter, total deadline set, `Retry-After` always wins. --- *Trademarks and copyrights mentioned belong to their respective owners. Educational reference only; not affiliated with or endorsed by them.*