Case study

Design a Distributed Rate Limiter

Enforce per-user and per-IP request limits globally across thousands of API gateway nodes.

Redistoken bucketAPI gateway

Requirements

Functional: allow/deny request based on rules (100 req/min per API key, 1000/min per IP)
Return 429 Too Many Requests with Retry-After header
Support multiple algorithms: fixed window, sliding window, token bucket
Non-functional: decision latency < 5ms p99; accurate across all gateway nodes
Configurable rules per route, tenant, and tier

Back-of-envelope Estimation

Metric	Calculation	Result
API traffic	50K req/sec peak	Mid-size SaaS platform
Rate-limit checks	1 per request	50K Redis ops/sec
Keys in Redis	10M active API keys	~500 bytes/key → ~5 GB memory
Sliding window log	100 entries × 8 B × 10M keys	Prohibitive — use counters

Accuracy vs cost

Strict sliding window log is accurate but memory-heavy. Token bucket or sliding window counter (Redis INCR + TTL) is the production sweet spot.

API Design

Component	Interface
Middleware hook	allow(key, limit, window) → { allowed, remaining, resetAt }
Admin API POST /rules	Create rule: { match: route+key_type, limit, window, algorithm }
Response headers	X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset
429 body	{ error, retryAfterSeconds }

Data Model

Redis key pattern	Value	TTL
rl:{ruleId}:{clientKey}:tokens	float token count	window duration
rl:{ruleId}:{clientKey}:ts	last refill timestamp ms	window duration
rl:sw:{ruleId}:{clientKey}:{windowSlot}	request count	2× window

Rules stored in config service (etcd) and cached locally on gateways with watch-based updates. Client key derived from API key hash or IP + user ID.

High-level Design

Edge enforcement

Client ──► API Gateway cluster
                    │
                    ├── Local LRU cache (soft limit, 1ms)
                    └── Redis cluster (authoritative, Lua atomic scripts)
                              │
                         Config service (rules)

Every gateway runs rate-limit middleware before routing to backend. Lua script atomically refills and decrements token bucket. Local cache absorbs 80% of checks for hot keys with eventual sync.

Deep Dive: Token Bucket Lua Script

On each request: read tokens and last_refill; compute elapsed × refill_rate; cap at burst size; if tokens ≥ 1, decrement and ALLOW else DENY. Entire operation is O(1) and atomic in Redis.

Burst size = limit (allows short spikes)
Refill rate = limit / window_seconds
Race-free across gateways via single Redis key per client+rule

Deep Dive: Redis Failure Modes

Policy	Behavior	Tradeoff
Fail open	Allow traffic if Redis down	Risk overload; use for non-critical APIs
Fail closed	Reject all	Safer for billing/auth; hurts availability
Local fallback	Conservative in-memory limits	Per-node inaccuracy; prevents total outage

Hot keys

A single viral API key can saturate one Redis shard. Shard rate-limit keys by hash tag or use local token pools with periodic sync for mega-tenants.

Failure Modes & Monitoring

SLO	Target
Check latency p99	< 5ms
False allow rate	< 1% during Redis degradation
429 accuracy	Within 5% of true limit

Dashboard: top limited clients, 429 rate by route, Redis latency
Alert: Redis cluster failover, rule sync lag, sudden 429 spike on single tenant

System Design