I'm working through system design as an AI engineer, and I'm writing up each problem as I go. This one is a rate limiter. It looked like the easy one. It caught me out in three places.
The problem
Picture a public API that sends SMS messages, something like Twilio. Thousands of companies call it from their servers, on free, paid and enterprise plans.
Two things keep going wrong. A buggy script on a free account loops forever and slows the API down for everyone else. And some customers send bursts to squeeze out more than they pay for.
So we need a rate limiter: a cap on how many requests a client can make in a time window. Go over the cap and the API answers with HTTP 429 Too Many Requests.
Step 1: Ask before designing
I wrote my questions down first. These are the answers I settled on:
- Everything is limited together (sending and status checks), with one limit per client.
- The client is the API key, not the IP address. Lots of customers can share one IP, and one customer can use many.
- Over the limit gets a 429 with a
Retry-Afterheader. - Free gets 60 requests per minute, paid gets 600, enterprise gets 6,000. About 90% of active accounts are free, 9% are paid and 1% are enterprise.
- 100,000 accounts in total, and 20,000 of them active in the peak minute.
- Many API servers behind a load balancer, and the check can only add a few milliseconds.
The question I almost skipped was "who is the client?" Nearly everything else in the design hangs off the answer.
Step 2: Estimate the worst case
I assumed every active account sits exactly at its limit.
| Tier | Active accounts | Requests/min | Requests/sec |
|---|---|---|---|
| Free | 18,000 | 1,080,000 | 18,000 |
| Paid | 1,800 | 1,080,000 | 18,000 |
| Enterprise | 200 | 1,200,000 | 20,000 |
| Total | 20,000 | 3,360,000 | 56,000 |
That's 56,000 requests per second, and the limiter checks every one of them, including the ones it ends up rejecting. A disk-based database can't take that on the hot path, so the counters have to live in memory.
One more number. Paid and enterprise accounts are only 10% of accounts, but they're 68% of the traffic. I didn't think that mattered until the very end.
Step 3: Where does the count live?
My first answer was that the limiter should "make sure the requests across servers add up to 60". That's just the requirement said again. It doesn't tell you how.
Here's what actually goes wrong. If every server keeps its own count, the load balancer spreads one customer's requests across, say, 3 servers, and each server only sees a third of them. With a local limit of 60 on each, that customer can send 180 requests a minute and nobody complains.
So the count has to live in one place that all the servers share. I'd use Redis, because it's in memory and handles this kind of load.
There are two kinds of data here, and I'd keep them apart:
- Config: key X is on the free tier, so the limit is 60 a minute. This almost never changes, so each gateway can cache it in memory and refresh it every minute or so.
- State: key X has used 43 so far. This changes on every request, so it lives in Redis.
I'll come back to why that split matters.
The race condition I missed
Say a key has used 59 of its 60 and two requests arrive at the same moment on two different servers. Each server reads the count (59), sees it's under 60, lets the request through and writes 60. Both got through, when only one should have.
My fix was to keep the servers in sync with each other. That doesn't work. They'd have to message each other on every request, which is slow and messy, and there's still a gap between "check" and "update" where both can decide at the same instant.
The real fix is to stop doing three steps (read, compare, write) and make it one step inside the store. Redis can add 1 to a counter and hand back the new value as a single operation. Server 1 gets 60 and goes ahead. Server 2 gets 61 and gets a 429. It's the same idea as the atomic claim that makes sure only one worker picks up a job from a message queue.
Step 4: Choosing the algorithm
Fixed window. Put the current minute in the key (X:12:00), increment it on every request, and let it expire. It's simple and cheap, one number per key.
But look at the boundary. A client sends 60 requests at 12:00:59 and another 60 at 12:01:00. That's 120 requests in about 2 seconds, and nothing gets blocked.
My first reaction was "that's fine, the window is whatever the platform defines". That's wrong. The limit exists to protect the backend, and the backend was sized for 60 a minute. If all 18,000 free accounts did this at once, it would see about 112,000 requests a second, double what it was built for.
Token bucket. Each client has a bucket that holds up to a set number of tokens. Every request takes one, and an empty bucket means a 429. Tokens drip back in at a steady rate.
The nice part is that you don't need a timer. You store two numbers per key, the tokens left and the time you last saw it, and you work out the refill only when a request shows up:
tokens_now = min(capacity, tokens_saved + (now - last_seen) x refill_rate)
Here's a small example I worked by hand (capacity 3, refill 1 token a second, bucket starts full):
| Time | Tokens available | Result | Tokens left |
|---|---|---|---|
| t=0 | 3 | Allowed | 2 |
| t=0 | 2 | Allowed | 1 |
| t=0 | 1 | Allowed | 0 |
| t=0 | 0 | 429 | 0 |
| t=1 | 1 | Allowed | 0 |
| t=5 | 3 (4 would have built up, capped at 3) | Allowed | 2 |
| t=6 | 3 (2 saved plus 1 refilled) | Allowed | 2 |
I went with the token bucket because there's no boundary to exploit. What I give up is simplicity: two numbers per key instead of one, and the refill maths has to run as one atomic step, since it reads and writes two values.
| Tier | Bucket size | Refill |
|---|---|---|
| Free | 60 | 1 token/sec |
| Paid | 600 | 10 tokens/sec |
| Enterprise | 6,000 | 100 tokens/sec |
One thing to know: a bucket the size of a full minute lets a client burst a whole minute's worth at once. If that's too generous, make the bucket smaller. That's a product decision more than a technical one.
The check itself
Redis runs a Lua script as one uninterrupted step, so the whole check is atomic:
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2]) -- tokens per second
local t = redis.call('TIME') -- Redis's own clock
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
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 + math.max(0, now - ts) / 1000 * rate)
local allowed, retry_after = 0, 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
else
retry_after = math.ceil((1 - tokens) / rate)
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) * 2)
return { allowed, math.floor(tokens), retry_after }
Two details. It uses Redis's clock, not each gateway's, because different machines have slightly different clocks and I don't want them disagreeing about "now". And idle keys expire on their own, so inactive accounts don't eat memory. A key that expired just starts with a full bucket, which is the right behaviour anyway.
The full picture
What the 429 should say
My first answer was "tell them the calls for the minute are over". That's wrong for a token bucket, because there is no minute. Tokens come back continuously, so the useful thing to tell a client is how long until one token exists:
HTTP/1.1 429 Too Many Requests
Retry-After: 1
X-RateLimit-Limit: 60
X-RateLimit-Remaining: 0
For a free key that refills 1 token a second, an empty bucket means Retry-After: 1. If it refilled 1 token every 2 seconds, it would be 2. Successful responses carry the X-RateLimit headers too, so a well-behaved client can slow down before it hits the wall.
Scaling it
56,000 checks a second is within what a single Redis node can do for simple commands, but Lua scripts cost more, so I'd want headroom. I'd spread keys across several Redis nodes with consistent hashing on the API key, so adding a node only moves about 1/N of the keys.
And a key that moves, or a counter that gets lost, isn't a disaster. The client just starts with a full bucket. Worst case, one extra burst.
Replication is asynchronous, so after a failover the last few updates can be lost and a client might briefly get a bit more than its limit. For a rate limiter I'm happy with that. It picks availability over perfect accuracy.
When the limiter itself breaks
If Redis is unreachable, the limiter can't check counts, and it has to pick a default.
- Fail open: let requests through. Customers keep working, but nobody is limited.
- Fail closed: reject requests. The backend is safe, but every customer gets errors.
My first answer was to split by tier: fail open for paying customers, fail closed for free ones. Then I gave a reason that pointed the opposite way ("I'd rather give paying customers an error"), which is fail closed. I'd mixed the two up.
Even after fixing that, the split doesn't hold up against the numbers. Paid and enterprise are 68% of the traffic, so failing open for them leaves two-thirds of everything unchecked. Failing closed for them means errors for the customers who pay. Failing closed for everyone means a protective component takes down the whole product.
What I'd do instead is fail open for everyone, with a safety net. If a gateway can't reach Redis, it switches to a local in-memory bucket using the tier limit divided by the number of gateways. It's rough, but it still stops a runaway script, and it raises an alert straight away.
This only works because each gateway already has the tier config cached. If tier info lived in Redis too, it would disappear in exactly the outage where I need it. That's the reason config and state live in different places.
What I took away
- Ask who the client is before anything else. The rest of the design hangs off it.
- A counter that each server keeps by itself isn't a limit. The count has to be shared.
- "Read, check, write" is a race. Make it a single atomic step inside the store.
- A fixed window leaks at the boundary. Check an algorithm against what the limit is protecting, not just against its own definition.
- Your 429 response has to match your algorithm. With a token bucket, tell the client how many seconds to wait, not that the minute is over.
- Decide what happens when the limiter fails before it happens, and check the decision against your own traffic numbers.
Next I'm going to try the order notifications for something like Flipkart, and this time I'll attempt the whole design on my own before I look anything up.
Top comments (1)
Great write-up. The structured step-by-step reasoning made following along very engaging. Keep up the awesome work!