Rate Limiting Algorithms From Scratch: Token Bucket vs Sliding Window Log in Redis Lua

Rate limiting sounds simple: allow N requests per minute, reject the rest. But the difference between a rate limiter that works and one that works correctly under concurrent load is whether the check-and-increment is atomic. This post breaks down the two algorithms I implemented for throttleGate and why each exists.

Why Not Fixed Window?

Fixed-window rate limiting (resetting a counter every 60 seconds) has a well-known boundary problem: traffic spikes at the window boundary. If you allow 100 requests/minute, a client can send 100 requests at 11:59:59 and another 100 at 12:00:00 — effectively 200 requests in 2 seconds. Fixed-window is simple but leaky.

Both token-bucket and sliding-window-log solve this, just in different ways.

Sliding Window Log

Maintain a sorted set of timestamps representing each request. When a new request arrives, remove entries older than the window, count what remains, and decide. This gives perfect accuracy but costs memory proportional to the number of requests in the window.

-- KEYS[1] = sorted set key
-- ARGV: windowMs, maxRequests, now, cost

redis.call("ZREMRANGEBYSCORE", KEYS[1], 0, now - windowMs)
local count = redis.call("ZCARD", KEYS[1])

if count + cost <= maxRequests then
    redis.call("ZADD", KEYS[1], now, now .. ":" .. math.random())
    return {1, maxRequests - count - cost, 0, resetTimestamp}
end

return {0, maxRequests - count, retryAfter, resetTimestamp}

Best for: General-purpose rate limiting where precision matters more than memory. This is throttleGate's default algorithm.

Token Bucket

A bucket holds C tokens, refilling at R tokens per second. Each request consumes cost tokens. If the bucket has enough, the request passes and tokens are consumed. If not, the request is rejected until enough tokens refill.

The elegance of token-bucket is that it naturally handles bursts. A full bucket of 100 tokens allows 100 immediate requests, then smooths out to the refill rate. It also supports variable-cost requests — an expensive endpoint can cost 5 tokens while a cheap one costs 1.

-- KEYS[1] = bucket key
-- ARGV: capacity, refillRate, now_seconds, cost

local data = redis.call("HMGET", KEYS[1], "tokens", "lastRefill")
local elapsed = math.max(0, now - (data[2] or now))
local tokens = math.min(capacity, (data[1] or capacity) + elapsed * refillRate)

if tokens >= cost then
    tokens = tokens - cost
    redis.call("HMSET", KEYS[1], "tokens", tokens, "lastRefill", now)
    return {1, tokens, 0, ...}
end

return {0, tokens, (cost - tokens) / refillRate, ...}

Best for: Bursty endpoints, API keys with different costs, login attempt throttling.

Stacked Limits

The real power comes from stacking multiple rules. A single request can be checked against per-IP, per-API-key, per-tenant, and per-endpoint limits simultaneously. Each rule gets its own Lua script execution, and if any rule rejects, the request gets a 429. The headers reflect the most restrictive limit.

Atomicity via Lua

Running these in Lua via Redis EVALSHA guarantees atomicity. No race conditions, no TOCTOU bugs. The script either completes fully or not at all. This is the same technique that Redis uses internally for its own rate limiting features, and it's the only correct way to do distributed rate limiting without distributed locks.