> ## Documentation Index > Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt > Use this file to discover all available pages before exploring further. # Design: Rate Limiter > System design for distributed rate limiting ![Rate Limiting Algorithms](https://mintcdn.com/devweeekends/2f8Rfaato9LS1FSq/images/system-design/rate-limiting.svg?fit=max\&auto=format\&n=2f8Rfaato9LS1FSq\&q=85\&s=62d39400bc5ed9a78f25e25add54eac6) ## Problem Statement Design a rate limiter that: * Limits requests per user/API key to prevent abuse * Works across multiple servers (distributed) * Has minimal latency impact * Supports different rate limits per tier > [!NOTE] > > This is a **medium** difficulty problem but very important! Rate limiting is asked frequently because it touches on distributed systems concepts. Know the algorithms well! ## Step 1: Requirements ### Functional Requirements * Limit requests per user/IP/API key * Different limits for different endpoints * Different tiers (free: 100/hour, paid: 10,000/hour) * Return appropriate error when limit exceeded ### Non-Functional Requirements * **Low Latency**: \< 10ms overhead per request * **Accurate**: No significant over-limiting or under-limiting * **Distributed**: Work across multiple servers * **Fault Tolerant**: Fail open if rate limiter is down ### Quick Estimation ``` ┌─────────────────────────────────────────────────────────────────┐ │ Scale Estimation │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ API Traffic: │ │ • 10 million API calls per hour (peak) │ │ • 10M / 3600 = ~2,800 requests per second │ │ │ │ Users: │ │ • 1 million unique users/API keys │ │ │ │ Storage per user (sliding window): │ │ • User ID: 16 bytes │ │ • Counter: 8 bytes │ │ • Window timestamp: 8 bytes │ │ • ~32 bytes per user │ │ • 1M users × 32 bytes = 32 MB │ │ │ │ Very lightweight! Redis can handle this easily │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ## Step 2: Rate Limiting Algorithms ### Algorithm 1: Token Bucket ⭐ (Most Common) ``` ┌─────────────────────────────────────────────────────────────────┐ │ Token Bucket │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ Concept: Bucket holds tokens, requests consume tokens │ │ Tokens are added at a fixed rate │ │ │ │ Parameters: │ │ • bucket_capacity = 10 tokens (max burst) │ │ • refill_rate = 1 token/second │ │ │ │ Time 0s Time 1s Time 2s Time 3s │ │ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │ │ │█████│ │████ │ │███ │ │████ │ │ │ │█████│ │████ │ │███ │ │████ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └─────┘ └─────┘ └─────┘ └─────┘ │ │ 10/10 8/10 6/10 7/10 │ │ │ │ t=0: Start with 10 tokens │ │ t=1: 2 requests used 2 tokens, 1 refilled → 9 tokens │ │ Wait... 2-1=8 tokens │ │ t=2: 3 requests, 1 refilled → 8-3+1 = 6 tokens │ │ t=3: 0 requests, 1 refilled → 7 tokens │ │ │ │ Pros: Simple, allows bursts, smooth rate │ │ Cons: Need to track per-user bucket state │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ```python theme={null} class TokenBucket: def __init__(self, capacity: int, refill_rate: float): self.capacity = capacity # Max tokens self.refill_rate = refill_rate # Tokens per second self.tokens = capacity self.last_refill = time.time() def allow_request(self) -> bool: # Refill tokens based on time elapsed now = time.time() time_elapsed = now - self.last_refill new_tokens = time_elapsed * self.refill_rate self.tokens = min(self.capacity, self.tokens + new_tokens) self.last_refill = now # Check if we have tokens if self.tokens >= 1: self.tokens -= 1 return True return False ``` ### Algorithm 2: Sliding Window Log ``` ┌─────────────────────────────────────────────────────────────────┐ │ Sliding Window Log │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ Concept: Store timestamp of each request, count in window │ │ │ │ Limit: 5 requests per minute │ │ │ │ Timeline: │ │ ──────────────────────────────────────────────────────► │ │ | 10s | 20s | 30s | 40s | 50s | 60s | │ │ ● ● ● ● ● │ │ req1 req2 req3 req4 req5 │ │ │ │ At t=65s, new request comes: │ │ • Window: [5s, 65s] │ │ • Remove req1 (at 10s, outside window) │ │ • Count remaining: 4 requests │ │ • 4 < 5, so ALLOW │ │ │ │ Storage: Redis Sorted Set │ │ ZADD rate:user123 │ │ ZREMRANGEBYSCORE rate:user123 0 │ │ ZCARD rate:user123 │ │ │ │ Pros: Very accurate │ │ Cons: Memory intensive (stores every request) │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ### Algorithm 3: Sliding Window Counter (Recommended) ``` ┌─────────────────────────────────────────────────────────────────┐ │ Sliding Window Counter │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ Concept: Combine fixed window with weighted average │ │ │ │ Limit: 100 requests per minute │ │ │ │ Previous window Current window │ │ ┌─────────────────┬─────────────────┐ │ │ │ │ ● │ │ │ │ 84 req │ 15 req │ │ │ │ │ (so far) │ │ │ └─────────────────┴─────────────────┘ │ │ ▲ │ │ Current time │ │ (25% into current window) │ │ │ │ Weighted count = prev × (1 - position) + current │ │ = 84 × 0.75 + 15 │ │ = 63 + 15 │ │ = 78 │ │ │ │ 78 < 100, so ALLOW │ │ │ │ Pros: Memory efficient (just 2 counters), accurate enough │ │ Cons: Slight approximation │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ```python theme={null} class SlidingWindowCounter: """ Memory-efficient sliding window using two fixed windows """ def __init__(self, redis, limit: int, window_seconds: int): self.redis = redis self.limit = limit self.window_seconds = window_seconds def allow_request(self, user_id: str) -> bool: now = time.time() current_window = int(now // self.window_seconds) previous_window = current_window - 1 # Position within current window (0.0 to 1.0) position = (now % self.window_seconds) / self.window_seconds # Get counts from Redis current_key = f"rate:{user_id}:{current_window}" previous_key = f"rate:{user_id}:{previous_window}" current_count = int(self.redis.get(current_key) or 0) previous_count = int(self.redis.get(previous_key) or 0) # Weighted average estimated_count = previous_count * (1 - position) + current_count if estimated_count >= self.limit: return False # Increment current window counter pipe = self.redis.pipeline() pipe.incr(current_key) pipe.expire(current_key, self.window_seconds * 2) pipe.execute() return True ``` ## Step 3: Algorithm Comparison | Algorithm | Memory | Accuracy | Complexity | Best For | | - | - | - | - | - | | **Token Bucket** | O(1) per user | Good | Simple | General use, allows bursts | | **Leaky Bucket** | O(1) per user | Good | Simple | Smooth output rate | | **Fixed Window** | O(1) per user | Poor at edges | Very simple | When accuracy less important | | **Sliding Log** | O(N) per user | Perfect | Medium | When accuracy critical | | **Sliding Counter** | O(1) per user | Very good | Medium | Best balance ⭐ | ## Step 4: High-Level Design ``` ┌─────────────────────────────────────────────────────────────────┐ │ Rate Limiter Architecture │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────┐ │ │ │ Client │ │ │ └────┬────┘ │ │ │ │ │ ▼ │ │ ┌──────────┐ │ │ │ API │ │ │ │ Gateway │ │ │ └────┬─────┘ │ │ │ │ │ ▼ │ │ ┌─────────────────┐ │ │ │ Rate Limiter │◄──── Where to put it? │ │ │ Middleware │ • API Gateway (recommended) │ │ └────────┬────────┘ • Application layer │ │ │ • Separate service │ │ │ │ │ ┌─────────▼─────────┐ │ │ │ Redis Cluster │ │ │ │ (Rate Counter) │ │ │ └───────────────────┘ │ │ │ │ │ ┌───────┴───────┐ │ │ │ │ │ │ ALLOWED REJECTED │ │ │ │ │ │ ▼ ▼ │ │ ┌────────┐ ┌────────┐ │ │ │ Process │ │ 429 │ │ │ │ Request │ │ Error │ │ │ └────────┘ └────────┘ │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ### Response Headers ```http theme={null} HTTP/1.1 200 OK X-RateLimit-Limit: 100 X-RateLimit-Remaining: 45 X-RateLimit-Reset: 1640000000 # When rate limited: HTTP/1.1 429 Too Many Requests Retry-After: 30 X-RateLimit-Limit: 100 X-RateLimit-Remaining: 0 X-RateLimit-Reset: 1640000000 ``` ## Step 5: Distributed Rate Limiting ### Challenge: Multiple Servers ``` ┌─────────────────────────────────────────────────────────────────┐ │ Distributed Challenge │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ Problem: User requests hit different servers │ │ │ │ User A (limit: 10/min) │ │ │ │ │ ┌───────┼───────┐ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ ┌──────┐┌──────┐┌──────┐ │ │ │Srv 1 ││Srv 2 ││Srv 3 │ │ │ │ 3req ││ 4req ││ 5req │ │ │ └──────┘└──────┘└──────┘ │ │ │ │ Each server thinks: "Only a few requests, allow!" │ │ Total: 12 requests (exceeded limit!) │ │ │ │ Solutions: │ │ ────────── │ │ 1. Centralized counter (Redis) ← Recommended │ │ 2. Sticky sessions (same user → same server) │ │ 3. Sync counters between servers (complex) │ │ 4. Split limit across servers (10/3 ≈ 3 per server) │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ### Redis-Based Solution ```python theme={null} class DistributedRateLimiter: """ Uses Redis for distributed rate limiting with Lua script for atomic check-and-increment """ SLIDING_WINDOW_SCRIPT = """ local key = KEYS[1] local window_size = tonumber(ARGV[1]) local limit = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local window_start = now - window_size -- Remove old entries redis.call('ZREMRANGEBYSCORE', key, 0, window_start) -- Count current entries local count = redis.call('ZCARD', key) if count < limit then -- Add new request redis.call('ZADD', key, now, now .. ':' .. math.random()) redis.call('EXPIRE', key, window_size) return {1, limit - count - 1} -- allowed, remaining else return {0, 0} -- rejected, 0 remaining end """ def __init__(self, redis_client, limit: int, window_seconds: int): self.redis = redis_client self.limit = limit self.window_seconds = window_seconds self.script = self.redis.register_script(self.SLIDING_WINDOW_SCRIPT) def allow_request(self, user_id: str) -> Tuple[bool, int]: key = f"rate:{user_id}" now = time.time() result = self.script( keys=[key], args=[self.window_seconds, self.limit, now] ) allowed = result[0] == 1 remaining = result[1] return allowed, remaining ``` ## Step 6: Rate Limiting by Tier ```python theme={null} class TieredRateLimiter: """ Different rate limits for different user tiers """ TIER_LIMITS = { "free": { "requests_per_minute": 60, "requests_per_day": 1000, }, "basic": { "requests_per_minute": 600, "requests_per_day": 10000, }, "pro": { "requests_per_minute": 6000, "requests_per_day": 100000, }, "enterprise": { "requests_per_minute": 60000, "requests_per_day": 1000000, } } def check_rate_limit(self, user_id: str, tier: str) -> RateLimitResult: limits = self.TIER_LIMITS[tier] # Check minute limit minute_key = f"rate:{user_id}:minute" minute_count = self.redis.incr(minute_key) if minute_count == 1: self.redis.expire(minute_key, 60) if minute_count > limits["requests_per_minute"]: return RateLimitResult( allowed=False, reason="minute_limit", retry_after=self.redis.ttl(minute_key) ) # Check daily limit day_key = f"rate:{user_id}:day:{date.today()}" day_count = self.redis.incr(day_key) if day_count == 1: self.redis.expire(day_key, 86400) if day_count > limits["requests_per_day"]: return RateLimitResult( allowed=False, reason="daily_limit", retry_after=self.redis.ttl(day_key) ) return RateLimitResult( allowed=True, remaining_minute=limits["requests_per_minute"] - minute_count, remaining_day=limits["requests_per_day"] - day_count ) ``` ## Step 7: Complete Architecture ``` ┌─────────────────────────────────────────────────────────────────┐ │ Complete Rate Limiter System │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────────────────────────────────────┐ │ │ │ API Gateway │ │ │ │ ┌───────────────────────────────────┐ │ │ │ │ │ Rate Limiter Middleware │ │ │ │ │ └───────────────┬───────────────────┘ │ │ │ └──────────────────┼──────────────────────┘ │ │ │ │ │ ┌───────────────┼───────────────┐ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │ │ Redis │ │ Redis │ │ Redis │ │ │ │ Primary │◄──►│ Replica │◄──►│ Replica │ │ │ └─────────┘ └─────────┘ └─────────┘ │ │ │ │ Config Store (Rules): │ │ ┌─────────────────────────────────────────────────────────┐│ │ │ /api/v1/* → 100 req/min (default) ││ │ │ /api/v1/auth → 10 req/min (stricter) ││ │ │ /api/v1/data → 1000 req/min (relaxed) ││ │ │ tier:free → 60 req/min ││ │ │ tier:pro → 6000 req/min ││ │ └─────────────────────────────────────────────────────────┘│ │ │ │ Monitoring: │ │ • Rate limited requests per endpoint │ │ • Users hitting limits frequently │ │ • Redis latency metrics │ │ • Alert when rejection rate > threshold │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` ## Key Design Decisions | Decision | Choice | Reasoning | | - | - | - | | **Algorithm** | Sliding Window Counter | Best memory/accuracy trade-off | | **Storage** | Redis | Fast, atomic operations, built-in expiry | | **Location** | API Gateway | Catch early, reduce backend load | | **Failure Mode** | Fail open | Availability over protection | | **Atomicity** | Lua scripts | Avoid race conditions | ## Common Interview Questions > **What if Redis is down?** > > **Fail open strategy**: > > 1. If Redis unavailable, allow all requests > 2. Log warning for monitoring > 3. Availability > perfect rate limiting > 4. Have backup local rate limiter (approximate) > > **Alternative**: Fail closed for critical endpoints (auth, payments) > **How to handle distributed clock skew?** > > 1. Use Redis server time, not client time > 2. Redis `TIME` command for consistency > 3. NTP sync on all servers > 4. Allow small tolerance in window boundaries > **How to rate limit by IP vs API key?** > > **Layer the limits**: > > ``` > 1. IP-based limit (rough, for unauthenticated) > 2. API key limit (main rate limit) > 3. User account limit (cross all keys) > > Check all three, reject if any exceeded > ``` > **How to prevent race conditions?** > > Use atomic operations: > > 1. Redis Lua scripts (atomic execution) > 2. INCR command (atomic increment) > 3. WATCH/MULTI/EXEC (optimistic locking) > > ```lua theme={null} > -- Atomic check and increment > local count = redis.call('INCR', key) > if count == 1 then > redis.call('EXPIRE', key, window) > end > return count > ``` > **How to handle burst traffic?** > > 1. Token bucket naturally allows bursts up to capacity > 2. Use higher limit with shorter window > 3. Queue excess requests instead of rejecting > 4. Implement retry with exponential backoff on client > 5. Consider adaptive rate limiting based on system load ## Quick Reference Card ``` ┌─────────────────────────────────────────────────────────────────┐ │ Rate Limiter Cheat Sheet │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ When asked about rate limiter, mention: │ │ │ │ 1. Algorithm choice (usually sliding window counter) │ │ 2. Redis for distributed counter │ │ 3. Lua script for atomicity │ │ 4. Put in API Gateway layer │ │ 5. Different limits per tier │ │ 6. Fail open strategy │ │ 7. Return headers: X-RateLimit-Remaining, Retry-After │ │ 8. Monitor: rejection rate, users hitting limits │ │ │ │ Redis commands: │ │ • INCR key - increment counter │ │ • EXPIRE key sec - set TTL │ │ • ZADD set score - sorted set (sliding log) │ │ • ZREMRANGEBYSCORE - clean old entries │ │ • ZCARD set - count entries │ │ │ └─────────────────────────────────────────────────────────────────┘ ``` This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.