Design a Distributed Rate Limiter
Enforce tenant quotas across servers while making burst behavior and outage policy explicit.
Infrastructure, platform and reliability engineers.
Your approach: Use diagrams or prose to explain responsibilities, state, capacity and failure behavior. Show the calculations requested by the question.
The problem
Design a rate limiter used by API servers in two regions. Explain the client-visible quota contract, how simultaneous requests consume allowance, and what happens when shared state is unavailable. Choose and justify an algorithm without assuming all limits need identical consistency.
- Serve 100,000 checks/second across 10,000 tenants, with one tenant producing 20% of checks.
- Each tenant has a sustained request limit and a separately configured burst allowance.
- Clients retry after rejection. Regions can lose contact for five minutes while still receiving traffic.
Work within these constraints
Declare p95 additional server-side latency during normal operation.
Required target: ≤ 10 milliseconds
Specify the maximum overshoot allowed across simultaneous requests and regional partitions.
State which requests fail open or closed and how recovered allowance avoids a second full burst.
What to deliver
Algorithm and contract
Define tokens or counters, time semantics, rejection responses and retry guidance.
State and atomicity
Show key ownership, atomic updates and tenant isolation across API servers.
Capacity and hot keys
Estimate state size and load; handle the hot tenant and expired counters.
Partition walkthrough
Trace a regional partition and recovery, comparing accuracy with availability.