## Scenario Design a distributed rate limiter for an API. It must support per-tenant limits, short bursts, several application regions, and policy changes without restarting servers. Compare fixed window, sliding window, leaky bucket, and token bucket, then select a baseline. Discuss request identity, atomic state updates, caching, consistency, failure policy, hot keys, clock behavior, scalability, observability, and response headers. ### Constraints & Assumptions - The baseline policy is token bucket with capacity `B` and refill rate `R` per second. - A limit decision must be atomic for one key. - The caller needs a deterministic allowed or rejected response plus retry guidance. - Global cross-region exactness is expensive; state the chosen scope and overshoot bound. - If fixed regional capacities and refill rates sum to the global policy, traffic skew causes unused capacity or false rejection, not overshoot. Account separately for local leases, reallocation, and failure behavior. ### Clarifying Questions to Ask - Is the limit per user, API key, tenant, IP, endpoint, or a hierarchy? - Is the goal abuse protection, fairness, cost control, or downstream protection? - How much overshoot is acceptable across regions or local caches? - Should the service fail open or closed during state-store failure? - Are bursts permitted and how quickly should unused capacity recover? ```hint Keep refill and consume atomic Store tokens and last-refill time together. One server-side transaction or script computes refill, checks cost, and writes the new state. ``` ### What a Strong Answer Covers - Algorithm trade-offs and a precise token-bucket transition. - Key construction, policy versioning, atomic Redis or equivalent operations, TTL, and hot-key mitigation. - An explicit global-versus-regional contract and a numeric worst-case overshoot bound that includes local leases, reallocation, partitions, and store failures. - Layered fallback behavior tied to endpoint risk. - Metrics for allowed, rejected, store errors, decision latency, saturation, and fairness. ### Follow-up Questions 1. How would hierarchical tenant and user limits be enforced atomically? 2. What happens when application-server clocks disagree? 3. How can a local token lease reduce central-store traffic while bounding overshoot?