Walkthrough 2 — Design a Rate Limiter

# Design a Rate Limiter ## The brief Build a rate-limiting service for an API gateway. Enforce per-user and per-IP limits across distributed gateway instances. ## Step 1: Requirements - Per-user limits (e.g., 100 req/min for free, 10K req/min for pro). - Per-IP limits (anti-abuse). - Per-endpoint limits (expensive endpoints get tighter quotas). - Distributed: 10+ gateway instances share state. - Low latency: each check < 5ms. - Graceful degradation if rate-limit service is down. ## Step 2: Pick an algorithm Compare: - **Token bucket**: bursty-tolerant; simple. - **Sliding window log**: accurate; memory-heavy. - **Sliding window counter**: good accuracy, low memory. **Best choice.** Sliding window counter: - Current window count + (previous window count × overlap fraction). - Reset every window (e.g., 60s). - Memory: 2 counters per (user, endpoint). ## Step 3: Storage Redis is the canonical choice: - Atomic INCR. - TTL for window expiration. - Fast (< 1ms per check). Schema: ``` Key: rate_limit:{user_id}:{endpoint}:{window_id} Value: counter TTL: 2 × window_size ``` ## Step 4: Algorithm pseudo-code ```python def is_allowed(user_id, endpoint, limit, window_sec): now = int(time.time()) current_window = now // window_sec previous_window = current_window - 1 current_count = redis.incr(f"rl:{user_id}:{endpoint}:{current_window}") redis.expire(f"rl:{user_id}:{endpoint}:{current_window}", 2 * window_sec) previous_count = int(redis.get(f"rl:{user_id}:{endpoint}:{previous_window}") or 0) elapsed_in_current = (now % window_sec) / window_sec overlap_fraction = 1 - elapsed_in_current effective_count = current_count + previous_count * overlap_fraction if effective_count > limit: return False return True ``` ## Step 5: Architecture ``` [Client] ↓ [API Gateway (many instances)] ↓ (check rate limit) [Rate Limiter Service (or library call to Redis)] ↓ [Redis Cluster] ``` In practice: most gateways have rate limiting as a library call from each gateway instance to Redis. No need for a separate service. ## Step 6: Configuration Limits need to be configurable per user, tier, endpoint: ```json { "free_tier": { "default": "100/min", "/api/expensive": "10/min" }, "pro_tier": { "default": "10000/min", "/api/expensive": "1000/min" } } ``` Stored in a config service (Consul, etc.) or DB. Loaded by gateway with caching. ## Step 7: Rate-limit response When over limit: ``` HTTP/1.1 429 Too Many Requests X-RateLimit-Limit: 100 X-RateLimit-Remaining: 0 X-RateLimit-Reset: 1614556800 Retry-After: 60 Content-Type: application/json {"error": "rate_limit_exceeded", "limit": 100, "window": "1 minute"} ``` Client implements exponential backoff. ## Step 8: Graceful degradation If Redis is down: - **Fail open** (allow all requests): better UX, but no protection. - **Fail closed** (reject all): protects backend but visible outage. - **Local fallback**: each gateway falls back to per-instance counters (allows more than intended but still bounded). Choice depends on use case: payments → fail closed; non-critical → fail open with alerting. ## Step 9: Scaling For very high QPS (millions/sec): - **Redis Cluster**: shard by user_id. - **Hot users**: a single celebrity user might exceed one Redis node. Shard their key across multiple nodes (read-then-aggregate). - **Local approximation**: each gateway maintains a local counter; periodically syncs to Redis. Less accurate but no per-request Redis call. For most apps: single Redis instance handles 100K+ ops/sec; sufficient. ## Step 10: Monitoring Metrics: - Rate-limit hits per user/endpoint. - 429 response rate. - Redis latency from gateway. - Cache hit rate (for limit configuration). Alerts: - High 429 rate (legitimate users being throttled?). - Redis latency spikes (rate-limit service degraded). ## Common follow-ups - **What if user has variable limits (paid by usage)?** Real-time quota updates from billing service. - **What about burst tolerance?** Add a token-bucket layer on top of sliding window. - **What if Redis dies mid-window?** TTL ensures stale data clears; brief inaccuracy acceptable. - **API key vs user_id?** Same algorithm; different key. ## Self-rubric - [ ] Chose appropriate algorithm (sliding window counter) - [ ] Identified Redis as storage; explained atomicity - [ ] Wrote correct pseudo-code (including overlap fraction) - [ ] Designed 429 response with proper headers - [ ] Handled graceful degradation - [ ] Discussed scaling (Redis Cluster, hot keys) - [ ] Identified monitoring needs ## Deliverables - Algorithm pseudo-code. - Architecture diagram. - Configuration format. - 429 response format.