System Design Interview: Design a Distributed Rate Limiter

A rate limiter looks simple until an application runs on several servers. If each server permits 100 requests per minute, a client reaching ten servers could receive ten separate allowances. Adding capacity has accidentally changed the product's usage policy.

The difficult questions appear when requests arrive together, a dependency becomes unavailable or one customer sends more traffic than a storage node can handle. Counting requests is only part of the design. The service must make a fast decision and explain what that decision means under failure.

Introduction

A distributed rate limiter controls admission across multiple application instances. It can protect shared infrastructure, prevent one customer from dominating capacity and enforce an API usage policy. These objectives overlap, but they do not always require identical guarantees.

A traffic protection mechanism might tolerate a small temporary overshoot while preserving availability. A monthly paid allowance may need a durable usage ledger and a carefully defined reservation process. Treating both as the same counter hides an important correctness boundary.

For this design, imagine a reporting API used by several organisations. Each organisation can start ten units of report generation per second, with a burst capacity of twenty units. These are illustrative requirements, chosen to make the calculations understandable. A cheap report costs one unit; an expensive report may cost several.

We will begin with a single region and several gateways, then consider regional expansion. The aim is a design whose normal operation, scaling limits and failure behaviour can all be explained in an interview.

Define the Policy Before Choosing Storage

Decide which identity owns the allowance

An organisation may have several users and API keys. If the product sells a shared organisation allowance, every key belonging to that organisation must consume the same budget. Limiting each key independently would let a customer increase its allowance by creating more credentials.

Derive the organisation identifier from trusted authentication context. A key might be organisation:42:report-generation. Do not accept a caller-supplied organisation header as proof of identity, and do not include raw API secrets in cache keys or logs.

Anonymous traffic needs different controls. An Internet Protocol address provides a coarse abuse signal, but offices, schools and mobile networks often share addresses. A strict per-address limit can block unrelated people, while an attacker with many addresses can evade it. Combine it with endpoint protection and authenticated identity when available.

Separate fairness, capacity and contractual quotas

The organisation bucket provides fairness between customers. It does not prove the database can handle total admitted load. If 10,000 organisations each use their allowance simultaneously, the service can still become overloaded.

Add an endpoint or system capacity control where necessary. For report generation, also bound active jobs. Ten admitted requests per second creates approximately 600 active operations if each lasts a minute and the system reaches a steady state. The relationship depends on queueing and workload, but illustrates why rate and concurrency are different dimensions.

A daily or monthly allowance is another policy. It may count completed work, admitted work or successful results. State which event consumes it. Do not assume a rapidly expiring Redis entry can double as an auditable billing record.

Specify the observable behaviour

Write down whether rejected requests consume tokens, whether abandoned requests receive a refund and whether retries count as new attempts. In this example, a confirmed rate rejection does not consume tokens. An admitted attempt does, even if the downstream application later fails.

That decision is deliberately simple for traffic protection. Refunding every failed request can create a loop in which expensive failing operations consume unlimited server work. If refunds are required, give admissions identities and make refunds idempotent so repeated cleanup cannot manufacture tokens.

Also define configuration changes. Reducing capacity from twenty to five should clamp the current balance to five. Raising capacity need not immediately fill the added space. Product requirements should choose the transition instead of leaving it to a deployment accident.

Estimate the Work the Limiter Must Handle

Suppose the API receives a hypothetical peak of 50,000 admission checks per second across all organisations. If every request consults shared state, the limiter must sustain at least that many operations, including rejected traffic. An abusive client can therefore overload the limiter even when the application behind it is protected.

Model the distribution as well as the total. Fifty thousand requests spread over 20,000 organisations differs substantially from 40,000 requests targeting one organisation key. The latter can saturate one partition while the rest are mostly idle.

Memory depends mainly on active identities and retention. A bucket contains a balance, timestamp and perhaps a policy version, but keys, object representation and database bookkeeping add overhead. Measure a representative dataset rather than multiplying a theoretical sixteen-byte record by the number of customers.

Allocate a decision latency budget within the API's total latency budget. An illustrative target might be a few milliseconds for most regional checks, with a strict timeout below the API deadline. Measure under load, failover and connection pressure; an average from an idle laptop says little about these conditions.

Compare the Main Algorithms

Fixed windows

A fixed window keeps a counter for a named period, such as the minute beginning at 12:30. Admission increments the counter while it is below the allowance. Implementation and reporting are straightforward, especially if the product promises a calendar-period quota.

The boundary is its main weakness for burst protection. A customer could send its full allowance at 12:30:59.9 and another full allowance at 12:31:00.1. Both windows comply, yet the backend sees nearly twice the allowance in a fraction of a second.

Expiration also requires care. Creating a counter and setting its expiry independently can leave a permanent counter if the process stops between them. The counter update and initial expiry need an atomic implementation, with the remaining window length determining retention.

Sliding windows

An exact sliding log records accepted request times and counts entries within the preceding interval. For an allowance of 100 per minute, it considers the sixty seconds immediately before each decision. This removes the fixed boundary jump, but storage and cleanup grow with accepted traffic.

A sliding counter estimates usage using adjacent windows. Halfway through the current minute, it can combine the current count with half the preceding minute's count. The estimate assumes older traffic was reasonably distributed, so it is an approximation rather than an exact rolling history.

Choose an exact log only when that precision justifies its cost. A policy expressed as an exact rolling window should not silently become a weighted estimate merely because that version is cheaper.

Token buckets

A token bucket has a maximum capacity and refill rate. An idle bucket fills only to its capacity; it cannot accumulate a month's unused permission and spend it in one burst. Each admitted operation spends a specified number of tokens.

Our bucket holds twenty units and replenishes at ten units per second. It permits twenty one-unit operations immediately after sufficient idle time, then sustains roughly ten units per second. During a period of length T, admitted cost is bounded by starting tokens plus tokens earned during that period, assuming authoritative state is retained.

That final condition matters. Resetting the bucket after a cache eviction grants a fresh burst. The mathematical bound does not survive arbitrary state loss automatically.

Leaky buckets and queues

A leaky bucket often describes a mechanism that smooths output at a fixed rate. Depending on the implementation, excess work is queued or rejected when the permitted backlog is full. That can suit jobs, but queueing changes the user's experience from immediate admission to waiting.

For an interactive API, an unlimited queue is dangerous. Requests can exceed deadlines while retaining memory and connections. For our API, reject when the admission budget is unavailable, then place accepted asynchronous jobs into a separate bounded work queue.

Build the High-Level Architecture

The request path is client, edge protection, gateway authentication, policy lookup, limiter decision and application processing. Rejected requests stop before report generation. Policy lookup uses a locally cached configuration snapshot; decisions use shared mutable bucket state.

Separate these kinds of data. Policies change relatively infrequently and can be distributed asynchronously. Bucket balances change with every admitted request and need coordinated updates. Loading a customer's subscription record from the main relational database on every check would add latency and another dependency to the critical path.

Gateway integration

Put the authoritative check in a shared gateway component or middleware used consistently by every entry point. Internal routes, batch APIs and alternative hostnames must not bypass protection for the same expensive operation.

The application can perform another check closer to the constrained resource, such as acquiring a report-worker permit. This protects against jobs whose cost differs from the gateway's estimate. The checks serve distinct purposes and should produce distinct metrics.

Avoid accidental double charging when a request passes through two gateways. Decide which component owns the organisation admission decision. If repeated checks are necessary, carry a trusted admission identifier and use an explicit deduplication protocol.

Policy distribution

A policy record can contain scope, capacity, refill rate, operation costs, failure mode and version. Validate it before distribution. Negative refill rates, zero capacity for enabled endpoints and request costs exceeding capacity should not reach the hot path unexpectedly.

Gateways retain the last known valid policy if the configuration service briefly fails. Record which version each instance uses and measure propagation delay. Support teams cannot explain inconsistent throttling if half the gateways apply yesterday's allowance without visibility.

For urgent suspension, a separate fast revocation path may be needed. An eventually refreshed policy cache should not be assumed to provide immediate access revocation.

Make Each Decision Atomic

The stored state can be represented as:

key: organisation:42:report-generation
tokens: 7.5
lastRefill: server timestamp
policyVersion: 3

For capacity C, refill rate R, balance B and elapsed time E, calculate available tokens as min(C, B + R * E). Admit when the balance is at least the request cost, then subtract the cost. Save the updated balance and timestamp together.

The entire read, refill, comparison and deduction must be indivisible relative to another decision for that bucket. Otherwise, two requests can read the final token and both proceed. A transaction in application memory does not coordinate gateway instances.

A short Redis script is one implementation option. Redis documents that scripts execute atomically and block other server activity while running, which is why a decision should involve a fixed, small amount of work. Validate inputs before writes and handle script deployment or reload after failover. Redis scripting documentation.

This pseudocode illustrates the decision rather than a complete Redis implementation:

atomically for this bucket:
    state = load bucket, or initialise full
    effectiveNow = max(authoritativeNow, state.lastRefill)
    elapsed = effectiveNow - state.lastRefill
    available = min(capacity, state.tokens + elapsed * rate)

    allowed = available >= cost
    remaining = available - cost if allowed else available
    retryDelay = 0 if allowed else (cost - available) / rate

    save remaining and effectiveNow
    retain state until it would certainly be full if idle
    return allowed, remaining, retryDelay, policyVersion

Handle disabled policies, zero refill rates and requests that can never fit within capacity explicitly. They should not produce division by zero or an endlessly repeated retry suggestion.

Work through simultaneous requests

Suppose a bucket contains two tokens at time zero. Three one-unit requests arrive together. The first atomic decision leaves one token, the second leaves zero and the third is rejected. Their arrival order may be arbitrary, but they cannot all consume the same balance.

After 150 milliseconds, the bucket has earned 1.5 tokens. A one-unit request leaves 0.5 tokens. A two-unit request would need another 1.5 units, corresponding to 150 milliseconds at the configured rate, assuming no other request spends tokens first.

That assumption is why retry guidance is an estimate, not a reservation. A client waiting for the advertised interval competes with other users in its organisation. Sleeping until a particular time does not guarantee admission.

Treat time and retention as correctness inputs

Use one consistent time source for a bucket, usually the authority processing its state. Gateway clocks can disagree and make refill depend on which gateway handled a request. Clamp negative elapsed time and avoid moving the stored timestamp backwards.

A forward wall-clock jump can grant a premature refill. Capping at capacity limits that individual grant, but repeated clock problems remain harmful. Monitor clock health and state the tolerated timing error. A process-local monotonic clock is useful locally, but is not automatically comparable across machines or restarts.

Expire idle entries only after enough time has passed for their balance to replenish fully. With capacity twenty and a rate of ten, an empty bucket requires two seconds. Retention should also account for timestamp anomalies and operational margin. Expiring after half a second would repeatedly grant fresh bursts.

Design Useful Responses and Client Behaviour

A confirmed exhausted allowance returns HTTP 429 Too Many Requests. Include a short explanation identifying the applicable public policy and, when meaningful, Retry-After. RFC 6585 defines this status and allows the retry header; it does not prescribe a counting algorithm. HTTP 429 specification.

For example:

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

{
  "code": "report_rate_limit_exceeded",
  "message": "The organisation report allowance is temporarily exhausted.",
  "policy": "report-generation"
}

Integer seconds cannot express a tenth of a second, so round upwards. A separately documented response field can expose finer guidance if useful. Avoid exposing another tenant's identity or sensitive internal capacity information in rejection details.

Clients should apply bounded backoff with random variation, honour meaningful retry guidance and stop when their own deadline expires. A thousand clients retrying at precisely the same boundary can create another burst even when each follows the nominal delay.

Explain how idempotency interacts with application retries. A caller retrying report creation after a timeout should use the same logical request identifier to avoid duplicate jobs. That guarantee is separate from whether the second admission attempt consumes another rate token.

Decide What Happens During Failure

Shared-state unavailability

If the state service times out, the gateway does not know whether allowance exists. It can fail open, fail closed or enter a constrained fallback. Choose per endpoint and describe the resulting risk.

A public read endpoint may continue under a conservative local limit. New expensive report jobs may be temporarily declined. Return an infrastructure availability response, such as an appropriate 503, when admission cannot be evaluated, instead of claiming the customer's quota is definitely exhausted.

Local fallback introduces an aggregate bound that depends on gateway count. If each of fifty instances grants two fallback requests per second, the fleet can grant one hundred. Autoscaling changes that figure. A conservative fallback needs assessment against the full fleet, including recovery overlap.

Ambiguous timeouts and lost state

A timeout after the store deducted a token leaves the gateway uncertain whether the operation happened. Retrying the deduction can charge twice. Proceeding without knowing the result can admit work without confirmed permission. For traffic protection, conservative extra charging may be acceptable; strict quotas need request identities and durable deduplication.

Store failover may lose recent state according to replication and durability configuration. Restarting a bucket full can temporarily increase admitted traffic. An eviction policy that discards active buckets also changes the effective limit. Monitor these events and reserve capacity for them rather than presenting the limiter as perfectly exact under all failures.

Recovery should be gradual. When shared state returns, many gateways may reconnect and clients may retry together. Limit reconnect pressure, restore authoritative decisions and observe the transition before removing fallback protection.

Choose storage settings for admission state

Redis uses asynchronous replication by default. Its documentation also explains that waiting for replica acknowledgements does not turn the deployment into a strongly consistent system or eliminate every failover loss. Configure durability according to the admitted overshoot budget and measure the resulting latency. Redis replication.

Admission state deserves a deliberate memory policy. Redis supports policies that evict keys under memory pressure and a no-eviction policy that instead rejects relevant writes when memory is exhausted. Neither outcome is free for this application: eviction can grant fresh allowance, while rejected writes activate the limiter's failure path. Redis eviction policies.

A practical starting point is to isolate limiter state from a general content cache. A surge in cached image metadata should not unexpectedly erase active customer buckets. Reserve memory headroom, monitor write failures and verify that idle-bucket expiry actually removes inactive identities.

Document the recovery starting balance as well. Initialising every missing bucket full preserves the normal burst policy but grants another burst after data loss. Starting recovered buckets empty is conservative but temporarily rejects legitimate users. Distinguishing ordinary new identities from a known recovery event can support a controlled policy, provided that distinction is itself reliable.

Scale Across Customers and Regions

Partitioning and hot identities

Partition by organisation so unrelated buckets can reside on different state nodes. Keep data needed for one atomic decision together. If a request must consume both an organisation allowance and a global allowance, cross-partition coordination becomes a new problem.

One option is sequential checks with documented conservative charging when a later check rejects. Another is co-locating related budgets and updating them atomically. Neither creates free global coordination: a genuinely global key can become a bottleneck regardless of how well customer keys are distributed.

A very busy organisation remains a hot key. Short local rejection caching may reduce repeated checks when admission is unavailable, at the cost of occasionally rejecting a request that could now succeed. Keep that interval bounded and invalidate it when the relevant policy changes.

Leasing token batches

Gateways can obtain small token batches from an authority and spend them locally. This reduces shared-store operations but strands capacity at quiet gateways. A busy gateway can reject while another holds unused tokens belonging to the same organisation.

Specify whether these are irrevocable grants for a period or leases that expire. If an authority reclaims unused tokens while a disconnected gateway continues spending them, the same allowance is issued twice. Local enforcement of expiry, ownership and recovery is essential.

The maximum outstanding allocation helps describe uncertainty. With ten gateways each holding up to five unreported units, as many as fifty units may be outside the authority's immediate view. Whether that represents overshoot, reserved allowance or temporary underutilisation depends on the allocation protocol.

Regional budgets

Independent full buckets in three regions triple the possible global allowance. To preserve a global target without a round trip for every decision, divide capacity and refill rate into regional budgets whose totals match the policy.

The trade-off is utilisation. A quiet region cannot automatically lend spare capacity to a busy one. A control plane can rebalance budgets, but must avoid activating the new allocation before the old allocation stops being usable.

Alternatively, route each organisation to a home authority or coordinate every decision globally. That simplifies the single-budget interpretation while adding network latency and regional dependency. Connect the choice to the acceptable overshoot and availability requirements established at the start.

Secure the Limiter and Its Configuration

A limiter becomes part of the service's trust boundary. An attacker who can modify policy configuration can remove protection or deny service to legitimate customers. Restrict administrative changes, keep an audit history and validate the scope of each update before distributing it.

Protect the state service from direct client access. Only authorised application components should submit decisions, and those components should use the smallest practical set of commands. A public client must not be able to reset its bucket, choose its own request cost or invoke arbitrary scripts.

Also bound the number and size of keys a request can create. Untrusted free-form route values can turn a request limiter into a memory exhaustion mechanism. Use stable operation categories and validated identity formats rather than embedding an entire URL or query string.

Rate limiting complements other controls. It does not replace authentication, authorisation or protection against a flood that saturates the network before requests reach the gateway. Each layer should defend a resource it can actually observe and control.

Observe and Test the Actual Guarantees

Measure decision latency, allowed and rejected cost, state errors, ambiguous timeouts, fallback activations and policy versions. Distinguish a healthy rejection protecting the service from an infrastructure failure preventing valid customers from working.

Avoid putting every organisation identifier into unbounded metric labels. Aggregate by endpoint and policy tier, then use sampled traces or targeted diagnostics for particular customers. Support logs should preserve useful identifiers without storing credentials.

Test empty and full buckets, weighted costs, repeated rejections, simultaneous final-token requests and long idle periods. Test policy changes while traffic is active. Express expected results as admitted cost and allowed error, not merely a count of successful HTTP responses.

Run failure scenarios with a slow state service, a dropped response after successful deduction, a restarted gateway and state failover. Check that deadlines remain bounded and the downstream job queue stays within safe capacity during fallback.

Roll out new policies in observation mode when possible. Compare proposed rejections with actual workload, then enforce for a limited population. This reveals legitimate client bursts and inaccurate operation costs before every customer is affected.

Further Improvements

Once the basic design is measured, operation cost can become more precise. A report scanning a month of data may cost more than one scanning an hour. Use a small set of understandable cost classes before introducing a complex estimator whose mistakes are difficult to explain.

Fairness within an organisation may also matter. A single API key can otherwise consume the shared budget and block all colleagues. Nested per-key limits can reduce that effect, provided their relationship to the organisation budget and partial charging is documented.

For interactive clients, exposing recent usage can reduce unnecessary retries. Such usage is observational: concurrent requests can change the balance immediately. Keep the admission decision authoritative, and avoid encouraging clients to treat a displayed remaining balance as a reservation.

These improvements should follow an observed problem. A centrally coordinated bucket with clear fallback behaviour is easier to operate than a collection of local and regional optimisations introduced before their error bounds are understood.

Summary

A distributed rate limiter starts with a precise policy: who owns the allowance, what consumes it and which errors are tolerable. Token buckets provide controlled bursts, while windows and concurrency controls solve related but different problems.

The implementation needs an atomic decision around shared state, sensible time handling and retention that does not reset partially depleted buckets. Useful rejection responses help clients recover without creating new traffic spikes.

Scaling and failure introduce the hardest trade-offs. Local fallback, token batches and regional budgets change where permission is held and how much uncertainty exists. Make those limits explicit, protect the constrained backend independently and test the failure paths that determine whether the design remains dependable.