Rate Limiting Algorithms: Token Bucket, Leaky Bucket, and Sliding Windows

Overview

The first rate limiter I wrote was a counter in Redis with a TTL. It worked, sort of, but it had a problem I didn't notice until someone pointed it out: a client could send 99 requests at the end of one minute and 99 at the start of the next, hitting my "100 per minute" limit with 198 requests in a two-second window.

That's the fixed-window problem, and it's the reason there are four or five different rate limiting algorithms instead of one. Each trades off accuracy, memory, and implementation complexity differently.

The four algorithms

Fixed window

import redis
import time

r = redis.Redis()

def allow(key: str, limit: int, window_seconds: int) -> bool:
    now = int(time.time())
    window = now // window_seconds
    cache_key = f"ratelimit:{key}:{window}"

    count = r.incr(cache_key)
    if count == 1:
        r.expire(cache_key, window_seconds)

    return count <= limit

Simple, fast, one counter. The problem is the boundary case: a client can do limit requests at 59.9s and another limit at 60.1s, effectively doubling the rate for one instant.

For lenient limits, this is fine. For strict limits — say, "5 login attempts per minute" — it's not. Someone attacking a login endpoint will happily wait for the window boundary.

Sliding window log

def allow(key: str, limit: int, window_seconds: int) -> bool:
    cache_key = f"ratelimit:{key}"
    now = time.time()
    cutoff = now - window_seconds

    pipe = r.pipeline()
    # Remove timestamps outside the window
    pipe.zremrangebyscore(cache_key, 0, cutoff)
    # Count requests in window
    pipe.zcard(cache_key)
    # Add this request
    pipe.zadd(cache_key, {str(now): now})
    pipe.expire(cache_key, window_seconds)

    _, count, _, _ = pipe.execute()

    return count < limit

Exact, but stores every request timestamp. For a limit of 10,000 per hour, each key holds up to 10,000 entries. At a million keys, that's a lot of memory.

The zremrangebyscore is important — without it, the set grows forever. The Redis sorted set operations are O(log N), so each request is fast, but the memory cost is real.

Use this for limits that need precision and where the volume is low. "3 password resets per hour per user" is a fine fit. "1000 API requests per second per key" is not — you'd have 1000 timestamps per second per key.

Sliding window counter

def allow(key: str, limit: int, window_seconds: int) -> bool:
    now = time.time()
    current_window = int(now // window_seconds)
    previous_window = current_window - 1
    elapsed_in_window = (now % window_seconds) / window_seconds

    curr_key = f"ratelimit:{key}:{current_window}"
    prev_key = f"ratelimit:{key}:{previous_window}"

    pipe = r.pipeline()
    pipe.get(curr_key)
    pipe.get(prev_key)
    curr_count, prev_count = pipe.execute()

    curr_count = int(curr_count or 0)
    prev_count = int(prev_count or 0)

    # Weight the previous window by how much of it we've moved past
    estimated = prev_count * (1 - elapsed_in_window) + curr_count

    if estimated >= limit:
        return False

    r.incr(curr_key)
    r.expire(curr_key, window_seconds * 2)
    return True

Two counters, approximate but smoothed at boundaries. Cloudflare published a writeup on this approach years ago and it's become the standard for API rate limiting at scale.

The approximation comes from assuming requests in the previous window were uniformly distributed. If they were, the estimate is exact. If they were clustered at the very end of the previous window, the estimate is slightly optimistic. In practice, this error is small enough to be acceptable for most rate limiting use cases.

Token bucket

Token bucket is the algorithm most rate limiters actually use, because it has the best properties for API traffic: a steady refill rate plus a configurable burst allowance.

import redis
import time

TOKEN_BUCKET_LUA = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

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

-- Add tokens for elapsed time
local elapsed = math.max(0, now - last_refill)
tokens = math.min(capacity, tokens + elapsed * refill_rate)

if tokens >= requested then
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2)
    return 1
else
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2)
    return 0
end
"""

allow_script = r.register_script(TOKEN_BUCKET_LUA)

def allow(key: str, capacity: int, refill_rate: float) -> bool:
    result = allow_script(
        keys=[f"ratelimit:{key}"],
        args=[capacity, refill_rate, time.time(), 1],
    )
    return bool(result)

Why the Lua script: the whole operation — read, compute, write — has to be atomic. Without it, two concurrent requests could both read the same token count, both decide there's a token available, and both consume it.

The two parameters:

• Capacity — the maximum number of tokens. This is the burst allowance.
• Refill rate — tokens added per second.

For "100 requests per minute, but allow a burst of 20": capacity = 20, refill rate = 100/60 = 1.67 tokens per second.

The burst behavior is what makes this suitable for API traffic. Real clients are bursty — a page load might fire 10 requests in 200ms, then nothing for a minute. Token bucket handles that gracefully while still enforcing the long-term rate.

Leaky bucket

Leaky bucket is the mirror image: it accepts requests at any rate but processes them at a fixed rate. Excess requests queue up and either wait or get dropped.

class LeakyBucket:
    def __init__(self, capacity: int, leak_rate: float):
        self.capacity = capacity
        self.leak_rate = leak_rate  # requests per second
        self.queue = 0
        self.last_leak = time.time()

    def allow(self) -> bool:
        now = time.time()
        elapsed = now - self.last_leak
        self.queue = max(0, self.queue - elapsed * self.leak_rate)
        self.last_leak = now

        if self.queue < self.capacity:
            self.queue += 1
            return True
        return False

Use this when you want a steady output rate — for example, limiting outbound requests to a third-party API that charges per request and has a documented rate limit. Token bucket allows bursts, which the third-party API might not appreciate.

For client-facing rate limiting, token bucket is almost always the right choice. Leaky bucket's smooth output doesn't match how real clients behave.

Distributed rate limiting

Single-server rate limiting is easy. Once you have multiple application servers, the counter has to be shared, and that's where it gets interesting.

The Redis approach is what most systems use. It's exact and the latency cost is acceptable for anything except the highest-throughput services. The failure mode — Redis down — is worth thinking about:

• Fail open — allow everything when Redis is unavailable. Don't rate limit during an outage. Right for public APIs where availability matters more than protection.
• Fail closed — block everything. Right for authentication endpoints where an outage is better than an open door.

I've seen both choices cause incidents. The important thing is deciding deliberately rather than discovering the behavior during an outage.

Where to apply rate limits

Rate limiting at multiple layers is normal and useful:

A layered approach lets you use coarse limits where they're cheap and fine limits where they matter. Edge rate limiting can't distinguish between users (it doesn't see authentication), but it can drop a flood before it reaches your origin.

What to return when rate limited

HTTP/1.1 429 Too Many Requests
Retry-After: 30
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 30
Content-Type: application/json

{
  "error": "rate_limit_exceeded",
  "message": "Too many requests. Retry after 30 seconds."
}

The Retry-After header is what well-behaved clients use to back off. It's technically optional but enormously useful — without it, clients either retry immediately (making things worse) or give up entirely (bad user experience).

The RateLimit-* headers are a draft standard, not universally implemented, but worth adding. Clients can read RateLimit-Remaining and slow down before hitting the limit.

Return 429, not 403. 403 means "you don't have permission." 429 means "you have permission, but you're going too fast." They're different errors and clients should handle them differently.

Pitfalls

• Rate limiting by IP address breaks for users behind NAT. A corporate network with 500 employees sharing one public IP will hit per-IP limits immediately. Use authenticated user IDs when available, IP only as a fallback.
• Not distinguishing endpoints. A limit of 100 per minute on all endpoints means the same budget applies to GET /health and POST /expensive-search. Weight them, or limit them separately.
• Forgetting WebSocket connections. WebSocket messages don't go through HTTP rate limiting middleware. You need per-connection limits in the WebSocket handler.
• Rate limiting on response size. A client can make 5 requests per minute but each one returns 100MB. Rate limit by bytes, not just request count.
• No monitoring. If you don't track rate-limit hits, you don't know whether your limits are too tight (breaking legitimate users) or too loose (letting abuse through).

Rate limiting is one of those features where the implementation is simple and the tuning is hard. Start with generous limits, measure what fraction of legitimate traffic hits them, and tighten from there.