Build a Tiered Rate Limiter With Runtime-Updatable Limits, Then Test and Scale It

Build a rate limiting service in Python. Different clients can belong to different rate limit tiers, for example free, pro and enterprise. The limits for each tier can be updated at runtime without restarting the service. A client makes a request with its identifier, and the service must enforce the limit of that client's tier; if the client has exceeded its limit, the service rejects the request. If a client has no tier configured, or its tier's configuration is missing or invalid, the service always falls back to one global default policy. Either default deny or default allow is acceptable, as long as you choose deliberately. The interviewer is watching how you clarify requirements, how you test and how you debug, not only whether the code runs. The four parts below were asked in this order within a one-hour session. ### Constraints and Clarifications - Parts 1 to 3 assume a single instance with all state in memory. - Tiers are named, for example `free`, `pro` and `enterprise`, and each client identifier belongs to at most one tier. - A tier's limit can change while requests are being served, for example raising the free tier's limit from 5 to 10. - You design the interface. A minimal one is a method that takes a client identifier and returns whether the request is allowed, plus methods to assign a client to a tier and to change a tier's limits. ### Clarifying Questions - What exactly is a tier's limit: a number of requests per time period, a burst size plus a sustained rate, or something else? Over what period? - Is the limit per client identifier, so that two free clients have separate allowances? - When a tier's limit changes, does the change apply to clients in the middle of a burst, and what happens to the allowance a client already has? - Should the global default be deny or allow, and can it be changed at runtime too? - Can requests arrive concurrently from several threads? - Should a rejection carry extra information, such as when the client may retry? ### Part 1 — Implement the tiered limiter Implement the service: configure tiers, assign clients to tiers, check a request from a client identifier, update a tier's limit at runtime, and apply the global default whenever a client's tier is missing or misconfigured. ```hint What a client must remember Decide the smallest per-client state that can answer "may this request go through now?" without keeping a record of every past request. ``` ```hint Walk through a limit change Take a free client that has just used up its allowance, raise the free tier's limit from 5 to 10, and work out exactly what that client's next request should see. ``` #### What This Part Should Cover - The per-client state and the exact arithmetic that allows or rejects a request - Tier updates that take effect without a restart, with defined behavior for a client's current allowance - The fallback to the global default for unassigned clients and missing or invalid tier configuration - The time source and safety under concurrent requests ### Part 2 — Justify the algorithm Why did you choose this rate limiting algorithm? What are the strengths and weaknesses of each of the common algorithms? ```hint Compare at the edges For each algorithm, consider what a client can get away with right around a window boundary, and how much each one has to store per client. ``` #### What This Part Should Cover - A comparison of at least three algorithms on burst behavior, accuracy and per-client memory - How the chosen algorithm's parameters express the tiers - When a different algorithm would be the better choice ### Part 3 — Test it, including refill After writing the code, add tests that verify it really works. When the tests run against the real clock, calls happen so close together that a client's allowance never gets a chance to refill, so refill behavior cannot be observed. How do you test refill and other time-dependent behavior? ```hint Control elapsed time Refill depends only on how much time has passed. Think about what a test would need to control to make an exact amount of time pass instantly, and what waiting for real time would cost. ``` #### What This Part Should Cover - Test cases for the core behaviors: allowing up to the limit, rejecting beyond it, refill, the cap, per-client isolation, tier updates and the fallback - A way to control time in tests, and why it beats sleeping - Deterministic assertions that would catch the common arithmetic bugs ### Part 4 — Evolve it into a distributed limiter The service is now a single instance with all state in memory. How would you evolve it into a cluster of rate limiter instances? ```hint Two instances, one client When two instances handle requests from the same client at the same moment, decide where that client's state lives and how a read, check and update on it stays atomic. ``` #### Clarifying Questions for this Part - Must the limit be exact across instances, or is a small over-allowance acceptable? - Is there a shared store the instances can use, and how would tier configuration reach every instance? #### What This Part Should Cover - Where the state lives (shared or partitioned) and how check-and-update stays atomic - How runtime tier changes reach every instance - Behavior when the shared store is slow or unavailable, and clock consistency across nodes ### What a Strong Answer Covers - Requirements clarified before coding: limit semantics, per-client scope, the default policy, concurrency - Correct refill arithmetic and capacity semantics, including what a runtime limit change does to existing allowances - Clear trade-off reasoning for the algorithm choice - Fast, deterministic tests that would catch real bugs - A credible distributed design with atomic updates, configuration propagation and a failure policy - Pacing that leaves time for tests and the distributed discussion within the hour ### Follow-up Questions - A client is moved from the free tier to the pro tier in the middle of a burst. What allowance should it have on its next request? - How would you tell a rejected client when it may retry? - With millions of distinct client identifiers, how do you keep the in-memory state from growing without bound? - In the distributed version, how would you avoid a network round trip on every request from a very high-traffic client?