Rate Limiting & Throttling - Technical.
Interview cheat sheet.

Essential guide to rate limiting for system design interviews. Covers algorithms (token bucket, sliding window), implementation strategies, distributed rate limiting, and real-world applications. Critical for protecting APIs, preventing DDoS attacks, and ensuring fair resource usage.

What is Rate Limiting?

• Definition: Mechanism to control the rate of requests a user/client can make to a service
• Purpose: Prevent abuse, ensure fair usage, protect resources, maintain QoS

Rate Limiting vs Throttling

• Rate Limiting: Hard limit - requests exceeding limit are rejected (429 Too Many Requests)
• Throttling: Soft limit - requests are delayed/queued rather than rejected

• Rate: Number of requests per time unit (e.g., 100 req/min)
• Burst: Maximum requests allowed in short time
• Window: Time period for counting requests
• Quota: Total allowed requests in a period

1. Token Bucket

How it works: Bucket holds tokens, requests consume tokens, tokens refill at fixed rate

Pros: Allows bursts, smooth rate limiting
Cons: Memory per user, complex implementation

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate
        self.last_refill = time.time()
    
    def allow_request(self):
        self.refill()
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False
    
    def refill(self):
        now = time.time()
        tokens_to_add = (now - self.last_refill) * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + tokens_to_add)
        self.last_refill = now

2. Leaky Bucket

How it works: Requests enter bucket, leak out at constant rate

Pros: Smooth output rate, prevents bursts
Cons: Can drop requests, less flexible

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.queue = []
        self.leak_rate = leak_rate
        self.last_leak = time.time()
    
    def allow_request(self, request):
        self.leak()
        if len(self.queue) < self.capacity:
            self.queue.append(request)
            return True
        return False
    
    def leak(self):
        now = time.time()
        leak_count = int((now - self.last_leak) * self.leak_rate)
        self.queue = self.queue[leak_count:]
        self.last_leak = now

3. Fixed Window Counter

How it works: Count requests in fixed time windows (e.g., per minute)

Pros: Simple, memory efficient
Cons: Burst at window boundaries (2x rate possible)

class FixedWindow:
    def __init__(self, window_size, limit):
        self.window_size = window_size
        self.limit = limit
        self.windows = {}
    
    def allow_request(self, user_id):
        window = int(time.time() / self.window_size)
        key = f"{user_id}:{window}"
        
        count = self.windows.get(key, 0)
        if count < self.limit:
            self.windows[key] = count + 1
            return True
        return False

4. Sliding Window Log

How it works: Store timestamp of each request, count recent requests

Pros: Accurate, no boundary issues
Cons: High memory usage

class SlidingWindowLog:
    def __init__(self, window_size, limit):
        self.window_size = window_size
        self.limit = limit
        self.requests = {}
    
    def allow_request(self, user_id):
        now = time.time()
        window_start = now - self.window_size
        
        # Clean old entries
        if user_id in self.requests:
            self.requests[user_id] = [
                ts for ts in self.requests[user_id] 
                if ts > window_start
            ]
        else:
            self.requests[user_id] = []
        
        if len(self.requests[user_id]) < self.limit:
            self.requests[user_id].append(now)
            return True
        return False

5. Sliding Window Counter

How it works: Hybrid of fixed window and sliding log

Formula:

rate = prev_window_count * ((window_size - elapsed) / window_size) + curr_window_count

Pros: Memory efficient, smoother than fixed window
Cons: Approximation, not 100% accurate

class SlidingWindowCounter:
    def __init__(self, window_size, limit):
        self.window_size = window_size
        self.limit = limit
        self.counters = {}
    
    def allow_request(self, user_id):
        now = time.time()
        curr_window = int(now / self.window_size)
        prev_window = curr_window - 1
        
        curr_key = f"{user_id}:{curr_window}"
        prev_key = f"{user_id}:{prev_window}"
        
        curr_count = self.counters.get(curr_key, 0)
        prev_count = self.counters.get(prev_key, 0)
        
        elapsed = now % self.window_size
        weight = (self.window_size - elapsed) / self.window_size
        rate = prev_count * weight + curr_count
        
        if rate < self.limit:
            self.counters[curr_key] = curr_count + 1
            return True
        return False

Challenges

1. Synchronization: Multiple servers need consistent view
2. Latency: Network calls add overhead
3. Race conditions: Concurrent updates

Solutions

1. Centralized Store (Redis)

def allow_request_redis(user_id, limit, window):
    key = f"rate_limit:{user_id}:{int(time.time() / window)}"
    
    pipe = redis.pipeline()
    pipe.incr(key)
    pipe.expire(key, window)
    count = pipe.execute()[0]
    
    return count <= limit

2. Distributed Tokens

• Divide rate limit across servers
• Each server manages portion of tokens
• Periodic rebalancing

3. Eventual Consistency

• Local counters with periodic sync
• Accept temporary over-limit
• Good for high-throughput systems

Where to Implement

1. API Gateway: Centralized, before reaching services
2. Load Balancer: Network level protection
3. Application Layer: Fine-grained control
4. CDN/Edge: Closest to users

Rate Limit Headers

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 45
X-RateLimit-Reset: 1672531200
Retry-After: 120

Configuration Patterns

rate_limits:
  - path: /api/*
    limit: 1000
    window: 3600  # 1 hour
  - path: /api/expensive/*
    limit: 10
    window: 60    # 1 minute
  - user_tier: premium
    limit: 10000
    window: 3600

1. Hierarchical Rate Limiting

• User → API Key → IP → Global
• Different limits at each level

2. Dynamic Rate Limiting

• Adjust limits based on:
  • System load
  • Time of day
  • User behavior
  • Resource availability

3. Cost-Based Rate Limiting

• Assign cost to operations
• Complex queries cost more
• Budget instead of count

class CostBasedLimiter:
    def allow_request(self, user_id, cost):
        budget = self.get_remaining_budget(user_id)
        if budget >= cost:
            self.deduct_budget(user_id, cost)
            return True
        return False

4. Adaptive Rate Limiting

• Machine learning based
• Detect patterns
• Prevent abuse proactively

Storage Requirements

Choosing an Algorithm

• High accuracy needed: Sliding Window Log
• Memory constrained: Fixed Window or Sliding Counter
• Burst traffic OK: Token Bucket
• Smooth rate required: Leaky Bucket
• Simple implementation: Fixed Window

1. Race Conditions: Use atomic operations
2. Clock Skew: In distributed systems
3. Memory Leaks: Clean up old data
4. DDoS: Rate limiting alone isn't enough
5. Business Logic: Don't rate limit critical paths

Questions to Expect

1. "Design a rate limiter for Twitter"
2. "How would you handle distributed rate limiting?"
3. "Trade-offs between algorithms?"
4. "How to handle burst traffic?"

Key Points to Mention

1. Scalability: How it scales with users
2. Accuracy vs Performance: Trade-offs
3. Failure Modes: What if Redis is down?
4. Monitoring: Metrics and alerting
5. User Experience: Graceful degradation

Design Approach

1. Clarify Requirements

   • Request rate? (100 req/s, 1000 req/hour?)
   • Scope? (Per user, API key, IP?)
   • Accuracy needs?
   • Distributed system?

2. High-Level Design

   • Where to place limiter
   • Algorithm choice
   • Storage system

3. Detailed Design

   • API design
   • Data structures
   • Handling edge cases

4. Scale & Optimize

   • Caching strategies
   • Sharding approach
   • Performance optimization

Twitter Rate Limiter

Requirements:
- 300 tweets/3 hours per user
- 100 follows/hour
- Real-time enforcement

Design:
1. API Gateway with rate limiting
2. Redis cluster for counters
3. Sliding window counter algorithm
4. Separate limits per operation
5. Async logging for analytics

Implementation Sketch

class TwitterRateLimiter:
    def __init__(self):
        self.limits = {
            'tweet': (300, 10800),    # 300 per 3 hours
            'follow': (100, 3600),    # 100 per hour
            'like': (1000, 3600)      # 1000 per hour
        }
    
    def check_rate_limit(self, user_id, action):
        limit, window = self.limits[action]
        key = f"{action}:{user_id}:{int(time.time() / window)}"
        
        count = redis.incr(key)
        if count == 1:
            redis.expire(key, window)
        
        if count > limit:
            ttl = redis.ttl(key)
            return False, ttl
        
        return True, None

Key Metrics

• Request rate per endpoint
• Rate limit violations
• P95/P99 latencies
• Cache hit rates
• Error rates

Alerting Rules

• Sudden spike in 429 errors
• Redis connection failures
• Memory usage trends
• Unusual traffic patterns

1. Start Conservative: Easier to increase limits
2. Clear Error Messages: Help users understand limits
3. Graceful Degradation: Don't break on limiter failure
4. Test at Scale: Load test rate limiting
5. Document Limits: Public API documentation
6. Multiple Strategies: Combine algorithms for robustness
7. Audit Logging: Track rate limit decisions
8. Circuit Breakers: Fail open if limiter fails

When to Use What

• API Gateway: Token bucket for flexible limits
• DDoS Protection: Fixed window at edge
• Database Protection: Leaky bucket for smooth load
• Microservices: Sliding window counter for accuracy
• Real-time Systems: In-memory token bucket

Common Limits

• GitHub API: 5000 req/hour
• Twitter API: 300 req/15-min window
• Google Maps: 1000 req/day free tier
• Stripe API: 100 req/sec

Remember for Interviews

1. There's no perfect algorithm - discuss trade-offs
2. Consider the full system, not just the algorithm
3. Think about failure scenarios
4. Mention monitoring and operations
5. Start simple, add complexity as needed