Rate limiting

Rate limiting caps how much work one caller may ask of your system in a period of time: 50 requests a second per API key, 5 OTP texts per phone number per 15 minutes, a million LLM tokens a minute per project. A caller over the limit gets a fast, cheap refusal, usually HTTP 429 with a hint of when to come back, instead of a slow answer that hurts everyone else. This lesson covers the algorithms, which key to count, and where in the stack each limit belongs.

Picture it first: the passport office on a Monday

At a busy passport office, a token machine prints a slip every 12 seconds, five a minute, and keeps a stack of 20 ready for the morning rush. When the stack runs out, you come back later. That machine is a token bucket: a refill rate (5 a minute) and a burst (20).

Inside, a guard lets only 40 people into the hall at once, because it has 40 chairs: a concurrency limit. Each applicant may book 2 appointments a day: a quota. And when two of six counters break down, the manager stops taking walk-in enquiries so appointments still get through: load shedding, a decision based on the office’s health, not on who you are.

Map it back. Applicants are API clients, the token machine is the limiter in your API gateway, the chairs are threads, connections or GPU slots, and the daily cap is your customer’s plan. Every mechanism says no early and cheaply, before the expensive work is spent.

Why limit at all

Every limit protects something. Name it, because it decides the key, the number and what happens when the limiter fails.

• Capacity. One client’s runaway script should not slow everyone else. Stripe’s per-user limiter rejects millions of requests a month, many from runaway test scripts.
• Fairness between tenants. A sudden spike usually comes from one tenant. AWS enforces per-tenant quotas so only that tenant’s unplanned traffic is rejected.
• Cost. An OTP text, a paid maps API or an LLM’s tokens cost real money. A bot triggering 100 OTP texts a second at an illustrative ₹0.20 each costs 100 × 0.20 × 3,600 = ₹72,000 an hour.
• Abuse. Credential stuffing, OTP guessing and scraping are all “too many tries”. At 1,000 guesses a second, an attacker covers 600,000 of a 6-digit OTP’s 1,000,000 values in a 10-minute window: a 60% chance. Allow 5 attempts per OTP and it falls to 0.0005%.
• Pricing. Limits are often the product. GitHub’s REST API allows 60 requests an hour unauthenticated and 5,000 signed in; OpenAI’s tiers set requests and tokens per minute by spend.

The last three have nothing to do with overload: even an infinitely scalable backend needs a limit on OTP sends.

Rate limits and their neighbours

Interviewers check whether you can tell rate limiting from its cousins. They differ in the signal they read and whose fault a rejection is.

A rate limiter judges the caller; a load shedder judges the system. Stripe runs both: request and concurrency limiters per user, plus load shedders that reserve capacity for critical calls such as creating charges. “Throttling” is used loosely (AWS means rejecting, NGINX by default means delaying), so say which you mean. The system-wide side is in backpressure and load shedding and the circuit breaker.

The algorithms, run on one trace

Every algorithm answers “may this key make one more request now?”, but each remembers something different and so treats bursts differently. Feed them the same traffic. In Figure 1 each is set to 5 requests per second and sees 20 requests: a burst of 14 in 0.7 seconds that straddles the one-second mark, then a steady 4 a second. Rejected requests don’t count against the limit.

Fixed window

Keep one counter per key per window, such as rl:k_8f2a:10:01 for the minute starting at 10:01. Increment it on each request, reject above the limit, and let the key expire. That is one integer and one atomic increment.

The flaw is the edge. In the trace, five requests pass at 0.70–0.90 s and five more at 1.00–1.20 s, because the counter reset at 1.00: 10 requests in half a second, twice the limit. Worse, the honest requests at 1.62 s and 1.87 s are rejected because the burst spent the second window. A window straddling a boundary can carry up to 2× the limit, and everyone throttled waits for the same reset.

Use it when the window is a calendar promise: “1 million calls a month, resetting on the 1st” is easy to explain, and a boundary burst is tiny next to a month.

Sliding window log

Store the timestamp of every allowed request; on each new one, drop timestamps older than a window and count the rest. It is exact: no rolling second ever holds more than 5. In the trace it is the strictest row, rejecting ten in a row and reopening at 1.87 s only when the 0.70–0.90 s requests age out.

The cost is state: a limit of 1,000 a minute can mean 1,000 entries per key, read and trimmed on every check. Use it when limits are small and mistakes expensive: “5 OTP sends per phone per 15 minutes” is five timestamps.

Sliding window counter

Keep current and previous window counters, and estimate the rolling count assuming the previous window’s requests were spread evenly. At 1.20 s, the rolling second still overlaps 80% of the first window, which allowed 5, so the estimate is 5 × 0.8 + 0 = 4 and the request passes as the fifth. At 1.62 s the estimate is 5 × 0.38 + 1 = 2.9, so a steady request passes that the exact log rejected.

Cloudflare measured it on 400 million requests from 270,000 sources: 0.003% were wrongly allowed or limited, and the estimate was on average 6% off the true rate. Use it when you need per-minute limits across millions of keys: two integers per key.

Token bucket

Give each key a bucket of up to b tokens that refills at r per second. A request takes a token (several for an expensive call); an empty bucket means 429. No timer drips tokens in: store the count and last-update time, and add elapsed × r, capped at b, before each decision.

With r = 5 and b = 5 the bucket starts full. The first burst gets 6 through: 5 stored tokens plus 0.25 s × 5 = 1.25 refilled while it arrived. After that, a token drips in every 200 ms, so roughly one request in four passes (1.10 s and 1.30 s), and the steady 4-a-second tail all passes. Remember: over any t seconds a token bucket admits at most b + r × t requests, a burst you chose rather than an accident of a window edge.

It is the common default. Amazon API Gateway throttles with a token bucket whose knobs are rate and burst, by default 10,000 requests a second with a 5,000-request bucket per account per Region; Envoy’s local rate limit filter takes max_tokens, tokens_per_fill and fill_interval; Stripe keeps a token bucket per user in Redis. Use it when a per-second API limit must tolerate the dozen calls an app screen fires at once.

Leaky bucket: a meter or a queue

The name covers two different things, and mixing them up is a classic slip.

As a meter, the level rises by one per request and drains at r per second, and a request that would overflow capacity b is rejected. Turn it upside down and it is a token bucket: the empty space is the token count, and with the same rate and capacity the two make identical decisions.

As a queue, excess requests are held and released at exactly r per second, and arrivals are rejected only when the queue is full. Output is perfectly smooth; callers pay in waiting instead of errors. NGINX’s limit_req works like this: with burst=20, excess requests are delayed to the configured rate and fail only beyond the burst. Add nodelay and the allowance is spent immediately, turning it back into a meter. Its default rejection status is 503, so set limit_req_status 429.

Use the queue where waiting is fine and the downstream needs smoothness, such as workers feeding an SMS aggregator that accepts 100 messages a second. For interactive APIs prefer the meter: a quick “try again” beats a spinner.

GCRA

The generic cell rate algorithm, from ATM networks, is a leaky-bucket meter that stores one timestamp per key: the theoretical arrival time (TAT), when the client would be caught up had it sent at exactly the allowed rate. Each allowed request pushes TAT forward by the emission interval T = 1 ÷ r. A request is rejected if it would push TAT more than b × T ahead of now.

With 5 a second and a burst of 5, T is 200 ms and the allowance is 1,000 ms. Six requests at t = 0 push TAT to 200, 400, 600, 800 and 1,000 ms, and the sixth would make it 1,200 ms, 200 ms over, so it is rejected. That 200 ms is exactly its retry time: token-bucket behaviour from one number per key, with Retry-After for free. Brandur Leach’s walk-through describes it in production at Stripe. It needs one clock, so read the time from the shared store, not each server.

Choosing what to count

The algorithm decides how you count; the key decides whose count it is. A wrong key lets an abuser spread across many counters or lumps innocent users into one.

Per IP address is the only choice before you know the caller: login, signup, anonymous search. It has two traps (Figure 3). Carrier-grade NAT puts many phones behind one public IPv4 address, so 100 a minute shared by 500 phones leaves each 0.2; Cloudflare offers an “IP with NAT support” characteristic for this reason, which adds a cookie-based visitor ID. On IPv6 the opposite happens: a host chooses its own 64-bit interface ID, so it can rotate through 2^64 addresses inside one /64. Count IPv6 clients per /64 prefix, not per address.

Per user or API key is the default after authentication: fair, stable and tied to a contract. Per tenant caps a whole customer, so one organisation’s 200 users can’t crowd out another’s. Per endpoint reflects cost: GET /orders and POST /reports/export should not share a budget. Global limits protect a fixed resource, such as a partner’s total throughput.

Not every request costs one

Weighted limits charge each request what it costs. GitHub’s GraphQL API charges points by how many lookups a query needs (see REST vs GraphQL vs gRPC). LLM APIs count tokens as well as requests: OpenAI enforces requests and tokens per minute together, whichever runs out first. When the cost is known only afterwards (tokens generated, rows returned), charge an estimate up front and settle later, letting the balance go negative; AWS describes this for variable-cost APIs.

Stack limits in layers

Real policies put several limits on one request; it passes only if all agree:

• A burst limit plus a quota: 50 a second with bursts to 100, and 1 million a month.
• Two buckets: AWS pairs a low-rate, high-burst bucket with a high-rate, low-burst one, so a large burst can’t land in one instant.
• Rate plus concurrency: GitHub allows 5,000 REST requests an hour, but no more than 100 concurrent requests.

Check cheap, broad limits first.

Where to enforce: defence in depth

Each layer knows different things and pays a different price per check, so production systems enforce several limits, cheapest and coarsest first. Figure 4 maps the layers.

Client SDK. The cheapest request is the one never sent. An SDK that paces itself, reads the RateLimit headers and honours Retry-After saves both sides a round trip. Google’s SRE book describes adaptive throttling: each client counts requests and accepts over two minutes, and once requests exceed twice the accepts, rejects new ones locally with probability max(0, (requests − 2 × accepts) ÷ (requests + 1)). But an attacker skips your SDK, so this is never enforcement.

Edge: CDN and WAF. The first layer sees everything, floods included, and knows the IP, path, headers and perhaps a bot score, but usually not the account. It is the place for per-IP rules, such as 20 login attempts a minute, before your origin spends CPU on TLS and application code. Edge counters are usually per location: Cloudflare counts per data centre, which works because anycast keeps a client on one location (see content delivery network).

API gateway. After authentication the gateway knows the key, tenant, plan and route, and a rejection costs no backend work. Per-key buckets and plan quotas live here, with counters in a shared store so 50 gateway pods agree. See API gateway.

Inside the service. Only the service knows what a request really costs and which object it touches: a phone number for OTPs, a merchant for payouts. Cost-weighted, per-object and concurrency limits belong here.

Outbound. Your partners rate-limit you: an SMS aggregator may accept 100 messages a second on your account. Put a limiter on your side, usually a leaky-bucket queue shared by all workers, so you smooth to their rate instead of discovering it through their 429s. This is daily life in a notification system.

The database. A connection pool is a concurrency limit: with 50 connections, the 51st query waits or times out. Size it from what the database can take, not from how many app servers you run (connection pooling).

Local or shared counters

Within one layer, the counter lives in each server’s memory or in a shared store. Local costs nothing per check and survives any outage, but with N servers behind a round-robin balancer a client can get up to N times its limit; NGINX’s zone and Envoy’s local filter are local. Shared, typically Redis, gives one count at the price of a sub-millisecond hop and a hot-path dependency. Large systems do both: a generous local bucket to absorb floods, then a precise shared check.

Race-free shared counts, hot keys and cross-region limits are the heart of the rate limiter design problem; see its deep dives on counting across servers, hot keys and regions.

Telling the client: 429, Retry-After and RateLimit headers

429 or 503? RFC 6585 defines 429 Too Many Requests for a user who “has sent too many requests in a given amount of time”: the client is over its budget. 503 Service Unavailable, in RFC 9110, means the server is temporarily overloaded or in maintenance, whoever is asking. So per-caller limits return 429 and load shedding returns 503. AWS draws the same line.

Retry-After gives the wait as an HTTP date or whole seconds; round up, so a token due in 200 ms becomes Retry-After: 1.

The RateLimit headers. The IETF HTTP APIs working group’s draft (revision -11, May 2026) defines two fields. RateLimit-Policy describes each quota: q units per w seconds, optionally with a unit qu and a partition key pk. RateLimit reports the live state: r units remaining within the next t seconds. Many APIs still send the older, unstandardised X-RateLimit-Limit, -Remaining and -Reset trio.

HTTP/1.1 200 OK
RateLimit-Policy: "per-key";q=50;w=1, "monthly";q=1000000;w=2592000
RateLimit: "per-key";r=4;t=1, "monthly";r=812400;t=1209600

The client may send 4 more requests this second, and has 812,400 of its monthly million left with 14 days (1,209,600 s) to go. Four rules keep the contract honest:

• Never cache a 429. RFC 6585 says caches must not store it, and the draft says to ignore RateLimit values on cached responses.
• Retry-After wins if both appear, says the draft.
• Don’t leak capacity to untrusted callers: for login and OTP endpoints, send a bare 429.
• Name the limit that tripped. The draft registers a quota-exceeded problem type whose violated-policies list tells the client which policy said no.

What a good client does

• Pace before the wall: r=4;t=1 means spread four requests over the second.
• Honour Retry-After; otherwise back off exponentially with full jitter: wait a random time between 0 and min(cap, base × 2^attempt), and cap attempts. Without jitter, everyone throttled at 10:00:00 returns at 10:00:01. More in timeouts, retries and backoff with jitter.
• Budget retries. AWS SDKs have used a token bucket for retries since 2016: retry freely while tokens last, then slowly.
• Make retries safe with an idempotency key, so a retried payment never charges twice.

Going deeper: concurrency limits and Little’s law

A rate limit counts arrivals, not how long each request holds a thread. Little’s law links the two: requests in flight L = arrival rate λ × time in the system W. At 1,000 requests a second and 50 ms each, 50 are in flight. If the database slows to 500 ms, the same 1,000 a second need 1,000 × 0.5 = 500 in flight. A server with 200 worker threads can finish at most 200 ÷ 0.5 s = 400 a second, so its queue grows by 600 every second until requests time out. A 1,200-a-second rate limit never fires: arrivals never changed.

A concurrency limit reads the right signal. Cap in-flight requests at 100 and, during the slowdown, the server completes 100 ÷ 0.5 s = 200 requests a second and rejects the other 800 in well under a millisecond, instead of letting every request wait in a growing queue. Stripe added a concurrent-requests limiter (“only 20 API requests in progress at the same time”) for its CPU-heavy endpoints; it fired 12,000 times in a month, against millions for its rate limiter, and ended the contention.

The hard part is the number, which shifts with every deploy and slow dependency. Netflix’s concurrency-limits library borrows from TCP congestion control: gradient = RTT_noload ÷ RTT_actual, and newLimit = currentLimit × gradient + queueSize, where the queue allowance defaults to the square root of the limit. Rising latency pushes the gradient below 1 and the limit shrinks. Callers can use AIMD instead: grow by one while calls succeed, cut sharply on timeouts and rejections.

Going deeper: fairness, retry storms and rollout

Fairness between tenants

Hard per-tenant limits waste capacity: give three tenants a third each, and one can’t use the others’ idle share. AWS prefers letting a tenant burst into unused capacity and taking it back when others need it; Google sets per-customer quotas in CPU seconds that deliberately add up to more than the service has. Weighted fair queueing gives each tenant its own queue, so a flood lengthens only that tenant’s queue. Details are in noisy neighbours and fairness.

Limits and retries: the 429 storm

A limiter can create the spike it was meant to stop. If every 429 says Retry-After: 1, a thousand clients return in the same second. Retries also multiply through layers: in AWS’s example, five layers that each make 3 attempts turn one failing query into 3^5 = 243. The fixes: client jitter, slightly randomised Retry-After values, continuously refilling buckets instead of windows that reset together, and retries at one layer only. See retry storm.

Fail open or fail closed

When the counter store is slow or down, each rule must already know what to do. Fail open (allow and alert) for ordinary API limits, because minutes without limits beat an outage; Stripe catches limiter errors at every level for this reason. Fail closed where the limit guards money or security, such as OTP sends and logins. Timeouts, circuit breakers and local fallback buckets are worked through in what happens when Redis is slow or down.

Shadow mode first

A limit set too tight is an outage you cause yourself. Run it in shadow mode first: evaluate, log “would have rejected” with the key, and allow everything. Stripe dark-launches each limiter this way. NGINX has limit_req_dry_run, and Envoy separates a filter_enabled percentage (check and record) from filter_enforced (actually reject). Versioned rule rollout is covered in the rate limiter design.

Cheat sheet

How to say it in the interview

“First I’d ask what the limit protects, because that picks the key and the failure mode. For a public API, I’d key on the API key after authentication, and on the IP, grouped by /64 for IPv6, before that. The algorithm is a token bucket, say 50 a second with bursts to 100: it absorbs an app screen’s burst and holds the long-run rate. Monthly quotas are calendar windows. I’d enforce in layers: per-IP rules at the CDN, per-key buckets at the gateway with counters in Redis, cost and concurrency limits in services, and an outbound limiter for partners like the SMS gateway. Over the limit is a 429 with Retry-After, never cached. New limits launch in shadow mode; if Redis is down, ordinary limits fail open while OTP and login fail closed.”

Why a token bucket rather than a fixed window? A fixed window can admit twice the limit across a boundary and makes throttled clients return together at the reset. A token bucket admits at most b + r × t in any t seconds, a burst you chose, and refills continuously.

How do you count across 50 gateway pods? Not in pod memory, or a client can get up to 50 times its limit. Keep counters in Redis, update them atomically in one script per check, and put a coarse local bucket in front. The rate limiter design works through the race and hot keys.

What happens if Redis goes down? Each rule decides in advance: fail open and alert for ordinary limits, fail closed for OTP and login, or fall back to a local bucket at the limit divided by the pod count. A few-millisecond timeout and a circuit breaker keep a sick Redis from slowing the API.

When do you return 429, and when 503? 429 when this caller is over its budget, 503 when the server is overloaded for everyone. Both can carry Retry-After.

What if requests vary wildly in cost? Charge by cost (points, tokens or bytes), estimating up front and settling afterwards, and add a concurrency limit for the resources a request count never sees.

Where to go next

• Design a rate limiter: the distributed version end to end: atomic Redis scripts, hot keys, regions.
• API gateway: the usual enforcement point.
• Backpressure and load shedding: the system-wide sibling of per-caller limits.
• Timeouts, retries and backoff with jitter: how clients should react to a 429.
• Noisy neighbours and fairness: sharing scarce capacity between tenants.
• Redis: the counter store behind most shared limiters.
• Metering and usage-based billing: counts exact enough to invoice.
• HTTP and HTTPS: the status codes and headers this contract relies on.

References and further reading

1. RFC 6585, Section 4: 429 Too Many Requestsrfc-editor.orgDefines 429 for a user who sent too many requests, the optional Retry-After, and that 429 responses must not be stored by a cache.
2. RFC 9110: HTTP Semantics (Retry-After and 503)rfc-editor.orgRetry-After as an HTTP date or whole seconds, and 503 as temporary server overload or maintenance.
3. RateLimit header fields for HTTP (draft-ietf-httpapi-ratelimit-headers-11)datatracker.ietf.orgRateLimit-Policy (q, qu, w, pk) and RateLimit (r, t, pk), Retry-After precedence, caching and information-disclosure rules, and the quota-exceeded problem type.
4. Scaling your API with rate limiters (Stripe)stripe.comRate limiters versus load shedders, the concurrent-requests limiter, token buckets in Redis, failing open and dark-launching new limits.
5. How we built rate limiting capable of scaling to millions of domains (Cloudflare)blog.cloudflare.comFixed window, sliding log and leaky bucket compared; the sliding window counter and its measured error on 400 million requests; per-PoP counting under anycast.
6. NGINX ngx_http_limit_req_modulenginx.orgA leaky bucket that delays excess requests up to burst, nodelay, the 503 default status, dry-run mode and per-key shared-memory state.
7. Throttle requests to your REST APIs (Amazon API Gateway)docs.aws.amazon.comToken-bucket throttling with a rate and a burst, best-effort targets, and the order in which per-client, per-method and account limits apply.
8. Fairness in multi-tenant systems (Amazon Builders’ Library)aws.amazon.comPer-tenant quotas, 429 versus 503, bursting into unused capacity, composed token buckets, charging true cost after the fact, layered admission control and evaluation mode.
9. Handling Overload (Site Reliability Engineering, Google)sre.googlePer-customer quotas in CPU seconds that are deliberately oversubscribed, and adaptive client-side throttling from requests and accepts.
10. Performance Under Load: adaptive concurrency limits at Netflixnetflixtechblog.medium.comLittle’s law, why fixed RPS limits go stale, and the gradient algorithm that finds a concurrency limit from latency.