Rate Limiter with Tiers, Runtime Config Changes and Multiple Rules

Implement a rate limiter that a service calls before handling each request: `allow(client_id)` returns whether the request may proceed. Build it with a token bucket or a sliding window, then extend it in the directions the interview took: clients belong to tiers with different limits, an operator can change a tier's limits while the service is running, one request can be subject to several rules at once, and the whole thing must be testable with a mock clock. ```python limiter = RateLimiter(config, clock=fake_clock) limiter.allow("client-42") # True or False ``` ### Clarifying Questions - Does the limiter run inside one process, or must several servers share the same limits? - Is a rejected request dropped, or should the caller learn how long to wait? - Should short bursts above the average rate be allowed, and how large? - When a tier's limits change, should a client's current state carry over or reset? - Does a request rejected by one rule still count against the other rules? ### Part 1 — One limit Implement `allow(client_id)` for a single limit, for example at most N requests per period, per client. Choose token bucket or sliding window and justify it. ```hint Compute instead of tick Think about how the limiter can bring a client's state up to date at the moment a request arrives, so that no background timer is needed. ``` #### What This Part Should Cover - The per-client state and the update performed on each call - Burst behavior and accuracy at window boundaries for the chosen algorithm - Time and memory per client, and thread safety ### Part 2 — Tiers that change at runtime Each client belongs to a tier, and each tier has its own limits. An operator can change a tier's limits, or move a client to another tier, without restarting the service. ```hint Separate the rule from the state Decide what each client's stored state should depend on, so that a new rule can be applied to it without corrupting it. ``` #### What This Part Should Cover - How configuration is looked up on each call and swapped safely - What happens to a client's existing state when its limits change - How a bad configuration is rejected before it takes effect ### Part 3 — Several rules per request A request can be subject to several rules at once, for example a per-second limit and a per-day limit, or a per-client limit and a global limit. It is allowed only if every rule allows it. ```hint All or nothing Consider what happens to the first rule's budget when the second rule rejects the request. ``` #### What This Part Should Cover - How rules are evaluated so that a rejected request consumes nothing - Thread safety when several rules are checked together - What the caller learns about which rule rejected it ### Part 4 — Testing with a mock clock Show how the limiter is tested without real waiting. ```hint Time as a dependency Ask where the limiter reads the current time, and what a test needs to control. ``` #### What This Part Should Cover - How the clock is injected - The specific test cases: boundaries, refill, bursts, configuration changes, rule interactions - Deterministic tests for concurrent callers ### What a Strong Answer Covers - Settles single-process versus shared limits, burst size and rejection behavior first - A correct lazy-refill token bucket or sliding window, with its boundary behavior explained - Configuration kept separate from per-client state, swapped atomically, with defined carry-over - Multi-rule checks that never consume budget for a rejected request - A clock abstraction and a concrete list of deterministic tests ### Follow-up Questions - Several servers must enforce one shared limit per client. What changes, and what happens when the shared store is slow or unavailable? - Millions of clients are idle most of the time. How do you keep memory bounded? - Some requests are more expensive than others. How do you charge them differently? - How do you return a precise "retry after" value to a rejected client?