Design a distributed rate limiter

How it works

1. Requirements

Functional: configurable rules (key, limit, window, algorithm) per customer tier and endpoint; return 429 with headers when over the limit; update rules without redeploying.

Non-functional: adds under ~1–2 ms per request; accurate within a small margin; highly available; scales to millions of requests per second.

2. Where it runs

As middleware in the API gateway or a sidecar next to each service, so every request is checked before it reaches business logic. Rules are loaded from a config store and cached locally.

3. Counting in a shared store

The usual design keeps counters in an in-memory store such as Redis, partitioned by key with consistent hashing so load spreads across nodes.

Each check must be atomic. For a token bucket, a small server-side script reads tokens and the last refill time, refills, takes a token if available, writes back and returns the result, all as one operation. A sliding window counter uses two per-window counters with expiry.

-- KEYS[1] = bucket key; ARGV = capacity, refill_per_ms, now_ms
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local cap, rate, now = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local tokens = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - ts) * rate)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate))
return allowed and 1 or 0

4. Making it fast and resilient

• One round trip: do the check in a single atomic call, and pipeline when several rules apply.
• Local pre-check: once a key is over its limit, cache “blocked until T” locally so further requests are rejected without a network call.
• Batching for very hot keys: each gateway takes a small allowance of tokens at a time (say 10) and spends them locally. Slightly less precise, far fewer calls.
• Failure mode: if the store is slow or down, fail open with a conservative local limit and alert; for security-sensitive limits like sign-in attempts, fail closed.
• Replication: run the store with replicas and automatic failover; losing a few seconds of counts during failover is acceptable.

5. Multiple regions

Strictly global counts need cross-region coordination, which adds latency. Common options: enforce limits per region (simple; a client could get the limit in each region), split the global budget between regions and rebalance periodically, or sync counts asynchronously and accept a small overshoot.

6. Responding

HTTP/1.1 429 Too Many Requests
Retry-After: 7
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 7

Log decisions as metrics (allowed and limited, per rule and tier) so you can tune limits and spot abuse.