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 register_script.

import time
import redis

r = redis.Redis()
token_bucket = r.register_script(open("token_bucket.lua").read())


def allow(user_id: str, rate: float = 5, capacity: float = 10) -> bool:
    allowed, _remaining = token_bucket(keys=[f"rl:{user_id}"],
                                       args=[rate, capacity, time.time(), 1])
    return allowed == 1

When each app server passes its own now, clock skew between servers turns directly into error. On Redis 5 and later, a script can call redis.call('TIME') to use the Redis server's clock instead.

Web servers and libraries

• nginx limit_req: uses the leaky bucket method. Excess requests up to burst are queued, and nodelay serves queued requests immediately instead of spacing them out. The default rejection status is 503, so set limit_req_status 429.
• Go golang.org/x/time/rate: a token bucket of size b refilled at r tokens per second.
• Java Guava RateLimiter and Bucket4j: token bucket style; Bucket4j also supports distributed stores such as Redis.
• Envoy and AWS API Gateway: throttle with a local token bucket and with "rate plus burst" settings respectively.
• Cloudflare has written about running rate limiting at scale with a sliding window counter approximation.

limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;

server {
    listen 80;
    location /api/ {
        limit_req zone=api burst=20 nodelay;
        limit_req_status 429;
    }
}

Common pitfalls

• Store outages: decide up front whether to allow everything (fail open) or reject everything (fail closed) when Redis is unreachable. Ordinary APIs usually fail open; security-sensitive limits such as login attempts may warrant failing closed.
• Recording rejected requests: if a sliding log also stores rejected requests, a client that keeps hammering is never released and memory keeps growing.
• Fairness: with only per-key limits, a huge number of users can still exceed total capacity. Combine per-key and global limits, and charge more for expensive operations.
• Burst size: a capacity that is too small rejects legitimate traffic, such as the parallel requests a single page load fires.
• Communication: send Retry-After and the remaining quota with every 429, and document your limits, so clients can pace themselves.

Summary

• Sharing a limit across servers requires a shared store such as Redis.
• Sending INCR and EXPIRE separately is not atomic; bundle them in a Lua script.
• The nginx, Go and Java ecosystems ship battle-tested token bucket and leaky bucket implementations.
• Design the outage policy, fairness, burst size and client communication together with the algorithm.

Further reading

• Rate limiting (Wikipedia)
• Token bucket (Wikipedia)
• Redis INCR command and the rate limiter pattern
• Redis EVAL command
• nginx ngx_http_limit_req_module
• RFC 6585: 429 Too Many Requests
• Go golang.org/x/time/rate