Backend # Rate Limiting Algorithms: From Token Buckets to Distributed Lua Scripts 2025-10-218 min read Lucio Durán Engineering Manager & AI Solutions Architect Also available in: [Español]() ## 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. ```python 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. ```lua -- 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: ```lua -- 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. ```lua -- 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. ```lua -- 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: ```python # 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 `: ```python 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: ```python 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: 1. **Edge (Cloudflare/nginx)**: IP-based, high limits (1,000/min), catches DDoS and scrapers 2. **API Gateway**: API key-based, per-plan limits (free: 60/min, pro: 600/min) 3. **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. ## Frequently asked questions ### Which rate limiting algorithm should I use? For most API rate limiting, GCRA or sliding window counter. Token bucket if you want to allow controlled bursts. Fixed window only for simple, non-critical limits. Sliding window log for exact counting when memory isn't a concern. ### How do I rate limit in a distributed system? Use Redis with atomic Lua scripts. Each rate limit check should be a single EVALSHA call that reads the current state, decides allow/deny, and updates state atomically. This avoids race conditions between distributed application instances. ### Should I rate limit by IP or by API key? Both, at different layers. IP-based limiting at the edge (Cloudflare, nginx) catches DDoS and unauthenticated abuse. API key limiting at the application layer enforces per-customer quotas. The two are complementary. ## Tips 1. **Tip:** Use GCRA (Generic Cell Rate Algorithm) over token bucket when you need smooth rate limiting. Token bucket allows bursts up to the bucket size; GCRA spaces requests evenly, which is what you actually want for API protection. 2. **Tip:** Always include ` X-RateLimit-Limit `, ` X-RateLimit-Remaining `, and ` X-RateLimit-Reset ` headers in your responses. Clients that respect these headers reduce your load voluntarily, free capacity for everyone. 3. **Tip:** In distributed setups, use a single Redis ` EVALSHA ` call for check-and-decrement. Two separate commands (GET then SET) create a race condition where concurrent requests both pass the check before either decrements. 4. **Tip:** Set your Redis key TTL to ` window_size + 1 second `, not exactly ` window_size `. Clock skew between application servers and Redis can cause keys to expire one request too early. - rate-limiting - token-bucket - sliding-window - gcra - redis - lua - api-gateway - distributed-systems [Back to Blog]()