Case study: Rate limiter for many servers

Lesson 56 gave the counting methods. A real service has many app servers behind a load balancer. The interviewer asks: "A client sends requests to many servers. How does the limit still hold?"

A weak answer says "keep a counter" and does not say where. A strong answer puts the counters in one shared place and does each check in one atomic step. It works out how many checks per second that place must take. It also says what happens when the shared place fails, and how an attacker can get around the limit.

At SDE-1 level you should explain why a counter in each server is wrong. At SDE-2 level you should use a shared store and an atomic step. At SDE-3 level you should size it, handle failure, and describe abuse.

Think of a bank with 10 counters. The rule says: at most Rs 10,000 a day for each customer. Each clerk keeps a paper list and never talks to the other clerks. A customer visits all 10 counters and takes Rs 10,000 at each one. The rule says Rs 10,000, but the customer got Rs 100,000.

The same happens with app servers. A load balancer (lesson 28) sends one client's requests to different servers. If each server counts for itself, the limit is multiplied by the number of servers. Dividing the limit by the number of servers does not work well either. The requests of one client are not spread evenly, so a client who sends few requests can still be refused. And a server that restarts forgets its counts.

The fix is one shared place that holds all counters. Every server asks it for each check.

Shared counters in Redis

Use Redis (lesson 37). It is fast because it keeps data in memory. The key names the rule, the client and the window, for example rl:search:key42:2026-10-20T10:15 for a fixed window of one minute. A check is one network call to Redis.

For a fixed window the check is: INCR the key, and refuse if the answer is above the limit. Old windows must disappear, so each key needs a time to live. That needs a second command, EXPIRE. Two separate commands are a problem. If the app server stops between them, the key never expires. Here the window is in the key name, so a new window uses a new key, and the old key is only wasted memory. If the key had no window in its name, the client would stay blocked until someone deleted the key. The Redis documentation names this problem. The fix is to run both commands as one unit. Use a transaction (MULTI and EXEC, which make Redis run the listed commands together) or one script.

Atomic steps

An atomic step cannot be interrupted (lesson 22). It matters here because many servers check the same counter at the same moment. Suppose the app reads a bucket, sees 1 token, and writes back 0. Two servers can both read 1, and both write 0. Both let the request pass, and one token served two requests. This is the lost update from lesson 21. So never read a counter and then write it from the app. Use INCR, or put the whole check in a script.

The token bucket (lesson 56) needs several steps: read the tokens and the last time, add the refill, take one token, write both back. Put them in one Lua script. Redis runs a script as one atomic step (lesson 37): no other command runs in the middle.

-- KEYS[1] = bucket key; ARGV = capacity, refill per second, ttl (whole seconds)
local t = redis.call('TIME')
local now = t[1] + t[2] / 1000000
local b = redis.call('HMGET', KEYS[1], 'tokens', 'last')
local capacity = tonumber(ARGV[1])
local tokens = tonumber(b[1]) or capacity
local last = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (now - last) * tonumber(ARGV[2]))
local allowed = 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'last', now)
redis.call('EXPIRE', KEYS[1], tonumber(ARGV[3]))
return allowed

Two details. First, the script reads the time from Redis (TIME), not from the app server. The clocks of different servers differ a little, and one clock for all checks avoids this. Second, the time to live is the time the bucket needs to fill from empty (capacity / refill). After that time an idle client would have a full bucket anyway, so the key can go, and idle clients cost no memory.

Speed and size

Each check is one Redis command. One Redis server can run only so many commands per second. When the load is higher, use several Redis servers. The app server picks one by the hash of the client key, as in lesson 28. Divide the hash by the number of Redis servers. The remainder is the server number. A key always goes to the same Redis server, so its count is never split. If you change the number of Redis servers, most keys move and their counters start again. For short windows that does little harm.

One key cannot be split. If an attacker sends a huge number of requests with one key, one Redis server takes them all. To protect it, an app server keeps a short note in its own memory: "this key is refused until the Retry-After time". During that time the app server refuses the key without calling Redis.

When the shared place fails

If the limiter cannot reach Redis, the service must choose. Fail open means to allow the requests. Users are served, but the limit is off. Fail closed means to refuse them. The limit holds, but the service is down. Choose by endpoint. For normal reads, fail open. For a login page that guards passwords, fail closed.

Quotas and rules

A rate limit works over seconds or minutes and protects the service from bursts. A quota is a total over a long period, such as a day or a month, that depends on the plan a customer pays for. A service usually needs both. The quota counter is another key, for example quota:key42:2026-10, increased with INCR. It is a fast guard, not the bill. The bill should come from the request log, because a counter can be lost.

The limits themselves (which plan, which endpoint, how many) are rules. Keep them in a database, and let each app server keep a copy for 30 to 60 seconds. An operator can then change a rule without changing the code.

A refused request gets status 429 (lesson 56). For a rate limit, add Retry-After. For a quota, the message tells the client when the quota resets.

Abuse

An attacker does not use one key. The attacker uses many IP addresses, many accounts, or many API keys, so that each key stays under its limit. So use layers: a limit for each IP address, a limit for each account or API key, and a global limit for each costly endpoint. For login, count by the account name that is being tried, whatever the IP address is.

The limiter is also a target. An attacker can send requests with new keys every time to fill the memory of Redis. Time to live bounds this: the keys of one minute are removed after that minute. Last, watch the number of refusals for each rule. If many good customers are refused, the rule is wrong. It is not an attack.

Assumptions (made up to teach with, not real traffic):

• Peak load is 500,000 checks per second. There are 1,500 app servers.
• One check is one script call. One Redis server runs 100,000 checks per second, because a script takes only 0.01 ms (10 microseconds) of its time. A Redis server runs one command or script at a time, so this time sets the limit. We plan for 70% busy.
• The state of one client takes 100 bytes, with the key name and Redis overhead. 20,000,000 clients are active in a day.
• A round trip inside one data centre takes 0.5 ms (lesson 14).
• The limit is 120 requests per minute for each key. The token bucket has capacity 20 and refill 2 per second (lesson 56).

Step 1: counters in each server. The client sends to the 10 servers in turn, and each server counts only its own requests. Each allows 120. The client sends 10 x 120 = 1,200 requests per minute before the first refusal. This answers the predict box: 10 times the limit.

Set each server to 120 / 10 = 12 instead. Now suppose a client sends 30 requests in one minute and 30 of them reach one server, by chance or because the balancer is sticky. That server allows 12 and refuses 18. The client sent only 30 of 120 allowed, and still got refusals.

Step 2: a shared bucket. The script above runs on Redis. We test it on a bucket with 20 tokens:

• 21 requests arrive at the same instant. 20 pass and 1 is refused.
• After 0.5 seconds, 0.5 x 2 = 1 token is back, and one request passes. After another 0.1 seconds only 0.2 tokens are back, so the request is refused.
• After the client is idle for 10 seconds, the key expires. The next 20 requests pass, as with a full bucket.

The time of a check, as the app server sees it, is 0.5 + 0.01 = 0.51 ms. This is below an assumed limit of 5 ms for the limiter.

Step 3: how many Redis servers.

• At 70% busy, one Redis server serves 100,000 x 0.7 = 70,000 checks per second.
• 500,000 / 70,000 = 7.1, so we need 8 servers. Each takes 500,000 / 8 = 62,500 checks per second, which is 62.5% busy.
• Memory: 20,000,000 clients x 100 bytes = 2,000,000,000 bytes = 2 GB. Each of the 8 servers holds 2 GB / 8 = 250 MB. The commands per second are the limit, not the memory.

Step 4: one busy key. An attacker sends 50,000 requests per second with one key. The limit is 2 per second. They spread over 1,500 app servers, so each app server sees 50,000 / 1,500 = 33 per second.

• Without a note in memory, all 50,000 per second go to one Redis server. That is 50,000 / 100,000 = 50% of it, for one attacker.
• With the note "refused until Retry-After, which is 1 second", each app server calls Redis once per second for this key. That is at most 1,500 calls per second, 33 times fewer.

Step 5: Redis fails. One of the 8 servers stops. Only the keys on that server are affected: 1 / 8 = 12.5% of clients. That is 62,500 checks per second with no shared counter. Normal reads fail open. The login page fails closed.

Step 6: quota with the rate limit. The Pro plan has a quota of 1,000,000 requests a month and a rate limit of 20 requests per second. A month of 30 days has 2,592,000 seconds.

• The average quota rate is 1,000,000 / 2,592,000 = 0.39 requests per second.
• The rate limit of 20 per second alone would allow 20 x 2,592,000 = 51,840,000 a month, which is 51.8 times the quota.
• A client at full speed uses the whole quota in 1,000,000 / 20 = 50,000 seconds, which is 13.9 hours. After that the quota refuses it until the month ends.

Step 7: abuse.

• An attacker has 10,000 IP addresses. The limit is 120 per minute for each address. (Assumption: each key lives 60 seconds.) In total the attacker sends 10,000 x 120 = 1,200,000 per minute, which is 20,000 per second. A limit for each IP address is not enough. Add a limit for each account on the login page (for example, 5 per minute), and a global limit on the costly endpoint.
• The attacker makes 20,000 new keys per second. At most 20,000 x 60 = 1,200,000 keys exist, which is 1,200,000 x 100 bytes = 120 MB. At 500,000 new keys per second it is 30,000,000 keys, which is 3 GB, or 375 MB on each of the 8 servers. The time to live bounds the memory.

• Shared counters solve a limit that holds across servers. They cost one network call for every request (0.51 ms in the example) and one more part that can fail. I would change to local counters, synced now and then, when the call is too slow. The limit is then only approximate.
• A script solves lost updates in a token bucket. It costs more work for Redis than one INCR (the script runs as one step, so a slow script blocks others). I would use INCR with a fixed window when the edge burst is acceptable.
• Failing open solves a service that stays up. It costs an unprotected service while Redis is down. I would fail closed for login and other places where abuse is expensive.
• Several Redis servers solve load (8 servers for 500,000 checks per second). They cost more servers to run, and a key stays on one of them.
• Quotas solve total use by plan. They cost another counter for each client, and a total that is only a guard.

"Each app server can keep its own counter, because the load balancer shares requests evenly." Then the client gets 10 times the limit in the example: 1,200 instead of 120. A split limit of 12 refuses good clients when the requests are not even.

"INCR and EXPIRE are two commands, so it is fine to send them one after the other." If the server stops between them, the key has no end time. If the key has no window in its name, the client stays blocked for ever. If it does, the key only wastes memory, and these keys add up. Use MULTI and EXEC or a script, so both run together.

"A limit for each IP address stops an attacker." An attacker with 10,000 addresses sends 20,000 requests per second, and each address stays under its limit. Add limits for each account and for the whole endpoint.

1. Why does a counter in each app server give a wrong limit? Why do INCR and EXPIRE need MULTI and EXEC or a script?
2. A service has 300,000 checks per second at peak. One Redis server runs 80,000 commands per second, and you plan for 70% busy. (a) How many Redis servers? (b) How many checks per second does each take? (c) Each client uses 150 bytes and 12,000,000 clients are active. How much memory does each Redis server hold?
3. A teammate says: "We limit each IP address to 100 login attempts a minute, so passwords are safe." An attacker has 5,000 addresses. What is wrong, and what do you add?