System Design · Design Question
Design a Rate Limiter
Cap request rates per user/IP/API key: algorithms, Redis counters, gateway placement, and distributed correctness.
1. Requirements
Functional
- Enforce limits like 100 req/min per user, 10 req/s per IP.
- Return 429 with optional
Retry-Afterwhen exceeded. - Configurable rules per key (user, API key, IP, route).
- Optional soft vs hard limits; weighted cost per endpoint.
Non-functional
- Low latency overhead on every request (sub-ms to low ms).
- Correct enough across many API servers (shared Redis state).
- High availability of the limiter path; define fail-open vs fail-closed.
Estimation snippet
Peak API QPS: 50k → every request hits limiter → 50k Redis ops/s
Keys: 10M active users/day; only hot keys stay in Redis (TTL)
Memory: ~100B–1KB per active bucket → size for hot set, not all users
Who is limited? user_id | api_key | IP | route
Where enforced? API gateway / sidecar / middleware / service mesh
Accuracy: approximate OK under race? or strict?
2. API / behavior
HTTP response when limited:
429 Too Many Requests
Retry-After: 12
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1710000000
Internal check API (if separate service):
POST /v1/allow
{ "key": "user:42", "cost": 1, "rule": "100/min" }
→ { "allowed": true, "remaining": 87 }
3. Algorithms
| Algorithm | Idea | Pros / cons |
|---|---|---|
| Token bucket | Tokens refill at rate R; request needs 1 token | Allows short bursts; smooth average — interview favorite |
| Leaky bucket | Queue drains at fixed rate | Smooth egress; can add latency |
| Fixed window | Count in [0:60); reset | Simple; burst at window edges (2x) |
| Sliding window log | Store timestamps; count in last T | Accurate; memory heavy |
| Sliding window counter | Weight previous + current window | Good accuracy/cost balance |
Token bucket (conceptual):
tokens = min(capacity, tokens + (now-last)*refill_rate)
if tokens >= cost: tokens -= cost; allow
else deny
4. Data model (Redis)
Key examples:
rl:user:42:tokenbucket → hash { tokens, ts }
rl:ip:1.2.3.4:fw:1710000060 → counter (fixed window)
Use Lua scripts or INCR+EXPIRE carefully for atomicity.
TTL keys so inactive users do not fill Redis forever.
5. High-level design
Client → API Gateway / Rate Limit Middleware
|
+--> Redis (shared counters / buckets)
|
+--allow--> Upstream services
+--deny ---> 429
Place the limiter at the edge so bad traffic never hits app servers. Rules config can live in a control plane (DB + push to gateways).
6. Deep dive — distributed issues
- Race: two nodes INCR without atomic script → over-allow; use Lua or Redis transactions.
- Redis down: fail open (availability) vs fail closed (safety) — product choice; say it.
- Multi-DC: per-region limits + global soft cap, or central Redis with latency cost.
- Costly routes:
cost=5for expensive search vscost=1for ping.
7. Scaling
- Redis Cluster; shard by rate-limit key.
- Local token cache with periodic sync for ultra-low latency (approximate).
- Hot keys (one viral user) → isolate or higher-capacity dedicated path.
8. Edge cases
- Clock skew across gateways → prefer Redis server time inside Lua.
- Retry storms after 429 → clients must honor Retry-After; add jitter.
- Shared NAT IPs → IP limits punish many users; prefer user/api_key.
- Rule config push lag → version rules; stale gateway may over/under allow briefly.
9. What to say aloud
“Token bucket in Redis via Lua at the API gateway, 429 with Retry-After, fail-closed for auth-sensitive APIs, and sliding/fixed window if product wants simpler quotas.”
Quick revision
- Clarify key (user/IP), limit, burst, and fail open vs closed.
- Token bucket = bursts + average rate; fixed window has edge bursts.
- Enforce at gateway; store state in Redis with atomic scripts.
- Return 429 + rate limit headers.
- Idempotent/atomic updates matter under concurrency.
- Multi-region needs explicit accuracy trade-offs.
- Weight expensive endpoints with higher cost.