Distributed Rate Limiting at Scale: Sliding Window Logs & Token Buckets with Redis Cluster

The Flaw in Fixed-Window Rate Limiting: The Boundary Burst Problem

Protecting backend services, payment gateways, and authentication endpoints against abuse requires robust rate limiting. In early iterations, engineering teams often reach for naive Fixed-Window Counters, such as incrementing an integer key in Redis with a 60-second TTL: INCR ratelimit:user_123:minute_42.

While computationally trivial, fixed-window counters introduce a critical security vulnerability: The Boundary Burst Exploit. Consider an API configured to permit 100 requests per minute:

• An attacker transmits 100 requests at 11:59:59 (the final second of Window A).
• The clock rolls over to 12:00:00 (Window B begins).
• The attacker immediately transmits another 100 requests at 12:00:01.

Under this pattern, the client transmitted 200 requests within a 2-second interval without ever violating the fixed-window limit. For downstream relational databases and AI inference microservices, this burst can cause connection pool starvation, CPU spikes, and cascading latency timeouts.

1. Algorithmic Trade-Offs: Sliding Window Log vs. Token Bucket

To eliminate boundary bursts, distributed architectures rely on two primary algorithms:

2. Atomic Sliding Window Log via Redis Lua

In distributed environments with multiple web workers (Gunicorn, ASGI, or Node clusters), rate limiting operations must be strictly atomic. Executing multiple commands from application code (e.g. ZREMRANGEBYSCORE, followed by ZCARD, followed by ZADD) introduces catastrophic race conditions where concurrent requests bypass thresholds.

By encapsulating the algorithm inside a Redis Lua script, Redis executes the entire sequence atomically in a single thread, guaranteeing thread-safe, lock-free evaluation:

-- atomic_sliding_window.lua
-- KEYS[1]: Rate limit key (e.g. {ratelimit:ip}:192.168.1.1)
-- ARGV[1]: Current UNIX timestamp in milliseconds
-- ARGV[2]: Window size in milliseconds (e.g. 60000 for 1 minute)
-- ARGV[3]: Max requests allowed in window
-- ARGV[4]: Unique request ID (prevents duplicate scoring)

local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local max_limit = tonumber(ARGV[3])
local request_id = ARGV[4]

local clear_before = now - window

-- 1. Evict timestamps that have fallen outside the rolling window
redis.call('ZREMRANGEBYSCORE', key, '-inf', clear_before)

-- 2. Count requests currently within the rolling window
local current_requests = redis.call('ZCARD', key)

if current_requests < max_limit then
    -- 3. Under limit: register current request timestamp
    redis.call('ZADD', key, now, request_id)
    -- Refresh TTL so idle keys automatically expire
    redis.call('PEXPIRE', key, window)
    return {1, max_limit - current_requests - 1, 0} -- Allowed, Remaining, Retry-After (0)
else
    -- 4. Rate limit exceeded: calculate retry-after duration based on oldest entry
    local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
    local retry_after = 0
    if oldest[2] then
        retry_after = math.ceil((tonumber(oldest[2]) + window - now) / 1000)
    end
    return {0, 0, retry_after} -- Blocked, Remaining, Retry-After (seconds)
end

3. Redis Cluster & Hash Tag Sharding: Avoiding Cross-Slot Errors

When scaling out from a standalone Redis instance to a Redis Cluster, keys are sharded across 16,384 hash slots based on CRC16 hashing. If a Lua script touches multiple keys, or if application code attempts multi-key transactions across nodes, Redis aborts with CROSSSLOT Keys in request don't hash to the same slot.

To ensure deterministic routing in clustered topologies, enforce Redis Hash Tags:

# Correct: Uses curly braces {} to enforce hash slot pinning
rate_limit_key = f"{{user_rl:{user_id}}}:api_v1"

# Any associated metadata keys also map to the same node:
log_key = f"{{user_rl:{user_id}}}:audit_trail"

By enclosing user_rl:{user_id} within braces, Redis Cluster hashes only the enclosed substring, guaranteeing that all operations for that user land on the exact same physical cluster shard.

4. Python / Django Middleware Implementation

Integrating the atomic limiter into a high-throughput Django application requires pre-loading the Lua script into Redis using SCRIPT LOAD to minimize network payload sizes:

import time
import uuid
from django.core.cache import cache
from django.http import JsonResponse
from redis import Redis

class DistributedRateLimitMiddleware:
    def __init__(self, get_response):
        self.get_response = get_response
        self.redis_client: Redis = cache.client.get_client()
        with open("scripts/lua/atomic_sliding_window.lua", "r") as f:
            self.lua_sha = self.redis_client.script_load(f.read())

    def __call__(self, request):
        if not request.path.startswith("/api/"):
            return self.get_response(request)

        client_ip = request.META.get("HTTP_X_FORWARDED_FOR", request.META.get("REMOTE_ADDR")).split(",")[0].strip()
        key = f"{{rate_limit:{client_ip}}}:window"
        now_ms = int(time.time() * 1000)
        window_ms = 60000 # 60 seconds
        max_requests = 100

        try:
            allowed, remaining, retry_after = self.redis_client.evalsha(
                self.lua_sha, 1, key, now_ms, window_ms, max_requests, str(uuid.uuid4())
            )
        except Exception:
            # Circuit breaker: Fallback open on Redis connectivity failure
            return self.get_response(request)

        if not allowed:
            response = JsonResponse(
                {"error": "Too Many Requests", "retry_after_seconds": retry_after},
                status=429
            )
            response["Retry-After"] = str(retry_after)
            response["X-RateLimit-Limit"] = str(max_requests)
            response["X-RateLimit-Remaining"] = "0"
            return response

        response = self.get_response(request)
        response["X-RateLimit-Limit"] = str(max_requests)
        response["X-RateLimit-Remaining"] = str(remaining)
        return response

5. Production Architecture Takeaways

• Fail-Open vs. Fail-Closed: For public APIs, design a circuit breaker that fails open if Redis experiences a cluster failover or network partition. For high-security payment or authentication routes, fail closed to prevent automated brute-force attacks during infrastructure degradation.
• Memory Grooming: The sliding window log creates ZSET members that must be cleaned. Always ensure the PEXPIRE command runs inside the Lua script so abandoned keys do not linger indefinitely in RAM.

Deploying atomic sliding window algorithms via Redis Lua provides rock-solid defense against burst exploitation, providing predictable capacity planning and sub-millisecond overhead across high-throughput distributed systems.