How to design a rate limiter

A rate limiter is one shared, contended counter in front of a service; every decision turns on what that counter does at a window boundary and how it stays correct when a rejection must cost less than an acceptance.

Name the job first

Three jobs share the name and disagree on what “correct” means.

• Abuse limits are the smallest (5 password resets/hr), and small limits are exactly where cheap approximate algorithms are worst.
• Put the limiter before auth: a rejection must cost less than an acceptance, or a flood buys free DB lookups.

Numbers that fix the architecture

• Core trade-off (a triangle): memory per key vs burst tolerance vs exactness.
• p99 latency < 5 ms -> at most one same-AZ round trip (~0.5 ms); INCR+EXPIRE = 1.0 ms = 20% of budget. Cross-region 150 ms = 30x over. Store lives in-region.
• Fail-open: limiter must be more available than the service; on store failure, allow through via a local fallback bucket at 100,000 / 20 = 5,000 req/s per node.
• Counter cannot be eventually consistent under burst (that is when copies disagree most).
• Redis: single-threaded, ~100k ops/s ceiling per instance -> at 30% util, 100,000 / 0.30 rounds to 4 shards (25% each, headroom absorbs failover).
• TTL keeps memory bounded without a cleanup job; keys carry a hash tag {client} so all of a client’s keys land on one shard (lets one script span keys).

The five algorithms

L = 100, W = 60 s, r = L/W = 1.667/s.

• Token bucket: tokens = min(C, tokens + (now-last)*r), lazy refill on read; admits A(T)=C+r*T (200 in 60 s at C=L), first C in one ms. C = burst knob. Validate not (cost>0) (NaN slips past <=).
• Leaking bucket: FIFO drains at exactly r; smooths the shape, delays instead of rejects. Draining full q=100 takes 60 s -> fatal for synchronous requests. Right for outbound calls to a capped third party. GCRA = counter form, 16 B, rejects early instead of queueing.
• Fixed window: cheapest, worst worst-case. Aligned windows; 2x count overshoot at boundary, unbounded instantaneous rate (10 req in 400 ms against 5/min = 300x). Aligned resets synchronize every client -> seeds retry storms. Right for daily/monthly quotas only.
• Sliding log: sorted set of timestamps; trim < now-W, count, admit if < L. Exact at any alignment, only exact Retry-After. Log only admitted requests or an attacker sets your memory (210 MB/window from one client). Right for small hard limits.
• Sliding counter (the default): est = p*(1-f) + c, f = fraction of current window elapsed. Two keys because window index is in the key name.

Sliding counter error

• Unbiased: previous-window arrivals are Binomial(p, 1-f), mean = p*(1-f) = the estimate.
• Typical (std dev) at p=L, f=0.5: sqrt(L)/2; relative error 1/(2*sqrt(L)) shrinks as L grows.
• Worst-case count still 2L (needs an end-spike + paced current window), but the 300x rate blowup is gone.

Excellent where limits are large, terrible where small -> choose per rule: counter for tiered quotas, log for L <= 20 abuse limits, token bucket where burst is a feature.

One script, never two commands

Three races come from splitting one decision:

• Lost EXPIRE: process dies between INCR and EXPIRE -> key with no TTL -> client blocked forever + memory leak until eviction removes live keys.
• Window never closes: unconditional EXPIRE refresh keeps pushing expiry out -> client stuck at 1/min. Fix EXPIRE ... NX (set only if no TTL).
• Read-modify-write across machines: two gateways read 5 tokens, both spend 1 -> two spent, one recorded.

Fix: send the whole decision as one Lua script via EVALSHA (40-char hash, not the ~800 B body; fall back to EVAL on NOSCRIPT). Redis is single-threaded, so a script is atomic by construction and collapses to one round trip.

• Read the clock in the script (redis.call('TIME')) to kill gateway skew — but the sliding-window script can’t, because the window index is in the key name (client must compute it to route). Client time is fine when W is large (±50 ms NTP skew = 0.08% of 60 s, 5% of 1 s).
• Sliding-counter PEXPIRE window*2 because this key becomes next window’s prev; expire after one and it degrades to fixed window.
• Scripts must be deterministic and short (a long sorted-set trim blocks the whole store).

Distribute, and the client contract

• Local counters over-admit Nx: 20 x 100 = 2,000. Dividing the limit L/N under-admits Nx (one persistent HTTP/2 connection pins all traffic to one node). Gossip bound is N*L regardless of sync interval. Central store is the only cheap exact option; key-owner sharding is “Redis with extra steps.”
• Cross-region = 30x budget: no global counter. Use per-region limits summing <= global, or per-region + async reconciliation (transient overshoot regions x L).
• Deny cache: in-process map client -> blocked-until. Only denials are cacheable (“allowed” expires on the next request), and the abuser is the one generating the most load. 50,000 req/s client: 3M ops -> 20 (one probe/gateway/window) = 150,000x fewer store ops. Holds only denials -> can never over-admit.
• 429 response carries Retry-After (seconds, not HTTP-date), RateLimit-Reset (seconds left) AND X-RateLimit-Reset (Unix ts) — they differ on purpose, never change either. Send headers on 200s too. 429 != 503. Intermediaries must not retry a 429. Always round Retry-After up.
• Retry storm: 100k clients told the same Retry-After fire within ~10 ms -> 100,000/0.010 = 10,000,000 req/s = 100x design point, self-re-synchronizing. Exponential backoff alone does nothing. Full jitter uniform(0, delay) spreads over the second -> exactly 100,000 req/s. Also: retry at one layer only; use a retry budget (retries funded in proportion to successes, ~1.1x steady state).

Silent failure to watch

Every failure announces itself except key eviction under memory pressure: allkeys-lru removes live counters, every request succeeds, dashboards stay green, and the limits are simply gone. Guard with volatile-ttl, a 70% memory alarm, a cap on log-based rules, and page on evicted_keys > 0.