Design and reason about a rate limiter that begins with one rule and evolves to support multiple rules, concurrent requests, handler failures, and deferred processing. Make each semantic choice explicit. ### Clarifying Questions to Ask - What does one rule contain: key, request limit, and fixed or rolling time window? - Must a request satisfy every applicable rule, or is one passing rule sufficient? - Is a permit consumed when work starts or only after the handler succeeds? - Does deferred processing preserve arrival order, priority, or a deadline? ### Part 1 - One Rule Define a limiter for a single rule and explain its state, decision operation, time source, boundary behavior, and complexity. Choose a fixed window, sliding log, sliding counter, token bucket, or another algorithm and justify it. #### What This Part Should Cover - A precise admission contract, clock handling, cleanup, and boundary tests. ### Part 2 - Multiple Rules Extend the design so one request may be subject to several rules, such as per-user and global limits. Explain whether checking and consuming all permits is atomic. #### What This Part Should Cover - Deterministic rule selection, all-rules semantics, and rollback or reservation when one rule rejects. ### Part 3 - Thread Safety Make the limiter correct when several threads call it concurrently. Discuss lock granularity, state ownership, and how to avoid accepting more work than a rule allows. #### What This Part Should Cover - Protects the complete read-check-update transition and identifies contention or deadlock risks. ### Part 4 - Handler Failure The reported contract says a request whose handler throws an exception should not count against the limit. Explain how permits are reserved and then committed or released without races or double release. #### What This Part Should Cover - Defines permit lifecycle and recognizes the trade-off between concurrency control and post-success charging. ### Part 5 - Deferred Requests and Ordering Instead of discarding limited requests, queue them and process them when capacity becomes available. Address queue bounds, fairness, cancellation, retries, out-of-order arrival, and whether this responsibility belongs in the limiter or a surrounding scheduler. #### What This Part Should Cover - Separates admission from durable scheduling while providing backpressure and explicit ordering guarantees. ### What a Strong Answer Covers - States one coherent set of semantics before selecting data structures. - Maintains correctness across multiple rules and concurrent calls. - Handles success, exception, timeout, and cancellation exactly once. - Bounds memory and wait time for deferred work. - Discusses monotonic clocks, distributed deployment, observability, and failure recovery. ### Follow-up Questions 1. How would the design work across many service instances without a lock shared in process? 2. What fairness policy prevents one hot tenant from starving others? 3. How would you test race conditions and time-window boundaries deterministically?