Rate Limiting
Rate limiting is the practice of controlling the number of requests a client can make to a system within a given time window. It sounds trivial — count requests, reject extras — but the implementation details determine whether your system gracefully degrades under load or collapses when you need it most. Every production API you have ever used enforces rate limits, and getting the algorithm wrong can either block legitimate users or let abusive traffic through.
Rate limiting is not just about protection. It is a fundamental capacity planning tool. It lets you make guarantees about system behavior under load, allocate resources fairly between tenants, and create predictable cost models for your infrastructure.
Why Rate Limiting Matters
Without rate limiting, a single misbehaving client — or a coordinated attack — can consume all your capacity:
Normal traffic: ████████░░░░░░░░░░░░ 40% capacity
Spike without RL: ████████████████████ 100% → cascading failure
Spike with RL: ████████████░░░░░░░░ 60% → graceful degradation
Rate limiting serves four distinct purposes:
| Purpose | Example |
|---|---|
| Security | Prevent brute-force login attempts |
| Availability | Protect backends from traffic spikes |
| Fairness | Prevent one tenant from starving others |
| Cost control | Cap expensive API calls per billing period |
Rate Limiting Algorithms
There are four major algorithms, each with different trade-offs. Understanding the math behind each one is critical for choosing the right approach.
Fixed Window Counter
The simplest algorithm. Divide time into fixed windows (e.g., 1-minute intervals) and count requests per window.
gantt
title Fixed Window Counter (limit: 5 req/min)
dateFormat X
axisFormat %s
section Window 1
Requests 1-5 (allowed) :done, 0, 60
section Window 2
Requests 1-3 (allowed) :done, 60, 120
section Window 3
Requests 1-5 (allowed) :done, 120, 180
Implementation in Python:
import time
from dataclasses import dataclass
@dataclass
class FixedWindowLimiter:
max_requests: int
window_size_seconds: int
def __post_init__(self):
self.windows: dict[str, dict] = {}
def allow_request(self, client_id: str) -> bool:
now = time.time()
window_key = int(now // self.window_size_seconds)
if client_id not in self.windows:
self.windows[client_id] = {}
client = self.windows[client_id]
if client.get("window") != window_key:
client["window"] = window_key
client["count"] = 0
if client["count"] >= self.max_requests:
return False
client["count"] += 1
return True
# Usage
limiter = FixedWindowLimiter(max_requests=100, window_size_seconds=60)
if not limiter.allow_request("user-123"):
raise RateLimitExceeded("Try again later")
The boundary problem: If a client sends 100 requests at 0:59 and 100 more at 1:01, they get 200 requests through in 2 seconds — double the intended rate. This happens because the counter resets at window boundaries.
Sliding Window Log
Fixes the boundary problem by tracking the exact timestamp of every request.
import time
from collections import deque
class SlidingWindowLogLimiter:
def __init__(self, max_requests: int, window_seconds: int):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.logs: dict[str, deque] = {}
def allow_request(self, client_id: str) -> bool:
now = time.time()
cutoff = now - self.window_seconds
if client_id not in self.logs:
self.logs[client_id] = deque()
log = self.logs[client_id]
# Remove expired entries
while log and log[0] <= cutoff:
log.popleft()
if len(log) >= self.max_requests:
return False
log.append(now)
return True
Trade-off: Exact correctness, but memory per client where is the number of requests in the window. For high-rate clients, this can be expensive.
Sliding Window Counter
A hybrid that combines fixed window counting with interpolation to approximate a sliding window, using memory per client.
import time
class SlidingWindowCounter:
def __init__(self, max_requests: int, window_seconds: int):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.clients: dict[str, dict] = {}
def allow_request(self, client_id: str) -> bool:
now = time.time()
current_window = int(now // self.window_seconds)
window_elapsed = (now % self.window_seconds) / self.window_seconds
if client_id not in self.clients:
self.clients[client_id] = {
"prev_count": 0,
"curr_count": 0,
"curr_window": current_window,
}
client = self.clients[client_id]
if client["curr_window"] < current_window:
client["prev_count"] = client["curr_count"]
client["curr_count"] = 0
client["curr_window"] = current_window
# Weighted count: previous window's remaining weight + current count
estimated_count = (
client["prev_count"] * (1 - window_elapsed)
+ client["curr_count"]
)
if estimated_count >= self.max_requests:
return False
client["curr_count"] += 1
return True
The estimated request count for the sliding window is:
This gives ~0.003% false positive rate in practice according to Cloudflare's measurements — close enough to exact for virtually all use cases.
Worked example. Limit 100 per minute. The previous minute had 84 requests, the current minute has 30 so far, and we are 15 seconds (25%) into it. The estimate is , so the request is allowed. At the same moment a true sliding log might hold anywhere from 30 to 114 requests, depending on when in the previous minute those 84 arrived. The approximation assumes they were spread evenly. That assumption is what makes it cheap (two counters per client) and what makes it slightly wrong when traffic is bursty at window edges. Cloudflare's 0.003% figure comes from real traffic, where edge-aligned bursts are rare. An adversary who knows the algorithm can do a little better than the limit, but never more than double it, and in practice far less.
Token Bucket
The most flexible algorithm. A bucket holds tokens; each request consumes a token. Tokens are added at a constant rate. This naturally allows controlled bursts while enforcing an average rate.
Key parameters:
| Parameter | Meaning | Effect |
|---|---|---|
| Bucket size () | Maximum tokens stored | Controls burst size |
| Refill rate () | Tokens added per second | Controls sustained rate |
package ratelimit
import (
"sync"
"time"
)
type TokenBucket struct {
mu sync.Mutex
tokens float64
maxTokens float64
refillRate float64 // tokens per second
lastRefill time.Time
}
func NewTokenBucket(maxTokens float64, refillRate float64) *TokenBucket {
return &TokenBucket{
tokens: maxTokens,
maxTokens: maxTokens,
refillRate: refillRate,
lastRefill: time.Now(),
}
}
func (tb *TokenBucket) Allow() bool {
tb.mu.Lock()
defer tb.mu.Unlock()
now := time.Now()
elapsed := now.Sub(tb.lastRefill).Seconds()
tb.tokens += elapsed * tb.refillRate
if tb.tokens > tb.maxTokens {
tb.tokens = tb.maxTokens
}
tb.lastRefill = now
if tb.tokens < 1 {
return false
}
tb.tokens--
return true
}
The math: After an idle period of seconds, the bucket has tokens available. A client that was silent for 10 seconds with tokens/sec and gets an immediate burst of 50 requests, then is limited to 10/sec thereafter.
The formal guarantee is worth knowing because it tells you exactly what a token bucket allows. If is the number of requests admitted in any interval from to , then
for every interval, not just aligned windows. That is the "arrival curve" used in network calculus, and it is why token buckets are the standard way to describe traffic contracts in networking (they are the policers and shapers in routers, and the model behind Linux's tc token bucket filter). Over one second a client gets at most requests. Over an hour it gets at most , which is essentially per second. The bucket size controls burst tolerance and nothing else.
Choosing : it should cover the legitimate burst a well-behaved client produces, such as a page load that fires 20 API calls at once, or a mobile app syncing after coming back online. Setting (one second of tokens) is a common, sensible default.
GCRA: A Token Bucket in One Number
The token bucket above stores two values per client (tokens and last refill time). The Generic Cell Rate Algorithm, from ATM networks, gives exactly the same admit/reject decisions while storing a single timestamp, the theoretical arrival time (TAT): the time at which the client's bucket would be completely full again.
- Emission interval (time per token). Burst tolerance .
- On a request at time : let . If , reject. Otherwise admit and set .
One value, one comparison, and the "reset" and "retry after" times fall straight out of it: the next request will be admitted at . GCRA is what redis-cell and the Go throttled library implement. Here it is as an atomic Redis script that also uses Redis's own clock, which avoids skew between application servers:
-- GCRA rate limiter. KEYS[1] = key
-- ARGV[1] = rate (requests per second), ARGV[2] = burst (bucket size b)
-- Returns {allowed (0/1), retry_after_ms, reset_after_ms}
local rate = tonumber(ARGV[1])
local burst = tonumber(ARGV[2])
local t = redis.call('TIME') -- server clock, no skew
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local T = 1000 / rate -- ms per token
local tau = (burst - 1) * T
local tat = tonumber(redis.call('GET', KEYS[1])) or now
if tat < now then tat = now end
if tat - now > tau then
return {0, math.ceil(tat - tau - now), math.ceil(tat - now)}
end
local new_tat = tat + T
redis.call('SET', KEYS[1], new_tat, 'PX', math.ceil(new_tat - now))
return {1, 0, math.ceil(new_tat - now)}
reset_after_ms is the time until the bucket is full again, and it is also a natural TTL: once the bucket is full, the key carries no information and can expire. Calling TIME inside a script used to be disallowed because scripts were replicated by re-running them, and the result was non-deterministic. Since Redis 5 scripts are replicated by their effects by default (and Redis 7 removed the old mode), so this is safe.
Leaky Bucket
The inverse of token bucket. Requests enter a queue (bucket) and are processed at a constant rate. If the queue is full, new requests are dropped.
import time
from collections import deque
from threading import Lock
class LeakyBucket:
def __init__(self, capacity: int, leak_rate: float):
self.capacity = capacity
self.leak_rate = leak_rate # requests processed per second
self.queue: deque = deque()
self.last_leak = time.time()
self.lock = Lock()
def allow_request(self, request_id: str) -> bool:
with self.lock:
self._leak()
if len(self.queue) >= self.capacity:
return False
self.queue.append(request_id)
return True
def _leak(self):
now = time.time()
elapsed = now - self.last_leak
leaked = int(elapsed * self.leak_rate)
for _ in range(min(leaked, len(self.queue))):
self.queue.popleft()
if leaked > 0:
self.last_leak = now
Token Bucket vs Leaky Bucket
Token bucket allows bursts up to the bucket size. Leaky bucket smooths traffic to a constant output rate. Choose token bucket when you want to allow burst traffic; choose leaky bucket when you need to protect downstream services that cannot handle spikes.
"Leaky bucket" is used for two different things, which causes confusion. Leaky bucket as a queue (the code above) holds requests and releases them at a steady rate: it shapes traffic and adds delay. Leaky bucket as a meter keeps only a counter that drains at rate and rejects a request if adding it would overflow: it polices traffic and is mathematically the same as a token bucket (a full leaky bucket is an empty token bucket). NGINX's limit_req is a meter with an optional delay queue: with burst set and no nodelay, excess requests wait in the queue; with nodelay they are served immediately as long as the burst allowance is not used up.
Note also that the queue version above never processes anything: _leak drops queued request ids as time passes rather than handing them to a worker. In a real shaper, the leak step is a worker that dequeues at the fixed rate and executes the request.
Algorithm Comparison
| Algorithm | Memory | Accuracy | Burst Handling | Complexity |
|---|---|---|---|---|
| Fixed Window | per client | Low (boundary issue) | Allows 2x burst | Simple |
| Sliding Log | per client | Exact | No bursts | Moderate |
| Sliding Counter | per client | ~99.997% | Minimal bursts | Moderate |
| Token Bucket | per client | Exact for rate | Controlled bursts | Moderate |
| Leaky Bucket | per client | Exact for rate | No bursts | Moderate |
| GCRA | per client, one timestamp | Same decisions as token bucket | Controlled bursts | Simple once understood |
A quick way to choose:
flowchart TD
Q["What are you limiting?"] --> A{"Need to allow short bursts?"}
A -->|"Yes"| TB["Token bucket or GCRA"]
A -->|"No, smooth output to a fragile backend"| LB["Leaky bucket as a queue"]
Q --> B{"Quota over a calendar period?"}
B -->|"Yes, e.g. 10,000 per day"| FW["Fixed window, aligned to billing period"]
Q --> C{"Need exact counts for security?"}
C -->|"Yes, e.g. login attempts"| SL["Sliding log, low limits only"]
C -->|"No, approximate is fine"| SC["Sliding window counter"]
Distributed Rate Limiting
Single-node rate limiting is straightforward. The hard problem is rate limiting across a distributed system where requests can hit any of N servers.
Centralized Counter with Redis
The most common production approach. All application nodes check a shared Redis counter.
graph TD
C1["App Server 1"] --> R["Redis Cluster<br/>(centralized counters)"]
C2["App Server 2"] --> R
C3["App Server 3"] --> R
C4["App Server N"] --> R
R --> D{Count < Limit?}
D -->|Yes| E["Allow Request"]
D -->|No| F["Return 429"]
Redis sliding window implementation using sorted sets:
import redis
import time
class RedisRateLimiter:
def __init__(self, redis_client: redis.Redis, max_requests: int,
window_seconds: int):
self.redis = redis_client
self.max_requests = max_requests
self.window_seconds = window_seconds
def allow_request(self, client_id: str) -> tuple[bool, dict]:
key = f"ratelimit:{client_id}"
now = time.time()
cutoff = now - self.window_seconds
pipe = self.redis.pipeline()
# Remove expired entries
pipe.zremrangebyscore(key, 0, cutoff)
# Count remaining entries
pipe.zcard(key)
# Add current request (score = timestamp, member = unique ID)
pipe.zadd(key, {f"{now}": now})
# Set expiry on the key
pipe.expire(key, self.window_seconds)
results = pipe.execute()
request_count = results[1]
allowed = request_count < self.max_requests
remaining = max(0, self.max_requests - request_count - 1)
headers = {
"X-RateLimit-Limit": str(self.max_requests),
"X-RateLimit-Remaining": str(remaining),
"X-RateLimit-Reset": str(int(now) + self.window_seconds),
}
if not allowed:
# Remove the request we just added
self.redis.zrem(key, f"{now}")
headers["Retry-After"] = str(self.window_seconds)
return allowed, headers
Redis Latency Matters
Every rate limit check adds a round-trip to Redis (~0.5-2ms on the same AZ). At 100K requests/sec, that is 100K extra Redis commands per second. Use pipelining, connection pooling, and consider Redis Caching Patterns for optimization.
Atomic token bucket in Redis using Lua scripting:
-- KEYS[1] = rate limit key
-- ARGV[1] = max_tokens (bucket capacity)
-- ARGV[2] = refill_rate (tokens per second)
-- ARGV[3] = now (current timestamp in milliseconds)
-- ARGV[4] = requested tokens (usually 1)
local key = KEYS[1]
local max_tokens = tonumber(ARGV[1])
local refill_rate = 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 max_tokens
local last_refill = tonumber(data[2]) or now
-- Calculate token refill
local elapsed = (now - last_refill) / 1000.0
tokens = math.min(max_tokens, 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('PEXPIRE', key, math.ceil(max_tokens / refill_rate) * 1000)
return {allowed, math.floor(tokens)}
Two refinements to this script. It takes now from the caller, so application servers with skewed clocks will disagree about refill: a server whose clock is 2 seconds ahead refills 2 seconds' worth of tokens early, and one that is behind can produce a negative elapsed. Using redis.call('TIME') inside the script, as the GCRA version above does, removes the problem. And HMSET is deprecated in favour of HSET with several field-value pairs, which does the same thing.
The sorted-set limiter above has a smaller issue: it uses the timestamp string as the set member, so two requests in the same microsecond collapse into one entry and the client is undercounted. Use a unique member such as f"{now}-{uuid4()}".
Races, and Why Atomicity Matters
The naive distributed limiter reads the counter, decides, and writes it back. Two app servers doing that concurrently both read the same value:
sequenceDiagram
participant A as "App server A"
participant R as "Redis"
participant B as "App server B"
A->>R: GET rl:user42
B->>R: GET rl:user42
R-->>A: 99
R-->>B: 99
Note over A,B: limit is 100, both decide to allow
A->>R: SET rl:user42 100
B->>R: SET rl:user42 100
Note over R: 101 requests admitted, counter says 100
Under real load, with dozens of servers and a popular key, this lets a burst through at many times the limit. The fixes, in order of preference:
| Approach | How | Notes |
|---|---|---|
| Single atomic command | INCR then compare the returned value | Works for fixed windows. Set the TTL in the same step (SET key 0 EX 60 NX before INCR, or a script) so a crash cannot leave a counter without expiry. |
| Lua script | EVAL or EVALSHA runs the read-decide-write sequence atomically | Needed for token bucket, GCRA and sliding window counter. Keep scripts short: Redis runs one script at a time. |
MULTI/EXEC pipeline | Queues commands and runs them together | Atomic, but the decision cannot depend on a value read in the same transaction without WATCH, which retries under contention |
WATCH + optimistic retry | Abort and retry if the key changed | Correct, but degrades badly on hot keys |
The multi-tenant example later on this page calls INCR and then EXPIRE as two commands. If the process dies between them, the key never expires and the tenant is locked out until someone notices. A one-line Lua script (local c = redis.call('INCR', KEYS[1]) if c == 1 then redis.call('EXPIRE', KEYS[1], ARGV[1]) end return c) closes that gap.
Operating a Central Limiter
Running every request through Redis raises some operational questions that are easy to skip in design and painful in production:
- Redis Cluster key placement. Each key lives on one shard. A per-tenant limiter with several keys (per-second, per-minute, per-day) must keep them on the same shard if one script touches all of them. Use a hash tag:
rl:{tenant42}:secandrl:{tenant42}:minhash only the part in braces, so they land together. - Hot keys. A global limit ("10,000 requests per second across all users for this endpoint") is one key on one shard, taking 10,000 or more script calls per second. Split it into sub-keys, each with a limit of , and pick one at random per request. The total is enforced approximately and the load spreads.
- Failure policy. When Redis is slow or down, do you allow (fail open) or reject (fail closed)? Most API limits should fail open with a local fallback limiter, since rejecting all traffic because the limiter is broken is a self-inflicted outage. Security limits (login attempts, OTP verification) should fail closed or fall back to a strict local limit. Kong's
fault_tolerant: truein the example below is a fail-open setting. - Timeouts. Give the limiter call a tight timeout (a few milliseconds) and treat a timeout as the failure policy above. A limiter that adds 500 ms during a Redis hiccup has become the outage.
Local + Global Hybrid
For ultra-low latency, use local rate limiting with periodic synchronization:
sequenceDiagram
participant Client
participant AppServer as App Server (local counter)
participant Redis as Redis (global counter)
Client->>AppServer: Request
AppServer->>AppServer: Check local counter
alt Local limit not reached
AppServer->>Client: 200 OK (fast path)
else Local limit reached
AppServer->>Redis: Sync & check global
Redis-->>AppServer: Global count
alt Global limit not reached
AppServer->>Client: 200 OK
else Global limit reached
AppServer->>Client: 429 Too Many Requests
end
end
Note over AppServer,Redis: Periodic sync every 1-5 seconds
import threading
import time
class HybridRateLimiter:
def __init__(self, redis_client, max_requests: int,
window_seconds: int, num_servers: int,
sync_interval: float = 2.0):
self.redis = redis_client
self.max_requests = max_requests
self.window_seconds = window_seconds
self.local_limit = max_requests // num_servers # Fair share
self.sync_interval = sync_interval
self.local_counts: dict[str, int] = {}
self.lock = threading.Lock()
# Start background sync
self._start_sync_thread()
def allow_request(self, client_id: str) -> bool:
with self.lock:
count = self.local_counts.get(client_id, 0)
if count >= self.local_limit:
return False
self.local_counts[client_id] = count + 1
return True
def _sync_to_redis(self):
with self.lock:
for client_id, count in self.local_counts.items():
key = f"ratelimit:global:{client_id}"
self.redis.incrby(key, count)
self.redis.expire(key, self.window_seconds)
self.local_counts.clear()
def _start_sync_thread(self):
def sync_loop():
while True:
time.sleep(self.sync_interval)
self._sync_to_redis()
t = threading.Thread(target=sync_loop, daemon=True)
t.start()
Consistency Trade-off
The hybrid approach trades consistency for latency. With N servers syncing every S seconds, the system can temporarily allow up to extra requests during the sync window. This is acceptable for most API rate limiting but not for security-critical limits like login attempts.
Correction: what the hybrid code above actually enforces
The HybridRateLimiter sketch does not implement the flow in its diagram. Its local counters are cleared at every sync (every 2 seconds), so each server enforces local_limit per sync interval, not per window, and it writes the global counter to Redis but never reads it back. With a 60-second window and 30 sync intervals per window, a client could get up to 30 times the intended limit. A version that matches the diagram follows.
A sound hybrid uses token leasing: each server borrows small batches of quota from the global counter and spends them locally. The global counter is touched once per batch instead of once per request, and the total admitted can never exceed the global limit, because every token was handed out atomically by Redis.
import type { Redis } from "ioredis";
// Atomically take up to `want` tokens from a fixed-window global budget.
// Returns how many were granted (0..want).
const LEASE_SCRIPT = `
local used = tonumber(redis.call('GET', KEYS[1]) or '0')
local limit = tonumber(ARGV[1])
local want = tonumber(ARGV[2])
local grant = math.min(want, limit - used)
if grant <= 0 then return 0 end
redis.call('INCRBY', KEYS[1], grant)
redis.call('EXPIRE', KEYS[1], ARGV[3], 'NX')
return grant`;
export class LeasedLimiter {
private local = new Map<string, { tokens: number; window: number }>();
constructor(
private redis: Redis,
private limit: number, // global requests per window
private windowSec: number,
private batch: number, // tokens per lease, e.g. 1% of limit
) {}
async allow(key: string): Promise<boolean> {
const window = Math.floor(Date.now() / 1000 / this.windowSec);
let entry = this.local.get(key);
if (!entry || entry.window !== window) {
entry = { tokens: 0, window }; // new window, old lease is void
this.local.set(key, entry);
}
if (entry.tokens === 0) {
const granted = Number(await this.redis.eval(
LEASE_SCRIPT, 1, `rl:${key}:${window}`, this.limit, this.batch, this.windowSec * 2));
entry.tokens += granted;
if (granted === 0) return false; // global budget exhausted
}
entry.tokens--;
return true;
}
}
The trade-off is set by the batch size. With servers and batch , up to tokens can be leased but unused at the end of a window. That is under-admission (some legitimate requests rejected while unused tokens sit on other servers), never over-admission. Batches of about 1% of the limit, or what one server uses in a few hundred milliseconds, keep both the Redis load and the unfairness small. EXPIRE ... NX needs Redis 7. On older versions, set the TTL only when used is 0.
Envoy and Service-Mesh Rate Limiting
Envoy splits the problem the same way. Its local rate limit filter is a token bucket per proxy instance, with no network call. Its global rate limit filter calls an external gRPC rate limit service (Lyft's open-source ratelimit service, backed by Redis, is the reference implementation) with a set of descriptors, such as ("remote_address", "1.2.3.4") or ("api_key", "k_123"), ("path", "/search"), and the service applies the matching configured limit. A common setup is a generous local limit on every proxy to absorb floods cheaply, and a precise global limit for the per-customer contract.
Rate Limiting at Different Layers
Production systems enforce rate limits at multiple layers, each serving a different purpose.
graph TD
Client["Client"] --> CDN["CDN / Edge<br/>(DDoS protection, geographic limits)"]
CDN --> LB["Load Balancer<br/>(connection limits, IP-based throttle)"]
LB --> GW["API Gateway<br/>(per-API key, per-route limits)"]
GW --> App["Application<br/>(business logic limits)"]
App --> DB["Database<br/>(connection pool, query rate)"]
style CDN fill:#e1f5fe
style LB fill:#fff3e0
style GW fill:#e8f5e9
style App fill:#fce4ec
style DB fill:#f3e5f5
| Layer | What to Limit | Why |
|---|---|---|
| CDN/Edge | Requests per IP, per region | Stop DDoS before it reaches your infra |
| Load Balancer | Connections per IP, bandwidth | Prevent connection exhaustion |
| API Gateway | Requests per API key, per route | Enforce billing tiers, protect specific endpoints |
| Application | Business operations per user | Prevent abuse (e.g., max 10 password resets/hour) |
| Database | Queries per connection, connection pool size | Prevent query storms from overwhelming the DB |
API Gateway Rate Limiting
Most API gateways (Kong, AWS API Gateway, Traefik) have built-in rate limiting. Here is a Kong configuration:
# Kong rate limiting plugin
plugins:
- name: rate-limiting
config:
second: 50
minute: 1000
hour: 10000
policy: redis
redis_host: redis.internal
redis_port: 6379
redis_database: 0
fault_tolerant: true # Allow traffic if Redis is down
hide_client_headers: false
limit_by: credential # Per API key
NGINX Rate Limiting
NGINX uses the leaky bucket algorithm via its limit_req module. See Nginx Deep Dive for full configuration.
http {
# Define a rate limit zone: 10 requests/second per IP
limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;
server {
location /api/ {
# Allow up to 20 requests above the 10 r/s rate, served at once
# (nodelay). Burst slots free up at 10 r/s; beyond that, 429.
limit_req zone=api burst=20 nodelay;
limit_req_status 429;
proxy_pass http://backend;
}
}
}
Correction: the comment in this block used to read "Allow burst of 20, process excess without delay up to 10", which mixed up the two numbers. rate=10r/s is the sustained rate, burst=20 is how many requests above that rate are tolerated, and nodelay means those burst requests are forwarded immediately instead of being spaced out at the rate.
Response Headers and Client Behavior
Standard rate limit response headers (RFC 6585, IETF draft RateLimit fields):
HTTP/1.1 429 Too Many Requests
Content-Type: application/json
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1711027200
Retry-After: 30
{
"error": "rate_limit_exceeded",
"message": "Rate limit of 1000 requests per hour exceeded",
"retry_after": 30
}
Client-Side Rate Limit Handling
Good API clients implement exponential backoff with jitter when they receive a 429:
This prevents thundering herd effects when many clients are rate-limited simultaneously.
async function requestWithBackoff<T>(
fn: () => Promise<T>,
maxRetries: number = 5
): Promise<T> {
for (let attempt = 0; attempt <= maxRetries; attempt++) {
try {
return await fn();
} catch (error: any) {
if (error.status !== 429 || attempt === maxRetries) throw error;
const retryAfter = error.headers?.['retry-after'];
const delay = retryAfter
? parseInt(retryAfter) * 1000
: Math.min(1000 * Math.pow(2, attempt) + Math.random() * 1000, 30000);
console.warn(`Rate limited. Retrying in ${delay}ms (attempt ${attempt + 1})`);
await new Promise(resolve => setTimeout(resolve, delay));
}
}
throw new Error('Max retries exceeded');
}
Correction: the log line in this function previously wrapped each interpolated value in an extra pair of braces (a dollar sign followed by two opening braces). In a JavaScript template literal that interpolates an object literal such as {delay} and prints [object Object]. It now uses plain ${delay}.
The 429 Contract
A rate limit is an API contract, and the response that enforces it should tell a well-behaved client exactly what to do next. Getting the contract right is what separates a limit that clients adapt to from one that causes retry storms.
Status codes
| Code | Meaning | Use it when |
|---|---|---|
429 Too Many Requests | This client has exceeded its allowance (RFC 6585) | Per-key, per-user, per-IP or per-tenant limits |
503 Service Unavailable | The server cannot take the request right now, whoever sent it | Global load shedding, overload, maintenance |
403 Forbidden | Not allowed at all | The plan does not include this API. Do not use 429 for permanent denials. |
The distinction matters to clients: a 429 means "you, slow down", which a client can fix. A 503 means "we are struggling", where the right client action is to back off harder and possibly fail over.
Headers
Correction to the "Standard rate limit response headers" line in the section above: RFC 6585 defines the 429 status code, and says the response may include Retry-After. It does not define any X-RateLimit-* headers. Those are a widespread convention (GitHub, Twitter/X and many others use variants), not a standard. The IETF HTTPAPI working group's draft "RateLimit header fields for HTTP" standardises the idea, and its later revisions use two fields, RateLimit-Policy (the quota) and RateLimit (the current state). Because it is still a draft and has changed shape between versions, check the current text before relying on exact syntax.
What each piece should carry:
| Header | Content | Notes |
|---|---|---|
Retry-After | Seconds to wait (30), or an HTTP date | Defined in HTTP semantics (RFC 9110). The one header almost every client library understands. Send it on every 429 and 503. |
X-RateLimit-Limit | The quota for the current window | Convention |
X-RateLimit-Remaining | Requests left in the window | Send on successful responses too, so clients can slow down before hitting the limit |
X-RateLimit-Reset | When the window resets | Ambiguous across APIs: GitHub uses Unix epoch seconds, others use seconds remaining. Document which. |
X-RateLimit-Resource or policy name | Which limit was hit | Useful when several limits apply (per-second, per-day, per-endpoint) |
GitHub's REST API is a good public reference. It returns x-ratelimit-limit, x-ratelimit-remaining, x-ratelimit-used, x-ratelimit-reset (epoch seconds) and x-ratelimit-resource on every response. Authenticated users get 5,000 requests per hour, and unauthenticated requests get 60 per hour per IP. For abuse-oriented "secondary" limits it returns retry-after.
The body
Use a machine-readable error body, ideally application/problem+json (RFC 9457), with a stable error code, a human message, and the retry hint repeated:
{
"type": "https://api.example.com/errors/rate-limited",
"title": "Rate limit exceeded",
"status": 429,
"detail": "Limit of 1000 requests per hour for key k_123 exceeded.",
"limit": "1000/hour",
"retry_after_seconds": 30
}
The client's half of the contract
A correct client:
- Honours
Retry-After, in both its forms (seconds and HTTP-date), and adds a little jitter so that many clients told "30 seconds" do not all return at second 30. - Backs off exponentially with jitter when no hint is given.
- Caps total retry time and gives up with a clear error, rather than retrying forever.
- Does not retry non-idempotent requests blindly. A 429 is normally sent before any work is done, so it is safe to retry, but timeouts are not. See Timeouts, Retries and Backoff.
- Slows down proactively when
Remaininggets low, instead of waiting to be rejected.
The requestWithBackoff function above treats Retry-After as seconds only. Parsing both forms:
export function retryAfterMs(header: string | null | undefined, now = Date.now()): number | null {
if (!header) return null;
const secs = Number(header);
if (Number.isFinite(secs)) return Math.max(0, secs * 1000);
const date = Date.parse(header); // HTTP-date form
return Number.isNaN(date) ? null : Math.max(0, date - now);
}
// with up to 10% jitter so clients do not return in lockstep
export const withJitter = (ms: number) => ms + Math.random() * ms * 0.1;
The server's half
- Reject cheaply. The point of the limiter is to protect capacity, so the 429 path must not call databases or render templates. Check limits as early as possible, at the edge or gateway.
- Count rejected requests or not, deliberately. If rejected requests also consume quota, a client that retries aggressively locks itself out indefinitely. Most APIs do not count rejections. Brute-force protection is the exception, where counting failed attempts is the point.
- Be consistent across instances. If one instance says
Remaining: 400and the next says 429, clients cannot plan. That is an argument for a global limiter, or at least a global view, for the published contract.
Multi-Tenant Rate Limiting
In SaaS systems, you need different limits for different tiers:
from enum import Enum
from dataclasses import dataclass
class Tier(Enum):
FREE = "free"
PRO = "pro"
ENTERPRISE = "enterprise"
@dataclass
class RateLimitPolicy:
requests_per_second: int
requests_per_minute: int
requests_per_day: int
burst_size: int
TIER_POLICIES: dict[Tier, RateLimitPolicy] = {
Tier.FREE: RateLimitPolicy(1, 60, 1_000, 5),
Tier.PRO: RateLimitPolicy(10, 600, 50_000, 50),
Tier.ENTERPRISE: RateLimitPolicy(100, 6_000, 1_000_000, 500),
}
class MultiTenantRateLimiter:
def __init__(self, redis_client):
self.redis = redis_client
self.limiters: dict[str, dict] = {}
def check_all_limits(self, tenant_id: str, tier: Tier) -> bool:
policy = TIER_POLICIES[tier]
checks = [
self._check(tenant_id, "sec", 1, policy.requests_per_second),
self._check(tenant_id, "min", 60, policy.requests_per_minute),
self._check(tenant_id, "day", 86400, policy.requests_per_day),
]
return all(checks)
def _check(self, tenant_id: str, window: str,
duration: int, limit: int) -> bool:
key = f"rl:{tenant_id}:{window}"
count = self.redis.incr(key)
if count == 1:
self.redis.expire(key, duration)
return count <= limit
Note that check_all_limits increments every counter even when one of them rejects, so a tenant that hits its per-second limit still burns its daily quota on rejected requests. Check all limits first in one script and increment only if all pass. The INCR-then-EXPIRE race is covered in the distributed section above.
Fairness and Quotas
A per-client limit answers "how much may this client send?" Fairness asks a different question: "when the system is full, who gets the capacity?" The two are often confused.
Rate limits, quotas and concurrency limits
| Kind | Unit | Example | Protects against |
|---|---|---|---|
| Rate limit | Requests per short interval | 100 per second | Bursts and floods |
| Quota | Requests or units per billing period | 1 million per month | Overuse relative to a plan, cost |
| Concurrency limit | Requests in flight | At most 20 open requests per key | Slow, expensive requests tying up workers |
| Cost-based limit | Points per interval, weighted by request cost | GitHub GraphQL: 5,000 points per hour, a query's cost depends on how many nodes it may return | Cheap and expensive requests being treated as equal |
Concurrency limits deserve more use than they get. A rate limit of 100 per second allows 100 requests that each take 30 seconds, which means 3,000 in flight. Little's Law (, see Queueing Theory) says the load on your workers is rate times duration, and only a concurrency limit bounds that directly. Stripe described using both: a request-rate limiter for every user, and a concurrent-requests limiter for expensive endpoints.
Fair sharing under contention
When total demand exceeds capacity, a fixed per-tenant limit is either too strict (capacity sits idle when others are quiet) or too loose (it does not stop a big tenant from crowding out small ones at peak). Max-min fairness is the usual target: give every tenant up to an equal share, then redistribute what light users leave on the table to the heavy ones.
Worked example: capacity 1,000 requests per second, four tenants demanding 100, 200, 400 and 800.
- Equal share: 250 each.
- Tenants A (100) and B (200) need less than 250, so they get their full demand. 300 is used, 700 is left for C and D.
- C and D split 700: 350 each. C wanted 400 and D 800, so both are capped at 350.
Result: 100, 200, 350, 350. Nobody can get more without taking from someone who has less. Weighted versions give paying tiers larger weights, so an enterprise tenant with weight 4 gets four times a free tenant's share when both are busy.
Implementations:
- Weighted fair queueing at a gateway or work queue: one queue per tenant, served round-robin (deficit round-robin, in practice) with weights.
- Shuffle sharding of queues: each tenant is assigned to a few of many queues, so a noisy tenant fills only its queues. Kubernetes API Priority and Fairness uses shuffle sharding plus fair queueing to stop one controller from starving the API server.
- Adaptive per-tenant limits: compute each tenant's limit periodically from global load and recent demand, then enforce locally.
Prioritised load shedding
Under overload, not all traffic is equal. Stripe's write-up describes four layers: a per-user request-rate limiter, a per-user concurrent-requests limiter, a fleet-wide load shedder that reserves a share of capacity for critical requests, and a worker-utilisation shedder that drops lower-priority traffic first as workers fill up. The general shape is:
| Priority | Examples | Shed |
|---|---|---|
| Critical | Payments, auth, health checks | Last, or never |
| Normal | Regular API reads and writes | When near saturation |
| Deferrable | Analytics, bulk exports, prefetching | First |
The GracefulRateLimiter above encodes the same idea. Be careful that "critical" stays small: if every team labels its traffic critical, the classification protects nothing.
War Story (illustrative)
A public API enforced 1,000 requests per minute per key with a fixed window, and returned 429 with Retry-After: 60 regardless of when in the window the limit was hit. A large customer's integration ran 200 worker processes that all honoured Retry-After exactly. At 09:00:20 they hit the limit, every worker slept for 60 seconds, and at 09:01:20 all 200 woke up together and sent requests in the same second, which hit the new window's limit within two seconds. The pattern repeated every minute, so the customer used a few seconds of each minute and was rejected for the rest. Meanwhile each wave pushed the API's p99 up for everyone. The fix on the server side was to switch to a token bucket (burst 100, refill about 16.7 per second), so a client that hit the limit could continue at the sustained rate instead of being shut out until the window ended, and to compute Retry-After as the true time until one token was available, typically under a second. The client added jitter. Rejections fell by 95% and the periodic latency spikes disappeared.
Interview Questions
1. Compare the token bucket and the sliding window counter.
The token bucket allows bursts up to and a sustained rate , and guarantees at most requests in any interval of length . The sliding window counter approximates "at most N in any window" using two fixed-window counters weighted by the time elapsed. Both are per client. Choose the bucket when burst tolerance matters, the counter when the contract is phrased as "N per minute".
2. Why is GET then SET unsafe for a distributed limiter, and what do you use instead?
Concurrent servers read the same value and each admit, so the limit is exceeded. Use an atomic INCR for fixed windows, or a Lua script for anything that reads, decides and writes.
3. Design a rate limiter for 1 million requests per second across 200 gateway nodes.
A per-node local token bucket for cheap flood protection, plus a global limit through a central store using leased token batches, so Redis sees one call per batch rather than per request. Shard keys across a Redis cluster, split hot global keys into sub-keys, fail open with a local fallback for normal API limits, and use tight timeouts on the limiter call.
4. What is GCRA and why is it attractive?
The Generic Cell Rate Algorithm stores a single "theoretical arrival time" per client and makes the same decisions as a token bucket. One value means one key, one comparison, and the retry time falls straight out of it.
5. When should a limiter fail open, and when closed?
General API limits should fail open, perhaps with a local fallback limit, because rejecting all traffic when the limiter breaks is a self-inflicted outage. Security limits (login, OTP, password reset) should fail closed or fall back to strict local limits.
6. What should a 429 response include?
Retry-After with an accurate wait, limit and remaining-quota headers (on successes too), a machine-readable body naming the limit that was hit, and no expensive work on the rejection path. Use 503, not 429, for global overload.
7. Four tenants want 100, 200, 400 and 800 requests per second from a 1,000 rps system. What is the max-min fair allocation?
100, 200, 350 and 350. Satisfy everyone below the equal share, then split the rest equally among the others.
8. Why add a concurrency limit when you already have a rate limit?
Load on workers is rate times duration. A rate limit does not bound slow requests, so a client can stay within its rate while holding thousands of requests in flight. A concurrency limit bounds that directly.
9. A client honours Retry-After but still causes periodic spikes. Why?
Many workers received the same Retry-After and woke in lockstep, often aligned to a fixed window reset. Add client-side jitter, compute Retry-After from the true time until capacity is available, and prefer a token bucket over fixed windows so capacity returns gradually.
Graceful Degradation Strategies
When rate limits are hit, do not just return 429. Consider these strategies:
- Queue and delay — Accept the request but process it later
- Serve cached responses — Return stale data instead of rejecting
- Reduce quality — Return a simplified response (no recommendations, no personalization)
- Prioritize — Rate limit low-priority traffic first, keep critical paths open
class GracefulRateLimiter:
def handle_request(self, request, client_id: str):
priority = self.get_priority(request)
if priority == "critical":
# Never rate limit health checks, webhooks
return self.process(request)
if not self.limiter.allow_request(client_id):
if priority == "high":
return self.serve_cached(request)
elif priority == "medium":
return self.enqueue(request)
else:
return Response(status=429, body="Rate limited")
return self.process(request)
Testing Rate Limiters
Rate limiters are notoriously hard to test because they depend on time. Use clock injection:
type Clock interface {
Now() time.Time
}
type RealClock struct{}
func (RealClock) Now() time.Time { return time.Now() }
type MockClock struct {
current time.Time
}
func (m *MockClock) Now() time.Time { return m.current }
func (m *MockClock) Advance(d time.Duration) { m.current = m.current.Add(d) }
func TestTokenBucket(t *testing.T) {
clock := &MockClock{current: time.Now()}
bucket := NewTokenBucketWithClock(10, 1.0, clock) // 10 tokens, 1/sec refill
// Consume all tokens
for i := 0; i < 10; i++ {
if !bucket.Allow() {
t.Fatalf("request %d should be allowed", i)
}
}
// Next request should be rejected
if bucket.Allow() {
t.Fatal("request should be rejected")
}
// Advance time by 5 seconds, should have 5 tokens
clock.Advance(5 * time.Second)
for i := 0; i < 5; i++ {
if !bucket.Allow() {
t.Fatalf("request %d should be allowed after refill", i)
}
}
}
Further Reading
- Circuit Breaker Pattern — Complementary resilience pattern that works with rate limiting
- Consistent Hashing — How to distribute rate limit state across nodes
- CAP Theorem — Why distributed rate limiters must choose between accuracy and availability
- Nginx Deep Dive — NGINX's built-in rate limiting module
- Observability — How to monitor rate limit metrics and alert on anomalies
- "Using load shedding to avoid overload" (David Yanacek, Amazon Builders' Library). Correction: this was previously attributed to Google's SRE book. The SRE book's related chapters are "Handling Overload" and "Addressing Cascading Failures".
- Queueing Theory — Why concurrency, not just rate, determines load
- Timeouts, Retries and Backoff — The client side of the 429 contract
- Stripe's blog post "Scaling your API with rate limiters"
- Cloudflare's "How we built rate limiting capable of scaling to millions of domains"