Design an API Rate Limiter — System Design Interview Practice

Interview prompt

Design a distributed API rate limiter that enforces tenant, user, credential, IP, and endpoint quotas with predictable burst behavior, low overhead, and safe degradation.

• Define quota identity, policy precedence, token or refill semantics, burst capacity, response headers, time source, and scope inheritance.
• Partition counters by policy key, isolate hot tenants and endpoints, and choose strict versus approximate enforcement for multi-region traffic.
• Keep the decision path bounded and atomic; handle clock skew, retries, failover, counter loss, policy updates, and cache stampedes.
• Explain fail-open or fail-closed behavior by endpoint risk, abuse resistance, observability, auditability, and degraded local limits.

Requirements and scale assumptions

• Decide whether a request is allowed for a tenant, user, credential, IP, endpoint, or combined policy key.
• Support token-bucket, leaky-bucket, fixed-window, or sliding-window policies with explicit burst behavior.
• Return remaining quota, reset time, policy identity, and a retry hint when a request is rejected.
• Create, version, validate, and roll out policies without leaving counters in an ambiguous state.
• Support batch decisions for bounded requests and separate administrative policy reads from the hot path.
• Expose counter, policy, latency, rejection, and failover health to operators and policy owners.
• Keep a single decision below p99 5ms at the regional edge under normal load.
• Handle 1M decisions per second and 10M active policy keys with partitioned counters.
• Make each decision atomic for its key and document whether multi-region enforcement is strict or approximate.
• Prevent a limiter outage from taking down healthy traffic while preserving stricter protection for abuse-sensitive endpoints.
• Bound counter memory, policy propagation lag, retry work, and hot-key amplification.
• Serve 1M rate-limit decisions per second over approximately 10M active tenant, user, credential, IP, and endpoint keys.
• Assume a 90:10 allow-to-reject mix, with a few public endpoints and tenants producing disproportionate hot-key traffic.
• Replicate policy configuration globally, but keep the counter decision local when the product accepts bounded cross-region approximation.
• Expire inactive counters and retain policy versions, decision samples, and administrative audit records separately from hot counters.

• Decision throughput: 1M decisions/second — Capacity assumption that drives counter shards, connection pools, and local admission control.
• Active keys: 10M policy keys — Working-set estimate for counters and policy scopes, excluding expired keys.
• Decision latency: p99 < 5ms — Budget for the atomic counter operation and policy lookup on the regional path.
• Policy freshness: p99 < 30s — Example propagation target for policy versions; high-risk changes may require a stronger barrier.
• Enforcement error: < 1% approximate drift where allowed — Explicit bound for local multi-region approximation, measured against sampled authoritative decisions.

Key entities

• RateLimitPolicypolicyId (PK), scope, dimensions, algorithm, limit, windowOrRefillRate, burst, version, effectiveAt

  Versioned rules that map an endpoint request to one or more quota dimensions and specify the enforcement and failure contract.

• CounterBucketcounterKey (PK), policyId, windowStart or lastRefillAt, remaining, version, expiresAt, region

  Hot mutable state updated atomically by the decision service. Its expiration prevents inactive keys from consuming unbounded memory.

• RateLimitDecisiondecisionId, counterKey, requestId, allowed, remaining, retryAfterMs, policyVersion, decidedAt

  The response and sampled audit record for an allow or reject decision; high-volume raw decisions are sampled or aggregated.

• PolicyVersionpolicyId, version, checksum, status, publishedAt, retiredAt

  Propagation and rollout metadata that lets a region report which rules were actually enforced.

• QuotaOverrideoverrideId, policyId, subjectKey, limit, expiresAt, reason, approvedBy

  A bounded, audited exception for a subject or incident; it must not bypass global safety limits or authorization.

Data flow

1. 1. Resolve the quota identityThe gateway extracts tenant, user, credential, IP, endpoint, and request cost, normalizes them, and selects the applicable policy dimensions without trusting client-supplied identity.
2. 2. Load the effective policyThe decision service reads a locally cached policy version and rejects or falls back according to endpoint risk when policy freshness is outside the allowed bound.
3. 3. Atomically update countersThe service evaluates each token, refill, or window bucket in one atomic operation per key and consumes cost only when the policy allows the request.
4. 4. Return an actionable decisionThe response includes allowed, remaining, resetAt, retryAfter, and policy version so clients and operators can distinguish quota rejection from service failure.
5. 5. Propagate, expire, and audit asynchronouslyPolicy versions propagate to regions, inactive counters expire, hot-key and rejection metrics aggregate, and sampled decisions feed audit without slowing every check.

Deep dives and trade-offs

• Token bucket and burst semanticsA token bucket with capacity B and refill rate R permits controlled bursts while bounding long-term throughput; define whether cost can exceed one token. Store lastRefillAt and remaining tokens atomically, using a monotonic server time source rather than trusting client clocks. Return reset and retry hints derived from the actual policy, not a generic fixed delay that hides burst behavior.
• Policy precedence and identityA request may consume tenant, user, credential, IP, and endpoint buckets. Define whether all dimensions must allow and how the tightest retry hint is selected. Resolve identity at a trusted boundary and normalize IPv4, IPv6, forwarded headers, credentials, and endpoint templates consistently. Separate transactional traffic from bulk or public traffic so a global policy does not create accidental cross-tenant coupling.
• Atomic counters and hot keysThe counter update must be atomic for one quota key; a read followed by a write allows races that over-admit during bursts. A popular public endpoint or tenant can still overload its counter shard; use dedicated capacity, local admission, or hierarchical limits. Do not add a global lock to solve hot keys; isolate the key and accept an explicitly bounded approximation when product policy allows it.
• Multi-region enforcementA globally strict counter needs coordination and spends latency or availability budget; local counters are faster but can over-admit across regions. Choose strict, regional, or hierarchical enforcement per policy and report the policy mode in metrics and documentation. Clock skew and delayed replication can change window boundaries, so use server time and tolerate or compensate for bounded drift explicitly.
• Fail-open, fail-closed, and degraded modeFail closed for abuse-sensitive or expensive endpoints when the limiter cannot make a trustworthy decision; fail open or use a local emergency limit for low-risk reads. Cache the last validated policy and use bounded local counters during a regional dependency failure, but expose that enforcement is degraded. Protect the counter store itself with circuit breakers, admission control, and a separate emergency budget.
• Policy rollout and freshnessPublish immutable policy versions and apply them idempotently in each region; an effectiveAt barrier can coordinate high-risk changes. When a cache is stale, compare policy risk and freshness against the endpoint contract instead of silently using any available rule. Retain rollout history so an operator can explain which limit was enforced for a rejected request.
• Retries, response headers, and costA retry may represent a new request and should normally consume quota again; if a client retry must be idempotent, define a bounded request identity and replay window. Return standard remaining, limit, reset, and retry-after information without exposing another tenant's quota state. Batch decisions only within bounded limits and keep partial failures explicit rather than pretending unrelated keys share a transaction.
• Observability and abuse detectionMeasure decision latency, counter errors, rejection rate, policy freshness, hot-key skew, drift, and fail-open events by region and policy. Sample high-cardinality decisions and aggregate ordinary traffic so observability does not become a second overload source. Keep abuse analysis asynchronous; a slow detector should not delay a safe, already-bounded decision.
• Token bucket versus sliding windowUse token bucket for efficient low-latency decisions and controlled bursts; use a sliding or fixed window when boundary semantics are easier to explain or audit. Window algorithms can create boundary bursts, while token bucket requires careful refill arithmetic and atomic state.
• Centralized versus local countersUse a regional counter store for strict local enforcement and local emergency limits for resilience; document cross-region approximation separately. A globally centralized counter adds latency and can become a single failure domain; independent local counters can over-admit.
• Single-dimensional versus hierarchical quotasCombine tenant, subject, endpoint, and IP dimensions when abuse or fairness requires it, but keep the number of atomic buckets bounded. More dimensions improve isolation but increase decision cost, memory, and the difficulty of explaining which bucket rejected a request.
• Fail-open versus fail-closedSelect the failure mode per endpoint risk and offer bounded local emergency limits rather than one global policy. Fail-open can expose expensive or sensitive endpoints; fail-closed can turn a limiter outage into a broad application outage.
• Exact audit versus sampled telemetryKeep the decision response authoritative and sample or aggregate high-volume audit data, retaining full records for policy changes and exceptional events. Sampling reduces storage and cost but cannot answer every historical question without a defined reconstruction limit.