Distributed Rate Limiting with Redis, 429 Responses and Retry-After

One limit, four servers

A coupon-redemption API allows each key 100 requests a minute. It runs on four servers behind a load balancer, each with its own in-memory counter. A client that sends 100 requests per minute spread evenly is allowed 400 in practice, since the load balancer hands each server about a quarter of them, and a client that sends 400 will not be stopped at all. Per-process limiters are still useful as a cheap local guard, but a shared limit needs shared state. The usual shared store is Redis, because increments are fast, atomic and can expire on their own. See Redis for the data types used here.

The race that check-then-set creates

The tempting first implementation reads the counter, compares it with the limit, and writes back the incremented value. The problem is the gap between the read and the write. Two servers can both read the same value before either writes. The following program replays one such interleaving with a dictionary standing in for Redis, so the interleaving is explicit instead of left to luck.

# A dict stands in for Redis. Two API servers (A, B) check the same key.
LIMIT = 3

def naive_step_by_step():
    store = {"quota:key-77": 2}                 # 2 of 3 requests already used
    # Interleaving that real networks produce: both read before either writes.
    a_read = store["quota:key-77"]              # A: GET -> 2
    b_read = store["quota:key-77"]              # B: GET -> 2
    a_ok = a_read < LIMIT
    b_ok = b_read < LIMIT
    if a_ok:
        store["quota:key-77"] = a_read + 1      # A: SET 3
    if b_ok:
        store["quota:key-77"] = b_read + 1      # B: SET 3 (overwrites A)
    return a_ok, b_ok, store["quota:key-77"]

def atomic_incr():
    store = {"quota:key-77": 2}
    results = []
    for who in ("A", "B"):                      # INCR is one indivisible step
        store["quota:key-77"] += 1
        results.append(store["quota:key-77"] <= LIMIT)
    return results, store["quota:key-77"]

print("check-then-set:", naive_step_by_step(), "-> both allowed, counter says 3 but 4 requests ran")
print("INCR then compare:", atomic_incr())

check-then-set: (True, True, 3) -> both allowed, counter says 3 but 4 requests ran
INCR then compare: ([True, False], 4)

Both servers allowed their request and the counter says 3, yet four requests ran against a limit of three. The fix is to make the read-modify-write one atomic step. For a fixed-window counter, Redis's INCR command already is: it increments and returns the new value in a single operation, and you compare that returned value with the limit afterwards. Rejected requests still increment the counter in that pattern, which is harmless for a window that expires.

Fixed window in Redis, including the expiry trap

A window counter needs an expiry so the key disappears when the window ends. The common pattern is INCR and, when the result is 1, EXPIRE. Run as two separate commands, a crash between them leaves a counter with no expiry, and that key then blocks its client forever. A Lua script runs as a single unit on the Redis server, with no other command interleaved, so the two steps cannot be split. The scripts here are not executed in this course (no Redis server is installed), so test them against your own instance before relying on them.

-- KEYS[1] = counter key, e.g. "rl:key-77:1730000000"
-- ARGV[1] = window length in milliseconds
local current = redis.call('INCR', KEYS[1])
if current == 1 then
  redis.call('PEXPIRE', KEYS[1], ARGV[1])
end
return current

The caller picks the key (including the window number, for instance the current minute) and compares the returned count against the limit. Calling it from Python with the redis client:

import time
import redis

r = redis.Redis(host="localhost", port=6379)
fixed_window = r.register_script("""
local current = redis.call('INCR', KEYS[1])
if current == 1 then
  redis.call('PEXPIRE', KEYS[1], ARGV[1])
end
return current
""")

def allowed(api_key, limit=100, window_s=60):
    slot = int(time.time() // window_s)
    count = fixed_window(keys=[f"rl:{api_key}:{slot}"], args=[window_s * 1000])
    return count <= limit

Token bucket as a Redis script

A token bucket has two numbers of state, so it lives naturally in a Redis hash. The script reads them, refills from elapsed time, spends a token if one is available and writes the result back, all atomically. It takes the time from Redis itself using the TIME command, so all application servers agree even if their own clocks drift. Calling TIME inside a script that then writes is permitted on current Redis versions, but older ones restricted it, so check yours.

-- KEYS[1] = bucket key
-- ARGV[1] = capacity, ARGV[2] = refill tokens per second
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])

local t = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts = tonumber(data[2])
if tokens == nil then
  tokens = capacity
  ts = now
end

tokens = math.min(capacity, tokens + (now - ts) * rate)
local allowed = 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- let idle buckets expire after twice the time needed to refill from empty
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2)
return {allowed, math.floor(tokens)}

What the client should receive: 429 and Retry-After

When you reject, tell the client how to behave. The status is 429 Too Many Requests. The Retry-After header carries either a number of seconds or an HTTP date, saying when to try again. Many APIs also return headers with the limit, remaining count and reset time. The names are not fully standardised: X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset are common in practice, and an IETF draft proposes RateLimit-* headers, so document whichever set you choose. The program below builds that response from a token bucket, computing Retry-After as the time until one token will exist, rounded up to whole seconds.

import math

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity, self.rate = capacity, rate
        self.tokens, self.last = float(capacity), 0.0

    def check(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return 200, {"RateLimit-Remaining": str(int(self.tokens))}
        wait = math.ceil((1 - self.tokens) / self.rate)   # whole seconds, rounded up
        return 429, {"Retry-After": str(wait), "RateLimit-Remaining": "0"}

bucket = TokenBucket(capacity=2, rate=0.5)     # burst of 2, then one per 2 s
for t in [0.0, 0.1, 0.2, 1.0, 2.2]:
    status, headers = bucket.check(t)
    print(f"t={t:3.1f}  {status}  {headers}")

t=0.0  200  {'RateLimit-Remaining': '1'}
t=0.1  200  {'RateLimit-Remaining': '0'}
t=0.2  429  {'Retry-After': '2', 'RateLimit-Remaining': '0'}
t=1.0  429  {'Retry-After': '1', 'RateLimit-Remaining': '0'}
t=2.2  200  {'RateLimit-Remaining': '0'}

When Redis is down: fail open or fail closed

The limiter is now a dependency, and you must decide what a Redis outage means. Fail open lets requests through when the limiter cannot answer, so the site stays up but is unprotected for the duration. Fail closed rejects them, which is safer for a login route but turns a limiter outage into a full outage. A reasonable default is to fail open for general API traffic with a short timeout and an alert, and fail closed (or fall back to a conservative local limit) on security-sensitive routes. Also keep the limiter's call time small: set a tight timeout, so a slow Redis cannot make every request slow.

Common mistakes

• Read, compare, then write in the application. Symptom: under load the limit is exceeded by a margin that grows with concurrency, while single-user tests pass.
• `INCR` without a guaranteed `EXPIRE`. Symptom: a handful of clients permanently blocked until someone deletes keys; memory slowly climbs.
• Using each server's own clock to compute windows. Servers whose clocks differ by a second disagree on which window a request belongs to. Take time from Redis (TIME) or accept the skew.
• No timeout on the Redis call. A slow Redis makes every request slow; the limiter becomes the outage.
• Returning 429 with no `Retry-After`. Clients then retry immediately in a loop, which is the retry storm the limit was meant to stop.

How this shows up in real projects and interviews

The follow-up to "design a rate limiter" is always "now it runs on many servers". The credible answer is a central atomic counter or script in Redis, with a note on clock source, key expiry, failure behaviour and latency. Some teams accept approximate limits to avoid a network hop per request, such as each server taking a local slice of the budget and syncing periodically, trading accuracy for speed. For the wider architecture around that choice see System Design.