Fixed window counter: the naive approach
The simplest rate limiter. Divide time into fixed windows (e.g., 1-minute intervals), count requests per window, reject when the count exceeds the limit.
import time
import redis
r = redis.Redis()
def fixed_window(key: str, limit: int, window_seconds: int) -> bool:
"""Returns True if request is allowed"""
window = int(time.time() / window_seconds)
redis_key = f"ratelimit:{key}:{window}"
current = r.incr(redis_key)
if current == 1:
r.expire(redis_key, window_seconds + 1)
return current <= limit
The problem: boundary burst. At the edge of two windows, a client can make 2 * limit requests in a span of window_seconds. If your limit is 100/minute, a client can fire 100 requests at 11:59:59 and another 100 at 12:00:00, 200 requests in 2 seconds while "respecting" the limit.
Sliding window log: exact but expensive
Keep a sorted set of every request timestamp. For each new request, remove timestamps older than the window, count remaining entries, and decide.
-- sliding_window_log.lua
-- KEYS[1] = rate limit key
-- ARGV[1] = current timestamp (ms)
-- ARGV[2] = window size (ms)
-- ARGV[3] = max requests
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
-- Remove entries outside the window
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
-- Count current entries
local count = redis.call('ZCARD', key)
if count < limit then
-- Add this request
redis.call('ZADD', key, now, now .. ':' .. math.random(1000000))
redis.call('PEXPIRE', key, window)
return {1, limit - count - 1} -- allowed, remaining
else
return {0, 0} -- denied, remaining
end
This gives exact counts, no boundary burst problem. But it stores every request timestamp. At 1,000 req/s with a 60-second window, that's 60,000 entries per key. Memory usage becomes significant at scale.
Sliding window counter: the practical middle ground
Combine two fixed windows with weighted counting. Estimate the current window's count by interpolating between the previous and current windows:
-- sliding_window_counter.lua
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local current_window = math.floor(now / window)
local previous_window = current_window - 1
local elapsed = (now % window) / window -- 0.0 to 1.0
local current_key = key .. ':' .. current_window
local previous_key = key .. ':' .. previous_window
local current_count = tonumber(redis.call('GET', current_key) or '0')
local previous_count = tonumber(redis.call('GET', previous_key) or '0')
-- Weighted estimate
local estimated = previous_count * (1 - elapsed) + current_count
if estimated < limit then
redis.call('INCR', current_key)
redis.call('PEXPIRE', current_key, window * 2)
return {1, math.floor(limit - estimated - 1)}
else
return {0, 0}
end
Two keys per rate limit, O(1) operations, and the boundary burst problem is reduced (not eliminated, but reduced to acceptable levels for most use cases).
Token bucket: allowing controlled bursts
The token bucket is the classic algorithm. Tokens accumulate at a fixed rate up to a maximum (the bucket size). Each request consumes one token. If the bucket is empty, the request is denied.
-- token_bucket.lua
local key = KEYS[1]
local capacity = tonumber(ARGV[1]) -- max tokens
local rate = tonumber(ARGV[2]) -- tokens per second
local now = tonumber(ARGV[3]) -- current timestamp (ms)
local requested = tonumber(ARGV[4]) -- tokens to consume (usually 1)
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1])
local last_refill = tonumber(data[2])
if tokens == nil then
-- First request: initialize full bucket
tokens = capacity
last_refill = now
end
-- Calculate tokens to add since last refill
local elapsed = (now - last_refill) / 1000.0
local new_tokens = elapsed * rate
tokens = math.min(capacity, tokens + new_tokens)
local allowed = 0
local remaining = tokens
if tokens >= requested then
tokens = tokens - requested
allowed = 1
remaining = tokens
end
redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
redis.call('PEXPIRE', key, math.ceil(capacity / rate * 1000) + 1000)
return {allowed, math.floor(remaining)}
The token bucket has a nice property: it allows bursts. If a client has been idle, tokens accumulate and they can make several rapid requests. This is desirable for many API patterns, a client that polls every 10 seconds doesn't need perfectly smooth limiting.
But bursts are sometimes exactly what you don't want. That's where GCRA comes in.
GCRA: the cell rate algorithm
GCRA (Generic Cell Rate Algorithm) comes from ATM network traffic shaping. Instead of tracking tokens, it tracks when the next request should be allowed. Each request advances this "theoretical arrival time" (TAT) by a fixed increment.
-- gcra.lua
local key = KEYS[1]
local emission_interval = tonumber(ARGV[1]) -- ms between allowed requests
local burst_offset = tonumber(ARGV[2]) -- max burst tolerance (ms)
local now = tonumber(ARGV[3]) -- current timestamp (ms)
local tat = tonumber(redis.call('GET', key)) -- theoretical arrival time
if tat == nil then
-- First request: allow and set TAT
tat = now + emission_interval
redis.call('SET', key, tat)
redis.call('PEXPIRE', key, burst_offset + emission_interval)
return {1, 0} -- allowed, retry_after=0
end
local allow_at = tat - burst_offset
if now < allow_at then
-- Too early: request denied
local retry_after = allow_at - now
return {0, retry_after}
else
-- Allowed: advance TAT
local new_tat = math.max(now, tat) + emission_interval
redis.call('SET', key, new_tat)
redis.call('PEXPIRE', key, burst_offset + emission_interval)
return {1, 0}
end
For 100 requests per second, emission_interval = 10ms (one request every 10ms). The burst_offset allows some flexibility, setting it to 100ms lets clients send up to 10 requests at once before the spacing kicks in.
GCRA has favorable properties: single key per client, O(1) operations, no boundary bursts, smooth rate enforcement. Cloudflare uses this algorithm internally for their rate limiting product.
The distributed race condition
A common and dangerous bug in distributed rate limiting involves a race condition. Here is the broken implementation:
# BROKEN: race condition between check and decrement
def check_rate_limit(key, limit, window):
count = redis.get(key) or 0
if int(count) >= limit:
return False
# Between this GET and the INCR, other requests can pass!
redis.incr(key)
return True
With 100 concurrent requests hitting this code simultaneously, all 100 read count=0, all 100 pass the check, then all 100 increment. The limit is meaningless.
The fix: atomic operations via Lua scripts. Every Lua script in Redis executes atomically, no other command can interleave. All the Lua implementations above are atomic by design. Load them once with SCRIPT LOAD, then call with EVALSHA:
import redis
import hashlib
class DistributedRateLimiter:
def __init__(self, redis_client: redis.Redis):
self.r = redis_client
self._script_sha = None
def _load_script(self):
script = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
-- ... (token bucket implementation from above)
"""
self._script_sha = self.r.script_load(script)
def allow(self, key: str, capacity: int = 100, rate: float = 10.0) -> tuple[bool, int]:
if self._script_sha is None:
self._load_script()
now_ms = int(time.time() * 1000)
try:
result = self.r.evalsha(
self._script_sha, 1, key,
capacity, rate, now_ms, 1
)
except redis.exceptions.NoScriptError:
self._load_script()
result = self.r.evalsha(
self._script_sha, 1, key,
capacity, rate, now_ms, 1
)
allowed = bool(result[0])
remaining = int(result[1])
return allowed, remaining
The NoScriptError handling is important, if Redis restarts, cached scripts are lost. The retry with _load_script() handles this transparently.
Response headers: be a good citizen
Always include rate limit information in your HTTP responses:
from fastapi import FastAPI, Request, Response
from fastapi.responses import JSONResponse
app = FastAPI()
limiter = DistributedRateLimiter(redis_client)
@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
key = f"api:{request.client.host}:{request.url.path}"
allowed, remaining = limiter.allow(key, capacity=100, rate=10.0)
if not allowed:
return JSONResponse(
status_code=429,
content={"error": "Rate limit exceeded"},
headers={
"X-RateLimit-Limit": "100",
"X-RateLimit-Remaining": "0",
"X-RateLimit-Reset": str(int(time.time()) + 10),
"Retry-After": "10",
}
)
response = await call_next(request)
response.headers["X-RateLimit-Limit"] = "100"
response.headers["X-RateLimit-Remaining"] = str(remaining)
response.headers["X-RateLimit-Reset"] = str(int(time.time()) + 10)
return response
The Retry-After header on 429 responses is particularly important. Well-behaved clients (SDKs, scripts) use it to back off automatically. Without it, they retry immediately and make the situation worse.
Multi-tier rate limiting
In production, a three-tier approach works well:
- Edge (Cloudflare/nginx): IP-based, high limits (1,000/min), catches DDoS and scrapers
- API Gateway: API key-based, per-plan limits (free: 60/min, pro: 600/min)
- Per-endpoint: Specific limits for expensive operations (search: 10/min, export: 5/min)
Each tier runs independently with its own Redis key namespace. A request must pass all three to proceed. This layering means you can be generous at the edge (catching only obvious abuse) and strict at the endpoint level (protecting expensive resources).
After switching to atomic Lua scripts, the rate limiter becomes bulletproof. Twelve months of production use, zero incidents, zero race conditions. The implementation is less than 50 lines of Lua. Sometimes the simplest fix is the best one.