Rate Limiting

Why Rate Limiting Exists

A public API endpoint without rate limiting is a shared resource with no admission control. A single misbehaving client, whether a bug, a bot, or an attacker, can consume the capacity that was provisioned for thousands of users. Rate limiting is the mechanism by which a system enforces fairness: each client gets a bounded share of capacity, regardless of how aggressively they request.

The goals are distinct but often conflated. Availability protection keeps a single client from taking down the service for everyone else. Security prevents brute force and credential stuffing. Cost control bounds the bill when a compute-heavy endpoint is called at scale. Fairness ensures that a paying customer's experience is not degraded by a free-tier user consuming resources without bound.

What happens without rate limiting

Dimensions of rate limiting

Rate Limiting Algorithms

Rate limiting algorithms differ in how they track usage over time and how they handle bursts. The choice affects memory usage, accuracy at window boundaries, and whether you allow short bursts above the average rate. The three most important to understand are token bucket, fixed window, and sliding window.

Token bucket

The token bucket holds a maximum of N tokens. Tokens are added at a fixed rate (R per second). Each request consumes one token. If the bucket has tokens, the request is allowed. If empty, it is rejected. The bucket accumulates tokens while traffic is low, enabling bursts up to capacity when traffic spikes.

This is the algorithm behind most production rate limiters because burst handling maps to real-world usage: a user typing quickly generates short bursts of API calls, while a background job makes steady calls over time. Both are valid. Token bucket handles both correctly with one parameter set.

-- Called atomically via EVAL
local key        = KEYS[1]
local capacity   = tonumber(ARGV[1])   -- max tokens
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local now        = tonumber(ARGV[3])   -- current Unix timestamp (ms)
local cost       = tonumber(ARGV[4])   -- tokens this request costs

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

-- Refill tokens based on elapsed time
local elapsed = (now - last_refill) / 1000
tokens = math.min(capacity, tokens + elapsed * refill_rate)

if tokens >= cost then
  tokens = tokens - cost
  redis.call("HMSET", key, "tokens", tokens, "last_refill", now)
  redis.call("EXPIRE", key, 3600)
  return 1   -- allowed
else
  redis.call("HMSET", key, "tokens", tokens, "last_refill", now)
  redis.call("EXPIRE", key, 3600)
  return 0   -- rejected
end

Fixed window

Fixed window increments a counter for the current time window. The counter resets when the window expires. Implementation is a single Redis INCR with an expiry: trivially simple and extremely fast.

The weakness is the boundary burst. With a limit of 100/minute, a client can send 100 requests in the last second of minute 1 and 100 in the first second of minute 2, 200 requests in 2 seconds without violating the limit. If your system cannot handle a 2x burst, fixed window is insufficient.

def is_allowed(user_id: str, limit: int, window_sec: int) -> bool:
    now = int(time.time())
    window_key = now // window_sec   # floor to window boundary
    key = f"rl:{user_id}:{window_key}"

    count = redis.incr(key)
    if count == 1:
        redis.expire(key, window_sec * 2)  # safety: 2x TTL
    return count <= limit

Sliding window

Sliding window eliminates the boundary burst by tracking the exact time of each request within the window. On each request, timestamps older than (now - window_size) are removed. If the remaining count is below the limit, the request is allowed and its timestamp recorded.

The sliding window counter approximation is more practical at scale: instead of storing every timestamp, it combines the current window's counter with the previous window's counter, weighted by how much of the previous window overlaps with the current sliding window. This trades marginal accuracy for O(1) memory.

Algorithm comparison

Implementation: Distributed Rate Limiting

A single-process rate limiter is trivial. The challenge in production is distributed rate limiting: multiple application instances must share the same counter so that a client cannot bypass the limit by routing requests across different servers. Redis is the standard solution, a single Redis cluster holds all rate limit state, and application instances check against it on every request.

The critical requirement is atomicity. An INCR followed by an expiry check is not atomic: two simultaneous requests can both read "0" and both allow themselves, counting one request but allowing two. Redis Lua scripts run atomically (the server executes the entire script before processing any other command), making them the correct implementation primitive for rate limiters.

Application middleware pattern (FastAPI)

import time
from fastapi import Request, HTTPException
from redis.asyncio import Redis

redis = Redis(host="localhost", decode_responses=True)

RATE_LIMITS = {
    "free":       (100,  60),   # 100 req / 60 sec
    "pro":        (1000, 60),
    "enterprise": (None, None), # unlimited
}

async def rate_limit_middleware(request: Request, call_next):
    user = request.state.user           # set by auth middleware
    tier = user.subscription_tier       # "free" | "pro" | "enterprise"
    limit, window = RATE_LIMITS[tier]

    if limit is None:                   # enterprise: skip check
        return await call_next(request)

    key = f"rl:{user.id}:{int(time.time()) // window}"
    count = await redis.incr(key)
    if count == 1:
        await redis.expire(key, window * 2)

    remaining = max(0, limit - count)
    reset_at = (int(time.time()) // window + 1) * window

    if count > limit:
        raise HTTPException(
            status_code=429,
            detail="Rate limit exceeded",
            headers={
                "X-RateLimit-Limit":     str(limit),
                "X-RateLimit-Remaining": "0",
                "X-RateLimit-Reset":     str(reset_at),
                "Retry-After":           str(reset_at - int(time.time())),
            },
        )

    response = await call_next(request)
    response.headers["X-RateLimit-Limit"]     = str(limit)
    response.headers["X-RateLimit-Remaining"] = str(remaining)
    response.headers["X-RateLimit-Reset"]     = str(reset_at)
    return response

429 response best practices

Standard response headers

Where to enforce rate limits