Design an API rate limiter: atomic decisions and explicit failure policy
Follow a request from trusted identity and policy matching to a token decision. Distinguish request rate, concurrent work, billable quota and cross-region enforcement before choosing a counter.
1. Ask what resource we are protecting
Before choosing a sliding window, I would ask whether we are protecting infrastructure, enforcing a commercial quota or stopping login abuse. These need different correctness and outage policies. I will design online request admission with weighted token buckets, then discuss stricter extensions.
| Candidate asks | Illustrative interviewer reply | Design consequence |
|---|---|---|
| Which callers and keys? | Authenticated tenant and endpoint group; IP fallback before login. | Derive identity from verified credentials and trusted proxy metadata, not arbitrary headers. |
| What does the limit mean? | 100 requests/second with a burst of 200 for a typical policy. | Token bucket: sustained refill rate and burst capacity are separate parameters. |
| Do requests have equal cost? | Batch operations cost multiple tokens. | Resolve cost before admission; reject a single cost larger than bucket capacity. |
| How much traffic? | 1 million decisions/second peak, 10 million active buckets. | Shard by tenant/key and bound identity cardinality. |
| Must the limit be exact worldwide? | Regional protection is acceptable initially. | No false global guarantee; assign regional budgets if a global envelope is required. |
| What happens if the limiter fails? | Browse may use a bounded fallback; login and expensive writes deny. | Policy determines behavior; timeout is not the same as quota exhaustion. |
| Are in-flight requests also limited? | Yes for expensive endpoints, as a separate control. | Concurrency semaphore or worker permits supplement the rate limit. |
2. Declare the semantics of allowed and denied
My token decision is atomic within one bucket owner. A successful decision consumes admission capacity even if the backend later fails: this protects load, rather than billing successful transactions. For financial quota I would use a separate durable reservation ledger.
| Requirement | Agreed target or scope | Design implication |
|---|---|---|
| Decision contract | Return allowed, remaining estimate, retryAfter and policyVersion. | 429 only for a known exhausted policy; return 503 for a fail-closed infrastructure outage. |
| Latency | Illustrative p99 overhead below 5 ms within a region. | One network hop and one atomic operation; measure tail latency during resharding and failover. |
| Policy updates | Versioned rules with a controlled activation process. | Clamp existing tokens to a lower capacity; do not refill buckets just because a version changes. |
| Isolation | Tenant-level fairness plus endpoint limits. | Hot tenants cannot exhaust all shard CPU; place local connection and abuse guards first. |
| Security | Only trusted identity and bounded key construction. | No user-controlled policy bypass; hash sensitive identifiers in operational metrics. |
| Out of scope | Exact monthly invoicing and an unconstrained global transaction across all limits. | Explain where a separate quota authority or co-located multi-key decision is necessary. |
3. Calculate request load and worst-case fallback
I size for a peak of one million admission checks per second. I will benchmark the actual Lua/function or service operation under representative keys; a shard count is a starting allocation, not a promise that any Redis node supports a fixed rate.
| Quantity | Calculation | Interpretation |
|---|---|---|
| Decision traffic | 1M/s × 200 bytes combined request/response payload = 200 MB/s. | Excludes TLS, replication and connection overhead. Keep connections pooled. |
| Counter state | 10M active buckets × 128 logical bytes = 1.28 GB. | Keys, allocator and replication overhead can dominate; measure resident memory. |
| Logical shards | 1M/s / 64 = 15,625 decisions/s per shard at uniform load. | Hot-key traffic can exceed this even when cluster-average utilization is low. |
| Burst policy | B=200, r=100/s: accepted cost over interval t is bounded by B+r×t for a correctly serialized bucket. | In one second a full bucket can admit up to 300 tokens; 100/s is sustained rate, not a strict one-second ceiling. |
| Local fallback | 20 gateways × emergency capacity of 10 = 200 initial emergency tokens. | If each refills at 5/s, aggregate emergency refill is 100/s. Fleet growth must not silently multiply the budget. These are extra emergency admissions beyond any tokens already consumed at the unavailable primary, so this fallback does not enforce a strict shared global envelope. |
| In-flight load | 100 admitted requests/s × 10-second mean work = 1,000 concurrent operations. | Rate limiting alone does not cap concurrent work or downstream connections. |
4. Specify the bucket and policy invariants
The atomic operation stores available tokens and the last refill timestamp. It computes refill, checks cost and writes the result as one serialized action. A read in the gateway followed by a separate decrement lets concurrent callers overspend the same tokens.
| Record and key | Fields / invariant | Access pattern |
|---|---|---|
| Policy(tenantTier, endpointGroup, version) | capacity B, refill r, cost rule, failure mode and activation metadata. | Loaded and validated in the gateway; configuration service is not queried on every request. |
| Bucket(tenantId, endpointGroup) | tokens, lastRefill, appliedPolicyVersion. | Atomic update on one owner; 0 ≤ tokens ≤ capacity. |
| Optional Decision(bucketKey, requestId) | Short-lived decision result if transport retries must not consume twice. | Must be co-located with the bucket; retention and cardinality have a cost. |
| EmergencyBudget(gatewayId, policy) | Explicit allocation and validity window. | Fallback permits are bounded per assigned gateway; not an arbitrary full bucket at every process. |
| ConcurrencyPermit(resource, requestId) | Lease deadline and owner, independent of rate tokens. | Protect slow work; release or expire permits using a separate lifecycle. |
5. Make admission and transport retries unambiguous
I keep the decision API internal to trusted gateways. Untrusted clients cannot choose their own rate, capacity or zero-cost endpoint label. The response includes a policy version so debugging can explain why two gateways applied different rules during a rollout.
| Operation | Contract | Failure or retry behavior |
|---|---|---|
| CheckAndConsume(identity, route, cost, requestId) | Returns allowed, remaining, retryAfterMs, policyVersion and reason. | On timeout do not blindly retry a consume; use decision dedup or treat the outcome as unknown under the selected failure policy. |
| PublishPolicy(policy, expectedVersion) | Authenticated administrative write; validate capacity, refill and cost bounds. | Reject invalid or stale versions; publish signed/versioned snapshots to gateways. |
| HTTP admission failure | 429 with a bounded Retry-After for known quota exhaustion. | A denied request never reaches the protected backend; avoid reporting a false precise remaining global quota. |
| Limiter infrastructure failure | Apply the endpoint’s fail-closed or preallocated emergency policy. | 503 for unavailable enforcement on protected operations; observe fallback decisions separately. |
6. Draw policy distribution separately from the hot path
The gateway owns trusted identity extraction and policy matching. The bucket shard owns serialization. I intentionally keep the policy control plane away from the per-request path so an administrative outage does not instantly stop all requests with still-valid rules.
7. Execute the token decision atomically
For a bucket with tokens=30, rate=100/s, capacity=200 and 0.5 seconds elapsed, refill produces min(200,30+50)=80. A cost-20 request leaves 60. Two concurrent requests must observe a serialized evolution of this state, not both spend the original 80.
Resolve a trusted key
Authenticate first where possible; use tenant plus canonical endpoint group. Derive pre-auth IP only from the trusted ingress chain and put bounds on anonymous bucket creation.
Use one time authority
Compute elapsed time from the bucket authority clock, clamp negative elapsed to zero and cap tokens at capacity. Monitor forward/backward clock adjustments; monotonic behavior across failover needs explicit handling.
Refill and consume
In one atomic operation, refill; if tokens ≥ cost, subtract cost and allow. Otherwise leave tokens unspent and compute ceil((cost-tokens)/rate). Persist lastRefill consistently in both cases.
Expire idle state safely
Expire a bucket only after it would have fully refilled, with a conservative margin. Recreating it as full earlier than that manufactures capacity. A zero-refill quota is a different durable model.
Dispatch only after allow
Consume means admission, not successful business completion. Do not refund arbitrary backend failures: abusive callers could repeatedly trigger work without consuming protection capacity.
8. Explain rules, retries and multiple limits
Rules are read from a local versioned snapshot, while token state is updated at the shard. If an endpoint needs both a tenant bucket and a tenant-endpoint bucket, I co-locate those keys and evaluate all of them atomically when the storage model permits it.
Match deterministically
Order rules by explicit precedence, validate overlapping patterns during publish and use canonical route templates rather than arbitrary full URLs.
Compose limits honestly
For cross-shard global and tenant counters, sequential checks can consume one budget before another denies. That is conservative protection but not exact all-or-nothing accounting; do not pretend a pipeline is a transaction.
Handle unknown decision
If the store consumed a token but its response was lost, a second consume can charge twice. Choose bounded conservative loss or a request-ID result cache; document the memory and replay window.
Roll out stricter policy
Clamp current tokens to the new capacity and retain last refill. For a security-sensitive immediate change, require version acknowledgment or stop stale gateways; eventual config delivery has a propagation window.
Return actionable feedback
Return retry delay for the binding policy and explain that it is advisory under concurrent traffic. Clients use exponential backoff and jitter rather than synchronized retries.
9. Choose precision versus latency deliberately
For most regional protection I choose atomic per-tenant buckets and bounded outage behavior. If the interviewer changes the requirement to a strict global limit, I must change the architecture rather than merely add cross-region asynchronous replication.
| Decision | Chosen baseline | Alternative and trade-off |
|---|---|---|
| Fixed window | Useful for simple quotas with known boundary bursts. | Token bucket directly expresses burst plus sustained rate; sliding logs offer precise windows at higher state cost. |
| Global budget | Allocate disjoint regional budgets whose sum fits the agreed envelope. | A single global authority improves utilization and precision but adds WAN latency and an availability dependency. |
| Hot tenant | Preallocated leased tokens at gateways with conservative expiry and bounded grants. | One central bucket is simpler and more precise but can become a serialization hotspot. |
| State failover | Accept and measure bounded protection error if using asynchronously replicated counters. | Strict quotas need strongly durable serialization; restoring a stale counter can allow extra requests. |
| Failure policy | Fail closed for sensitive endpoints; bounded fallback for explicitly permitted reads. | Unbounded fail-open protects availability while potentially overwhelming the backend. |
10. Make outage behavior part of the design
I monitor decision latency, actual admitted cost, denial reasons, unknown outcomes, policy version skew, per-shard hot keys and fallback volume. A high rejection percentage alone cannot tell legitimate overload from an attack or a bad policy rollout.
| Failure | Detection | Recovery and remaining limitation |
|---|---|---|
| Bucket store timeout | Decision deadline exceeded. | Use the declared endpoint policy; avoid an unbounded retry loop or hidden double consumption. |
| Stale replica promoted | Counter rollback or failover event. | Measure possible extra admissions; strict endpoints require stronger storage or temporary denial until state is safe. |
| Clock jumps | Unexpected refill delta. | Clamp and alert; use a conservative maximum refill interval during recovery, accepting temporary under-admission. |
| Malicious identity cardinality | Bucket count and memory spike. | Bound key lengths, anonymous allocation rate and idle retention; do not allow random headers to create unlimited keys. |
| Gateway fleet doubles | Emergency allocation sum changes. | Redistribute a fixed emergency budget through control-plane grants; do not give every new instance an unlimited fresh burst. |
| Bad policy published | Version-specific denial spike. | Canary policy changes, validate constraints and roll back to an audited snapshot; do not reset all bucket balances. |
| Slow backend | Concurrency and queue age rise despite accepted rate. | Apply separate in-flight permits and circuit breakers; lowering rate may help but does not reclaim already-running work. |
11. Close by distinguishing four different controls
I have designed rate admission, not billing. Token buckets bound sustained cost and bursts; concurrency permits bound in-flight work; circuit breakers react to downstream failures; a durable quota ledger would enforce purchased entitlement. Combining their names does not combine their guarantees.
The core proof is the atomic bucket transition and the regional or global budget boundary. After that I would benchmark tail latency and test failure modes before optimizing local caching.
Technical references
Primary references explain underlying mechanisms. Workloads and architecture choices above remain proposed interview assumptions.