# Design a Distributed Rate-Limiting Service Design a rate-limiting service that protects APIs across many application instances. It should support per-user, per-tenant, and global limits while making an explicit trade-off among accuracy, latency, availability, and cost. ### Constraints & Assumptions - The limiter runs on the request path and must respond within a small latency budget. - Application instances and limiter nodes may restart or become partitioned. - Limits can change at runtime and can differ by route, identity, and plan. - Requests can be retried, and one tenant may generate a sudden burst. - Some endpoints require fail-closed behavior while others may fail open with bounded risk. ### Clarifying Questions to Ask - Are limits fixed-window, sliding-window, token-bucket, concurrency, or a combination? - What overshoot is acceptable during replication delay or partition? - Which identity is trusted, and how is it derived behind proxies? - What traffic scale, regional topology, and decision latency are expected? - Which routes fail open, fail closed, or use an emergency local limit? ### Hints - Define an exact decision API and response metadata. - Keep configuration distribution separate from hot-path counter state. - Compare centralized counters with locally leased token budgets. ### What a Strong Answer Covers - Key construction, policy precedence, algorithm choice, burst semantics, and response headers. - Atomic counter or token updates, sharding, hot-key handling, expiration, and clock behavior. - Multi-region consistency, local token leases, bounded overshoot, and partition policy. - Configuration versioning, staged rollout, emergency overrides, and auditability. - Authentication, spoofing resistance, tenant isolation, retries, and denial-of-service protection for the limiter itself. - Metrics, shadow evaluation, capacity planning, graceful degradation, and correctness tests. ### Follow-up Questions 1. How would you bound global-limit overshoot with active-active regions? 2. What happens when one celebrity account becomes a single hot counter key? 3. How would you roll out a stricter policy without unexpectedly blocking valid traffic? 4. When is a local approximate limiter safer than a remote exact one?