Prompt and Applicable Context
Design a rate limiter for a multi-tenant API platform: free tenants get 100 requests per minute, paid tenants get 10,000, and the platform runs across multiple application instances and regions. Compare algorithms and explain shared state, 429 responses, failure degradation, and verification.
This fits backend, platform, and system design interviews. A public interview record presents a per-user token-bucket coding problem with time-based refills; system-design material treats rate limiting as a standard multi-tenant API discussion. The core skill is shared state, tenant policy, and traffic protection—not memorizing one cloud provider’s settings.
What the Interviewer Evaluates
- Whether you separate average rate, burst capacity, tenant fairness, and global protection.
- Whether you can explain the boundaries and costs of token bucket, fixed window, and sliding window.
- Whether shared state is updated atomically across instances while hot keys, partitions, and clocks are addressed.
- Whether 429 responses, retry hints, degradation, and telemetry keep the limiter from becoming a single point of failure.
Clarifying Questions Before Answering
- Is the subject an API key, tenant, user, IP, or a combination? How are anonymous requests grouped?
- Is the policy an average rate, a strict sliding window, or controlled bursts? Is there also a daily quota?
- Does multi-region require exact global enforcement, or can a short overrun buy availability?
- Should rejected requests receive an immediate 429 or enter a bounded queue? Can the dependency tolerate bursts at all?
30-Second Answer Framework
I would put coarse IP and unauthenticated protection at the gateway, then enforce tenant-aware policy in the application layer. If the API tolerates short bursts, I would start with a token bucket. Each tenant bucket stores tokens and the last refill time in atomically shared state. Over-limit requests receive 429 with a computable retry hint. If exact global counting is not required, regional quotas and global overrun monitoring trade a little precision for latency; storage failures use an explicit fail-open or fail-closed policy with alerts.
Step-by-Step Deep Dive
Define the Budget and Fairness
One hundred requests per minute is the free tenant’s long-run budget, and 10,000 is the paid tenant’s. Both also need an independent burst capacity; a single global counter cannot express either policy. A global guard should cap aggregate RPS so one large tenant cannot exhaust database connections. A policy key should include tenant ID, API action, and policy version so unrelated endpoints do not accidentally share allowance.
Choose the Algorithm
| Algorithm | Main semantics | Cost and risk | Good fit |
|---|---|---|---|
| Token bucket | Bounded average rate with controlled bursts | Two state values; refill and consume must be atomic | User-facing APIs that tolerate short bursts |
| Fixed window | Count requests in fixed periods | A boundary can approach twice the configured rate | Simple rules where approximation is acceptable |
| Sliding window log | Exact count in the active window | Stores timestamps; memory and cleanup are expensive | Small populations needing strict precision |
| Sliding window counter | Weighted estimate from adjacent windows | Approximate but memory efficient; error must be stated | Large-scale fairness limits |
AWS API Gateway documents token-bucket throttling: token rate expresses steady-state traffic and burst expresses bucket capacity. It can return 429, but the limits are best-effort targets rather than an absolute mathematical ceiling. Keep policy intent separate from a platform’s guarantee.
Token-Bucket Invariant
The token count always stays in [0, capacity]. On arrival, refill by elapsed time times the refill rate, cap at capacity, and then check for at least one token; an allowed request consumes one. This order means an idle period accumulates only to the burst limit instead of creating unlimited credit after downtime.
~~~text allow(key, now): state = atomicRead(key) elapsed = max(0, now - state.lastRefill) refilled = min(capacity, state.tokens + elapsed * rate) if refilled < 1: atomicWrite(key, refilled, now) return reject(429) atomicWrite(key, refilled - 1, now) return allow ~~~
In production, the pseudocode must run as one Lua script, transaction, or equivalent compare-and-swap operation. Two independent read and write calls can oversell tokens under concurrency. Timestamps should come from a trusted monotonic source; clients must not submit them.
Placement and Shared State
The gateway blocks obvious IP floods and unauthenticated volume; the application layer applies tenant, user, or endpoint policy. If every instance counts only in local memory, load balancing lets one tenant spread calls across instances and receive multiple allowances. Shared Redis, an atomic key-value store, or a conditionally written database can hold state; the choice depends on latency, precision, and failure model.
Multi-region choices are explicit: one global store gives more exact allowance at cross-region latency; independent regional buckets are fast but can overrun briefly; regional allocations plus a global guard sit between them. Ask whether precision matters more than availability before claiming a global strict limit.
Rejection, Degradation, and Telemetry
Return 429 with Retry-After or remaining-quota headers. Clients should use bounded backoff rather than immediately retrying into a feedback loop. If limiter storage fails, high-risk writes commonly fail closed or enter a bounded queue; low-risk reads may fail open briefly, but need a local circuit breaker, expiry, and aggregate cap. Monitor allow and reject rates, per-tenant quota hits, storage latency, hot keys, script errors, and actual downstream load separately.
High-Quality Sample Answer
I would use two layers: the gateway protects against IP and unauthenticated floods, while the application enforces tenant and endpoint policy. Free and paid tenants have separate rate and burst values. I would default to a token bucket because an API can usually tolerate a short burst while still enforcing a long-run average. Each bucket stores tokens and its last refill time, and one atomic script performs refill, check, and consume in shared storage.
If regions do not require an exact global result for every request, I would allocate regional quotas and use global telemetry to detect unusual overruns. If payment or quota settlement must be strict, I would use a stronger-consistency decision point and accept the latency. Over-limit requests receive 429 and retry guidance; storage failure chooses fail closed, short fail open, or a bounded queue by endpoint risk. I would then load-test burst capacity, window boundaries, tenant fairness, failure recovery, and downstream load—not just the number of 429s.
Common Mistakes
- “Use Redis counters” → no policy semantics or atomicity → specify bucket state, script boundaries, and failure behavior.
- One quota for every tenant → a large tenant starves small ones → partition policy by tenant and endpoint, then add a global guard.
- Treating a fixed window as a strict per-minute ceiling → boundary traffic can approach twice the rate → state the error and choose sliding or token bucket when needed.
- Opening the floodgates when limiter storage fails → the dependency collapses first → choose bounded degradation by business risk and alert on it.
- Telling clients to retry 429 immediately → rejected traffic becomes more load → provide retry guidance, jitter, and a cap.
Follow-Up Questions and Responses
How do you stop one tenant from multiplying allowance across 20 instances?
Put bucket state in shared storage visible to every instance and update it atomically under the tenant policy key. If only local counters are available, call the result approximate and add a gateway-wide cap; do not claim global precision.
What if 100 requests per minute must be enforced strictly across regions?
Use a stronger-consistency global decision point or serialize deduction through a tenant’s home region. The cost is cross-region latency and lower availability during a regional failure. If a short overrun is acceptable, use regional quotas plus reconciliation and write the error into the SLO.
How do you stop a slow limiter from dragging down the API?
Set strict timeouts and a circuit breaker around the limiter call. Keep a local safety cap for storage outages and degrade by endpoint risk. Track limiter latency, timeouts, and script failures independently from business success rate.
When should you queue instead of returning 429?
Queue only when work is asynchronous, wait time fits the user’s budget, and the dependency needs smoothing. The queue must be bounded and reject when full. Interactive reads or unbounded waits should usually return 429 honestly.
How do you test the fixed-window boundary flaw?
Send one burst just before the window ends and another just after it starts, then count requests in every rolling interval. Repeat with token-bucket idle refill, a full-bucket burst, and concurrent consumption using a controlled clock.