Distributed Rate Limiting: Token Bucket vs. Sliding Window Counter in Redis

The Flaw in Fixed-Window Rate Limiting

Rate limiting is the frontline defense of any production API. It protects relational databases against denial-of-service spikes, prevents credential-stuffing attacks on authentication endpoints, and enforces fair-use quotas on commercial API tiers. However, many engineering teams implement rate limiting using naive Fixed-Window counters (e.g., storing a count in Redis with a 60-second TTL keyed by user_id:minute).

Fixed-window rate limiting contains a fatal mathematical vulnerability: boundary traffic bursting. If a user is allowed 100 requests per minute, they can issue 100 requests at 12:00:59 and another 100 requests at 12:01:00. Over a two-second window, the client successfully fires 200 requests—doubling your allowable capacity and potentially crashing sensitive downstream database services. Eliminating this requires sliding window algorithms.

1. Algorithmic Showdown: Token Bucket vs. Sliding Window

• Token Bucket: A bucket holds up to $B$ tokens. Tokens refill at a steady rate $r$ per second. Each incoming request consumes one token. If the bucket is empty, the request is rejected.
  • Strengths: Permits controlled bursts (up to bucket capacity $B$) while strictly enforcing long-term average throughput.
  • Complexity: Requires computing fractional token refills based on timestamps on every single request.
• Sliding Window Counter: Evaluates the exact rolling time window (e.g. the preceding 60.0 seconds from the current microsecond).
  • Strengths: 100% mathematically immune to boundary burst attacks; guarantees that no rolling 60-second frame ever exceeds the limit.
  • Storage: Uses Redis Sorted Sets (ZSET) where timestamps serve as scores.

2. Atomic Sliding Window Rate Limiter with Redis Lua Scripts

Executing multiple Redis commands (checking size, adding an element, setting expiration) across a network introduces race conditions. Under high concurrency, multiple parallel requests can read an old count and all succeed. The solution is executing the sliding window check inside an atomic Redis Lua script:

-- rate_limiter.lua
-- KEYS[1]: Rate limit key (e.g. 'ratelimit:user_123')
-- ARGV[1]: Current Unix timestamp with milliseconds
-- ARGV[2]: Rolling window duration in seconds
-- ARGV[3]: Maximum allowed requests in window

local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local clear_before = now - window

-- 1. Remove expired timestamps outside the rolling window
redis.call('ZREMRANGEBYSCORE', key, 0, clear_before)

-- 2. Count current active requests inside the window
local current_requests = redis.call('ZCARD', key)

if current_requests < limit then
    -- 3. Quota available: Record current request with unique timestamp
    redis.call('ZADD', key, now, now)
    redis.call('EXPIRE', key, window + 1)
    return {1, limit - current_requests - 1} -- {Allowed: true, Remaining: count}
else
    -- 4. Quota exceeded: Reject request
    return {0, 0} -- {Allowed: false, Remaining: 0}
end

3. Django Middleware Integration

Integrate the atomic Lua script cleanly into Django middleware, setting industry-standard HTTP rate limit response headers (X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After):

import time
from django.core.cache import cache
from django.http import JsonResponse

# Pre-load SHA1 digest of the Lua script for maximum Redis throughput
LUA_SCRIPT = "..." # Lua code string from above
redis_client = cache.client.get_client()
script_sha = redis_client.script_load(LUA_SCRIPT)

class SlidingWindowRateLimitMiddleware:
    def __init__(self, get_response):
        self.get_response = get_response

    def __call__(self, request):
        if request.path.startswith('/api/'):
            client_id = request.user.id if request.user.is_authenticated else request.META.get('REMOTE_ADDR')
            key = f"ratelimit:{client_id}"
            now = time.time()
            window_seconds = 60
            max_limit = 100

            # Execute atomic Lua script in Redis (< 1ms)
            is_allowed, remaining = redis_client.evalsha(
                script_sha, 1, key, now, window_seconds, max_limit
            )

            if not is_allowed:
                response = JsonResponse({
                    'error': 'API rate limit exceeded. Slow down your requests.'
                }, status=429)
                response['Retry-After'] = str(window_seconds)
                response['X-RateLimit-Limit'] = str(max_limit)
                response['X-RateLimit-Remaining'] = "0"
                return response

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

        return self.get_response(request)

"A rate limiter with race conditions is not a rate limiter—it is an illusion. Executing sliding window calculations atomically inside Redis guarantees zero boundary bursts and sub-millisecond overhead."

Key Architectural Takeaways

Protecting modern APIs requires moving beyond fragile fixed-window counters. By leveraging Redis Sorted Sets and atomic Lua script execution, you achieve true sliding-window rate limiting that completely eliminates boundary burst vulnerabilities and maintains strict throughput compliance under heavy concurrent load.