Rate Limiter: Shared State and Atomicity Deep Dives
How do you ensure consistent rate limiting across multiple gateway instances?
Level: Senior
You run 10 gateway instances behind a load balancer. A client with a limit of 100 requests a minute sends 200, and the load balancer spreads them evenly: 20 to each gateway. If every gateway keeps its own buckets, each sees 20 requests, well under 100, and all 200 pass — twice the limit. With 50 gateways, the same client could get 50 times its limit.
Counting has to happen in one place that every gateway shares.
What the Shared Store Has to Do
- Answer in one round trip. The check is on the path of every request.
- Update a bucket atomically. Read, decide and write must happen as one step, or two gateways can spend the same token.
- Forget on its own. A bucket has to disappear once it stops mattering, without a cleanup job.
Notice what it does not need: durability. A bucket that is lost is a full bucket, so the worst a lost write can do is let a few extra requests through.
Why Redis, and Why Not the Others
Redis does all three: it keeps everything in memory, runs a short script atomically (the next deep dive), and expires keys by itself. A Redis Cluster spreads the buckets over shards.
A relational database can make the update atomic too, with one UPDATE … RETURNING per check. But it makes every check a durable write — logged to disk before it answers — which is exactly the cost a rate limiter does not need, at 3 million checks a second.
Memcached has atomic incr/decr and compare-and-swap. That is enough for a fixed-window counter — Cloudflare's rate limiter counts in a memcached fork — but a token bucket's read-decide-write would need a compare-and-swap loop that retries whenever another gateway got there first, and the retries pile up on the busiest keys.
Scaling the Store
A Redis Cluster splits keys into 16,384 hash slots and gives each shard a range of them. Every bucket lives in exactly one slot, so every check of a client's key goes to the same shard, and all of them run on that shard's single command thread, one after another. Capacity grows by adding shards: the estimate needs 50 primaries for 3 million checks a second, each with a replica.
What "One Count" Can Promise
On one primary, every gateway sees every update, because all of them go through the same thread. Replication to the replica, however, is asynchronous. If a primary fails, the replica that takes over may not have its last writes; Redis's documentation is explicit that "acknowledged writes can still be lost during a failover". For the buckets on that shard, the last moments are forgotten: some clients get a few extra requests, then everything is normal again. WAIT makes the window smaller but does not close it.
For a rate limiter that is an acceptable trade. For billing or quotas that must never be exceeded it is not, which is why those keep their totals in a durable store.
The Alternative: Local Counts, Synced Periodically
Each gateway counts locally and sends its counts to a central store every second; the central store adds them up and sends back each client's total. Gateways keep working if the central store is down, and the hot path has no network call.
The cost is accuracy. Between syncs, every gateway admits up to the full limit on its own: with 10 gateways and a limit of 100 a minute, a client can get 1,000 requests through before the first sync catches it. That is fine for coarse limits ("no more than 50,000 a second from one tenant"), not for per-client ones. Token leasing, in the deep dive on hot keys, is a middle ground that never overshoots.
Across Regions
All of this assumes the gateways share one Redis Cluster in one region. A limit that has to hold across regions is a different problem — a round trip between regions takes tens of milliseconds, too slow for the hot path — and it is one of the Staff-level discussion topics.
How do you ensure atomic check-and-update of token bucket state under concurrent requests?
Level: Senior
A client has one token left. Two of its requests arrive at the same moment on two gateways. Gateway A reads "1 token", allows its request and writes 0. Gateway B read "1 token" before A's write landed; it allows its request too, and also writes 0. Two requests passed on one token.
The Problem: Read, Decide, Write
A check is three steps: read the bucket, decide (and compute the new token count), write it back. If the steps of two checks can interleave, both can read the same state. In a test, 50 threads doing the three steps as separate Redis commands against a bucket of 100 tokens let through far more than 100 requests; the same checks done by a script let through exactly 100.
How Redis Makes It Atomic
Redis executes commands on one thread, one at a time, and a Lua script runs the same way. In Redis's words: "While executing the script, all server activities are blocked during its entire runtime." A script that reads, decides and writes is therefore atomic — no other command runs in the middle — without any lock.
The Script
-- One token bucket, checked and updated in one atomic step.
-- KEYS[1] the bucket, e.g. rl:key:ak_abc123
-- ARGV capacity, tokens added per period, period in ms, cost of this request
local capacity = tonumber(ARGV[1])
local per_ms = tonumber(ARGV[2]) / tonumber(ARGV[3])
local cost = tonumber(ARGV[4])
local t = redis.call('TIME') -- Redis's clock: one clock for every gateway
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000) -- ms
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity -- no key: a full bucket
local ts = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * per_ms)
local allowed, retry_ms = 0, 0
if tokens >= cost then
tokens, allowed = tokens - cost, 1
else
retry_ms = math.ceil((cost - tokens) / per_ms) -- until enough tokens are back
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil((capacity - tokens) / per_ms)) -- full by then, so no key means the same
return {allowed, math.floor(tokens), retry_ms}What each part is for:
TIME: Redis's clock, not the gateway's. Many examples pass each gateway's own clock in as an argument. Gateways' clocks disagree, and then the elapsed time between two checks can come out negative — tokens taken away — or too large — tokens added twice. Clocks kept in step by NTP typically differ by milliseconds; a host whose synchronization has failed can be seconds off. In a test of that version, a client sending at half its limit through two gateways whose clocks were 2 seconds apart had 60 of its 120 requests rejected: every request that reached the gateway whose clock was behind. CallingTIMEinside a script that writes is allowed because Redis replicates a script's effects (its writes), not the script itself — the default since Redis 5.0 and the only mode since 7.0.- Milliseconds. With whole seconds, two requests in the same second would refill nothing between them.
math.max(0, now - ts). If a failover moves the bucket to a replica whose clock is a little behind, the elapsed time could come out negative. Clamped, a clock step can only pause refills, never take tokens away.- The rate as two integers, tokens per period in milliseconds, so that "100 a minute" is exact.
- An expiry equal to the time to refill. A missing key means a full bucket, so the key may disappear exactly when the bucket would be full again —
(capacity − tokens) ÷ rate. After one request from a full 100-a-minute bucket, that is 600 ms. A fixedEXPIRE key 3600would keep every idle bucket 60 times longer than needed; an expiry shorter than the refill time would hand out tokens too early. HSETwith several fields:HMSEThas been deprecated since Redis 4.0.0.- Integers in the reply. Redis turns Lua numbers into integers on the way out, so the script returns the tokens rounded down and the retry time in milliseconds rather than a fraction of a second.
Calling It
Load the script once with SCRIPT LOAD, which returns its SHA1 digest, and run it with EVALSHA and that digest, so the script's text is not sent on every call:
EVALSHA <sha1> 1 rl:key:ak_abc123 100 100 60000 1
The script cache is not part of the data: it is empty after a restart, and on a replica that has just been promoted. EVALSHA then fails with NOSCRIPT, and the client loads the script again and retries; most Redis clients do this on their own. Inside a pipeline that retry is not possible — the other commands have already gone — so clients send the full script with EVAL when pipelining.
Redis 7.0 and later offer a cleaner option: functions. FUNCTION LOAD registers a named function that Redis stores with the data, persists and replicates, and FCALL calls it by name; there is no NOSCRIPT. In a Redis Cluster, the function must be loaded on every primary.
What It Costs
About 3 µs of server time per call in our test, against 0.3 µs for a plain INCR: one Redis process ran 121,000 to 180,000 calls a second. The network round trip, a few hundred microseconds, costs far more than the script.
Alternatives
An optimistic transaction. WATCH the key, read it, compute, then MULTI … EXEC: Redis runs the transaction only if no other client changed the key since the WATCH, and otherwise returns nothing, and the client starts again. That is a correct check-and-set — in a test, two clients racing for one token got exactly one between them. But every check takes several round trips, and on a busy key the transactions keep failing and retrying.
A lock. Take a lock (SET lock NX PX 100), read, write, release. It is one round trip to take the lock and one to release it, gateways wait on each other on busy keys, and the lock's own expiry must outlast the work it protects. A script needs none of this.
One number instead of two. The generic cell rate algorithm (GCRA) stores only the time at which the bucket will next be full and makes the same decisions; the redis-cell module implements it as one command, CL.THROTTLE. It is smaller (84 bytes per key against 132 in our measurement), at the price of a less obvious formula.
How do you handle multiple rate limit rules per request?
Level: Mid
A request arrives from API key ak_abc123, which belongs to the tenant org_acme, from the address 203.0.113.42. Three rules apply: 1,000 requests a minute per IP address, 100 a minute per API key, and 10,000 an hour per tenant. All three have to be checked without tripling the latency.
One Key per Rule
Each rule has its own bucket, under its own key:
- Per IP address:
rl:ip:203.0.113.42 - Per API key:
rl:key:ak_abc123 - Per tenant:
rl:tenant:org_acme
The gateway builds the three keys and calls the token-bucket script once for each, with that rule's capacity and rate.
Sending Them Together
On one Redis server, the three calls go in one pipeline: written back to back, answered together, one round trip.
In a Redis Cluster the three keys hash to different slots — in a test, slots 10,489, 2,034 and 1,700 — and usually to different shards. One script cannot take all three: Redis rejects a script whose keys are in different slots with a CROSSSLOT error. The client sends each call to the shard that owns its key, all three at once, so the request still waits about one round trip: that of the slowest shard.
Combining the Answers
Each call returns {allowed, remaining, retry_ms}. The rule is simple: reject if any rule rejects, and wait for the longest retry.
| Per IP | Per API key | Per tenant | Decision | Retry-After |
|---|---|---|---|---|
| Allow | Allow | Allow | Allow | — |
| Allow | Reject (0.6 s) | Allow | Reject | 1 s |
| Reject (2 s) | Allow | Allow | Reject | 2 s |
| Reject (2 s) | Reject (0.6 s) | Reject (0.4 s) | Reject | 2 s |
The headers describe the tightest rule, the one with the fewest requests left, and the body names it.
Does a Rejected Request Still Cost Tokens?
When the per-IP rule rejects a request, the per-key and per-tenant scripts in the same round trip have already taken a token each. Two consequences: a client that keeps pushing past one limit also drains its others — usually what you want, since abuse should cost the abuser — and a rejected request still counts against its tenant.
Envoy's rate limit service behaves the same way: it counts every rule that matches and returns "a logical OR of all the individual rate limit decisions", and it has an opt-in setting to stop counting once one of the keys is already over its limit. If a rejected request must not cost the other rules anything, there are two ways:
- Check in order, stop at the first rejection. The rules are no longer sent together, so the request pays a round trip per rule.
- Refund. When the combined answer is no, give the tokens back to the rules that allowed it, with a second call.
We send all three together and accept the charge: one round trip, and the cost lands on clients that are already over a limit.
