The rate limiter must decide, for every request, whether it exceeds the limit for its key — user id, IP, or API key — in ~1ms, at a scale of thousands of limiter checks per second across millions of keys. Functional requirements: per-key limits, configurable windows (1/sec to 10K/min), burst tolerance, and 429 responses with Retry-After headers.
The token bucket is the workhorse algorithm: the bucket holds up to capacity tokens, refilling at rate/sec continuously. A request passes if a token is available, else 429. Bursts up to capacity pass instantly; sustained traffic beyond rate is throttled. Alternatives — fixed window (bursty at boundaries), sliding log (exact but memory-heavy) — exist, but token bucket dominates in practice because it needs only two numbers per key.
Storage: Redis, one key per limiter key, holding (tokens, last_refill). The machine stores the bucket state in a Lua script run with EVAL so check-and-refill is atomic — no TOCTOU race between reading, computing tokens, and writing back. At 100K concurrent users × 1 key each with a 60s TTL, that is ~100K Redis keys and roughly 10-50K ops/sec of limiter traffic — one Redis instance handles it; shard by user id hash if it grows.
The bottleneck is never Redis throughput — it is the network round trip on the hot path. The machine mitigates with a local in-memory cache layer that pre-checks approximate limits and only hits Redis on likely violations or every N ms. The shared cache must tolerate drift; the Redis decision is the authoritative one.
Data model: ratelimit:{key} → {tokens: float, last: unix_ms} with TTL = window. Clock skew between app servers must not matter — timestamps come from the Redis server's clock inside the Lua script.
Client → LB → API gateway
└─ local token cache (fast path)
└─ Redis EVAL lua (authoritative)
└─ pass → backend | fail → 429 + Retry-After