Design an API rate limiter

01Problem and scope

An API rate limiter decides whether a request may consume allowance before it reaches protected work. The design starts by defining the identity, counted event, time interval and failure policy—not by choosing a counter store. For example, a video-to-audio conversion API can allow at most three accepted admissions for account u42 in any rolling 60 seconds. Limits for infrastructure protection, authentication abuse, paid quotas and priority classes may use different strictness and outage behavior.

Use an authenticated account/API key with a fleet-wide limit of three accepted admissions in any rolling 60 seconds. A failed conversion still consumes its admission; an internal retry of the same remote procedure call (RPC) to check admission must not consume allowance twice. Fixed clock-minute counters and burst budgets implement different contracts. Keep network DDoS filtering and financial settlement outside this service: an expiring limiter is not a billing ledger.

Policies are versioned and strict mode is explicit. A faster approximate mode is a separate product choice, not a silent substitution. The bounded trace uses account u42 and policy p7 with the three-admission, 60-second rule; larger limits change state and pruning costs, which the capacity estimates address.

02Functional requirements

1. Authenticate and classify: Identify the caller and applicable API class before checking quota.
2. Admit or deny: Atomically check and consume the applicable allowance, forward admitted work, or return HTTP 429 with a reason and retry guidance.
3. Share allowance across gateways: A request reaching a different gateway must not receive a fresh per-user budget.
4. Recover decision retries: Use a gateway-generated stable decision ID so an internal decision-RPC retry recovers its committed result after a lost response.
5. Manage policy: Administrators can publish audited effective policy versions, inspect aggregate denials and temporarily disable an endpoint during an incident.

Distinct quota policies

These policies describe how much deviation from the advertised allowance is permitted. They are separate from the algorithm that accounts for requests over time: choosing a fixed window, rolling log or token bucket still has to satisfy the selected policy's actual promise.

These are separate product policies, not harmless implementation shortcuts.

Retry identity and atomic scope

A public caller cannot repeatedly reuse one ID for free conversions. Business execution retries need their own idempotent contract; distinct external attempts receive distinct admission identities.

Initially, limits that must be checked together share one account owner: the service responsible for serializing changes to that account’s quota state. Independent global or IP limits may run conservatively before the account decision. Consuming one budget and failing another may waste capacity; distributed all-or-nothing rollback across unrelated owners is outside this contract.

03Non-functional requirements

1. Peak workload: Ten million decision checks/s across one million active identities. Count rejected requests too: a three-per-minute user may still hammer the limiter ten times per second.
2. Latency: Five-millisecond p99 decision budget within a region. Never queue limiter requests without a bound; on timeout, apply and record the endpoint's configured failure mode.
3. Availability: 99.99% for ordinary policies. Strict policies deny or return unavailable when safe authority cannot be established, so successful-admission availability can be lower during partitions.
4. Exact admission rule: For u42/convert, at most three accepted timestamps lie in (now−60s, now].
5. Durability and replay: Every accepted decision survives the declared single-node failure. Replaying its decision ID returns the original result without inserting another timestamp.
6. State retention: Expire idle state only after it cannot affect any policy interval or retry horizon. Cache eviction must never reset strict allowance.
7. Time authority: Use one trusted shard decision clock with bounded error; callers cannot supply admission timestamps.

Clock failures and conservative expiry

The limiter restores allowance by deciding that old admissions have aged out. A clock jump can therefore change how much work it permits, even when no request record was lost. Conservative expiry means retaining an admission until the available clock bounds prove it is outside the rolling interval.

04Capacity estimates

Workload assumptions and arithmetic

One million users making ten checks/s produces ten million decisions/s. At an illustrative 250 bytes/request plus response, traffic is roughly 2.5 GB/s before transport framing, replication and retries. A single fast memory store is not automatically a ten-million-operation service. If benchmarks demonstrate 50,000 decisions/s per owner at the latency target, 200 owners are needed before spare capacity; at 60% planned utilization, provision about 334 owner equivalents. Measure the real script, key distribution and durable replication policy.

Worked estimates

The alternatives retain different amounts of timing information. A fixed counter stores a total for one clock interval; a rolling log retains individual admission times; minute buckets retain one total per minute. The table uses a larger cap to show how exact event history can cost more memory than aggregated counts.

Capacity implications and limits

These are logical estimates, not Redis allocation guarantees. Add key strings, ordered-set nodes, policy dimensions, decision replay records, replication and allocator slack. A three-entry rolling log is small; a million-entry hourly limit is a different choice. Accepted-event memory is bounded by the quota; denial-result replay memory can grow with attack traffic, so retain only trusted internal RPC retries for a short horizon and cap identities.

At ten million checks/s, a 99% internally cached deny interval can remove 9.9 million repeated owner calls for already-exhausted keys, provided the cached denial never outlives the earliest safe retry time and policy changes can invalidate it. It may reject conservatively; caching a positive admission would be unsafe because allowance changes on every accepted request.

05APIs and contracts

Request and response example

This is the internal request from a trusted gateway to the quota owner, not a public request whose caller may choose an identity or policy. CheckAndConsume asks for one recorded admission decision; the returned deadline tells the gateway when a denied caller may try a new check.

CheckAndConsume {
  principal: u42, apiClass: convert, decisionId: gateway7-r104,
  policyVersion: p7, trustedGatewayIdentity: g7
}
Decision {
  allowed: false, reason: quota_exhausted,
  retryAt: "2026-09-22T12:01:00Z", retryAfterMs: 10000,
  policyVersion: p7, decisionId: gateway7-r104
}

The example decision is made at 12:00:50 UTC. Store the absolute, conservatively calculated retryAt deadline with a denial; calculate the remaining duration when sending or replaying it. If the reply is recovered at 12:00:59, the remaining wait is one second, not a fresh ten seconds. Round the public Retry-After delay up to whole seconds and account for bounded clock error when translating the deadline at a gateway. Reaching that time permits a new check; it does not reserve capacity. A replay still reports the original denial.

Authentication establishes principal identity before routing. The owner validates policy version; an obsolete gateway receives a policy-refresh response rather than accidentally selecting a separate empty quota key. Separate policy identity from usage identity: changing p7 to p8 does not reset usage unless that is the explicit product rule. For a stricter rolling limit, the owner applies the new threshold to retained usage; a longer new window needs enough history or a conservative migration period.

The public endpoint returns 429 only for a known quota denial. A limiter outage is distinguishable from quota exhaustion, for example a 503 on strict endpoints. RFC 6585 defines 429 and permits Retry-After; the response must not be stored by caches. An internal gateway may keep a private conservative deny-until hint, which is a different mechanism.

The response never exposes other tenants' quotas or raw policy internals. Bound both RPC and public request sizes. Decision IDs are scoped to the gateway/session retry protocol, and retries after the documented replay horizon are treated as new attempts or require a separate operation-status check; they are not an unlimited deduplication promise.

06Data model and access patterns

Keep policy configuration, admitted usage and retry outcomes distinct. A policy states the rule; usage records what has consumed it; a replay record recovers the answer to one interrupted check. Routing and owner metadata identify which server may change that state after a move or failure.

For a rolling log, index accepted events by timestamp and distinct event ID. Multiple admissions can share the same timestamp; the ID prevents an ordered-set insertion from overwriting another event. Pruning deletes timestamps at or before now−window, because our interval excludes its left boundary. For a positive limit L and n ≥ L remaining admissions, at least n − L + 1 entries must expire before another can fit. Use the expiry of entry n − L in timestamp order (zero-based). When n = L, this is the oldest entry. After a policy change from five to three admissions, five retained entries require the first three to expire; waiting for only the oldest would give premature retry guidance. Include the conservative clock margin. If several applicable limits deny, use the latest of their eligible retry deadlines, then check all limits again on the next attempt.

The policy store is durable and relatively low-throughput; versioned snapshots are cached at gateways and owners. The owner changes usage on each admission; losing this state would restore spent allowance, so it cannot be treated as a disposable cache. A sorted structure supports removal and oldest-time lookup, while a bounded ring can work when ordering and maximum size are enforced. Full timestamps and adequate counters avoid overflow and ambiguous wraparound.

Expire idle usage keys only after their last accepted timestamp is outside every relevant window. A whole-key time to live (TTL) does not remove old fields from a continually active hash, so pruning remains necessary. Never use an eviction policy that silently discards live strict counters under memory pressure: shed new work, add capacity or move policies to a bounded representation.

07Basic working design

Single-process critical section

A mutex is a lock that lets one execution at a time enter the protected code. Using one per quota key keeps a request's count check and increment together, while unrelated users can proceed independently. This controls concurrency inside the process; it does not preserve memory after a restart.

Begin with one API process, a dictionary keyed by (user,api) and a mutex around each key's update. For a simple clock-minute counter, the process stores a minute number and count. This is a useful working baseline for learning admission, but it does not yet meet the rolling requirement. At the response boundary, a permitted request increments the counter before conversion starts; a conversion failure does not refund it.

The first request and its result

The caller's first request locks u42, observes an empty current bucket, writes count one, releases the lock and runs conversion. The second and third increment it; the fourth receives a denial. Keep the decision step separate from business execution so a slow conversion never holds the counter lock.

What a restart invalidates

On one process this is easy to inspect and test. Send four concurrent requests and verify that exactly three enter the work queue. Then restart the process: all usage disappears. The baseline therefore makes only a single-process, restart-loses-state promise. It is unsuitable for an exact cluster-wide quota or a security policy requiring durable admissions, but its limitations are now explicit rather than hidden behind the word “cache.”

Negotiate the window semantics

This is also where the interviewer can change the requirement. If they merely want a best-effort per-instance overload guard, the tiny local limiter may be the correct final answer. Our stated rolling, cluster-wide contract requires further work.

08Find the baseline flaws

Fixed-window boundary burst

At 12:00:58, :59 and :59.5 the caller consumes three fixed-minute slots. At 12:01:00, :00.2 and :00.4 the caller consumes the next three. Six requests pass in 2.4 seconds. The implementation is correct for fixed clock buckets and wrong for our rolling contract. Adding a second independent API process creates another failure: each process grants three, so load balancing increases the user's allowance.

The stored state determines which timing questions the limiter can answer. A fixed-interval count cannot reconstruct exact admission times; a rolling log can, at higher storage cost. Token and leaky buckets model available capacity or scheduled work instead, so the following rows are different contracts rather than interchangeable implementations.

Sliding-window counter approximation

The sliding-window counter estimates usage as currentCount + previousCount × (1 − elapsed/window). For example, 15 seconds into a 60-second bucket, eight accepted requests in the previous bucket and two in the current bucket give 2 + 8 × 0.75 = 8. This assumes the older requests were evenly distributed. Their exact rolling count could instead be anywhere from two to ten, depending on timestamps. Use this memory-saving approximation only when the contract permits it; our strict cap still uses the sliding-window log. Redis algorithm comparison.

Token-bucket behavior

A token bucket with capacity three and refill one token/s admits three at second zero. At second two, min(3,0+2×1)=2 tokens exist, so two more pass. That is useful for smoothing conversion load, but cannot replace “three in any 60 seconds.” We select a rolling log for this strict example.

Shared allowance needs shared authority

The performance counterexample remains: a single process cannot safely handle ten million checks/s while also doing conversions. State ownership, distribution and durability must be designed separately from the algorithm choice. A benchmark that only measures dictionary memory answers none of those questions.

09Improve the design, step by step

1. First, replace the minute count with an atomic rolling log. Trigger: the six-request boundary test. Prune, count, compare and append under one key lock or one short owner operation. The improvement is exact interval behavior. The cost grows with accepted entries, and a long prune can block other requests. Cap policy sizes and bound work; choose a token bucket when the product permits burst/rate semantics and benefits from constant state.

2. Second, move usage to shared partition owners. Trigger: multiple gateways multiply allowance and overload one CPU. Route (principal,apiClass) to one partition and store together all of that principal’s limits that must be checked in one decision. Gateways now observe one allowance. The costs are an RPC on each uncached decision and routing/rebalancing operations; a stale routing table can reach a previous owner. The old owner rejects the stale ownership version, and handoff prevents it from accepting writes after the new owner takes over. Local counters remain preferable for explicitly per-instance circuit protection.

3. Third, make strict acceptance durable. Trigger: a crashed owner loses r103 and grants a fourth slot. Use an owner backed by a replicated, linearizable state machine or transactional store whose commit acknowledges the promised failure policy before returning allow. The benefit is preserved admissions through failover. The cost is replication latency and reduced availability during partitions. Plain asynchronously replicated Redis may be suitable for an approximate abuse-control contract, but is not by itself proof of lossless strict failover. Redis WAIT reports replica acknowledgments; its documentation explicitly does not turn Redis into a strongly consistent store or eliminate acknowledged-write loss during failover. Consistent hashing moves keys; it does not preserve their values.

4. Fourth, protect the limiter from denied traffic. Trigger: exhausted accounts generate most checks. Gateways cache conservative deny-until hints and apply coarse local overload ceilings before contacting owners. This reduces repeated owner work without creating extra admissions. It can over-reject after policy increases and needs version invalidation. For high-throughput soft policies, small leased budgets can reduce RPCs, but their sum must be bounded and reclamation must not duplicate outstanding credits. We do not apply independent positive caches to the exact rolling rule.

10Detailed architecture

Identity-aware request path

The public path enters an identity-aware gateway, which consults a versioned policy cache. If a private deny hint says the caller’s allowance is still exhausted, the gateway can reject locally. Otherwise the router resolves the quota partition and sends one decision RPC to its current owner. That owner applies the rolling operation and commits the resulting state through its replica group before returning a strict allowance.

Policy control versus admission data

The final diagram separates the configuration/control plane from the per-request data plane. Administrators edit the durable policy store; a distributor publishes versioned updates to gateways and owners. Policy changes do not create new empty usage state by accident. Routing configuration supplies ownership epochs. The old owner stops accepting an epoch before the new owner receives traffic, with state transfer and commit position checked during rebalance.

Admission replay versus business retries

Only a returned allow decision causes the gateway to forward business work. The downstream API still needs its own idempotency and overload controls. A rate limit constrains admissions over time, not necessarily concurrency: if each conversion lasts a minute, even a modest sustained admission rate can fill workers. Add a separate concurrency cap when that resource model requires it.

Telemetry and strict state

Metrics flow asynchronously and cannot be authoritative for admission. A telemetry outage must not erase quota state. Owner replicas are shown because acknowledgment survival is part of the contract; their placement and failover mechanism must be supported by the selected storage system, not inferred from three database icons.

Ordered policy activation

A new policy takes effect for a partition when its owner records the change in the same ordered stream as admissions. Saving the administrator’s configuration alone does not make owners enforce it. For an all-partition activation deadline, the control plane must establish that every serving owner has installed the version or make nonacknowledging owners unavailable; an old policy lease cannot be renewed indefinitely. This separates publishing configuration from enforcing it. A rollout may temporarily over-reject, but it cannot claim the tighter global rule while old owners continue admitting under a larger cap.

11Write path and acknowledgement

Admission is a state-changing operation even when its response is a denial. The following trace defines account u42, API class convert, policy p7, accepted times 0, 10 and 20 seconds, and a limit of three in a rolling 60-second interval.

1. At second 50, gateway g7 authenticates the caller as u42 and assigns internal decision ID r104. It selects convert policy p7; the public caller cannot override the principal or policy.
2. The router resolves partition 418 and epoch 12. Owner A rejects an outdated epoch or asks the gateway to refresh routing.
3. A obtains trusted decision time and checks whether r104 already has a recorded result with the same payload. A replay returns that result without another insertion.
4. In one atomic operation, A removes admissions at or before −10. The entries at 0, 10 and 20 remain, so count equals three. It records a denial for this retry horizon and returns retry-after ten seconds. r104 is not inserted into accepted usage.
5. At second 60, a new external attempt gets r105. Pruning removes r101 at second zero. A appends r105, commits through its durability policy, and returns allow.
6. The gateway forwards the conversion once under its business request contract. If the decision RPC reply was lost, it retries r105; if the downstream reply is lost, it recovers that business operation rather than inventing another free conversion.

An exhausted rolling log grows only with accepted events, not every denial. Decision replay retention is separately bounded. The gateway does not sleep for ten seconds while holding a worker thread; it returns clear retry guidance and expects callers to wait before retrying and add randomized delay so retries do not arrive together.

12Read and delivery path

Policy and dashboard reads do not reserve allowance. This path explains policy refresh and conservative denial reuse; every eventual admission still requires an authoritative atomic consume.

The limiter has no harmless read-only “remaining quota” check that can authorize later work. Remaining allowance can change immediately after a read, so every admitted operation must perform the atomic check-and-consume. A dashboard may show approximate usage with an asOf timestamp, but that display is not a reservation.

1. A gateway starts with a validated policy snapshot, including version and expiry. It subscribes to updates or polls a version manifest; failed refresh keeps a policy-specific last-known-good state only for the documented grace period.
2. For u42 at second 50, the owner returns a denial and earliest safe retry time. The gateway may retain a private deny hint until that time, scoped to identity/API/policy semantics.
3. A subsequent request at second 55 can be denied locally. It cannot extend the deny hint merely because another denied request arrived; denied traffic does not consume or refresh accepted usage.
4. At second 60, the gateway must consult the owner again. It cannot transform the expired denial into an allow without consuming state.
5. A policy update that raises the limit can invalidate deny hints early. A lowered limit is enforced at the owner even if a gateway still has an older snapshot; a refresh response prevents stale gateways bypassing it.

Public 429 responses include only appropriate per-caller guidance and are not stored in shared caches. Observability reads go to snapshots or replicas when approximate data is acceptable, keeping dashboards from competing with the authoritative update path.

13Correctness deep dive

Two gateways contend for the last slot

atomic admit(key, decisionId, payload, trustedNow, epoch):
  require epoch == currentOwnerEpoch
  require valid types, sizes and policy before mutation
  if replay[decisionId] exists:
      require replay.payloadHash == hash(payload)
      return replay.result with remaining wait recomputed from stored retryAt
  now = conservativeOwnerTime(trustedNow, lastTime)
  remove only entries proven outside window by conservative time bounds
  if accepted.count >= limit:
      releaseEvent = accepted.sortedByTime[accepted.count - limit]
      result = DENY(retryAt = conservativeExpiry(releaseEvent, window))
  else:
      append (decisionId, now) to accepted
      result = ALLOW
  record replay result and lastTime
  commit under required durability policy; return result

Atomic winner and replay result

G1 wins: its atomic operation observes two, appends r103 and commits three. G2 then observes three and denies. G1 crashes after commit: G2 still observes the durable third entry; G1's retry reads the recorded result. G1 crashes before commit: no admission was returned, and the retried operation may consume the remaining slot. If the system cannot tell whether an acknowledged admission survived failover, it must not advertise this exact guarantee.

Redis atomicity is not failover durability

Redis scripts can serialize the prune/check/insert operation on one owner, but validate inputs before mutation because script errors do not imply general transactional rollback. Multi-key scripting in a cluster also has placement constraints. Running the operation atomically on one process is only part of the guarantee. Accepted usage must survive failover, old owners must stop admitting, and clocks and policy changes must obey the stated rules.

Multiple quota-owner tradeoff

For two quota dimensions on different owners, checking both independently can waste a token when the second denies. Accept conservative under-admission, colocate the state, or adopt a real reservation/commit protocol. Do not claim that two sequential atomic scripts constitute one atomic multi-owner decision.

14Failure and recovery

When one account is hot, hashing more keys does not split that account's serialized decision stream. Cached denial reduces repeated failures; accepted throughput still has a per-owner limit. A distributed credit protocol may help a different burst contract, but exact rolling timestamps need coordinated accounting. Bound retries to avoid turning a two-millisecond timeout into three overlapping owner calls. Monitor original requests separately from retry amplification.

Clock recovery can be conservative: keep recently accepted entries longer after a suspect jump and temporarily deny. This sacrifices availability while retaining the safety claim. Document that behavior so operators do not “fix” an incident by clearing strict counters.

15Operations, security, and cost

Verified identity and bypass protection

Authenticate gateways and derive identities from verified credentials. IP-only controls punish users whose network address translation (NAT) gateway gives them the same public address and can be evaded by address rotation; account-only login caps can let an attacker lock out a victim. Combine endpoint-specific account rules with coarse network safeguards, progressive delays and bounded anonymous identity state. Hashing attacker-controlled strings does not bound the number of distinct keys.

Latency and policy behavior signals

Tie metrics to the contract: p99 check latency against five milliseconds, denied rate by reason, strict-mode unavailable responses, active-key count, prune cost, owner CPU, replication lag and downstream concurrency. Compare admitted events against a reference rolling-window checker in sampled logs. A low rejection rate is not inherently good if protected conversion workers are overloaded.

Rolling-window memory cost

At 12 GB logical rolling-log state, three copies mean at least 36 GB before runtime overhead and replay records. At 10M decisions/s, replication and network can dominate memory expense. Measure CPU-time per decision and bytes per accepted mutation; a denied request need not create a replicated usage event unless replay semantics demand a result record. Bounded gateway retries reduce that need.

Shadow decisions and clock/failover tests

Roll out policy/code versions in shadow mode, comparing decisions without double-consuming live allowance. Then enable a small cohort and test boundary timestamps, simultaneous same-time requests, owner loss after acknowledgment and moving a live partition. For a new longer window, backfill sufficient retained history or use a conservative transition; changing a key prefix is not a migration plan.

16Decision ledger and limitations

A leaky bucket is appropriate when we want to queue and pace work, but waiting adds latency and requires a bounded queue. A token bucket is appropriate when a short burst is acceptable and long-run rate matters. Weighted windows and bucket counters save memory but need an explicit error model. None is universally “best.”

This design intentionally distinguishes safety from availability. A security-sensitive exact cap cannot remain fully available through arbitrary authority failures while also forgetting no admitted work. A best-effort protection rule can choose a simpler Redis-backed path and state the overshoot. The interviewer should hear the contract first and the storage brand second. The next scaling decision follows a measured hot-key and replication benchmark, not an assumed operations-per-second claim.

17Interview closing

“I clarified that the policy is three accepted admissions in any rolling 60 seconds across the fleet. A fixed-minute counter fails at the boundary, so I keep accepted timestamps and atomically prune, count and append on one quota owner. Gateways derive identity, cache versioned policy and route to that owner. A strict allow is returned only after the chosen durable commit; retries carry a stable internal decision identity. Two gateways competing for the final slot serialize at the same authority, and only one can consume it.

“I scale independent keys across owners, keep conservative deny hints at gateways and bound retries and anonymous state. The costs are an RPC, replicated writes and unavailability when strict state cannot safely fail over. A hot quota key still has a serialization limit. I would next measure p99 decision time, state bytes and owner throughput under the real distribution, including denied traffic.”

If the interviewer changes the requirement to “allow a burst of 100, sustained 10/s,” switch to a token bucket and demonstrate refill arithmetic. If they add a global paid budget spanning regions, discuss colocated authority or reserved regional credits with an explicit accounting protocol. Do not retain an exact global claim while quietly granting independent regional allowances.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.