A rate limit is a promise: "no more than R requests per second, with burst B." The mechanism that keeps the promise across thousands of instances is the token bucket stored in Redis and drained atomically. Walk one request through it.
trace stepSystem
The API gateway extracts the limiter key — API key, user ID, or IP. That key maps to a bucket: capacity
B tokens (say 100) refilling at R tokens/second (say 20). The bucket lives in Redis as a key holding {tokens, lastRefillTs}.trace stepSystem
The limiter runs a Lua script against Redis (one round trip, ~0.5–1ms). The script fetches the key:
tokens = 3.4, lastRefill = 1718800000.000. If the key doesn't exist (first request, or idle long enough to expire), it is created full: tokens = B.trace stepSystem
Elapsed time since
lastRefill is converted into tokens: with 0.8s elapsed and R = 20/s, refill = 16. Tokens become min(B, 3.4 + 16) = 19.4. The cap at B is what makes the bucket a bucket and not a hoard — idle time buys at most one full burst.trace stepSystem
The script now branches: if
tokens >= 1, deduct one, persist {tokens-1, now}, and return ALLOW. If not, persist {tokens, now} and return DENY. The entire read-modify-write happens inside one Lua script, and Redis executes scripts atomically — no interleaving, no lost updates. This is the entire race-free guarantee: two simultaneous requests can't both read tokens = 1.trace stepSystem
ALLOW: the request proceeds with a
RateLimit-Remaining header (19.4 tokens left). DENY: the response is 429 with Retry-After: 3 — the seconds until a token refills (ceil((1 - tokens)/R)). The gateway may also set X-RateLimit-Limit / X-RateLimit-Remaining / X-RateLimit-Reset so clients can self-throttle before hitting the wall.trace stepSystem
Time-based refill means no background job, no timer, no clock drift problem — the next request recomputes from wall time. Idle buckets self-clean: a
PEXPIRE (say 2× bucket full-refill time) drops keys that are fully refilled and unused, so a million users leaving don't leave a million stale keys.tokens, last = get(key) or (B, now)
tokens = min(B, tokens + (now - last) * R) # refill by elapsed time
if tokens >= 1:
set(key, tokens - 1, now); expire(key, 2 * B / R)
return ALLOW
else:
set(key, tokens, now)
return DENY, ceil((1 - tokens) / R) # Retry-AfterThe cost ledger per request: one Lua round trip to Redis (~0.5–1ms), one atomic read-modify-write, and zero background work. The guarantee: exact rate enforcement across any number of instances, because the counter lives in one place and the check is atomic — the two properties that make distributed rate limiting equivalent to a single-machine limiter.