Real-World Use

On one server, an in-memory token bucket is enough. Once a load balancer spreads a user's requests over many servers, per-server counters loosen the limit by the server count. This chapter covers sharing a limit through Redis, the limiters built into web servers and libraries, and the pitfalls that come up in production.

A fixed window with Redis INCR and EXPIRE

The most common distributed implementation creates one key per window and counts with INCR. INCR is atomic, so concurrent increments from many servers never lose a count. Each key gets an expiry so past windows clean themselves up.

import time
import redis

r = redis.Redis()


def allow_naive(key: str, limit: int, window: int) -> bool:
    bucket = f"rl:{key}:{int(time.time()) // window}"
    count = r.incr(bucket)            # atomic +1; a missing key becomes 1
    if count == 1:
        r.expire(bucket, window)      # set the expiry on the first hit only
    return count <= limit

There is a gap here. INCR and EXPIRE are each atomic, but the pair is not. If the process dies or the connection drops between them, the key is left without an expiry and lives forever. The fix is to bundle both commands into one Lua script.

Atomicity with a Lua script

While Redis runs a Lua script sent with EVAL (or EVALSHA), no other client command and no other script is executed. That makes read-compute-write free of race conditions and also cuts the work down to one network round trip. A few things to keep in mind:

• The whole server waits while a script runs, so keep scripts short.
• If a script fails halfway, writes it already made are not undone. This is not a relational database rollback.
• Pass every key the script touches through KEYS. In Redis Cluster, all keys of one script must live in the same hash slot.

Here is a script that keeps an entire token bucket in one Redis hash.

-- KEYS[1] = bucket key, ARGV = rate, capacity, now (seconds), cost
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate)
local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) * 2)
return {allowed, tostring(tokens)}

A missing key is treated as a full bucket, so once enough time has passed for the bucket to refill, letting the key expire changes nothing. The remaining tokens are returned as a string because Redis truncates Lua numbers to integers in replies. From Python, load it with redis-py's .