Building High-Throughput Distributed Rate Limiters with Redis and the Token Bucket Algorithm

Protecting web APIs and microservices from abusive traffic, credential-stuffing bots, runaway scripts, and Distributed Denial of Service (DDoS) attacks is a foundational security mandate. In-memory local rate limiters stored in single application server memory fail the moment an application scales horizontally across a cluster of server nodes or containers: a malicious client can bypass limits simply by distributing requests across multiple backend instances. In 2026, enterprise web systems require a centralized, atomic distributed rate limiter.

Among various rate-limiting algorithms (Fixed Window Counter, Sliding Window Log, Leaky Bucket), the Token Bucket algorithm executed via atomic Redis Lua scripts remains the gold standard. It allows controlled bursts of legitimate traffic while strictly enforcing sustained throughput limits with sub-millisecond evaluation latency. This engineering guide walks through algorithm mechanics, Lua script design, and high-throughput Python API middleware integration.

Comparing Rate Limiting Algorithms

Evaluating algorithm trade-offs under high concurrency:

The Token Bucket Mechanics

The Token Bucket operates using three parameters:

1. Bucket Capacity ($B$): The maximum number of tokens a bucket can hold (defines burst capacity).
2. Refill Rate ($R$): How many tokens are added back to the bucket per second.
3. Last Refreshed Timestamp ($T$): When tokens were last computed.

When a request arrives, the algorithm calculates how many tokens were generated since the last request: $\Delta Tokens = \Delta Time imes R$. If the bucket has at least 1 token, the request is permitted, and 1 token is subtracted. If 0 tokens remain, the request is immediately rejected with HTTP 429 Too Many Requests.

The Atomic Redis Lua Script (`token_bucket.lua`)

Because multiple concurrent application servers query Redis simultaneously, token calculation and deduction must execute atomically in a single round trip to eliminate race conditions:

-- token_bucket.lua
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local now = tonumber(ARGV[4])

-- Retrieve current tokens and last updated timestamp
local data = redis.call('HMGET', key, 'tokens', 'last_updated')
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    -- First time client is seen: initialize full bucket
    tokens = capacity
    last_updated = now
else
    -- Replenish tokens based on elapsed time
    local delta = math.max(0, now - last_updated)
    local tokens_to_add = delta * refill_rate
    tokens = math.min(capacity, tokens + tokens_to_add)
    last_updated = now
end

-- Check if sufficient tokens exist
if tokens >= cost then
    tokens = tokens - cost
    redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2)
    return {1, tokens} -- Allowed: returns 1 and remaining tokens
else
    redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)
    return {0, tokens} -- Rejected: returns 0
end

Integrating with Python FastAPI Middleware

Wrap the Redis Lua script in high-speed async middleware:

# middleware/rate_limiter.py
from fastapi import Request, HTTPException
import redis.asyncio as redis
import time

r = redis.Redis(host="localhost", port=6379, db=0, decode_responses=False)

# Load compiled Lua script once into Redis script cache
with open("token_bucket.lua", "r") as f:
    lua_script = f.read()
rate_limit_sha = None

async def rate_limit_middleware(request: Request, call_next):
    global rate_limit_sha
    if not rate_limit_sha:
        rate_limit_sha = await r.script_load(lua_script)

    client_ip = request.client.host
    key = f"rate_limit:{client_ip}"
    
    capacity = 60      # Allow bursts up to 60 requests
    refill_rate = 1.0  # Refill 1 token per second (60 req/min sustained)
    cost = 1
    now = time.time()

    allowed, remaining = await r.evalsha(
        rate_limit_sha, 1, key, capacity, refill_rate, cost, now
    )

    if allowed == 0:
        raise HTTPException(
            status_code=429, 
            detail="Rate limit exceeded. Please slow down."
        )

    response = await call_next(request)
    response.headers["X-RateLimit-Remaining"] = str(int(remaining))
    return response

Conclusion

Distributed rate limiting is an indispensable pillar of modern cloud architecture. By combining the Token Bucket algorithm with atomic Redis Lua scripts, engineering teams protect upstream databases and microservices from abuse while providing smooth burst capacity for legitimate users with microsecond evaluation overhead.