Design a rate limiter
Two million clients, twenty gateways, one limit each. The round turns on where the count lives: in one shared store every gateway asks, with a small bucket on each gateway that answers the clients already refused.
The round this design follows
Why not keep the counters inside each gateway?
Because a client’s requests are spread across every gateway. With twenty gateways each counting 120 a minute on its own, one client can get 2,400 a minute through, twenty times the limit. Dividing the limit by twenty fixes the total and breaks the client whose connection sticks to one gateway, who is then refused at six a minute. A shared count is the only way the limit means what it says, so the per-gateway bucket stays, but only as a filter in front of the shared store.
Sliding-window counter, token bucket or sliding log?
The sliding log keeps a timestamp for every request and is exact, but at 50 bytes a timestamp it needs 12 GB where the counters need 400 MB. The token bucket and the sliding-window counter cost the same, a couple of small fields per client. I pick the window counter when the limit is stated per minute, because it counts exactly what the product said, and the token bucket when the product wants to allow a burst and then a steady rate. Either answer is fine if you say why.
How big does the limiter store have to be?
Memory is small: two million clients with two counters of 100 bytes each is 400 MB. Load is what sizes it. Two hundred thousand checks a second at two store operations each is 400 thousand operations a second; at 100 thousand a second per in-memory store process, run at half capacity, that is 8 shards.
What should happen when the limiter store is down?
Decide it before the interviewer asks. For an ordinary api I fail open: the gateway waits a few milliseconds for the store, then lets the request through, and its local bucket still caps each client per gateway. For an endpoint that exists to stop abuse, such as login, I fail closed, because letting guesses through unchecked is the failure the limiter is there to prevent. Say which endpoints get which.
Two gateways check the same client at the same moment. Can both get through?
With read-then-write, yes: both read 119, both see room, both write 120, and 121 requests got in. The fix is to let the store do the arithmetic: an atomic increment returns the new count, so one gateway sees 120 and the other sees 121 and refuses. The previous window is closed and never changes, so reading it outside the increment is safe.