Design an API rate limiter

01Specify exactly what consumes allowance

Design a limiter for a video-to-audio conversion API: account u42 may receive at most three accepted admissions in any rolling 60 seconds across all gateways. An admission is permission to start one conversion attempt. A conversion that later fails still consumes its admission. The limiter is not a billing ledger and does not guarantee that downstream work runs only once.

Use authenticated account identity plus API class as the quota key. The client cannot choose another account, its own policy or a fabricated timestamp. Gateways assign internal decision IDs so a retry of one interrupted limiter call can recover its answer without consuming allowance again. Distinct external attempts receive distinct decision IDs.

Choose strict enforcement for this exercise. If the service cannot establish the current quota state, return unavailable rather than create a fresh local allowance. That sacrifices successful-admission availability during some failures. A best-effort overload guard could deliberately choose a simpler, more available policy, but that would be a different contract.

Ask which identity owns the allowance, what event consumes it, whether bursts are allowed, and whether uncertainty should deny or admit. For this exercise the interviewer accepts a strict rolling admission limit even when that reduces availability.

02Functional requirements

Agree on these supported actions before selecting components.

1. Decide admission for the correct account. Check the authenticated account and API class before starting a video-to-audio conversion; return an allow, a known quota denial or an unavailable decision.

2. Apply the stated rolling policy. Allow at most three accepted admissions in any rolling 60 seconds across all gateways. A later conversion failure does not refund that admission.

3. Recover interrupted internal checks. Gateways assign decision IDs and recover the same recorded outcome after response loss without consuming another slot.

4. Manage policy and retry guidance. Apply authorized policy changes to existing usage, and return meaningful retry timing for known quota denials without reserving a future slot.

03Non-functional requirements

Use these as illustrative interview assumptions to agree with the interviewer. Numerical targets require measurement; they are not claims about an existing product or a proven implementation. p95 (the 95th percentile) means 95% of measured operations finish within the stated time.

1. Precision and failure behavior. No extra strict admission is permitted because a gateway, owner or clock is uncertain. Fail closed when safe shared state or trustworthy decision time cannot be established; this intentionally sacrifices admission availability.

2. Workload. Plan for ten million checks/s, including denied requests. The separate cap-500 storage example sizes a higher configured policy and does not change the three-per-minute running example.

3. Decision latency. Target p95 of five milliseconds from the trusted gateway’s limiter call to its answer within one region under the admitted planning load. Validate the actual synchronous transaction and hot-key mix; the assumed 50,000 decisions/s owner benchmark is not proof.

4. Durable accepted usage. An acknowledged allow and its replay result must survive one database-node failure within the region. Failover cannot reset allowance or promote known stale usage as current.

5. Bounded state and work. Bound decision-retention windows, active keys, retries and downstream concurrency. Live usage cannot be evicted merely to reclaim memory while it still affects the rolling window.

6. Trusted callers and time. Authenticate gateway callers and policy writers. The client cannot supply another principal, choose its own timestamp or reuse an internal allow as unlimited permission for downstream work.

04Serialize one account’s admission decision

Begin with one application and a SQL database. For each quota key, lock its account-usage row in a transaction. Read the database’s decision time, remove accepted events outside the rolling interval, count those remaining and append a new event only if the count is below three. Save the decision result in that same transaction, then respond after commit.

Suppose u42 was admitted at seconds 0, 10 and 20:

The database row lock makes the whole check-and-consume operation indivisible with respect to other requests for u42. If two gateways both compete for the last slot, one completes first; the other sees its accepted event and denies. An atomic counter increment after a separate unlocked check would not provide that result.

Release the transaction before running the conversion. A slow conversion must not hold the quota lock. This is already a working fleet-wide limiter when every gateway uses that database path. Its limits are decision throughput, per-key serialization and the cost of durable state changes.

05Choose the algorithm that matches the promise

A fixed-minute counter is cheaper, but it answers a different question. Three requests at 12:00:58, :59 and :59.5 followed by three at 12:01:00, :00.2 and :00.4 all pass separate clock-minute buckets. Six admissions occur in 2.4 seconds, violating the chosen rolling rule.

For a token bucket of capacity three refilling one token per second, three requests pass immediately from a full bucket; two more can pass two seconds later. That is useful for a burst-tolerant throughput policy, but it cannot stand in for three admissions per rolling minute.

Keep the rolling log for this worked design. Its retained accepted-event count is bounded by the cap under an unchanged policy. A large hourly cap can make that state expensive, which is a reason to renegotiate precision or choose another contract, not silently substitute an approximation.

06Include denied traffic in capacity

Assume one million active identities each generate ten checks/s: ten million limiter decisions/s. An exhausted account may continue sending requests, so a three-per-minute allowance does not bound the request rate reaching the limiter.

The 50,000 decisions/s figure is a benchmark input to validate, not a claim about a particular database. Test the actual transaction, replication policy and hot-key distribution against an illustrative five-millisecond decision budget.

Decision replay records have a different bound from accepted events. Attackers can cause many denials, so retain internal decision results for a short documented retry horizon and cap trusted gateway request sizes and identities. Runtime overhead, policy dimensions and duplicate retries may cost more than the packed timestamp bytes.

07Separate a denial from an unavailable limiter

The trusted gateway calls the limiter using this internal operation:

CheckAndConsume(principal, apiClass, decisionId, policyVersion)

Only an allow result authorizes forwarding the business request.

A known exhausted quota becomes HTTP 429 with suitable Retry-After guidance. An unavailable strict limiter becomes a retryable service error, such as 503, rather than falsely claiming the user exhausted a known quota. Do not publicly cache the 429 response. An internal gateway may retain a conservative private denial hint for that account and API.

At second 50 in the example, the earliest retry time is second 60. If a lost response is recovered at second 59, report approximately one remaining second, rounded conservatively for the public header, not a fresh ten-second delay. Reaching that time permits another check; it does not reserve the next slot.

Policy version identifies configuration, not a new empty usage key. Changing the cap must apply to retained usage. A new longer window requires enough historical data or a conservative transition. A stale gateway must refresh its policy rather than create a separate allowance accidentally.

08Keep rules, usage and recovered answers distinct

Index usage by quota key, timestamp and distinct event ID. Two requests may share the same timestamp and still be separate admissions. Remove old individual entries on active keys; whole-key expiry alone does not prune an account that remains busy forever.

Retry recovery checks the decision identity before counting or appending. Reusing that identity with a different payload is rejected. The transaction saves usage and its recoverable answer together. Otherwise a crash can consume allowance without recording what to return on retry.

Never treat live strict usage as disposable cache data. Evicting an active key under memory pressure would reset its allowance. Expire state only after it can no longer affect a policy window or supported retry horizon; shed load or add capacity when live state does not fit.

09Distribute keys while keeping each allowance whole

Partition by a stable hash of account and API class. Each partition is hosted by one replicated database group; its leader processes conflicting transactions in order and acknowledges writes only after the required replicas have durably retained them. Choose a datastore that actually supports this commit and failover contract. Stateless gateways can then scale independently while consulting the same allowance for u42.

A minority partition does not grant strict admissions. Routing changes use the datastore’s validated leadership and state-transfer mechanism rather than starting an empty new counter service. This keeps the interview focused on the admission design while making the required storage guarantee concrete.

A very hot account still has one serialized decision stream. Adding unrelated partitions does not split it safely. Reduce repeated denials by caching the returned deny-until time privately at gateways. When that hint expires, the gateway checks the owner again; it cannot transform an expired denial into a cached allow. A policy increase can invalidate the hint early, otherwise it may conservatively reject for a little longer.

Place a coarse local overload guard before the shared limiter to protect it from attack traffic. This guard can reject extra work but cannot create additional strict allowance. Cache hits, dashboards and approximate remaining-quota displays never reserve permission to execute.

Use three replicas in independent regional failure domains and require a durable majority for the selected one-node-loss target. Measure the five-millisecond p95 gateway-to-limiter budget with that replication path enabled. If it cannot be met, discuss a larger budget or a different enforcement contract rather than weakening acknowledged-state safety silently.

10Recover decisions without granting free work

If the database commits allow for decision r105 but its reply is lost, the gateway retries r105. The saved result returns allow without adding another timestamp. This internal protocol is different from letting a public caller reuse one ID for unlimited conversions. The gateway must also avoid forwarding the same recovered business operation repeatedly without the downstream API’s idempotency protection.

If a database leader fails after acknowledging an admission, the chosen replicated store must preserve that committed event through failover. A replacement reading an older two-event snapshot could grant a fourth slot incorrectly. Plain asynchronous replication is not sufficient evidence for the strict promise; choose weaker enforcement explicitly if that is the available infrastructure.

The worked timestamp arithmetic assumes a trustworthy decision clock. Exact real-time expiry under arbitrary clock faults is outside the basic design; uncertain clock recovery pauses strict admissions rather than expiring records speculatively. Make this assumption explicit instead of treating timestamps as proof of physical time.

Fail closed when the quota group is unreachable or its safe state is uncertain. For a trusted clock moving backward, do not move decision time backward and reopen earlier state. A suspicious forward jump must not expire recent events prematurely. Stop admissions until the service’s time bounds are restored; detailed clock-error accounting is an Advanced follow-up.

Limit retries and time spent waiting. The limiter should reject or fail within a bounded budget instead of accumulating a queue that consumes more resources than the API it protects.

11Protect both the quota and the downstream workers

Measure decision latency, accepted and denied rates, unavailable strict decisions, hot-key traffic, state size and replication health. Compare sampled admissions with a reference rolling-window checker. A low denial rate is not success if the conversion workers are overloaded.

Rate limits control arrivals over time; they do not directly cap concurrent work. If conversions take a minute, even an acceptable sustained admission rate can fill the worker pool. Add a separate bounded work queue and concurrency cap, and decide whether a failed admission-to-execution attempt is charged under the stated rule.

Account rules need verified credentials. IP-only limits can punish unrelated users sharing one public address and can be evaded through address rotation. Use endpoint-specific combinations of account and network controls without allowing attackers to allocate unlimited anonymous keys. Administrative policy changes need authorization and an audit trail.

A policy migration must preserve usage. Raising a cap is straightforward; lowering it may require several old events to expire before another admission fits. Test simultaneous last-slot requests, boundary timestamps, lost replies, failover after acknowledgment and memory pressure. Do not “repair” a strict-state incident by clearing the counters.

12Check the design against the requirements

Use the agreed lists to check the finished design. The tests below still need to establish the targets; a proposed mechanism is not a measured result. FR refers to the numbered functional requirements above; NFR refers to the numbered non-functional requirements.

13Rapid revision

Remember: Checking and consuming must happen together; otherwise two gateways can both take the last slot.

In a 90-second close, state the identity, counted event, rolling interval and failure policy. Walk the 0/10/20/50/60-second example, then the two-gateway last-slot race. Finish with the tradeoff: exact shared enforcement costs coordinated state and may reject during uncertainty. If the interviewer instead wants a burst of 100 and a sustained ten per second, choose a token bucket and explain its arithmetic rather than carrying the wrong rolling contract forward.

Recall the key ideas

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