Loading...
Loading...
Token bucket, leaky bucket, sliding window logs, and distributed rate limiting
Nine prefix scans return 20 drivers from 2M updating at 400k fixes per second, yet the same pipe carries abuse. Your auth endpoint sees 100k requests per second from a scrape bot mixed with 200 per second from real users. A flat 1000-per-minute per IP blocks whole offices behind one corporate NAT, meaning thousands sharing one address, while admitting bot bursts at window edges. The algorithm decides smoothness and burst tolerance. Token bucket, meaning tokens refilling at rate r with capacity b for bursts, admits bursts then throttles; leaky bucket, meaning queued requests dripping at a fixed rate, smooths everything; fixed window, meaning counts reset per calendar minute, doubles at boundaries; sliding log, meaning stored timestamps per request, is precise but heavy; sliding-window counter, meaning two fixed windows weighted by elapsed fraction, approximates precisely with two integers.
| Algo | Model | Burst | Distributed |
|---|---|---|---|
| Token bucket | Tokens refill at rate r, cost 1 per request, bucket size b | Yes; burst up to b | Per-node + Lua/redis script atomic |
| Leaky bucket | Requests queue and drip at fixed rate, overflow drops | No; smooths | Queue impl |
| Fixed window | Count in window [0,60s), reset | 2× at boundary | Simple counter |
| Sliding log | Store timestamps of each request, evict older than window | Precise | Heavy (list) |
| Sliding window counter | Fixed windows weighted: count = cur + prev * (1 - elapsed/window) | Near-precise, efficient | Two counters (Redis) |
One Redis counter, meaning a central count in the in-memory store, works until twelve gateways each hold local buckets admitting 100 per minute, turning a global 100 into 1200. Central Lua execution, meaning an atomic server-side script reading, comparing, and incrementing in one round trip, buys exactness for about 0.5ms extra. Split local budgets buy zero-latency checks for a few percent overshoot between 5s gossip syncs. Like traffic metering with one central ramp signal versus each on-ramp guessing, precision costs a round trip. Edge gateways such as Envoy, a service proxy, hold coarse limits protecting the stack while services hold fine per-principal limits for fairness, keyed by authenticated identity rather than IP.
Lua script atomically gets counter, checks limit, increments with TTL. Single source of truth but extra RTT. Example bucket check in one round trip.
429 Retry-After, X-RateLimit-Remaining.Spec 100 requests per minute with burst 20 means capacity 20 for bursts and refill 100/60 near 1.67 tokens per second sustained. Tokens equal min(capacity, tokens plus rate times elapsed) with cost 1 each: idle 60s banks 20, so 20 instant requests pass and the 21st waits 0.6s, while sustained flow holds 100 per minute forever. Fixed windows double at edges: 100 at second 59.9 plus 100 at second 0.0 admits 200 in a second. Sliding-window counter estimates current plus previous times (1 minus elapsed/window), so 10 plus 100 times 0.75 equals 85 at 15s in, throttling correctly.
Token bucket: capacity b=20, rate r=100/min ≈ 1.67/s tokens = min(b, tokens + r × elapsed); request costs 1 idle 60s → 20 tokens → 20 instant requests pass, 21st waits ~0.6s sustained: 100/min forever; burst: at most 20 above the average Fixed-window trap (limit 100/min, windows :00–:59): 100 requests at :59.9 + 100 at :00.0 → 200 in ~1s, both "within limit" Sliding-window-counter fix: estimate = cur + prev × (1 − elapsed/window) at :00:15 with prev=100, cur=10 → 10 + 100×0.75 = 85 → still throttles correctly
Token bucket admits bursts then throttles to refill: user-facing APIs that spike. Leaky bucket queues and drips fixed: downstreams that cannot spike at all such as SMS gateways or payment rails. Pick burst tolerance, not fashion.
Exact sliding log stores one timestamp per request: 100k rps times 60s equals 6M entries evicted constantly. Sliding-window counter keeps two integers within a few percent. Exactness costs a list; approximation costs two counters.
Central Lua on Redis, an in-memory store, returns remaining plus retry-after in one round trip near 0.5ms with a single source of truth, but Redis becomes the hot path. Split-budget divides global 1200 per minute across 12 gateways at 100 local each, gossiping usage every 5s with brief 5 to 10% overshoot between syncs. Billing-grade limits stay central; UX-grade fairness goes local. Windows keyed on wall-clock jump on NTP steps or leap seconds replaying quota, while token buckets keyed on monotonic elapsed time, meaning a clock that never moves backward, do not.
Central (precise): Lua on Redis, GET count, compare, INCR with TTL, atomically cost: +1 RTT (~0.5ms) per request; single source of truth; Redis is the hot path script returns remaining + retry-after in the same round trip; no second call Split-budget (fast): global 1200/min ÷ 12 gateways = 100/min local each gateways gossip usage every 5s; over-admitters lend quota to under-admitters drift: brief 5–10% overshoot between syncs; acceptable for fairness, not for billing Billing-grade: central counter only. UX-grade: local + periodic sync.
Five thousand employees behind one corporate NAT share one IP, so IP-keyed limits throttle the company when one team load-tests. Meanwhile mobile clients retrying every 429 instantly triple shed load into self-DDoS. Key by authenticated user or API key with IP fallback for anonymous endpoints, tier buckets by plan such as free 100 per minute versus pro 5k, and weight tokens by endpoint cost so one SMS counts more than one read. Return 429 with Retry-After plus remaining and reset headers, document exponential backoff with jitter, and fail explicitly: edge limiters fail open admitting on Redis outage for availability, billing limiters fail closed rejecting for revenue.
Return 429 with Retry-After plus X-RateLimit-Remaining/Reset, and document exponential backoff with jitter (1s, 2s, 4s + random). A client that retries instantly at full rate turns a 10-second scrape burst into a 10-minute self-DDoS; the limiter holds, but nothing useful gets through.
Two calls let two gateways both read 99 and admit requests 100 and 101. One EVALSHA script, meaning a cached atomic Redis execution, reads window counters, rolls windows when elapsed exceeds length, estimates current plus previous weighted, rejects past limit, else increments with expiry and returns admitted plus remaining. Every gateway runs this against one Redis key packing cur, prev, reset timestamp in a single HASH, keeping Cluster atomicity per slot without CROSSSLOT errors.
-- sliding-window-counter in one EVALSHA (KEYS[1]=key, ARGV: limit, window_ms, now_ms)
local cur = redis.call("HMGET", KEYS[1], "cur", "prev", "reset_ts")
local elapsed = tonumber(ARGV[3]) - tonumber(cur[3] or ARGV[3])
if elapsed >= tonumber(ARGV[2]) then -- window rolled: prev=cur, cur=0
redis.call("HMSET", KEYS[1], "prev", cur[1] or 0, "cur", 0, "reset_ts", ARGV[3])
cur = {cur[1] or 0, 0, ARGV[3]}
end
local estimate = tonumber(cur[2]) + tonumber(cur[1]) * (1 - elapsed / tonumber(ARGV[2]))
if estimate >= tonumber(ARGV[1]) then return {0, ARGV[1] - estimate} end -- rejected
redis.call("HINCRBY", KEYS[1], "cur", 1)
redis.call("PEXPIRE", KEYS[1], ARGV[2] * 2)
return {1, ARGV[1] - estimate - 1} -- admitted + remaining in one round trip
100/min across 12 gateways: every gateway runs THIS script against one Redis;
global precision for +1 RTT (~0.5ms). No local counters, no drift, no 2x boundary.One global bucket drops mid-checkout customers alongside decade-old blog scrapers when melting. Priority lanes, meaning separate buckets per traffic class with strict preference, serve checkout first from generous rarely-hit budgets, throttle authenticated reads to refill with Retry-After guidance, and shed anonymous scrape-prone traffic first with challenges. Degradation order ships in config: serve stale cache, disable recommendations, throttle reads, never throttle the payment webhook confirming money moved.
| Lane | Budget | Under overload |
|---|---|---|
| Checkout / payment | Generous, rarely hit | Served first; sheds last; queue briefly rather than reject |
| Authenticated reads | Per-plan tiers | Throttled to refill rate; Retry-After guides backoff |
| Anonymous / scrape-prone | Tight, IP+behavior keyed | Shed first; challenge (CAPTCHA, proof-of-work) before admit |
REST counts requests; one nested GraphQL query, meaning a flexible API language where clients name fields, fans to a thousand resolver fetches while login costs one. Points-based limiting as published by GitHub, Stripe, and Shopify, all API platforms, prices the AST, meaning the parsed query tree, before execution: sum field weights with depth plus breadth caps such as max depth 10 and first 100, reject over budget pre-execution. Executing then counting bills air after the thousand fetches already ran. Rate-limit the planner, not just the resolver.
Cost analysis before execution:
query { user { repos(first: 100) { issues(first: 50) { title } } } }
cost = 1 + 100×(1 + 50×1) ≈ 5,101 points vs budget 5,000/hr → rejected pre-execution
never execute-then-count: the thousand fetches already happened; the limiter billed air.
Depth + breadth caps as backstop: max depth 10, max first: 100; static analysis rejects
the absurd before cost math runs. Rate limit the planner, not just the resolver.Lua stays atomic on one node until Cluster, meaning sharded Redis routing keys by hash slot, rejects multi-key scripts spanning slots with CROSSSLOT errors. Hash tags, meaning the bracketed substring forcing shared slots, colocate related keys such as rl with user123 in braces, or pack cur, prev, reset timestamp as HSET fields under one HASH key needing no tags. Atomicity is per slot, so each principal lives in exactly one. Even then, one celebrity key such as a gateway health-check counter can roast its slot across 16384 shared slots, so shard counters rather than only keys.
Single-node Lua: KEYS[1]=rl:user123, KEYS[2]=rl:user123:prev → fine (one node).
Cluster: slot(crc16("rl:user123")) ≠ slot(crc16("rl:user123:prev")) → CROSSSLOT ✗
Fixed: KEYS = {rl:{user123}:cur}, {rl:{user123}:prev} → same {...} tag → same slot ✓
or pack: one HASH rl:{user123} with fields cur/prev/reset_ts; single key, no tags needed.
Hot-slot warning: millions of principals share 16384 slots evenly, but ONE celebrity key
(gateway health-check counter) can still roast its slot. Shard counters, not just keys.The API returns 500s for 30 seconds and every mobile client retries with backoff, so recovery brings a synchronized wave triple the normal rate against cold buckets. Rejected alternative: admit the wave burst-first and trust the healed backend to absorb 4x. The 300k queued retries plus normal 100k/s land in seconds, fixed windows reopen with full quota per key, and the backend melts a second time from the cure. The working recovery staggers re-admission: buckets refill at normal rate rather than granting spare capacity, Retry-After headers spread clients with jittered delays, and priority lanes admit checkout traffic before anonymous retries. Token buckets naturally meter the ramp since banked tokens cap the burst at capacity, while fixed windows reopen fully and re-thunder. Size bucket capacity for steady bursts, not outage replays, and let the limiter convert a cliff into a slope.
Outage: 30s of 500s → 300k queued retries + normal 100k/s = 4x wave on recovery
token bucket b=20, r=100/min: each key admits at most 20 instantly, then 1.67/s
→ wave spreads over minutes automatically; backend warms behind the meter
fixed window: new minute opens with full 100 quota per key → entire wave admitted
in seconds → second outage from the cure. Prefer buckets across outage edges.
headers: Retry-After: 7 (jittered 5–10s per client) + priority lanes for checkout.One Lua script holds 100 per minute exact across 12 gateways for 0.5ms, and token buckets spread the 4x retry wave into a slope. Yet every bucket meters events one request at a time. What counts 10TB resting on disks where 80,000 mappers read local blocks in parallel?