Rate Limiting and Throttling: Token Bucket, Sliding Window, and Distributed Approaches

Why Rate Limits Exist

Rate limiting protects your service from being overwhelmed — whether by a misbehaving client, a DDoS attack, or a legitimate traffic spike that exceeds your capacity. Without rate limits, one aggressive client can consume all your resources and degrade the experience for everyone else.

The interesting engineering challenge isn't "should we rate limit?" but "which algorithm gives us the behavior we actually want?"

Token Bucket

The token bucket algorithm is probably the most widely used rate limiter. It's intuitive: imagine a bucket that holds tokens. Tokens are added at a fixed rate (say, 10 per second). Each request consumes one token. If the bucket is empty, the request is rejected.

The bucket has a maximum capacity, which determines your burst allowance. A bucket with capacity 100 and refill rate 10/second allows a burst of 100 requests followed by a sustained rate of 10/second.

# Token bucket in Python
import time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate          # tokens per second
        self.capacity = capacity  # max tokens
        self.tokens = capacity    # start full
        self.last_refill = time.monotonic()

    def allow(self, tokens=1):
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens = min(
            self.capacity,
            self.tokens + elapsed * self.rate
        )
        self.last_refill = now

        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

Token bucket is what AWS API Gateway and Stripe use. It's friendly to bursty traffic patterns — a client that's been quiet for 10 seconds has accumulated tokens and can make a burst of requests without being throttled.

Sliding Window Log

The sliding window log keeps a timestamped log of every request. To check the rate, you count entries within the last N seconds. If the count exceeds the limit, reject.

# Sliding window log with Redis sorted sets
import time
import redis

r = redis.Redis()

def is_allowed(client_id, limit, window_seconds):
    key = f"ratelimit:{client_id}"
    now = time.time()
    window_start = now - window_seconds

    pipe = r.pipeline()
    # Remove entries outside the window
    pipe.zremrangebyscore(key, 0, window_start)
    # Count entries in the window
    pipe.zcard(key)
    # Add current request
    pipe.zadd(key, {f"{now}:{id(now)}": now})
    pipe.expire(key, window_seconds + 1)
    results = pipe.execute()

    current_count = results[1]
    return current_count < limit

This gives exact counts — no approximation. The downside is memory usage. At 10,000 requests per minute per client, you're storing 10,000 entries per client. For a service with millions of clients, that adds up fast.

Sliding Window Counter

The sliding window counter is a hybrid that reduces memory usage by combining fixed window counters with proportional weighting. Instead of storing every request timestamp, you keep counters for the current and previous windows.

To estimate the rate: weighted_count = previous_window_count * overlap_percentage + current_window_count

For example, if you're 30% through the current 60-second window: weighted_count = prev_count * 0.7 + curr_count. It's an approximation, but the error is small and the memory savings are significant — two counters per client instead of thousands of timestamps.

Cloudflare uses this approach for their rate limiting products. It's the sweet spot between accuracy and resource efficiency for most applications.

Fixed Window Counter

The simplest approach: divide time into fixed windows (e.g., one-minute intervals) and count requests per window. Reset the counter at each window boundary.

The problem is boundary bursts. A client could make 100 requests at 11:59:59 and another 100 at 12:00:01 — 200 requests in 2 seconds while technically staying within a 100-per-minute limit. The sliding window approaches solve this, which is why I wouldn't recommend fixed windows for anything user-facing.

Distributed Rate Limiting

All the algorithms above work great on a single server. But if you've got 10 API servers behind a load balancer, a per-server rate limit of 100/minute is really a system-wide limit of 1000/minute. That's not what you want.

Centralized with Redis

The most common solution: use Redis as a centralized counter store. All API servers check the same Redis instance before processing a request.

The implementation above using Redis sorted sets already works in a distributed setting. For the token bucket, you can implement it with Redis Lua scripts to ensure atomicity:

-- Token bucket as a Redis Lua script (atomic operation)
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local data = redis.call('hmget', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now

local elapsed = now - last_refill
tokens = math.min(capacity, tokens + elapsed * rate)

local allowed = 0
if tokens >= requested then
    tokens = tokens - requested
    allowed = 1
end

redis.call('hmset', key, 'tokens', tokens, 'last_refill', now)
redis.call('expire', key, math.ceil(capacity / rate) + 1)

return { allowed, tokens }

Local Rate Limiters with Synchronization

If Redis latency is a concern (it adds 0.5-1ms per request), you can run local rate limiters on each server and periodically sync with a central store. This is less precise but eliminates the Redis round-trip from the hot path.

Envoy proxy uses this approach with its rate limiting service. Local token buckets handle the fast path, and a background thread syncs consumption rates to a central service.

Handling Rate-Limited Clients

When a client hits the rate limit, return HTTP 429 (Too Many Requests) with a Retry-After header indicating how many seconds to wait. Include rate limit headers in every response so clients can self-regulate:

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1693526400

For API clients you control, implement client-side rate limiting. Don't rely on the server rejecting requests — that wastes network round-trips. Use a local token bucket that mirrors the server's limits and back off proactively.

One more thing: differentiate between rate limiting (protecting your service) and throttling (controlling client consumption for billing). They're often conflated but have different goals and might warrant different limits — a free-tier user gets 100 requests/minute, a paid user gets 10,000, and your infrastructure limit is 50,000 across all clients.