Rate Limiting and Throttling

The Fixed Window Counter Algorithm

The fixed window algorithm is the most straightforward approach to rate limiting. It works by dividing time into discrete, equal-sized windows, such as one-minute intervals. For each request, the system increments a counter associated with the user or IP address within the current window. If the counter exceeds the predefined limit, the system rejects subsequent requests until the next window begins. The primary reasoning behind this method is its simplicity and efficiency; it requires minimal memory and computation. However, it suffers from a significant edge-case vulnerability: if a burst of traffic occurs precisely at the boundary between two windows, the system might allow double the intended limit within a very short duration. This occurs because the window resets instantly at the start of a new period, ignoring activity from the immediate past. Despite this, it remains useful for non-critical services where precise traffic shaping is less important than overhead minimization.

class FixedWindowCounter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.count = 0
        self.start_time = 0

    def allow_request(self, current_time):
        # Reset window if current_time exceeds window boundaries
        if current_time - self.start_time > self.window_size:
            self.start_time = current_time
            self.count = 0
        
        if self.count < self.limit:
            self.count += 1
            return True
        return False

Sliding Window Log

To solve the boundary issue of the fixed window approach, the sliding window log keeps a timestamp of every request made by a user within a rolling duration. When a new request arrives, the system removes all timestamps that are older than the current time minus the window size. It then checks the length of the remaining log; if the count is below the limit, the request is processed, and its timestamp is appended to the log. This method provides strict enforcement because it effectively smooths out traffic spikes across the entire window rather than just the fixed segments. The reasoning is that memory-based accuracy is prioritized over performance. While more precise, this approach is memory-intensive because it stores individual timestamps for every request, which can lead to high storage costs if millions of users are active simultaneously. It is best applied when high-value transactions require absolute strictness.

import collections

class SlidingWindowLog:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.logs = collections.deque()

    def allow_request(self, current_time):
        # Remove expired timestamps
        while self.logs and self.logs[0] <= current_time - self.window_size:
            self.logs.popleft()
        
        if len(self.logs) < self.limit:
            self.logs.append(current_time)
            return True
        return False

Leaky Bucket Algorithm

The leaky bucket algorithm is designed to smooth out irregular traffic flows into a steady, constant stream. Imagine a bucket with a small hole at the bottom; incoming requests enter the bucket as water. The bucket drains at a fixed, constant rate, representing the processing capacity of the server. If the incoming traffic exceeds the capacity of the bucket, the excess is discarded or dropped. The reasoning here is that it protects downstream systems from 'bursty' traffic that could lead to cascading failures or latency spikes. By strictly enforcing a constant outflow, it ensures the backend remains within its optimal operating parameters regardless of how fast requests arrive initially. This is particularly useful in systems where predictable load is more critical than handling sudden bursts of activity. It trades off response time for stability, as requests that would otherwise be processed quickly might be delayed by the bucket's drainage rate.

import time

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.leak_rate = leak_rate # requests per second
        self.water = 0
        self.last_leak_time = time.time()

    def allow_request(self):
        # Calculate leakage based on elapsed time
        now = time.time()
        elapsed = now - self.last_leak_time
        self.water = max(0, self.water - (elapsed * self.leak_rate))
        self.last_leak_time = now
        
        if self.water < self.capacity:
            self.water += 1
            return True
        return False

Token Bucket Algorithm

The token bucket algorithm provides a balance between the strictness of the leaky bucket and the flexibility needed to handle natural traffic bursts. In this model, a bucket is filled with tokens at a fixed rate, up to a maximum capacity. Each request consumes one token to proceed; if no tokens are available, the request is throttled. The reasoning for this approach is that it allows a user to consume a burst of tokens if they haven't sent requests for a while, effectively allowing for temporary 'burstiness' up to the defined bucket capacity. Once the burst is exhausted, the system reverts to the constant refill rate. This provides a much better user experience than the leaky bucket for interactive applications where users occasionally perform multiple rapid actions. It is highly configurable and can be tuned specifically to the needs of different tiers of users by adjusting refill rates or bucket sizes.

import time

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()

    def consume(self):
        # Refill based on time elapsed
        now = time.time()
        self.tokens = min(self.capacity, self.tokens + (now - self.last_refill) * self.refill_rate)
        self.last_refill = now
        
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Distributed Rate Limiting

In a distributed system, individual instances of an application must synchronize their state to enforce a unified rate limit across the entire cluster. If local counters were used, a user could circumvent limits by spreading requests across multiple load-balanced servers. To prevent this, we utilize a centralized data store, such as an in-memory cache, to maintain a global counter for each user. When a request hits any node, the node communicates with the cache to increment the counter and check the limit. The reasoning for this centralized approach is consistency; it ensures that the policy is applied identically regardless of which node handles the request. However, this introduces a new bottleneck and latency, as every request now requires a network call to the shared cache. High-performance systems mitigate this by using asynchronous updates or local batches to reduce the number of remote calls required while maintaining effective global oversight.

class DistributedRateLimiter:
    def __init__(self, redis_client, user_id, limit):
        self.redis = redis_client
        self.key = f"rate_limit:{user_id}"
        self.limit = limit

    def allow_request(self):
        # Atomic increment in cache
        current_count = self.redis.incr(self.key)
        if current_count == 1:
            self.redis.expire(self.key, 60) # Set TTL to 1 minute
            
        return current_count <= self.limit

Interview questions

All System Design interview questions →

Check yourself

Take the full System Design quiz →