Rate Limiting

Token Bucket Algorithm

Token Bucket controls rate by allowing bursts while maintaining average rate.

How it Works

Bucket with capacity C tokens
Refill rate R tokens per second

1. Request arrives
2. If bucket has tokens:
   - Remove one token
   - Allow request
3. If bucket empty:
   - Reject request

Example: C=10, R=2/sec
- Burst: 10 requests instantly
- Sustained: 2 requests/sec

Implementation

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.refill_rate = refill_rate  # tokens per second
        self.tokens = capacity
        self.last_refill = time.time()
        self.lock = threading.Lock()
    
    def allow(self):
        with self.lock:
            self._refill()
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False
    
    def _refill(self):
        now = time.time()
        elapsed = now - self.last_refill
        new_tokens = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + new_tokens)
        self.last_refill = now

# Usage
limiter = TokenBucket(capacity=100, refill_rate=10)  # 100 burst, 10/sec sustained

if limiter.allow():
    process_request()
else:
    return 429  # Too Many Requests

Characteristics

Aspect	Value
Burst handling	Excellent (allows bursts up to capacity)
Memory	O(1)
Accuracy	Good
Complexity	Low

Sliding Window Rate Limiting

Sliding Window tracks requests in a time window that slides forward.

Variants

1. Sliding Window Log:
   Store timestamp of each request
   Count requests in window
   Accurate but memory-heavy

2. Sliding Window Counter:
   Combine current and previous window counts
   Weighted average
   Approximate but efficient

Implementation

class SlidingWindowLog:
    def __init__(self, window_seconds, max_requests):
        self.window = window_seconds
        self.max_requests = max_requests
        self.timestamps = []
        self.lock = threading.Lock()
    
    def allow(self):
        with self.lock:
            now = time.time()
            cutoff = now - self.window
            
            # Remove old timestamps
            self.timestamps = [t for t in self.timestamps if t > cutoff]
            
            if len(self.timestamps) < self.max_requests:
                self.timestamps.append(now)
                return True
            return False

class SlidingWindowCounter:
    def __init__(self, window_seconds, max_requests):
        self.window = window_seconds
        self.max_requests = max_requests
        self.prev_count = 0
        self.curr_count = 0
        self.window_start = time.time()
    
    def allow(self):
        now = time.time()
        self._rotate_window(now)
        
        # Weighted count
        elapsed = now - self.window_start
        weight = 1 - (elapsed / self.window)
        estimated = self.prev_count * weight + self.curr_count
        
        if estimated < self.max_requests:
            self.curr_count += 1
            return True
        return False
    
    def _rotate_window(self, now):
        if now - self.window_start >= self.window:
            self.prev_count = self.curr_count
            self.curr_count = 0
            self.window_start = now

Comparison

Method	Accuracy	Memory	Performance
Log	Exact	High	Medium
Counter	Approximate	Low	High

Leaky Bucket Algorithm

Leaky Bucket processes requests at a fixed rate, smoothing bursts.

How it Works

Bucket with capacity C
Leak rate R per second

1. Request arrives
2. If bucket not full:
   - Add to bucket
   - Allow request
3. If bucket full:
   - Reject request

Requests processed at constant rate R
Bursts are smoothed out

Implementation

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.leak_rate = leak_rate  # requests per second
        self.water = 0  # current water level
        self.last_leak = time.time()
        self.lock = threading.Lock()
    
    def allow(self):
        with self.lock:
            self._leak()
            if self.water < self.capacity:
                self.water += 1
                return True
            return False
    
    def _leak(self):
        now = time.time()
        elapsed = now - self.last_leak
        leaked = elapsed * self.leak_rate
        self.water = max(0, self.water - leaked)
        self.last_leak = now

Token Bucket vs Leaky Bucket

Aspect	Token Bucket	Leaky Bucket
Burst handling	Allows bursts	Smooths bursts
Output rate	Variable	Fixed
Use case	API rate limiting	Traffic shaping

Distributed Rate Limiting

Challenges

Problem:
- Multiple nodes
- Need global rate limit
- Network latency
- Race conditions

Solutions

1. Centralized:
   Single rate limit service
   Simple but single point of failure

2. Distributed with Redis:
   Use Redis for coordination
   Atomic operations

3. Local + Synchronization:
   Local rate limiting
   Periodic sync between nodes

4. Consistent Hashing:
   Route by client ID
   Each node limits its shard

Redis Implementation

class DistributedRateLimiter:
    def __init__(self, redis_client, rate, window):
        self.redis = redis_client
        self.rate = rate
        self.window = window
    
    def allow(self, key):
        """Sliding window with Redis"""
        now = time.time()
        window_start = now - self.window
        
        pipe = self.redis.pipeline()
        pipe.zremrangebyscore(key, 0, window_start)  # Remove old
        pipe.zadd(key, {str(now): now})  # Add current
        pipe.zcard(key)  # Count
        pipe.expire(key, self.window)  # Set TTL
        
        results = pipe.execute()
        request_count = results[2]
        
        return request_count <= self.rate

# Usage
limiter = DistributedRateLimiter(redis, rate=100, window=60)

if limiter.allow(f"user:{user_id}"):
    process_request()
else:
    return 429

Strategies

Strategy	Consistency	Performance	Complexity
Centralized	Strong	Low	Low
Redis	Strong	High	Medium
Local + Sync	Eventual	Highest	High
Consistent Hash	Per-shard	High	Medium

Best Practices

1. Use Redis for distributed rate limiting
2. Implement local caching for hot keys
3. Handle Redis failures gracefully
4. Monitor rate limit metrics
5. Provide clear error responses (429 + Retry-After)