Rate Limiting via Redis Token Bucket Algorithms

Rate limiting is a foundational pillar of API security and infrastructure management. Without strict rate limiting, web applications are vulnerable to credential brute-forcing, automated scraping, denial-of-service (DDoS) attacks, and database connection exhaustion.

In distributed microservice environments where application servers run across multiple load-balanced nodes, local in-memory rate counters fail. Rate limiting state must be synchronized globally using a high-speed, centralized store. Redis—paired with atomic Lua scripts—provides the ideal solution. In this article, we compare rate-limiting algorithms, write an atomic Token Bucket Lua script, and return standard RFC 6585 headers.

1. Evaluating Rate Limiting Algorithms

• Fixed Window Counter: Counts requests within fixed time blocks (e.g., 100 req/minute). Drawback: Vulnerable to traffic spikes at window boundaries (e.g. 100 requests at 00:59 followed by 100 requests at 01:01).
• Sliding Window Log: Logs timestamps of every request in a Redis Sorted Set (ZSET). Extremely precise, but consumes memory quickly under high traffic.
• Token Bucket: A bucket holds up to $N$ tokens. Tokens refill continuously at a defined rate (e.g., 10 tokens/sec). Each request consumes 1 token. If the bucket is empty, the request is rejected with HTTP 429. This algorithm accommodates brief bursts while enforcing steady rate ceilings.

2. Atomic Execution with Redis Lua Scripts

Executing multiple Redis commands (e.g., GET, calculating refill, then SET) from application code introduces race conditions in concurrent environments. By packaging logic inside a Redis Lua Script, Redis executes the entire script atomically, blocking other commands until completion without requiring heavyweight distributed locks.

Below is a production-grade Token Bucket Lua script executing inside Redis:

-- Token Bucket Rate Limiting Script in Lua
-- KEYS[1]: Rate limit key (e.g. "rate_limit:user_8492")
-- ARGV[1]: Bucket capacity (e.g., 60)
-- ARGV[2]: Refill rate in tokens per second (e.g., 1)
-- ARGV[3]: Current epoch timestamp in seconds
-- ARGV[4]: Requested tokens (usually 1)

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])

-- Retrieve current bucket state
local data = redis.call("HMGET", key, "tokens", "last_updated")
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    -- Initialize fresh bucket
    tokens = capacity
    last_updated = now
else
    -- Calculate tokens accumulated since last request
    local delta = math.max(0, now - last_updated)
    tokens = math.min(capacity, tokens + (delta * refill_rate))
    last_updated = now
end

-- Check if sufficient tokens exist
if tokens >= requested then
    tokens = tokens - requested
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    redis.call("EXPIRE", key, math.ceil(capacity / refill_rate))
    return {1, math.floor(tokens)} -- Allowed: 1, Remaining Tokens
else
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    return {0, math.floor(tokens)} -- Blocked: 0, Remaining Tokens
end

3. Python Middleware Integration with Standard HTTP Headers

APIs enforcing rate limits must communicate remaining quota to clients using standard HTTP headers (RFC 6585):

• X-RateLimit-Limit: Maximum allowed request capacity.
• X-RateLimit-Remaining: Remaining available tokens.
• Retry-After: Recommended wait time in seconds before retrying.

import time
import asyncio
from fastapi import FastAPI, Request, Response, status
import redis.asyncio as aioredis

app = FastAPI()
redis_client = aioredis.from_url("redis://localhost:6379", decode_responses=True)

# Register compiled Lua script on Redis server
LUA_SCRIPT = """[Lua script content above]"""
rate_limit_lua = redis_client.register_script(LUA_SCRIPT)

@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
    client_ip = request.client.host
    rate_key = f"rate_limit:{client_ip}"
    
    capacity = 60      # Max burst capacity
    refill_rate = 1    # 1 token per second refill
    now = int(time.time())
    
    # Execute Lua script atomically
    result = await rate_limit_lua(keys=[rate_key], args=[capacity, refill_rate, now, 1])
    is_allowed, remaining_tokens = result[0], result[1]
    
    if is_allowed == 0:
        return Response(
            content='{"error": "Too Many Requests", "message": "Rate limit exceeded"}',
            status_code=status.HTTP_429_TOO_MANY_REQUESTS,
            headers={
                "X-RateLimit-Limit": str(capacity),
                "X-RateLimit-Remaining": "0",
                "Retry-After": "60",
                "Content-Type": "application/json"
            }
        )
        
    response = await call_next(request)
    response.headers["X-RateLimit-Limit"] = str(capacity)
    response.headers["X-RateLimit-Remaining"] = str(remaining_tokens)
    return response

Conclusion

Implementing Token Bucket rate limiting via Redis Lua scripts provides low-latency, thread-safe protection for public API ecosystems. By combining atomic server-side script execution with standard HTTP 429 response headers, backend infrastructure remains protected against unexpected traffic bursts.