Design a Rate Limiter: Algorithm Trade-offs, Scalability and Availability

Design a rate limiter for a service that many clients call over HTTP. The limiter caps how many requests a client can make in a period of time and rejects the excess, so that one noisy client cannot degrade the service for everyone else. The round is a pure high-level design discussion, and the interviewer cares more about your reasoning and trade-offs than about a polished final diagram. The story gives no product context or limits. For practice, assume the standard scope: the service runs on many stateless servers behind a load balancer, limits are set per client (for example per API key, or per IP address for anonymous traffic), and over-limit requests receive an HTTP 429 response. ### Constraints and Clarifications - The discussion is expected to compare several rate limiting algorithms, then cover scalability and availability. - A limit applies to a client's total traffic, whichever server handles each request. - The limiter must not become a single point of failure for the service it protects. ### Clarifying Questions - Where should the limiter run: inside each service, in an API gateway, or as a separate service? - Are limits per second, per minute or per day, and are short bursts allowed? - How exact must a limit be: is a small overshoot acceptable? - If the limiter cannot reach its shared state, should requests be let through or rejected? ### Part 1 — Requirements and placement State the functional and non-functional requirements and decide where the limiter sits in the request path. Explain what a client sees when it is limited. ```hint Who sees the request first Consider what each placement can know about the client, and what it costs in latency and operational effort. ``` #### What This Part Should Cover - Requirements, including accuracy, added latency and failure behavior - Placement options and the reason for the chosen one - The client-facing contract: status code and headers - How limit rules are defined and changed ### Part 2 — Comparing algorithms Compare the main rate limiting algorithms (fixed window counter, sliding window log, sliding window counter, token bucket and leaky bucket) and choose one for this service. Use a concrete example to show where the simpler ones go wrong. ```hint Walk the window edge Trace what each algorithm allows when a client sends its full allowance just before a window ends and again just after the next one starts. ``` #### What This Part Should Cover - How each algorithm decides and what state it keeps per client - Burst behavior and accuracy at window boundaries - Memory and computation cost at scale - A justified final choice ### Part 3 — Scalability and availability Make the chosen algorithm work across many servers, then keep it working when parts of the system fail. Explain where the counters live, how concurrent updates stay correct, how the design grows with traffic, and what happens when the counter store is slow or unavailable. ```hint Shared state is the weak point List the ways the shared counter store can fail and decide, for each one, whether protecting the backend or serving clients matters more. ``` #### What This Part Should Cover - A shared counter store with atomic updates and partitioning - Added latency and how to keep it small - Replication, failover and the fail-open versus fail-closed decision - Monitoring of limiter decisions and limiter health ### What a Strong Answer Covers - Requirements stated before design, including what "accurate enough" means - A genuine comparison of algorithms with their failure cases, not just their names - Correct handling of concurrent updates from many servers - A clear plan for when the limiter's own dependencies fail - Trade-offs explained in plain terms throughout ### Follow-up Questions - How would you give premium clients higher limits without code changes? - How would the design change if limits had to hold across several data centers? - How do you deal with a client that rotates IP addresses or API keys to dodge its limits? - How would you test the limiter before turning it on for real traffic?