A rate limiter decides, on every API request, whether the caller is still within its allowance. If it
is, the request goes on to the backend. If it is not, the caller gets 429 Too Many Requests and a
header saying when to try again. It protects the API from one client's runaway loop, keeps a free
tier from eating capacity that paying customers need, and makes abuse expensive.
The logic fits in ten lines. The hard parts are everything around it: the check runs a million times
a second, it must agree across every gateway server, it must add only a millisecond or two, and when
its own store fails it must not take the API down with it. This write-up follows one request: Lumen,
a weather widget on the free tier, calls GET /v1/forecast?city=Lyon with its API key. It passes
through the gateway, the limiter identifies it, finds its rule, takes a token from its bucket in
Redis, and either reaches the forecast service or gets a 429.
Now draw it yourself, cold
You can nod along to a finished design and still freeze five minutes into the real round. In the 14-day free trial you draw this system yourself while an interviewer asks questions and grades every decision.
Understanding the problem
Functional requirements
- Identify each client by its API key, its user id or its IP address.
- Limit each client's requests according to configurable rules, for example 10 requests a second with bursts of 20 on the free tier.
- Reject requests over the limit with HTTP 429, and tell the client when it may retry.
Questions worth asking, with the answers you will usually get:
- Who uses the limiter? Our own API. It is a component of the gateway, not a product sold to others.
- What is a client? An API key when the request carries one, else the signed-in user, else the IP address.
- What do the rules look like? A few hundred of them, set by engineers: per tier, per route, and overrides for single keys. They change a few times a week, and a change should apply without a deploy.
- How exact must it be? A few requests over at the edges is fine. A client getting double its limit, or a whole burst slipping through, is not.
- What if the limiter fails? The API keeps serving, with an approximate limit. Login stays protected.
Out of scope: billing, quotas measured in days or months, and abuse detection (bot scoring, blocking accounts). The limiter enforces the rules it is given; it does not decide who is malicious.
Non-functional requirements
- Fast. The check adds under 10 ms at p99, and about 2 ms in practice. It runs on every request, so every millisecond is paid a million times a second.
- Global. A limit holds across all 25 gateways combined. A few extra requests while state catches up is acceptable; 25 times the limit is not.
- Available. If the limiter's store is slow or down, the API keeps serving within 5 ms of extra wait, under an approximate local limit.
- Scale. 1M requests a second at peak, from 100M daily active clients.
- Configurable. A rule change reaches every gateway within about 10 seconds, without a deploy.
Latency comes first because the limiter sits on the hot path of every request, including the ones it lets through. Global accuracy is the reason the limiter needs shared state at all. Availability decides what happens when that shared state fails, which is the question a senior candidate is expected to raise unprompted.
Back-of-the-envelope estimation
Round hard, and keep the numbers that change a decision.
Gateways. A gateway server (Envoy or NGINX on a large machine) proxies about 40,000 requests a second.
requests: 1M / s at peak
gateways: 1M ÷ 40,000 = 25 gateways
25 gateways means 25 separate memories. A counter kept in one of them sees about a 25th of a client's traffic.
Redis operations. Each request makes one call to Redis: one script that refills, checks and takes a token. A small script costs Redis about 10 µs of CPU, and Redis runs commands on one thread per node.
calls: 1M / s, one script each
per primary: 1 s ÷ 10 µs = 100,000 scripts / s at full CPU
primaries: 1M ÷ 100,000 = 10 at full load
run 20, about 50,000 / s each
Running at half load leaves room for a hot key, a failover and the traffic of the replicas.
Memory per bucket. A bucket is a Redis hash with two fields, the tokens left and the time of the
last refill, under a key such as rl:{ak_lumen}:forecast.
per bucket: key ~30 B + two fields + hash and expiry overhead
≈ 150 B
every client: 100M × 150 B = 15 GB
per primary: 15 GB ÷ 20 = 0.75 GB, the same again on each replica
15 GB is the ceiling, not the working set. A bucket expires once it would have refilled anyway, 3 seconds on the free tier, so only clients active in the last few seconds have a key at all.
Network. An EVALSHA call carries the script's hash, the key and two numbers.
per call: ~150 B request + ~30 B reply = 180 B
cluster: 1M × 180 B = 180 MB / s ≈ 1.4 Gbps
per primary: 1.4 Gbps ÷ 20 ≈ 72 Mbps
Latency. Most of the budget is the network hop to Redis.
identify 0.01 ms parse a header, hash a key
match rule 0.01 ms a map in memory
Redis call 0.3 ms one round trip in the same zone
~1 ms across zones
script 0.01 ms inside Redis
p99 about 2 ms, with queueing
timeout 5 ms, then the local fallback
budget 10 ms
| Quantity | Estimate | What it decides |
|---|---|---|
| Requests | 1M / s | One Redis call per request, never two |
| Gateways | 25 | Counters in gateway memory are wrong by up to 25 times |
| Scripts per primary | 100,000 / s at full CPU | 20 primaries at half load, sharded by key |
| Memory | 15 GB at most | Fits in RAM easily; TTLs keep it far smaller |
| Network | 1.4 Gbps | No concern; one round trip is the cost that matters |
| Redis round trip | 0.3 to 1 ms | Same region, pooled connections; a 5 ms timeout |
See it in the flythrough19 · At scale
Core entities
- Rule: what it matches (a tier, a route, a single key), what it counts by (key, user or IP), the bucket's capacity, its refill rate, and what to do when Redis fails (open or closed).
- Client: the identity requests are counted under:
ak_lumen, a user id, or an IP address. - Bucket: per client and rule, the tokens left and the time of the last refill. It lives in Redis with a TTL.
- Rule set: a numbered version of all the rules, stored centrally and held in every gateway's memory.
The rule is configuration and changes a few times a week. The bucket is state and changes on every request. Keeping them apart is what lets a rule change without touching a single bucket: the capacity and refill rate go into each call, and the bucket only remembers two numbers.
System interface
The limiter is called by the gateway, not by end users. Inside the gateway it offers one check:
check(client, rule) -> { allowed, remaining, resetAt, retryAfter }
What a client sees is HTTP. An allowed request goes on to the backend, and the gateway adds headers to the backend's response:
200 OK
X-RateLimit-Limit: 20 the bucket's capacity
X-RateLimit-Remaining: 4 whole tokens left
X-RateLimit-Reset: 2 seconds until the bucket is full again
A rejected request never reaches the backend:
429 Too Many Requests
Retry-After: 1 seconds until a token is free, rounded up
X-RateLimit-Limit: 20
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 2
Each status code is chosen on purpose:
| Case | Response | Why |
|---|---|---|
| Within the limit | The backend's response, with the headers | The client can pace itself before it hits the limit |
| Over the limit | 429 with Retry-After | 429 means "slow down and retry", which a client library can act on |
| Login while Redis is down | 503 with Retry-After | The limiter cannot decide, so it says the service is unavailable rather than blaming the client |
| Unknown API key | 401, from authentication | Not a rate-limit answer at all |
403 would tell the client it is never allowed, and 500 would page your on-call for a client that is
behaving as designed. The X-RateLimit-* names are a common convention rather than a standard; an
IETF draft defines RateLimit and RateLimit-Policy fields for the same purpose. Retry-After is
standard HTTP and takes either an HTTP date or a whole number of seconds; send seconds. Some APIs
send X-RateLimit-Reset as a Unix timestamp instead; here it is a number of seconds, which is also
what the IETF draft chose, because it does not depend on the client's clock.
High-level design
Start with the smallest design that limits one client correctly on one gateway, then make it global.
1. Identify the client and find its rule
The limiter is middleware in the API gateway: the fleet of servers that every request passes through after the load balancer, which already handles TLS, authentication and routing. Putting the check there means one implementation, every route covered, and no service that can forget it. A request it rejects costs the backend nothing.
There are three places it could go. A library inside every backend service adds no hop, but each service must adopt it, and a request is rejected only after it reached the service. A dedicated rate-limiter service that the gateway calls can be owned, scaled and deployed on its own, but it adds a network hop to every request, out of a 10 ms budget, and one more fleet that has to stay up. The gateway step has neither cost: the gateway already sits on every request's path.
See it in the flythrough02 · Into the gateway
The first step is to decide whom to count. The limiter takes, in order:
- The API key, if the request carries one. Lumen's
X-Api-Keyresolves toak_lumen. - Otherwise the user id, the
subclaim of a verified session token. - Otherwise the IP address: the one your own load balancer appended to
X-Forwarded-For, never one the client wrote there. For IPv6, use the /64 prefix, because one home or phone controls a whole /64, which is effectively unlimited addresses. Many providers hand out a /56 or a /48, so a /64 limit narrows the evasion rather than closing it.
See it in the flythrough03 · Who is calling
IP limits need care. Thousands of phones can share one carrier address, so IP rules are set higher than key rules, and they mostly protect the routes that run before a client has an identity, such as login and sign-up. Every request is also counted by IP before its key is looked up, under a generous limit, so a flood of made-up keys cannot overload the key store.
Next, the rule. A few hundred rules fit in memory, so each gateway holds them in a map, compiled
at load time. The most specific rule wins: an override for this key, then this tier on this route,
then this tier, then the route's default. For Lumen it is the free tier on GET /v1/forecast: a
bucket of 20 tokens, refilled at 10 a second.
See it in the flythrough04 · Find the rule
2. Decide: allow, or answer 429
Now the limiter needs an algorithm: a rule for turning "10 a second, bursts of 20" into a yes or no. There are four common ones.
Fixed window counter. Count requests per client per calendar minute, in a key like
{ak_lumen}:12:00, and reject once the count passes 600. It is one INCR per request and one
integer per client. The flaw is at the boundary. A client can send 600 requests in the last tenth of
a second of 12:00 and 600 more in the first tenth of 12:01. Both windows are within their limit, and
the server takes 1,200 requests in 0.2 seconds, twice what any minute should hold.
See it in the flythrough05 · Bad: fixed window
Sliding window log. Keep a timestamp for every request in the last minute (a sorted set in Redis)
and count them. It is exact, and it is what you reach for when "600 a minute" must mean exactly that
over any 60 seconds. The cost is that it stores one entry per request. Each request trims the old
entries with one ZREMRANGEBYSCORE, adds its own with ZADD, and counts with ZCARD. A sorted set
entry costs about 100 B, so a client at its limit holds 600 × 100 B = 60 KB, where a bucket holds
150 B. A million clients at their limit would need 60 GB, four times the 15 GB that all 100M buckets need
together.
Sliding window counter. Keep the fixed-window counts for this minute and the last, and weight the last one by how much of it still overlaps the sliding minute:
limit 600 a minute, 15 s into the current minute
last minute: 600 requests, current: 200
estimate: 600 × (45 ÷ 60) + 200 = 450 + 200 = 650 > 600 → reject
A fixed window would have allowed it (200 is under 600). It costs two counters and has no 2x boundary burst. The estimate assumes last minute's requests were spread evenly, so it is approximate. If all 600 of them came in its first 10 seconds, none of them is inside the sliding minute at 12:01:15, yet the estimate still counts 450 and rejects a client that sent only 200 in the last 60 seconds.
Token bucket. Each client has a bucket that holds up to 20 tokens and gains 10 a second. A request takes one token, or is rejected if there is none. Two numbers describe the state: the tokens left and the time they were counted. Nothing runs on a timer. The bucket is refilled lazily, when the next request arrives, by the time that has passed:
capacity 20, refill 10 / s
12:00:00.000 tokens 3.0
12:00:00.250 elapsed 0.25 s × 10 / s = +2.5 → 5.5
take 1 → allowed, 4.5 left
The capacity sets the largest burst, 20, and the refill rate sets the long-run average, 10 a second. A client that was quiet for 2 seconds has a full bucket and may send 20 at once, then 10 a second after that. Over any one minute, at most 20 + 10 × 60 = 620 requests get through, against 1,200 for the fixed window.
See it in the flythrough06 · Great: token bucket
Choose the token bucket. It allows the bursts real clients make (a page that loads and fires six calls at once), holds the average firmly, needs two numbers per client, and has no boundary to game. The sliding window counter is a fine second choice when the rule is written as "600 a minute" and you want the window to read that way.
When the bucket has a token, the request goes on, and the gateway adds the headers from what the
check returned. Remaining is the whole tokens left, 4. Reset is the time to refill to 20:
(20 - 4.5) ÷ 10 = 1.55 seconds, rounded up to 2.
See it in the flythrough11 · Allowed
When it has none, the gateway answers at once. Suppose the bucket holds 0.4 tokens. The next whole
token is (1 - 0.4) ÷ 10 = 0.06 seconds away, and Retry-After takes whole seconds, so it says 1. A
well-behaved client library waits a second and retries; one that ignores the header just collects
more 429s.
See it in the flythrough12 · Rejected
Deep dives
1. How does the limit hold across 25 gateways?
The load balancer spreads Lumen's connections over all 25 gateways. The limit is 10 a second for Lumen, not 10 a second per gateway.
BadA counter in each gateway's memory
Keep the buckets in each gateway's memory. It is the first thing you write: no network call, no new dependency, and a check that costs microseconds. It is also exact on one server, so it passes every test on a laptop. In production the load balancer spreads Lumen over all 25 gateways, so each sees about a 25th of its requests and each allows Lumen its full 10 a second. Together they allow 250 a second, 25 times the rule. Worse, the error moves with the fleet: autoscale from 25 to 40 gateways for a traffic peak and Lumen's limit becomes 400 a second at the moment the API can least afford it. A restart also forgets every bucket, and a new bucket starts full. A rolling deploy of 25 gateways hands every client 25 fresh bursts of 20, 500 extra requests per client, every time you ship.
See it in the flythrough07 · Bad: a count per gateway
GoodRoute each client to one gateway
Make the load balancer hash the API key, so every request from ak_lumen reaches the same gateway,
and the counter in that gateway's memory is exact. It works until the fleet changes: adding a
gateway moves a 26th of the keys, and their buckets start full on the new one. A gateway that dies
takes its counters with it. A heavy client pins one gateway while others sit idle. And the load
balancer now needs to read API keys, which most layer 4 balancers cannot.
GreatOne shared store
Keep every bucket in Redis, and have every gateway check the same key. The limit is now global by construction, whatever the fleet size and wherever a request lands. Redis fits the job: the state is two numbers per client, lost buckets are cheap (they start full), every operation is in memory, and one round trip in the same region takes 0.3 to 1 ms.
See it in the flythrough08 · Great: one shared store
The cost is a network call on every request, and a dependency the API now has to survive losing. Deep dives 3 and 4 deal with each.
2. How do concurrent checks stay correct?
Two gateways can check Lumen's bucket in the same millisecond.
BadGET, then SET
The gateway reads the bucket, does the arithmetic, and writes it back. With one token left:
t = 0.0 ms A GET tokens → 1
t = 0.1 ms B GET tokens → 1
t = 0.2 ms A SET tokens 0 → allowed
t = 0.3 ms B SET tokens 0 → allowed
Both requests are allowed on one token, and the bucket ends at 0 as if only one happened. Under a burst, many gateways read the same value, and the client gets several times its limit. It also costs two round trips.
See it in the flythrough09 · Bad: GET then SET
GoodAn atomic counter, INCR with EXPIRE
INCR is atomic in Redis: two gateways incrementing at once get 600 and 601, never 600 twice. That
makes window algorithms safe: increment, then compare the result to the limit. The trap is the
expiry. INCR then EXPIRE as two calls leaves a gap: a gateway that dies between them leaves a key
with no TTL, and once that count passes the limit the client is blocked forever. Send both in one
MULTI/EXEC transaction, with EXPIRE key 60 NX (Redis 7.0 and later) so only the first request
sets it. This is correct
for a fixed or sliding window counter, but a token bucket needs to read, compute and write, which
INCR cannot express.
A distributed lock would also make GET-then-SET correct, at the price of two more round trips and every gateway queueing on a popular client's lock. That is the opposite of fast.
GreatOne Lua script
Redis runs a Lua script atomically: no other command runs on that node until it finishes. So the
whole bucket update goes into one script, loaded with SCRIPT LOAD and called by its hash with
EVALSHA. The script cache is not persisted, so after a restart or failover a call can fail with
NOSCRIPT; the client then sends the script once with EVAL, which most cluster clients do for you.
-- KEYS[1] = rl:{ak_lumen}:forecast
-- ARGV[1] = capacity (20), ARGV[2] = refill per second (10)
local cap = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local t = redis.call('TIME')
local now = t[1] * 1000 + math.floor(t[2] / 1000) -- ms
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or cap -- a new bucket is full
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + math.max(0, now - ts) * rate / 1000)
local allowed = 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { allowed, tostring(tokens) }
See it in the flythrough10 · Great: one Lua script
Four details matter:
- One round trip. Refill, check, take and write happen in one call, so the check costs one network hop, 0.3 to 1 ms, however many steps it has.
- Redis's clock, not the gateway's. If each gateway passed its own time, a gateway whose clock
runs 50 ms ahead would add tokens and one that runs behind would remove them.
TIMEinside the script gives one clock per bucket.math.max(0, …)guards against a clock that steps back after a failover. Since Redis 5, a script replicates the writes it makes rather than the script itself, so callingTIMEis allowed and replicas store the same values. - The TTL. An empty bucket refills in 20 ÷ 10 = 2 seconds, and a full bucket is the same as no bucket. So the key expires 3 seconds after its last use (2 seconds plus a margin), and an idle client costs no memory.
- Return the tokens as a string. Redis converts a Lua number in a reply to an integer, so 4.5
would come back as 4. The gateway parses the string and computes
Remaining,ResetandRetry-Afterfrom it.
If one request must pass two rules, such as Lumen's overall limit and its limit on /v1/forecast,
both keys carry {ak_lumen}, and a two-key version of the script checks both buckets before taking
from either, so a request rejected by the second rule
does not spend a token from the first.
3. How does it reach 1M checks a second within 2 ms?
BadOne Redis
Put every bucket on one Redis primary with a replica for failover. It is tempting because the data fits: 15 GB at most, well within one large machine, and 1.4 Gbps fits one network card. The limit is CPU. Redis runs commands on one thread, and one primary runs about 100,000 scripts a second at full load. A million a second is ten times that, so the queue grows by 900,000 calls every second. After 10 ms it holds 10,000 - 1,000 = 9,000 waiting calls, and at 10 µs each the next one waits 90 ms, far past the 2 ms target and the 10 ms budget. A bigger machine does not help, because more cores do not run Lua faster on one thread. Read replicas do not help either, because every check writes.
GoodRedis Cluster, sharded by client key
Redis Cluster splits keys over 16,384 hash slots, and each primary owns a range. The slot is a CRC16
of the key, or of the part inside braces when the key has them. That part is the hash tag, and it
is why the key is rl:{ak_lumen}:forecast: every bucket of ak_lumen, for every rule, lands in the
same slot, and a script that touches two of them is still a single-node call.
key: rl:{ak_lumen}:forecast
hashed: ak_lumen
CRC16: 0x4B83 = 19,331
slot: 19,331 mod 16,384 = 2,947
owner: primary 4 (slots 2,457 to 3,275 of 20 even ranges)
See it in the flythrough14 · Shard by key
Run 20 primaries at about 50,000 scripts a second each, and give each a replica in another zone. The gateways use a cluster-aware client that caches the slot map, so each check goes straight to the right primary, over a connection pool kept open (a new TCP and TLS handshake would cost more than the check itself). Gateways and Redis sit in the same region: about 0.3 ms to a primary in the gateway's own zone, and up to about 1 ms across zones, well inside a 2 ms p99.
What sharding by key does not fix is one key that is busier than a node.
GreatShard by key, and take hot keys off Redis
Suppose Lumen ships a bug and every installed widget retries in a loop: 100,000 requests a second from one key. Every one of them is a script on primary 4, which has room for about 50,000 a second more. Its other clients start timing out, all for a client whose answer is always "no".
The fix is to let the gateway remember a "no". When the script denies a request, it returns the
tokens left, so the gateway knows when the next token is due: with 0.4 tokens, 60 ms from now. The
gateway keeps rl:{ak_lumen}:forecast → no until now + 60 ms in a small local cache, keyed like the
bucket so one rule's "no" never blocks another rule, and answers 429 itself until then, without
calling Redis.
without the cache: 100,000 calls / s to primary 4
with the cache: each gateway calls about once per new token
25 gateways × 10 / s = about 250 calls / s
When a token appears, a few gateways race for it; one wins and the others cache a new "no". The client still gets exactly its 10 a second.
See it in the flythrough15 · A hot key
Two other tools belong in the same kit. A gateway can count locally and sync in batches: it admits requests against a local slice of a hot key's budget and every few milliseconds sends one script call that takes the batch's total from the bucket, trading a little accuracy for one call instead of hundreds. And a flood from a few addresses can be blocked at the edge, by the CDN's or WAF's own rate rules, before it reaches a gateway at all.
A client that is hot because it is big, not broken, needs a different fix. A key with a limit of
20,000 a second would take 40% of one primary's planned 50,000 a second. Split its bucket into 8 sub-buckets with their own
hash tags, {ak_big:0} to {ak_big:7}, each with an eighth of the capacity and rate, and let each
gateway pick one at random per request. The load spreads over up to 8 primaries. The limit becomes
approximate (a request can be rejected by one sub-bucket while another has tokens), which is fine for
a client that large.
4. What happens when Redis is slow or down?
A primary fails over, a network partition cuts a zone off, or a bad deploy of the Redis fleet stalls every node. The limiter must still answer within its budget.
BadFail closed, and wait
Wait for Redis with no timeout, and reject any request whose check fails. It looks like the safe choice: no client can exceed its limit if nothing gets through unchecked. Now follow a failover. A primary dies, and Redis Cluster promotes its replica only after the node timeout, 15 seconds by default. With no timeout of their own, the gateways' calls to the dead node hang on the open TCP connection, and every request holding one waits with them. That primary owns a 20th of the keys, so about 50,000 requests a second stall, then fail and get a 429. Over 15 seconds that is 750,000 requests refused for clients that never reached their limit. If the whole Redis fleet stalls, it is a million requests a second refused because a component that exists to protect the API is unavailable. The limiter has become the outage.
See it in the flythrough16 · Bad: fail closed
GoodFail open, with a timeout
Give the Redis call a 5 ms timeout, and allow the request when it fails. The API stays up, and for a failover of a few seconds that is often acceptable. Two costs remain. Every request to the dead primary still pays the full 5 ms before it is let through: 50,000 requests a second each spend half the 10 ms budget waiting on a node that will not answer. And nobody on that primary is limited. If it is primary 4 while Lumen's retry loop from deep dive 3 is running, all 100,000 requests a second reach the forecast service unchecked, 1.5M requests over a 15-second failover. Login is open too, so a credential-stuffing run gets unlimited password guesses for as long as Redis is down. An outage of the limiter is exactly when an abusive client can do the most harm.
GreatA timeout, a circuit breaker and a local bucket
- Timeout. 5 ms on the Redis call, well inside the 10 ms budget.
- Circuit breaker. After repeated timeouts (say, half the calls to a primary within a second), the gateway stops calling that primary for a few seconds instead of paying 5 ms on every request, then lets one call through to test whether it is back.
- Local fallback. When a call times out, or while the breaker is open, the gateway runs the same token bucket in its own memory, set to the rule divided by the number of gateways. For Lumen that is a refill of 10 ÷ 25 = 0.4 a second and a capacity of 20 ÷ 25 = 0.8, rounded up to 1 so the client can make a request at all.
See it in the flythrough17 · Great: fail open, locally
The local limit is approximate. A client whose connections all reached one gateway gets a 25th of its rate for the duration, and one spread unevenly gets a little more. Both are better than no limit and better than no API.
The failure mode is per rule. Most rules fail open to the local bucket. Login, password reset
and payments fail closed: while the breaker is open, they answer 503 with Retry-After. A
credential-stuffing run is exactly the traffic that would like the limiter to be down.
Two quieter failures are worth naming. Redis replicates asynchronously, so a failover can lose the
last few milliseconds of writes, and some clients get a few extra tokens. That fits the accuracy
requirement. And a gateway that loses its slot map follows Redis Cluster's MOVED redirects, which
costs an extra round trip per call until it refreshes, so refresh the map as soon as the first
redirect arrives.
5. How do rules change without a deploy?
BadRules in the gateway's code
Write the rules into the gateway's configuration and ship them with the gateway. It is simple, reviewed like code, and needs no store. But every change is a deploy. When Jane's company signs a contract and needs its limit raised today, it waits an hour for a build and a rolling restart of 25 gateways. When an abusive key is sending 100,000 requests a second, blocking it also takes that hour. And one typo, a refill of 0.1 a second where 10 was meant, rolls out to all 25 gateways at once: every free-tier client is limited to 6 requests a minute, and undoing it takes another hour.
GoodRead the rule from a database on every request
Keep the rules in a Postgres table and have the gateway read the matching rule on every request. Every change applies at once, and there is no deploy. But the rules change a few times a week, and they are read a million times a second. That is a second network round trip on every request, 0.3 to 1 ms, which doubles the limiter's latency for data that is almost never different from the last read. It is also a million queries a second against a table of a few hundred rows, which needs a fleet of read replicas of its own. And the rules database becomes one more dependency the API cannot run without: if it is down for a minute, 60M requests arrive with no rule to check them against.
GreatA versioned rule set, polled and swapped in memory
Keep the rules in a rules store: a versioned file in object storage, a table, or a key in etcd. Every change produces a new version, reviewed like code:
version: 43
rules:
- match: { tier: free, route: "GET /v1/forecast" }
key: api_key
capacity: 20
refill_per_s: 10
on_redis_failure: open
- match: { route: "POST /v1/login" }
key: ip
capacity: 5
refill_per_s: 0.1 # 6 a minute
on_redis_failure: closed
Each gateway polls the store every 10 seconds (a conditional GET that costs nothing when the version is unchanged). When it finds version 43, it parses and checks the whole file (every route compiles, every capacity is positive), builds a new rule map, and swaps one pointer. Requests already in flight finish on version 42; new ones use 43. A file that fails the check is ignored, the gateway keeps 42, and an alert fires. Because the gateway polls on its own, a store outage changes nothing: the last good version keeps working. Each gateway also writes the version it is running to local disk, so a gateway that restarts during the outage boots with rules instead of none.
Why poll rather than push? A push, such as an etcd watch or a message on a pub/sub channel, applies a change in well under a second. But a gateway that was restarting or partitioned when the message went out misses it and stays stale until something corrects it, so a push design needs the poll behind it anyway. Rules here change a few times a week, and 10 seconds is fast enough, so polling alone is the simpler design. If rules changed constantly, push a nudge and keep the poll as the backstop.
See it in the flythrough18 · Rules without a deploy
No bucket needs migrating. The capacity and refill rate go into each script call, so if version 43
raises Lumen's capacity to 40, the next call refills up to 40. If a rule lowers a capacity, the
script's math.min clamps the bucket on its next use. The TTL is set from the rule on each call,
so one edge remains: a bucket that expires under the old, shorter TTL just after a rule slows its
refill starts full. At worst a client gets one extra burst, once, which the accuracy requirement
allows.
Final design
One allowed request. Lumen's widget sends GET /v1/forecast?city=Lyon with its key. The load
balancer passes it to one of 25 gateways, which authenticates it and runs the limiter middleware.
The limiter keys it as ak_lumen and finds the free-tier rule for the route in memory: capacity 20,
refill 10 a second. It checks its local cache for a recent "no" and finds none. It hashes
{ak_lumen} to slot 2,947 and sends one EVALSHA to primary 4 over a pooled connection. The script
reads 3.0 tokens counted 250 ms ago, refills to 5.5, takes one, writes 4.5 with Redis's time and a
3-second TTL, and returns allowed and "4.5". The request goes on to the forecast service, and the
response carries X-RateLimit-Remaining: 4 and X-RateLimit-Reset: 2. The limiter added under
a millisecond.
One rejected request. A burst empties the bucket. The script finds 0.4 tokens, allows nothing,
and returns "0.4". The gateway answers 429 with Retry-After: 1, caches "denied for 60 ms", and
answers Lumen's next requests in that window from memory.
See it in the flythrough13 · Every request
When Redis fails. Calls to primary 4 time out at 5 ms, the breaker opens, and every gateway limits Lumen with a local bucket of 0.4 tokens a second until the replica takes over and the breaker closes again. Login answers 503 for the duration.
See it in the flythrough20 · End to end
| Component | Role | Scales by |
|---|---|---|
| Load balancer | Spreads connections over the gateways | Managed, horizontal |
| API gateway | Authentication, routing, and the limiter middleware | 25 servers at 40,000 requests / s |
| Limiter middleware | Identify, match the rule, call Redis, set the headers or answer 429 | Runs in every gateway |
| Rules in memory | The current rule set, compiled into a map | A copy per gateway |
| Deny cache | "No until time t" per hot key | A small map per gateway |
| Local buckets | The fallback while the breaker is open | Per gateway, rule ÷ 25 |
| Redis Cluster | Token buckets, one Lua script per check | 20 primaries and 20 replicas, by hash slot |
| Rules store | Versioned rule sets, polled every 10 s | One small file |
What is expected at each level
Junior. You put the limiter in front of the API, explain one algorithm (a fixed window or a token bucket), keep the counters in a shared store such as Redis, and return 429 when a client is over its limit.
Mid-level. You compare the fixed window, the sliding windows and the token bucket, and say what
each does at a window boundary. You pick one with a reason, keep the update atomic in Redis, set
Retry-After and the limit headers, and own one deep dive end to end.
Senior and above. You lead with the numbers: 1M checks a second, 25 gateways, about 100,000 scripts a second per Redis node, 20 primaries, at most 15 GB of buckets. You write the token bucket as one Lua script using Redis's clock, shard by a hash tag, and handle a hot key with a local deny cache. You choose the failure mode per rule, with a timeout, a circuit breaker and a local fallback, and you change rules without a deploy. At the top of this level you also argue for the simplest design that meets the numbers (a step in the gateway and one Redis cluster, no separate limiter service), say how it grows, and raise the trade-offs a team would weigh: accuracy against load for a client split across sub-buckets or counted locally, and which endpoints may fail closed.
Common mistakes
- Counters in each server's memory. The limit multiplies by the number of servers, and changes every time the fleet scales.
- GET then SET. Two gateways read the same token and both spend it. Make the update one atomic operation in Redis.
- A fixed window with no comment on the boundary. It allows twice the limit across the minute edge. Name it, then fix it or accept it.
- INCR, then EXPIRE, as two calls. A crash between them leaves a key that never expires and blocks the client for good.
- The gateway's clock in the script. Clock skew between gateways adds and removes tokens. Use
TIMEinside Redis. - No timeout on the Redis call. A slow Redis becomes a slow API.
- Failing closed everywhere. An outage of the limiter becomes an outage of the API.
- Trusting
X-Forwarded-Foras sent. A client can write any address there; use the one your load balancer added. - A rule change that needs a deploy. Limits are configuration; keep them in a versioned store the gateways poll.