Pattern — Rate Limiting (Token Bucket)

The problem it solves

A fast caller finds a slower resource and drives it past what it can serve. Drill 84's order gateway accepted 15,000 orders/s onto a queue a processing tier could only drain at 4,000/s, and the backlog grew by 11,000 every second until the pipeline stalled. Drill 21's cold cache sent every request to a feature store, then three retries each with no jitter turned one request into four synchronized waves that saturated it for 45 minutes. Both are the same shape: arrivals outrun service, and nothing at the edge counts the rate or says "not this many." You need a limiter that admits work at a sustainable rate, tolerates short bursts, and rejects the rest cheaply — before it becomes backlog.

The pattern

A token bucket is a counter that refills at a fixed rate and drains one token per admitted request. Two numbers define it: a refill rate r (tokens added per second — the sustainable throughput) and a capacity b (the most tokens the bucket can hold — the allowed burst). Every request tries to take one token: if the bucket has ≥1, take it and admit; if it's empty, reject immediately with HTTP 429 Too Many Requests and a Retry-After. The bucket refills continuously (min(b, tokens + r × Δt)), so quiet periods bank a burst up to b while the long-run admit rate can never exceed r. It is O(1) — two numbers per key, updated lazily on each request — which is why it scales to per-user and per-endpoint limits.

How to apply it

Size everything from the measured drain rate of the thing you are protecting, not a guess.

1. Set r to the resource's real capacity. Drill 84's processing tier drains 4,000 orders/s, so r = 4000 tokens/s. Measure it under load; don't infer it from CPU. This is the number the long-run admit rate converges to.
2. Set b for the burst you can absorb, not more. Capacity ≈ 1–2× the per-second rate is a safe default: b = 8000 lets a 2-second quiet spell fund one 8,000-order spike, then the tier catches up. Bigger b = smoother but a deeper transient overshoot; b = r is nearly a leaky bucket (almost no burst). Never set b to "a comfortable-looking big number" — that just relocates Drill 84's backlog inside the bucket.
3. Reject fast and honestly. On an empty bucket return 429 in under 5 ms, before the work item is created, with Retry-After: 1 and rate headers (X-RateLimit-Limit, -Remaining, -Reset). Never accept-then-drop; a 202 you can't honor is Drill 84's exact failure.
4. Scope a bucket per limiting dimension. One global bucket protects the shared resource; per-API-key / per-tenant buckets (e.g. 1000 r/s, b = 2000 each) stop one noisy client starving the rest — Drill 84's "stay fair" requirement. Key = (tenant_id, route).
5. Make it distributed if you have >1 edge node. A local bucket on each of 10 gateways enforces 10 × r, not r. Keep the counter in Redis (INCR/DECR or a Lua token-bucket script, atomic), or hand each node a slice of the global rate. Redis-cell / CL.THROTTLE implements this directly.
6. Pair it with the neighbors, not instead of them. Rate limiting is the admission gate on Drill 84's bounded queue (30s × 4000 = 120,000 cap) and concurrency limit; on the retry path (Drill 21) a per-client token bucket caps retries at ~10% of request volume so a retry storm can't self-amplify. Combine with backoff + jitter on the client so rejected callers decorrelate instead of re-hammering in lockstep.

flowchart TD
    A["Request arrives"] --> B["Refill: tokens = min(b, tokens + r x dt)<br/>(r = 4000/s, b = 8000)"]
    B --> C{"tokens >= 1 ?"}
    C -->|"yes"| D["Take 1 token · admit<br/>(enqueue, under bounded cap)"]
    C -->|"no (bucket empty)"| E["Reject fast · 429<br/>Retry-After, under 5 ms"]
    D --> F["Long-run admit rate <= r<br/>burst tolerated up to b"]
    E --> F

When to use it — and when not

Reach for it on any edge that fronts a resource with a known, finite service rate — an API tier, a shared pricing service, a retry path, a third-party quota you must stay under. It is the right tool when you can name the rate you must not exceed and can afford to reject the overflow. Skip it, or choose differently, when: the spike is transient and self-draining and a small buffer would absorb it (rate-limiting there just pushes needless 429s onto callers); the real fix is genuinely more capacity (a limiter keeps you alive, it does not make you faster); or you need perfectly smooth output with zero burst — then a leaky bucket (fixed-rate drain, no accumulation) fits better than a token bucket's burst allowance. Fixed-window counters are simpler but let 2× the limit through at a window boundary; sliding-window log is exact but O(requests) in memory. And a limiter needs somewhere for shed load to go — a caller that backs off, or a lower-priority tier to drop — otherwise you've only chosen where the loss lands.

Signals it's working

• The 429 rate is a first-class SLI and rises under a spike — non-zero 429s are healthy shedding. Flat-zero 429s under a 3× spike means the limiter isn't wired (Drill 84's original green dashboards).
• Admitted-work p99 stays flat through the spike (Drill 84: admitted orders still execute in ~300 ms) while excess is rejected at the edge.
• The protected resource never exceeds its rate — the feature store / processing tier sees ≤ r, and the bounded queue stays below its cap and its 70% alarm.
• A game-day load test holds arrivals at 3× r for 10 minutes and asserts: bounded queue, honest 429s with Retry-After, stable admitted-p99 — degradation, not collapse.

Seen in the wild

• Stripe rate-limits its API with a token-bucket and returns 429 with rate-limit headers; GitHub, Twitter/X, and most public APIs expose X-RateLimit-Remaining / -Reset on the same model.
• Amazon — API Gateway usage plans (rate + burst) and DynamoDB's per-partition capacity are token buckets; Envoy / Istio and NGINX limit_req (leaky-bucket variant) enforce it at the mesh and proxy edge.
• Redis ships CL.THROTTLE (redis-cell), a ready-made distributed token bucket; Netflix concurrency-limits applies the same shed-fast reflex adaptively.
• Guava RateLimiter and Google Cloud / Kubernetes API server all implement token-bucket limiting in-process.

See it

The CardsScene shows the two load-bearing numbers (r = 4000/s refill, b = 8000 burst) beside the tradeoff (bigger b = smoother but deeper overshoot); the ChainScene carries the mechanism — refill → take a token → admit, or empty → 429 in under 5 ms — so the protected tier never exceeds r.

Named concepts: token bucket, rate limiting, burst capacity, admission control.