## Reason About Rate Limiting Under Memory and Throughput Pressure Design an in-memory rate limiter and then extend the design for two production concerns: request volume is too high to retain one queue entry per request, and the service must increase accepted-request throughput without violating the chosen limit semantics. The exact limit, time window, key scope, and boundary convention are not specified. Ask for them and keep them configurable so tests and implementation cannot silently use different values. ### Constraints & Assumptions - A request is evaluated for a named key such as a user, account, or API credential. - The decision returns allowed or rejected plus enough information to compute a retry time when the policy supports it. - Time is supplied by a monotonic or controlled clock for deterministic tests. - The policy must state whether it is an exact sliding window, a fixed window, a token bucket, or an approximation. ### Clarifying Questions to Ask - What is the limit, interval, burst allowance, and key cardinality? - Must the limit be globally strict across servers, or is bounded temporary overshoot acceptable? - Does a rejected request consume quota? - How precise must retry timing be, and what clock behavior is assumed? ### Part 1 — Implement the Core Limiter Choose a rate-limiting algorithm, define its invariant, and give pseudocode for evaluating one request. Explain boundary behavior and operation cost. #### What This Part Should Cover - Exact semantics for admission, expiration, and bursts. - Per-key state and cleanup of inactive keys. - Atomicity when requests for one key arrive concurrently. - Tests immediately before, at, and after a window boundary. ```hint Name the policy first A deque-based sliding window and a token bucket can both be called a rate limiter, but they make different promises about bursts and retry timing. ``` ### Part 2 — Bound Memory with Time Buckets Assume a design that retains recent request timestamps no longer fits in memory. Replace individual timestamps with a bounded set of time buckets and explain the accuracy trade-off. #### What This Part Should Cover - Bucket identity, count, rotation, and expiration. - Memory bounded by keys and bucket count rather than request count. - The maximum timing error introduced by bucket width. - Behavior after a long idle period or a large clock jump. ```hint Aggregate equivalent history Requests that fall in the same small time interval can share one counter if the policy accepts bucket-width precision. ``` ### Part 3 — Improve Throughput Identify bottlenecks in a single locked limiter and propose optimizations for many keys and for one very hot key. State which optimizations preserve strict global limits and which permit bounded approximation. #### What This Part Should Cover - Sharding state by key to avoid one global lock. - Constant-time updates and bounded cleanup work. - Local quota leasing or batching as an explicit consistency trade-off. - Metrics for decisions, latency, overshoot, bucket error, and hot keys. ```hint Separate ordinary and hot keys Hash sharding helps independent keys, while a single dominant key needs reduced coordination or a deliberately partitioned quota. ``` ### What a Strong Answer Covers - A fully specified rate policy rather than an implementation whose semantics are inferred from code. - Memory analysis and a precise account of bucket approximation. - Concurrency-safe state transitions and configurable limits used consistently by code and tests. - Throughput improvements with their strictness and overshoot costs made explicit. ### Follow-up Questions 1. How would you expire millions of inactive keys without scanning them all on every request? 2. What is the worst-case admission error for a bucketed sliding window? 3. How would you change limits at runtime without corrupting existing state? 4. How would local quota leases recover when one limiter instance fails while holding unused quota?