Rate Limiting in System Design: Algorithms and Failure

Design rate limiting with token buckets, Redis, fair budgets, safe retries, and explicit failure policies. Understand where rate limits stop protecting a system.

A shared API can be healthy at an average of 100 requests per second and still fall over when one tenant submits a burst of expensive work. A request counter helps only if it counts the right thing, rejects before the protected work starts, and keeps a meaningful boundary when machines disagree or fail.

I approach rate limiting as an admission contract: who may consume which resource, at what pace, with how much burst capacity, and under which failure assumptions? Choosing Redis or a token bucket comes after those questions.

Consider a multi-tenant data-export API. Clients submit exports, poll their status, and download completed files. A status poll is cheap. Submitting an export can create minutes of work. Giving both operations the same request allowance is simple, but it can be a poor approximation of the resource I need to protect.

This article builds that design from the policy outward. The numbers are illustrative, not benchmark results. The important distinction is between an algorithm’s mathematical behavior and the guarantees an entire deployed system can actually keep.

Start with the policy, not the counter

Suppose the API assigns each authenticated tenant a bucket that refills at 20 cost units per second and holds at most 40 units. A status poll costs one unit; an export submission costs ten. These are server-chosen admission weights, not a claim that one export always consumes exactly ten times the CPU of a poll.

A full bucket permits four export submissions together. After that, one second restores enough capacity for two more. This deliberately permits a burst. It does not promise that every trailing second contains at most 20 units.

DecisionDefine explicitlyWhy it matters
IdentityAn authenticated client, tenant, user, or trusted network identity.One client may have many IPs; many clients may share one IP.
CostOne request or a trusted estimate of operation cost.A cheap lookup and a large export consume different resources.
ScopePer endpoint, tenant, service, region, or global budget.Independent copies of a full budget multiply available capacity.
Time and burstA named window, rolling interval, or refill rate with capacity.The same average rate can permit very different short bursts.
ChargingWhich attempts consume capacity, including retries and rejections.Business idempotency does not automatically deduplicate quota charges.
FailureFail open, fail closed, or a bounded fallback allocation.Availability and enforcement make different trade-offs during an outage.

I would also give export execution a separate worker-concurrency budget. Admission creates a durable job; a worker starts it only when execution capacity is available. The submission limiter protects the API and queue arrival rate. The worker limit protects active execution. A daily purchased export allowance, if the product needs one, belongs in a durable usage ledger with its own reservation and reconciliation rules.

Decide what counts before implementing it. In this example, a rate rejection consumes no tokens. An admitted request is charged even if later application work fails. Business-level deduplication prevents creating the same export twice, but does not automatically make two admission attempts one charge. A refund policy is possible, but it needs a precise definition and bounded accounting.

Choose the algorithm that matches that contract

The common algorithms answer different questions. A fixed window can enforce an exact count for each named minute while still allowing a large burst across a minute boundary. That is a consequence of its contract, not necessarily an implementation bug.

AlgorithmContractBoundary
Fixed windowCount admissions within each fixed interval.Can admit twice the limit across a window boundary.
Sliding window logCount accepted events in the trailing interval.Exact for that interval, but allows a burst up to the limit and retains event state.
Weighted sliding counterBlend current and previous fixed-window counts.An estimate that can undercount or overcount clustered arrivals.
Token bucketRefill at rate r, cap at capacity C, debit operation cost.Allows bursts; it does not cap every interval at r times its duration.
Leaky bucket meterDrain accumulated debt and immediately accept or reject.Capacity permits bursts; accepted work is not automatically paced.
Leaky bucket shaperQueue work and release it according to a schedule.Requires a bounded queue, deadlines, cancellation, and actual delayed dispatch.

For a fixed limit of 100 per minute, 100 admissions just before a boundary and another 100 just after it can be valid. An exact sliding log removes this boundary effect by checking the actual trailing interval. It can still admit 100 requests together after an idle period. A rolling window does not imply smooth output.

A weighted two-window counter estimates the trailing count from the current bucket and a fraction of the previous one. It saves state by assuming how earlier arrivals were distributed. Imagine all 100 earlier requests arrived immediately before the boundary. At 54 seconds into the next minute they are still in the true trailing minute, but a linear estimate counts only about ten. Admitting roughly 90 more can be consistent with the estimate and violate a strict rolling limit. Use this approximation when its error is acceptable, not when the product promises an exact rolling allowance.

“Leaky bucket” also needs qualification. A meter can track debt and reject when capacity is exhausted. A shaper actually queues work and releases it on a schedule. A nonzero meter capacity allows a burst; a shaper needs bounded queue space, deadlines, and cancellation. Returning a suggested retry time does not create such a queue. RFC 3290’s metering and shaping discussion is useful background, although its original units are network traffic.

A token bucket separates burst from sustained rate

A continuous token bucket has capacity C, refill rate r, and an admission cost c. Before each decision, add the tokens recovered since the last update, capped at capacity. Admit only when the resulting balance can pay the cost, then subtract it.

The next figure uses a smaller, separate example: capacity three, refill one token per second, and unit-cost requests. Four simultaneous arrivals spend three tokens and reject one. Nothing in this limiter queues that rejected request.

An illustrative token-bucket burst and refill traceRead left to right. The bucket has capacity three, refills one token per second, and every request costs one token. At time zero a full bucket receives four simultaneous requests: three are admitted and one is rejected without being queued. One second later one new token is available, so one more request can be admitted, leaving zero tokens.Token bucket: an illustrative burst and refillt=0: BUCKET FULL1113 tokens availablet=0: BURST OF 43 admitted1 rejected0 tokens remaint=1s: REFILL+1 token arrives1 request admitted0 tokens remainCAPACITY 3 · REFILL 1 TOKEN / SECOND · COST 1The extra burst request is rejected immediately. It is not queued.All values and times are illustrative.
An illustrative token-bucket burst and refill traceRead downward. In this illustrative example a bucket of capacity three refills one token per second, and requests each cost one token. At time zero a burst of four admits three requests and rejects the fourth without queuing. At one second a token refills and admits one request, leaving zero tokens again.Token bucket: an illustrative traceCapacity 3 · refill 1 token/s · cost 1t=0: BUCKET FULL1113 tokens availablet=0: BURST OF 43 admitted1 rejected0 tokens remaint=1s: ONE TOKEN REFILLED+1 token → admit 10 tokens remainREJECTED, NOT QUEUEDThe fourth burst request does not wait.
Illustrative values: capacity 3, refill 1 token per second, cost 1 per request. A full bucket admits three requests from the simultaneous burst, rejects the fourth without queuing, then admits one request after the next token refills.

With a fixed policy, intact state, and the modeled continuous clock, admitted cost over an interval of length Δ is bounded by C + r × Δ. Capacity controls the burst; refill controls the sustained rate. This is an adaptation of the token-bucket envelope described in RFC 3290, using operation cost rather than bytes.

Validate the policy. A request whose cost exceeds capacity can never fit, however long it waits. A zero refill rate is not a normal continuously recovering bucket. Define supported costs, numeric ranges, and rounding. An implementation using fixed-point units should preserve fractional refill credit rather than accidentally changing the contract through integer truncation.

The estimated wait is the missing tokens divided by the refill rate, rounded up for a whole-second response. It is guidance, not a reservation. Another request may spend the recovered tokens first.

Make the entire decision atomic

Two gateways can both read a balance of ten, both admit a ten-unit export, and both write zero. The final stored balance looks reasonable while twice the available capacity was spent. Making only the final write atomic does not fix that race.

Read, refill, cap, check, debit, and update expiry must share one atomic boundary for the policy being enforced. In Redis, a short Lua script or Redis Function is one way to provide that boundary on the responsible server. Redis documents atomic script execution; it also means a long script blocks other work on that server. A pipeline reduces round trips but does not isolate a conditional decision.

An atomic single-key limiter shared by gateway replicasRead left to right. An authenticated identity and trusted selected policy produce one subject and policy key. Gateway replicas A and B send requests to the same Redis key on one shard. A single atomic operation reads, refills, checks and debits the budget and sets expiry. Each request is admitted or rejected; only admitted requests reach the application handler. Redis failure follows an explicit endpoint policy such as a bounded local quota or rejection. This diagram does not claim atomicity across multiple shards.One key, one atomic distributed rate-limit decisionTRUSTED IDENTITYAuth + selected policyOne subject/policy keyGATEWAY AReplicaGATEWAY BReplicaONE REDIS KEY / SHARDAtomic operationread → refill → checkdebit → set expiryAdmit or reject each requestREJECTNo handler entryADMITRate check passedAPPLICATION HANDLEROnly after admissionREDIS UNAVAILABLE: EXPLICIT FALLBACK POLICYBounded local quota or reject, as the endpoint contract requires.No unlimited fallback is implied.One key only. Limits across shards are not globally atomic.
An atomic single-key limiter shared by gateway replicasRead downward. Authenticated identity and trusted policy select one key. Both gateway replicas use the same Redis key on one shard. A single atomic operation performs read, refill, check, debit and expiry. Rejecting a request does not enter work, and only admission leads to the application handler. Redis failure has an explicit endpoint policy, such as a bounded local quota or rejection. Multiple limits across shards are not globally atomic.One key, one atomic decisionAUTH + TRUSTED POLICYOne subject/policy keyGATEWAY AReplicaGATEWAY BReplicaONE REDIS KEY / ONE SHARDAtomic operationread → refill → checkdebit → set expiryAdmit or reject each requestREJECTNo workADMITRate check passedAPP HANDLERAfter admissionREDIS UNAVAILABLEUse the explicit endpoint policy:bounded local quota or reject.No unlimited fallback is implied.One key only. No cross-shard atomicity.
Both gateway replicas use one atomic decision on the same subject/policy key. This single-key algorithm does not make organization and user limits across shards globally atomic. Redis failure needs an explicit endpoint contract, such as bounded local admission or rejection.

The figure shows one authoritative key on its owning shard. Gateways send the trusted identity, selected policy, and server-defined cost to that decision. The application handler starts only after admission. Reading a replica and later writing the primary would introduce a stale balance into the decision.

The following is conceptual pseudocode, not executable Redis code. It assumes a fixed policy and one atomic transition. The expiry operation uses the same clock domain as the stored timestamp.

# Conceptual atomic transition, not executable Redis code.
# Fixed policy: C > 0, r > 0, 0 < cost <= C.
# Time is seconds in the coordinator's clock domain.
now = coordinator_time_seconds()
state = read(key) or {tokens: C, last: now}
effective_now = max(now, state.last)
tokens = min(C, state.tokens + r * (effective_now - state.last))

if tokens >= cost:
    tokens = tokens - cost
    allowed = true
    retry_after_seconds = 0
else:
    allowed = false
    retry_after_seconds = ceil((cost - tokens) / r)

write(key, {tokens: tokens, last: effective_now})
expire_no_earlier_than(key, effective_now + C / r + safety_margin)
return {allowed, tokens, retry_after_seconds}

A real script must validate its arguments before mutation, handle numeric and storage errors, and receive every accessed key explicitly. Redis’s EVAL key contract matters in Cluster; dynamically inventing undeclared keys inside the script is not a safe shortcut. Script deployment and reload behavior also belong in the client integration.

Time and disappearing state are correctness problems

Using the coordinator’s clock removes disagreements between gateway clocks from the ordinary calculation. It does not create a perfect clock. Redis TIME returns server wall-clock time. Clock corrections and a failover to a differently timed machine can still affect refill.

The pseudocode keeps an effective timestamp that never moves backward relative to stored state. This avoids crediting the same elapsed period twice after a rollback. A forward jump can still refill early, and a backward jump can freeze refill until time catches up. The real-time rate guarantee therefore needs explicit clock assumptions, monitoring, and a response to large jumps.

Expiry is cleanup, not the refill mechanism. A missing bucket is normally recreated full. Therefore a partially depleted bucket must not disappear before it could legitimately recover. Under a fixed policy and ordinary nondecreasing time, waiting at least C/r after the latest state update is conservative. Round the expiry upward, allow a buffer, and account for future stored timestamps. An arbitrary short TTL quietly grants fresh bursts.

Eviction is a different way to lose state. A Redis cache that discards keys under pressure is not automatically a suitable enforcement store. Redis eviction policies make that trade-off explicit. Choosing no eviction moves the problem toward write failures; it still needs a failure policy. Keep the limiter’s capacity plan separate from disposable application-cache keys.

Configuration changes deserve similar care. Putting a new policy version in every key gives a clean rollout boundary, but also creates fresh buckets. Changing capacity, refill, or cost interpretation in place requires a migration rule. A rollout should not accidentally replenish every tenant at once.

Name the distributed guarantee

An atomic decision on a healthy primary is a useful guarantee. It is not a promise that every acknowledged debit survives failover. Redis replication is asynchronous by default. Lost recent state can allow additional work after promotion. Replica acknowledgments can reduce some risks, but do not turn the system into an arbitrary-failure, strongly consistent global ledger.

A timeout is also ambiguous. The server may have debited a bucket while the response was lost. Retrying blindly may charge twice. Deduplicating admission with a request identifier can address a defined retry window, but adds state, retention, and identity rules. An idempotency key in the export service solves a different problem unless the admission protocol explicitly participates.

Hierarchical policies add another boundary: a request may need user capacity, tenant capacity, and global service capacity. To debit all or none in one Redis operation, the relevant keys must fit the supported atomic boundary. Redis Cluster supports multi-key operations when keys are co-located in a hash slot. A tenant hash tag can help, but a very hot tenant can concentrate load on that slot.

If separate checks on different shards charge one bucket before another rejects, document whether that conservative token loss is acceptable. A compensating increment is not automatically an atomic rollback. A global bucket can also become a coordination hotspot. Start by asking whether strict global accounting is actually required for this resource.

Independent full buckets on five gateways permit roughly five times the intended aggregate refill and burst. Regional buckets do the same unless the policy deliberately allocates the total allowance. Local limiting is still useful for early overload protection or a deliberately partitioned budget. Budget leases can reduce coordination, provided outstanding allocations, renewal, expiry, restart behavior, and redistribution remain bounded. “Fall back to a local limiter” needs numbers and ownership rules.

Rate limits do not bound active work

Arrival rate is a flow. Concurrency is the work currently occupying capacity. Under stable conditions, Little’s Law relates average in-flight work to throughput multiplied by average time in the system. At 100 requests per second and two seconds average residence time, the corresponding average is about 200 requests in flight. This illustrative calculation is not a percentile-latency or queue-size guarantee.

Rate admission and concurrency permits are separate budgetsRead left to right. In an illustrative unit-cost policy, a token budget refills at one hundred tokens per second. An admitted request next needs a separate active-work permit, with a concurrency limit of twenty. Either rate rejection or concurrency overload prevents handler entry. Work has a bounded deadline, and its acquired permit is released in finally. Passing the rate gate does not reserve concurrency, and no automatic token refund is implied.Rate and concurrency answer different questionsIllustrative budgets for unit-cost requestsTOKEN BUDGET100 tokens/s (example)Rate admission onlyACTIVE-WORK LIMIT20 permits (example)Independent gateBOUNDED HANDLERDeadline-bound workRelease in finallyRelease permit in finallyRATE REJECTNo handler entryOVERLOADNo handler entryRATE ADMISSION DOES NOT RESERVE CONCURRENCYA rate-admitted request can still fail the active-work gate.Charging and refund rules must be explicit; no automatic refund is implied.
Rate admission and concurrency permits are separate budgetsRead downward through separate gates. An illustrative unit-cost token budget refills at one hundred tokens per second, followed by an independent limit of twenty active-work permits. Rate rejection or a full concurrency budget returns without entering work. The handler runs within a deadline and releases its permit in finally. Rate admission can still be followed by concurrency overload, and refund policy must be explicit.Rate budget, then active-work permitUnit-cost example; separate policiesTOKEN BUDGET100 tokens/s (example)Rate admission onlyREJECTNo workACTIVE-WORK LIMIT20 permits (example)Independent gateOVERLOADNo workBOUNDED HANDLERDeadline-bound workRelease permit in finallyadmittedpermit acquiredINDEPENDENT BUDGETSRate admission can still hit overload.Work starts only after both gates.Refund rules must be explicit.
A rate budget controls admission over time. A concurrency permit controls active work. Rejected requests never enter the handler, and a rate-admitted request can still fail the concurrency gate. Release acquired permits in finally, bound work by deadlines, and define charging or refunds explicitly.

For a synchronous expensive operation, use a separate concurrency permit. If rate admission succeeds but no permit is available, choose an explicit outcome: shed the request or place it in a bounded queue with a deadline. Do not build an unbounded waiting room inside a gateway. A rate debit is not automatically refunded when the concurrency gate rejects.

Release permits on success, failure, and cancellation, typically through a structured cleanup boundary. For distributed permits, define lease ownership and recovery without letting an expired lease leave old work running alongside its replacement. A cancelled HTTP request is not proof that a database query, export worker, or remote side effect stopped.

For the asynchronous export example, enforce execution concurrency in the workers. Make job cancellation a durable state transition, stop further work cooperatively where possible, and define how completion races with cancellation. The API’s admission token pays for accepting the request; it does not control the whole lifetime of the export.

Give clients a useful rejection contract

Use a clear reason code that distinguishes a caller’s exhausted rate budget from a temporary inability to serve traffic. An illustrative policy rejection looks like this:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Cache-Control: no-store
Retry-After: 1

{
  "error": "rate_limit_exceeded",
  "scope": "tenant_export_api",
  "retry_after_seconds": 1
}

RFC 6585 defines 429 Too Many Requests and prohibits caching its responses. The explicit no-store directive makes that intent visible in this example. The response does not reveal another tenant’s usage or internal infrastructure details.

Retry-After accepts an HTTP date or a non-negative integer number of seconds. Here, one means one second after receipt, not one millisecond or a Unix timestamp. A client should honor valid delay guidance, add non-negative jitter after that delay to avoid synchronized returns, bound attempts by an overall deadline, and cancel both pending timers and in-flight requests when the operation is abandoned. If the required delay exceeds the deadline, stop or defer the operation.

Waiting does not make an unsafe operation safe to repeat. Retried export submission needs its own idempotency contract, and quota charging needs its own retry rule. A successful response containing a remaining allowance is also not a promise that the next concurrent request will be admitted.

As checked in October 2026, the IETF work proposing RateLimit and RateLimit-Policy fields remains an Internet-Draft. Document whichever response fields your API implements. Do not treat older X-RateLimit conventions or reset units as a universal standard.

Choose failure behavior per protected resource

If Redis is unavailable, I do not know that a caller exhausted its allowance. I know the admission dependency failed. A fail-closed API can report temporary service unavailability, commonly 503 Service Unavailable, according to its contract. Reserve rate-exceeded metrics and messages for actual policy rejections.

ConditionConsequenceRequired policy
Limiter unavailableThere is no trustworthy current admission decision.Choose availability, refusal, or a bounded fallback; distinguish this from known quota exhaustion.
Timeout after debitThe charge may have committed before its reply was lost.Bound retries and define deduplication for a logical admission attempt.
Lost or evicted stateA recreated bucket may grant capacity again.Define memory, expiry, restart, replication, and permitted overshoot assumptions.
Separate user and tenant checksOne budget may be charged before another rejects.Use a supported atomic boundary or explicitly accept conservative token loss.
Independent region budgetsEach region can admit against its own allocation.Partition the total budget or coordinate it, including allocation recovery.
Many instances use local fallbackTheir allowances add across the fleet.Bound the combined fallback allocation and its lifetime.

Keep the decision deadline short enough that limiter trouble does not consume the entire request deadline. Avoid nested automatic retries that amplify an outage. A fallback budget needs a maximum aggregate overshoot and a way to stop issuing fresh allocations on every process restart. Otherwise availability is being purchased with an unbounded enforcement gap.

Different operations may justify different choices. A cheap status endpoint might tolerate a small emergency allowance. An expensive export admission might reject when authoritative budget state is unavailable. A financial or purchased-usage limit may require stronger durable reservations than an availability-oriented request limiter provides.

Identity, rollout, and verification

Use an authenticated tenant or user identifier for that principal’s policy. A client-chosen tenant header must not mint fresh budgets. Only trust forwarded client IPs through the configured proxy chain. Coarse pre-authentication IP limits can protect authentication infrastructure, but shared NATs and changing addresses make them an imperfect identity for product fairness.

Bound state cardinality as well as traffic. Arbitrary URL paths, untrusted API keys, and random identifiers can turn the limiter into a memory-exhaustion target. Normalize routes, cap identity dimensions, expire safely, and keep raw identity values out of high-cardinality monitoring labels. The admission system needs its own protection.

Roll out a new policy in observation mode first when feasible. Advance a separate shadow bucket to model cumulative decisions without silently charging the live bucket. Then enable enforcement for a controlled slice and compare rejection reasons, tenant impact, and downstream saturation. Observation is useful evidence, but does not reproduce client retries caused by real rejection.

I would review these checks before calling the design ready:

  • Concurrent admissions cannot overspend one healthy authoritative bucket. Boundary bursts match the chosen algorithm’s contract.
  • Idle expiry does not grant an early refill. Eviction, failover, clock changes, and policy rollout have a documented effect on the guarantee.
  • Ambiguous timeouts, repeated request identifiers, and multiple applicable policies have explicit charging behavior.
  • Limiter latency, dependency errors, policy rejections, fallback admissions, active work, queue age, and state cardinality are observable separately.
  • Load tests include a hot tenant, a flood of distinct identities, synchronized retries, and recovery traffic. Fault tests exercise dependency loss and restart behavior.

No throughput number in a tutorial replaces those tests on the intended deployment. The pseudocode here explains the state transition; it has not been deployed or benchmarked.

A practical starting design

For this export API, I would start with a trusted per-tenant weighted token bucket, one short atomic decision on the owning Redis primary, and separate worker concurrency. I would accept the documented state-loss boundary only if the resource can tolerate it, choose an explicit dependency-failure policy, and keep durable product usage outside this transient admission state.

That design becomes more complex only when a real requirement demands it: exact rolling counts, tenant-plus-user accounting, regional budget allocation, durable purchased quotas, or a stronger failure guarantee. Each requirement changes the contract before it changes the infrastructure.

For related failure modes, see Deep Dive in Caching. For long-lived work, retries, and cancellation across a different resource boundary, see Resilient Large File Uploads with Signed URLs and ETags. More architecture articles are collected under Best Practices.

Reading note: Hello Interview’s distributed rate limiter guide informed the teaching progression from requirements to distributed trade-offs. The export scenario, prose, examples, cover, and diagrams here are original. Technical behavior is linked to primary sources alongside the relevant claims.

Share
Edit Template
Newsletter

Get new engineering deep dives

Scala, JVM, AI, and backend systems. I send practical articles when there is something worth reading.

Join the newsletter