Design a distributed rate limiter

Algorithm. Four candidates, and the boundary problem is the discriminator:

• Fixed window — a counter per key per minute. Trivial, but allows 2x the limit across a window boundary: 1,000 at 11:59:59 and 1,000 at 12:00:00.
• Sliding window log — timestamps of every request. Exactly correct, and O(n) memory per key. Fine for low limits, not for 1,000/minute across millions of keys.
• Sliding window counter — weight the previous window by how far into the current one you are. Two counters, bounded memory, smooths the boundary. Approximate, and the approximation is almost always acceptable.
• Token bucket — tokens refill at a fixed rate up to a cap. Two numbers per key. Permits bursts up to the bucket size, which is usually what you want: a client making 50 requests at once after idling is behaving reasonably.

Token bucket is the common answer, and being able to say why sliding-window-counter would be chosen instead (strict smoothing, no bursts) is the depth marker.

Where state lives. Instances are stateless, so the counter must be shared — Redis is the standard choice. The check-and-decrement must be atomic; a naive GET-then-SET races and lets several instances each grant the last token. A Lua script or INCR with an expiry makes it one round trip and one atomic operation.

Latency. This adds a network hop to every request. At high throughput, a local token bucket per instance holding 1/N of the budget, reconciled with the shared store periodically, removes the hop at the cost of some accuracy near the limit. Worth raising as an option, not as the default.

Failure — the part most candidates skip. If Redis is down, you fail open or fail closed. Failing closed turns a cache outage into a total API outage. Failing open means limits stop being enforced during exactly the incident when you might most need them. The usual answer is fail open with a conservative local limit as a backstop, and alarms — but the interviewer mainly wants to hear that you know it is a deliberate choice with a cost either way.

Response. 429 with Retry-After, and the remaining budget in headers so a well-behaved client can pace itself instead of hammering.