Design a Distributed Rate Limiter
Design a rate limiter for a public API that enforces per-user and per-IP request limits at scale. The service must handle high throughput, be deployable across multiple data center regions, and gracefully degrade when the rate-limiting backend is unavailable.
Requirements
- ✓Enforce per-user and per-IP rate limits (e.g., 1,000 requests/minute per user).
- ✓Return a clear 429 response with retry-after headers when limits are exceeded.
- ✓Support multiple limit windows (per-second, per-minute, per-hour).
- ✓The limiter must work across multiple API server instances.
- ✓Degrade gracefully: if the rate-limit store is unreachable, choose fail-open or fail-closed based on product policy.
Constraints & Scale
- —API receives ~500,000 requests/second at peak.
- —Rate limit decisions must add ≤ 2 ms to request latency (p99).
- —The limiter must be consistent across 10+ API nodes in a region.
- —Configurable limits: different limits per API key tier (free, pro, enterprise).
- —No shared memory between API processes — distributed counter required.
Identify the key requirements and constraints. What algorithms are candidates for rate limiting? What does 'distributed' add to the problem compared to a single-server limiter?
Core tension: single-server counters don't work across nodes; distributed counters add network round-trips. The 2 ms latency budget is tight — a Redis call is typically 0.5–1 ms in the same data center. Algorithm choice (token bucket, fixed window, sliding window log, sliding window counter) affects accuracy, memory, and implementation complexity.
Trade-offs
- ⚖Fixed window: simple, low memory, but allows 2× burst at window boundaries.
- ⚖Sliding window log: accurate, but memory grows with request count per user.
- ⚖Sliding window counter (hybrid): accurate within ~0.5% error, O(1) memory — best for most production systems.
- ⚖Token bucket: handles bursts naturally; refill rate maps to sustained limit.
Concepts used in this stage