Most rate limiters in production aren’t wrong because someone picked the wrong algorithm — they’re wrong because someone picked an algorithm that only works correctly on a single process, then deployed it across four replicas behind a load balancer. Each replica happily counts requests against its own in-memory dictionary, a client hammering the API gets routed round-robin across all four, and the “limit” that was supposed to cap them at 100 requests per minute quietly becomes 400. Nobody notices until the bill from a downstream API comes in, or an abuse pattern gets four times more room to operate than the limit was designed to allow.
The algorithm choice does matter — fixed window, sliding window, token bucket, and leaky bucket behave genuinely differently at the boundary conditions that make rate limiting hard, like bursty legitimate traffic and the edge of a time window. But the algorithm is only half the problem. The other half is coordination: how you make an increment-and-check operation atomic when it has to be correct across every replica of your API at once, without the check-then-increment race condition that silently doubles your effective limit under concurrent load.
You’ll learn:
- The real behavioral difference between fixed window, sliding window log, sliding window counter, token bucket, and leaky bucket
- Why fixed-window counters let through up to 2x their stated limit right at window boundaries
- How token bucket allows controlled bursts while sliding window enforces a smoother, stricter rate
- Why an in-memory rate limiter silently breaks the moment you run more than one API replica
- How to make a Redis-backed rate limiter atomic across replicas using a Lua script, avoiding the check-then-increment race
- A working token bucket implementation in Python you can drop into a FastAPI middleware
Table of Contents
- The Basics
- The Complete Architecture
- Core Layers Explained
- End-to-End Walkthrough
- Special Cases
- Scaling & Production Challenges
- Code Examples
- Common Pitfalls
- Production Best Practices
The Basics
What a Rate Limiter Actually Decides
At its core, every rate limiting algorithm answers one question for every incoming request: given how many requests this client has already made recently, should this one be allowed through, or rejected with a 429 Too Many Requests? Every algorithm in this post answers that question differently — some track a hard count in a fixed time slot, some track a continuously draining allowance, some track a smoothly weighted average across two adjacent windows — but the interface every one of them exposes to your application is the same: allow or deny, and usually how long until the client should retry.
Why the Algorithm You Pick Actually Matters
- Boundary behavior differs sharply. A client that’s well within a stated limit under one algorithm can burst well past it under another, purely because of how each algorithm treats the edge of a time window.
- Burst tolerance is a product decision, not just a technical one. Some APIs want to allow a client to use up a full minute’s quota in one fast burst, then be quiet; others want traffic smoothed out evenly. That’s an algorithm choice, not a config tweak.
- Getting it wrong is invisible until it isn’t. A rate limiter that only “mostly” works looks identical to a correct one in normal traffic — the gap only shows up under concurrent load or right at abuse thresholds, which is exactly when you need it to actually hold.
The Complete Architecture
client request
│
▼
┌─────────────────────┐
│ rate limit middleware │──── ask: allowed?
└─────────┬───────────┘
│
▼
┌─────────────────────┐
│ Redis (shared state) │ ← atomic INCR / Lua script
│ key: user:123:bucket │ so every API replica
└─────────────────────┘ agrees on the same count
│
allow ──┴── deny (429)
The guiding principle: the algorithm defines the math of when to allow a request, but the storage layer defines whether that math is actually correct once more than one process is evaluating it concurrently. Get the storage layer wrong and the best algorithm in the world still leaks.
Core Layers Explained
1. Fixed Window Counter
What it is: Divide time into fixed slots (e.g., every 00:00–00:59 of each minute), and count requests against whichever slot the current time falls into. When the slot count exceeds the limit, reject; when the clock ticks into a new slot, the counter resets to zero.
Why it matters: It’s the simplest algorithm to implement — a single counter with a TTL — and for that reason it’s still the most common one in the wild. But it has a well-known boundary flaw: a client can send its full limit in the last second of one window, then send its full limit again in the first second of the next, getting effectively double the intended rate across the two-second span straddling the boundary.
Production tip: Fixed window is fine for coarse, generous limits (10,000 requests/hour on a free tier) where a 2x boundary burst isn’t meaningfully harmful. It’s the wrong choice for tight limits where that burst matters, like a login-attempt limiter.
2. Sliding Window Log
What it is: Store a timestamp for every request a client makes, and on each new request, count how many stored timestamps fall within the trailing window (e.g., the last 60 seconds from now, not a fixed clock boundary), discarding anything older.
Why it matters: This is the most accurate algorithm — no boundary flaw at all, because the window is always relative to the current instant. The cost is storage: a growing list of timestamps per client instead of a single integer, which is heavier at scale.
Production tip: Redis’s sorted sets (ZADD, ZREMRANGEBYSCORE, ZCARD) implement this cleanly — score each entry by its timestamp, trim anything outside the window, and count what’s left. It’s precise, but budget for the extra memory per tracked client compared to a single counter.
3. Sliding Window Counter
What it is: A practical compromise: keep two fixed-window counters (the current window and the previous one), and estimate the sliding count as a weighted blend of both, based on how far into the current window you are.
Why it matters: This gets you most of the accuracy of a full sliding log — the boundary-burst flaw is dramatically reduced, not fully eliminated — while keeping the storage cost down to two integers per client instead of a growing timestamp list. It’s the algorithm most rate limiting libraries (including Cloudflare’s and Kong’s default implementations) actually ship, because it’s the best accuracy-to-cost ratio for most APIs.
Production tip: This is a reasonable default when you don’t have a specific reason to reach for token bucket or a full sliding log — it’s cheap, close enough to accurate, and easy to reason about.
4. Token Bucket
What it is: Each client has a bucket holding up to a maximum number of tokens. Tokens refill at a steady rate (say, one every 100ms, for a 10 req/s limit), and every request consumes one. An empty bucket rejects the request; a full one lets a client spend the whole bucket in one fast burst.
Why it matters: Token bucket is the only algorithm in this list that deliberately allows controlled bursting — a client that’s been idle can fire off a full bucket’s worth of requests instantly, then has to wait for tokens to refill. That’s a feature, not a bug, for APIs where legitimate clients genuinely burst (a mobile app syncing after being offline, a dashboard loading several widgets at once) but you still need a hard ceiling on sustained rate.
Production tip: Tune bucket capacity and refill rate as two separate knobs — capacity controls how much burst you tolerate, refill rate controls the long-run sustained rate. Conflating them into one “requests per minute” number loses that flexibility.
5. Leaky Bucket
What it is: The inverse of token bucket — requests enter a queue (the “bucket”) and are processed (“leak out”) at a strictly constant rate regardless of how bursty the arrivals were. A full queue drops new requests.
Why it matters: Leaky bucket enforces a genuinely smooth output rate, which matters when you’re the one calling a rate-limited downstream API and need to guarantee you never exceed their limit, rather than just capping your own inbound traffic. It’s less common for API-facing rate limiting because it adds request queuing and latency rather than a fast reject.
Production tip: Reach for leaky bucket specifically when you’re shaping outbound traffic to a third-party API with a strict limit, not when you’re protecting your own API’s inbound edge — token bucket or sliding window counter fit that case better.
End-to-End Walkthrough
Trace a burst of requests through a token bucket rate limiter backed by Redis, across two API replicas:
- Client sends 5 requests in quick succession to a limit of “10 requests, refilling at 1/second.” Both requests could land on either of two API replicas behind a load balancer.
- Replica A receives request 1. It runs a Lua script against Redis: read current token count, compute tokens added since last refill timestamp, subtract one for this request, write back the new count and timestamp — all inside one atomic Redis operation.
- Replica B receives request 2 a few milliseconds later, before Replica A’s write is even relevant to it, because both replicas talk to the same Redis key, not to their own local memory. Replica B’s Lua script execution is queued and atomic relative to Replica A’s — Redis single-threads command (and script) execution, so there’s no race between the two.
- Requests 3–5 continue the same way, each decrementing the same shared counter regardless of which replica handles it.
- Client sends request 11 immediately after. The bucket is empty (10 tokens consumed, refill rate is only 1/second, and under a second has passed) — the Lua script returns “deny,” and the API responds
429with aRetry-Afterheader computed from the refill rate. - One second later, a new request arrives. The Lua script computes elapsed time since the last write, adds one refilled token, and allows the request.
Special Cases
Per-user vs. per-IP limiting. Authenticated endpoints should key the limiter by user ID, not IP — NAT and corporate proxies put many legitimate users behind one IP, and a shared-IP limit punishes all of them for one user’s traffic. Unauthenticated endpoints (login, signup, password reset) fall back to IP-based limiting, which is also why brute-force login protection needs its own tighter limiter, separate from the general API limit.
Distributed rate limiting across replicas. This is the core reason to use Redis (or another shared store) instead of in-memory counters at all: every replica needs to observe the same count, or the effective limit scales with your replica count instead of staying fixed. An in-memory dict-based limiter is fine for a single-process dev server and actively wrong for anything horizontally scaled.
Burst allowance for legitimate spiky clients. A mobile app that batches requests after reconnecting, or a dashboard that fires off several parallel calls on page load, needs some burst tolerance or it gets rate-limited during completely legitimate use. Token bucket’s separate capacity/refill knobs are the natural fit here; a strict sliding window is not.
Rate limiting inside request handling itself. If your API accepts a request and then hands heavier work off to a background worker — building a report, sending a batch of emails — the limit usually belongs on the inbound endpoint, not the background job, since that’s the point where you actually control admission.
Scaling & Production Challenges
The check-then-increment race condition. The single most common bug in a homegrown rate limiter: reading the current count, checking it against the limit in application code, and only then issuing a separate increment — as two round trips to Redis instead of one atomic operation. Under concurrent requests, two requests can both read a count of 9 (under a limit of 10), both decide to allow, and both increment — letting through 11 instead of 10. The fix is doing the read, compute, and write inside a single Lua script (or MULTI/EXEC transaction, or Redis 7’s OBJECT command extensions), so Redis’s single-threaded execution model makes the whole operation atomic.
Clock drift across replicas. Algorithms relying on wall-clock timestamps (token bucket’s refill, sliding window’s trim boundary) should compute elapsed time using Redis’s own TIME command inside the Lua script, not each replica’s local clock — a few hundred milliseconds of drift is enough to make refill math subtly wrong if every replica trusts its own.
Redis as a single point of failure. A limiter that hard-fails closed when Redis is unreachable turns a Redis blip into a full API outage. Most production setups fail open instead — if Redis is down, let requests through rather than reject everything — since a limiter’s job is to prevent abuse, not become a second point of failure. Log the failure loudly either way.
Key expiry and memory growth. Every client key needs a TTL slightly longer than its window, or Redis accumulates a counter for every client that’s ever made one request and never expires it. Set it explicitly (EXPIRE after the Lua script’s write) and re-check it whenever you change the key’s data structure — it’s easy to silently forget on a later refactor.
Code Examples
A Redis-backed token bucket implemented as an atomic Lua script, called from Python:
import time
import redis
r = redis.Redis(host="localhost", port=6379, decode_responses=True)
# KEYS[1] = bucket key
# ARGV[1] = capacity (max tokens)
# ARGV[2] = refill_rate (tokens per second)
# ARGV[3] = now (unix timestamp, float)
# ARGV[4] = requested tokens (usually 1)
TOKEN_BUCKET_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
local bucket = redis.call("HMGET", key, "tokens", "last_refill")
local tokens = tonumber(bucket[1])
local last_refill = tonumber(bucket[2])
if tokens == nil then
tokens = capacity
last_refill = now
end
local elapsed = math.max(0, now - last_refill)
tokens = math.min(capacity, tokens + elapsed * refill_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 / refill_rate) + 1)
return {allowed, tokens}
"""
_script = r.register_script(TOKEN_BUCKET_SCRIPT)
def is_allowed(client_id: str, capacity: int = 10, refill_rate: float = 1.0) -> tuple[bool, float]:
now = time.time()
allowed, remaining = _script(
keys=[f"ratelimit:{client_id}"],
args=[capacity, refill_rate, now, 1],
)
return bool(allowed), float(remaining)
Wired into a FastAPI middleware:
from fastapi import FastAPI, Request
from fastapi.responses import JSONResponse
app = FastAPI()
@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
client_id = request.headers.get("x-api-key", request.client.host)
allowed, remaining = is_allowed(client_id, capacity=10, refill_rate=1.0)
if not allowed:
return JSONResponse(
status_code=429,
content={"detail": "rate limit exceeded"},
headers={"Retry-After": "1"},
)
response = await call_next(request)
response.headers["X-RateLimit-Remaining"] = str(int(remaining))
return response
A quick concurrency check:
seq 1 20 | xargs -P 20 -I {} curl -s -o /dev/null -w "%{http_code}\n" \
-H "x-api-key: test-client" http://localhost:8000/ping
With capacity 10, expect exactly 10 200s and 10 429s, regardless of how many replicas sit behind the load balancer — the Lua script, not any single replica’s memory, is the source of truth.
Common Pitfalls
Mistake: rate limiting with an in-memory counter behind a multi-replica deployment. Each replica tracks its own count, so the effective limit multiplies by replica count. Solution: back the limiter with Redis (or another shared store) the moment you run more than one process.
Mistake: separate read-then-write calls instead of one atomic operation. This is the check-then-increment race described above. Solution: do the whole read/compute/write inside a single Lua script or Redis transaction.
Mistake: using fixed window for a tight, security-sensitive limit. Login attempt limiting with a fixed window lets an attacker double their effective attempts by timing requests around the window boundary. Solution: use sliding window or token bucket for anything where the boundary-burst behavior is actually exploitable.
Mistake: forgetting a TTL on rate limit keys. Redis memory grows unboundedly as every client that’s ever made a request gets a permanent key. Solution: always set an expiry slightly longer than the window or refill period.
Mistake: failing closed when Redis is unavailable. A Redis outage becomes a full API outage instead of a rate-limiting gap. Solution: default to fail-open for rate limiting, with loud logging/alerting on the failure itself.
Production Best Practices
- Pick sliding window counter as your default, and reach for token bucket specifically when you want to reward idle clients with burst capacity.
- Always implement the check-and-decrement as one atomic Redis operation, via a Lua script — never two round trips.
- Key by authenticated user ID where possible, falling back to IP only for unauthenticated endpoints.
- Set a TTL on every rate limit key and compute it from the window/refill parameters, not a hardcoded guess.
- Decide your Redis-down behavior explicitly — fail open for general API limits, and treat that decision as a conscious tradeoff, not a default you never examined.
Wrapping Up
The algorithm you choose changes how your rate limiter behaves at the edges — how it handles a burst, a window boundary, an idle-then-active client — and picking one that doesn’t match your actual traffic pattern is a real, fixable design mistake. But the more common production incident isn’t an algorithm mismatch at all; it’s a limiter that was only ever correct on one process, silently multiplying its effective limit the moment a second replica joined the fleet. Get the atomicity right first, with a single Redis operation doing the read-check-write as one indivisible step, and the algorithm choice becomes a tuning decision instead of a correctness one.
If your current rate limiter is an in-memory dictionary and you’re running more than one replica, that’s the gap worth closing before anything else in this post.
