Design a Rate Limiter Service: Components, Scaling and Precision Trade-offs

Design a rate limiter service: a component that decides, for every incoming API request, whether the caller that sent it is still within its allowed number of requests, and rejects the request if it is not. The discussion followed a coding exercise on a simple limiter that allows each caller a fixed number of requests per time bucket, and it went through three parts on a whiteboard. ### Constraints and Clarifications - Each request carries an identifier of its caller, such as a user ID or an API key. - Traffic volume, the number of callers, the limits and the latency budget are not given. State your assumptions. ### Clarifying Questions - Does the limiter sit in front of the API services, for example in a gateway, or do the services call it before handling each request? - Is there one limit for every caller, or limits per caller, plan or endpoint, and how often do they change? - When the limiter cannot reach its own storage, should requests be allowed or rejected? - How strict must a limit be: is a caller getting a few percent over its limit acceptable? ### Part 1 — Components Draw the components a simple rate limiter service needs, and walk one request through them. ```hint Follow one request Trace a single request from the client to the allow-or-reject decision. Name every component it touches, and what each one stores or decides. ``` #### What This Part Should Cover - Where the limiter sits relative to the services it protects - Where limit rules and request counters are stored, and how a check reads and updates them - What a rejected client receives, and what is recorded for operators ### Part 2 — Scaling up The number of users grows a lot. How do you scale the rate limiter, which problems appear, and how do you solve them? ```hint One caller, many servers Once many limiter instances serve the same caller, ask where that caller's count lives, and how two instances avoid each counting only part of the caller's traffic. ``` ```hint The busiest caller Think about what happens to the counter storage when one caller sends a large share of all traffic, especially after that caller is already over its limit. ``` #### What This Part Should Cover - Counters shared across many limiter instances, partitioned so that they scale - Atomic updates under concurrent requests from the same caller - Hot callers, the latency added to every request, and failure of the counter storage - Traffic served from more than one region ### Part 3 — More precise limiting How would you make the rate limiter more precise, and what are the trade-offs? ```hint The edge of a bucket Consider a caller who sends a full bucket's worth of requests just before a bucket boundary and another full bucket's worth just after it. ``` #### Clarifying Questions for this Part - Does "more precise" mean enforcing the rate over any interval of the window's length, keeping counts exact across many servers, or both? #### What This Part Should Cover - The weakness of counting in fixed time buckets - Alternative algorithms with their accuracy, memory and per-check cost - Precision lost to distribution, and what exact counting costs in latency and availability ### What a Strong Answer Covers - A clear request path, with the limiter's placement justified and a defined response for rejected requests - Shared, partitioned, atomically updated counters, and why counting in each instance's memory fails - An explicit policy for when the counter storage is slow or down, and handling of hot callers - Precision choices tied to the use case, with their memory, latency and accuracy costs - Monitoring of the limiter's decisions and of its own health ### Follow-up Questions - A caller sends traffic to two regions at once. How do you enforce one limit across both, and how far over the limit can the caller get? - How would you change one caller's limit without redeploying anything, and how quickly would the change take effect? - A request is subject to both a per-caller limit and a per-endpoint limit. How do you check both without a rejected request using up part of the other limit?