Rate limiter

intermediateCommon atStripeAnthropicOpenAICloudflareGoogleRead firstRate limitingDistributed thinkingConcurrencyPractise in the Sandbox →

A rate limiter sits in front of an API and answers one question per request: has this key used up its allowance? Choosing the algorithm is the easy half; the concept page covers it. The design question is where the count lives. Many stateless gateways must share one count per key, so the standard answer is a token bucket held in a sharded in-memory store, updated by one atomic script per request: O(1) time and about 16 bytes per key, one extra round trip of latency, and a deliberate fail-open plan for when the store is down.

The problem

Every public API needs one. Without it, a single buggy retry loop, a scraper, or a customer’s batch job can take capacity from everyone else. Stripe, GitHub, and the OpenAI and Anthropic APIs all return 429 Too Many Requests when you exceed a quota.

A rate limiter has three jobs, and they pull in different directions:

Job	What it means	Pulls toward
Protect the backend	Total load never exceeds what the service can absorb	Strictness, global view
Fairness between tenants	One noisy customer can’t starve the rest	Per-key limits, tiers
Stay out of the way	The limiter adds microseconds, never becomes the outage	Local decisions, fail open

Most of the design is negotiating those three.

Requirements and scope

Pin these down before drawing anything. They decide the design, and interviewers leave them vague on purpose.

	In scope (typical)	Ask about
Functional	Limit requests per key (API key, user, IP) per route, with tiers (free 10/s, pro 100/s). Return 429 + Retry-After. Expose remaining quota in headers.	Is the key an account, a user, or an IP? Do some calls cost more than one unit (weighted)? Do rejected calls count?
Accuracy	Small overshoot (≈1-2%) is fine for API quotas.	Is any limit a hard one (billing, security, login attempts)? Those get a different, stricter path.
Scale	~200k req/s peak, millions of active keys, tens of gateway nodes.	Peak or average? One region or several?
Latency	Limiter adds < 1 ms at p99.	What’s the request’s total latency budget?
Availability	If the limiter breaks, the API must keep serving.	Fail open or fail closed, per rule?
Out of scope	DDoS at the network layer (that’s the CDN/edge), billing, abuse detection.

The clarifying question that changes the most

“Is this a hard limit or a protective one?” A protective limit (keep a noisy tenant from hurting others) tolerates overshoot and should fail open. A hard limit (at most 5 login attempts per minute, at most N paid units) must be exact and should fail closed. One system can support both, but they are different code paths.

Back of the envelope

Drag the assumptions. Two numbers drive the design: store operations per second, which sets how many shards you need, and bytes per key, which is why nobody runs a sliding log at this scale.

Back of the envelope

drag the assumptions

assumptions

peak requests per second200K/sactive limit keys (per hour)5Mstate per key (bytes)16 Brequests per window (for a log)1Kops/s one store shard sustains100K/sgateway → store RTT (ms)0.50 ms

so you need

store ops/s (one script call per request)200K/s

store shards needed (at 50% headroom)4

memory: token bucket / counter430 MB+≈70 B per key of store overhead (key name, TTL, entry)

memory: sliding log instead40.4 GBone 8-byte timestamp per allowed request

latency added per request0.55 msRTT + script time; this is on the hot path of every call

At 200k req/s and 5M active keys, counters fit in well under 1 GB, but the store must absorb one op per request, so it is sized by throughput, not memory. Push 'requests per window' up and watch the sliding-log row explode.

What to say out loud: “Memory is small, roughly keys × tens of bytes. The constraint is ops per second on the counter store and the round trip on every request. So I’ll shard the store by key and keep the per-request work to one atomic call.”

API and data model

The limiter is middleware, not a service anyone calls directly. Its contract is a single decision function and a rules table.

pseudocode: the contract

decide(key, route, cost = 1, now) -> Decision
    Decision = { allowed: bool, remaining: int, retry_after_s: number, reset_s: number }

Rule  = { match: (tier, route), rate_per_s, burst, mode: "protect" | "hard" }

State in the store, one entry per limit key:
    key     "rl:{account}:{route}"           -- who + what, chosen by the rule
    value   { tokens: float, updated_at: ms } -- the token bucket
    expiry  ~ burst / rate + slack           -- idle keys disappear on their own

Response headers (the IETF RateLimit header draft, and what most large APIs send):

HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 1

Two decisions hide in that sketch:

• The key’s granularity. account alone lets a cheap endpoint starve an expensive one. account + route gives each route its own budget. Many systems check several keys per request (per-route and per-account global), and the request must pass all of them.
• State has a TTL. Without one, every key that ever called you stays in memory forever. With a token bucket, a key that’s been idle longer than burst / rate is indistinguishable from a fresh one, so it’s safe to let it expire.

High-level design

Step through each flow. Watch which boxes light up on the hot path. The answer to “what does this cost?” is mostly “one extra round trip”.

Rate limiter: request paths

step through

flowAllowedRejected (429)Store is downRules change

The happy path adds one round trip to the counter store and nothing else.

A request arrives carrying an API key. The load balancer can send it to any gateway; there is no stickiness.

↺◀▶ Play▶1 / 6

The components:

Component	Role	Why it’s there
Gateway (×N)	Stateless. Builds the key, looks up the rule, asks the store, forwards or rejects.	Stateless nodes scale horizontally and can be replaced at any time.
Counter store	Holds bucket state, sharded by key hash, with a replica per shard.	One place to count, so N gateways enforce one limit. Sharding spreads the ops.
Rules config	Tiers and per-customer overrides, versioned.	Limits change without a deploy. Cached in every gateway’s memory.
Limit events	Async log of rejections and near-misses.	Dashboards, alerting, abuse detection. Never on the hot path.

Deep dive: which algorithm

The rate limiting concept page walks through every algorithm with a live simulator. For a distributed API limiter the choice usually comes down to this:

Algorithm	State per key	Fits a shared store?	Verdict here
Fixed window	1 int + window id	Yes: INCR + EXPIRE, trivial	Simple, but up to 2× overshoot at window edges
Sliding log	up to limit timestamps	Poorly: a sorted set per key, O(limit) memory	Exact; too big at 1,000s per window × millions of keys
Sliding window counter	2 ints	Yes	Good approximation (Cloudflare measured ~0.003% wrong decisions)
Token bucket	2 numbers	Yes, via a short script	Default: O(1), explicit burst, cheap Retry-After
GCRA	1 timestamp	Yes	Token bucket in a single number; same decisions

Token bucket wins because both product knobs, sustained rate and burst size, appear as parameters. Its refill is lazy, so idle keys cost nothing.

Deep dive: many gateways, one count

This is the heart of the interview. Each gateway sees only its slice of a key’s traffic. Run each strategy below, then change N, the traffic skew and the RTT.

Counting across gateways: where the limit leaks

simulator

reshuffle arrivals

gateway nodes N = 3arrivals / tick = 2limit L per 10 ticks = 10

Each gateway enforces the full limit on its own. Nothing is shared.

gateway 1

gateway 2

gateway 3

admitted per window

L = 10

window 1: 0 / 10over-admitted: 0wrongly rejected: 0store round trips / request: 0.0

allowedrejected / over limitthe limit

Each gateway allows up to L, so the client really gets up to N × L per window. With one node it's exact; add nodes and the bars climb past the line.

↺◀▶ Run▶t = 0 / 40

What the simulator shows:

Strategy	Over-admits?	Under-admits?	Cost per request
Local counter, full limit each	Yes, up to N×	No	0 RTT
Local counter, limit ÷ N each	No	Yes, when traffic is skewed	0 RTT
Central GET then SET	Yes: lost updates under concurrency	No	2 RTT + race
Central atomic script	No	No	1 RTT, hot key risk
Local + periodic sync	Bounded by sync interval	Slightly	≈0 RTT + background traffic

The usual production answer is central atomic for most limits. Add local + sync for very high-volume keys, or when a few percent of overshoot buys back the round trip; Stripe and others describe this hybrid.

Deep dive: the atomic check

The bug in “GET, then SET” is a check-then-act race (see Concurrency): two gateways read 99, both decide “under 100”, both write 100. The fix is to send the whole decision to the store so it runs as one indivisible step. In Redis that is a Lua script or a Redis Function. A single shard runs commands one at a time, so the script cannot interleave with another.

pseudocode: runs atomically on the shard that owns the key

on_store(key, rate, burst, cost, now):
    state  <- read key                       -- may be missing: treat as full bucket
    tokens <- min(burst, state.tokens + (now - state.updated_at) * rate)
    if tokens >= cost:
        tokens <- tokens - cost
        allowed <- true
    else:
        allowed <- false                     -- rejected calls take nothing
    write key = { tokens, updated_at: now }, expire after burst / rate
    retry_after <- allowed ? 0 : (cost - tokens) / rate
    return allowed, floor(tokens), retry_after

Details that come up:

• Whose clock is now? Gateway clocks drift. Use the store’s clock (TIME inside the script), or keep now monotonic per key, so one skewed gateway can’t hand out free tokens by reporting a future time.
• Rate and burst are arguments, so the store holds only state. A rules change takes effect on the next call with nothing to migrate.
• Multiple keys per request. If a request must pass both a per-route and a per-account limit, check them in one script on keys that hash to the same shard (Redis hash tags: rl:{acct_42}:route, rl:{acct_42}:global), so the check stays atomic.
• Integer arithmetic. Store milli-tokens and millisecond timestamps to avoid float drift.

Deep dive: hot keys, tiers and regions

Hot keys. One enormous customer means one key on one shard taking a large share of the load. Options, cheapest first:

1. Local pre-filter. Each gateway runs a small in-process bucket at about rate / N and rejects obvious excess before calling the store. The store sees only plausible traffic.
2. Batch tokens. A gateway takes 10 tokens at once and spends them locally. That cuts store calls 10× and allows a small, bounded overshoot. This is the “local + sync” strategy from the simulator.
3. Split the key. rl:acct_42:{0..7}, each with rate / 8, chosen at random per request. Load spreads over shards, and accuracy drops slightly at low volume.

Tiers and overrides. Resolve the rule in the gateway from an in-memory table (tier defaults, then per-customer overrides, then per-route). That’s a hash lookup, not a network call.

Multiple regions. A single global counter means a cross-region round trip, 50-150 ms, on every request, which is unacceptable. The standard answers:

• Give each region its own budget (limit × the region’s traffic share), or
• Enforce locally, and sync asynchronously across regions to correct drift. Accept that a client spraying requests across regions can briefly exceed the global limit.

Exact global limits across regions are rarely worth what they cost. Say so, and offer the regional-budget compromise.

Failure modes

What breaks	What you see	Design response
Store shard down / failing over	Timeouts on the hot path	Tight timeout (≈5 ms), circuit breaker, fail open to a local rate / N bucket; fail closed for hard rules
Store slow (p99 spike)	API latency rises with it	Timeout + breaker as above; alert on limiter latency separately
Hot key	One shard at 100% CPU	Local pre-filter, token batching, key splitting
Gateway clock skew	Some keys refill too fast	Use the store’s clock or per-key monotonic time
Rules config unreachable	New gateways can’t load rules	Ship a baked-in default rule set; keep serving the last known good version
Retry storms after 429	Rejections cause more traffic	Retry-After, client SDKs with exponential backoff + jitter; cheap rejection path
Memory growth	Store fills with dead keys	TTL on every key (≈ burst / rate)

What it costs

Operation	Time	Space
Decide one request (token bucket script)	O(1) on the store + 1 network RTT	O(1) per key, ≈16 B state + store overhead
Rule lookup in gateway	O(1) hash lookup, in memory	O(rules)
Sliding log alternative	O(log limit) per call (sorted set)	O(limit) per key
Total store memory	—	O(active keys); idle keys expire
Store throughput	one op per request, per limit checked	sharded: ≈ peak qps / ops-per-shard shards

In the interview

A good 45-minute arc:

1. Clarify (5 min). Key granularity, hard vs protective limits, scale, latency budget, single or multi region, fail open or closed.
2. Single node first (5 min). A token bucket per key in a hash map. State the O(1) cost and the TTL for idle keys. Link it to the concept so you can move fast.
3. Distribute it (15 min). Explain why local counters leak (N×) and why GET-then-SET races. Arrive at the sharded store with an atomic script, then the headers and 429.
4. Harden it (10 min). Store down → fail open with local fallback. Hot keys → pre-filter or batching. Rule changes without deploys.
5. Stretch (5-10 min). Multi-region budgets, weighted costs (e.g. an LLM API limiting tokens, not requests), concurrency limits alongside rate limits.

Follow-ups to expect: “Limit by tokens consumed, where the cost is only known after the response.” Reserve an estimate up front and settle the difference afterwards. “What if Redis adds too much latency?” Local batching. “How do you test it?” Inject a clock, run property tests on random traces, and run a load test that compares observed rate to the limit per key.

Check yourself

Check yourself

pick one

Ten stateless gateways each run an in-memory token bucket with the customer's full limit of 100 req/s. Traffic is spread round-robin. Roughly how much can the customer actually get?

A100 req/sBAbout 1,000 req/sCAbout 10 req/sDIt depends on the token bucket burst only

Check yourself

pick one

Your limiter does `count = GET key; if count < limit: SET key count+1`. Under load, customers exceed their limits. What's the fix that keeps exactness?

AAdd a mutex in each gatewayBMove the check and the increment into one atomic operation on the store (INCR or a script)CLower the TTL on the keyDRead from a replica to reduce load

Check yourself

pick one

The counter store's primary for a shard fails, and failover takes 20 seconds. The limit protects a backend from noisy tenants. What should gateways do during those 20 seconds?

AReject all requests for keys on that shard (fail closed)BWait for the store with a long timeoutCFail open with a coarse local limit (≈ rate / N per gateway) and alertDDisable the limiter globally until failover completes

Go deeper

• Stripe: Scaling your API with rate limiters: request-rate and concurrency limiters, load shedding, and the token bucket in Redis.
• Cloudflare: How we built rate limiting capable of scaling to millions of domains: the sliding window counter at the edge and its measured error.
• Redis docs: Scripting with Lua: why a script runs atomically, and the hash-tag rule for multi-key scripts in a cluster.
• IETF draft: RateLimit header fields for HTTP and RFC 6585 §4 (429).

Concept pages to drill: Rate limiting · Sliding window · Concurrency · Distributed thinking · Time handling · TTL and expiry

Related

Rate limiting (concept)Every algorithm, with a live simulator.

Distributed cacheThe same sharded in-memory store, as a product.

Load balancingWhy traffic for one key lands on every gateway.

Distributed thinkingPartitioning, replication and what fails.