Rate limiting for APIs: picking an algorithm, where to keep state and how to reject Intermediate

The problem

A search API can handle about 1,000 requests/second. One customer runs a data sync script that fires 3,000 requests/second for 5 minutes. The database saturates and p99 latency for every other customer shoots up.

Rate limiting answers three separate questions:

1. How to count? The algorithm decides which bursts get through.
2. Where to count? In each instance’s RAM or in a shared store such as Redis.
3. How to reject? Status code, headers and body so the client knows when to try again.

Getting one right and the other two wrong still fails: a correct algorithm where every Pod counts on its own multiplies the effective limit by the number of Pods.

Quick pick

Algorithm	Memory per key	Burst	Accuracy	Complexity
Fixed window	1 counter + window id	Up to 2× limit around a window boundary	Poor at boundaries	Very low (INCR + EXPIRE)
Sliding window log	1 timestamp per request in the window, O(limit)	Never exceeds the limit in any sliding window	Exact	Medium; RAM-heavy for large limits
Sliding window counter	2 counters (current and previous window)	Roughly the limit	Approximate, assumes evenly spread requests	Low
Token bucket	2 numbers: remaining tokens + last update time	Allows bursts up to capacity, then enforces the refill rate	Exact per the model	Low
Leaky bucket	A queue or 1 timestamp	Smooths: steady output, bursts are queued or rejected	Exact per the model	Low to medium (with a queue)

Default for public APIs: token bucket (or GCRA, a variant that stores a single timestamp). It allows clients reasonable bursts, caps the long-term rate, and needs only two numbers per key.

Five algorithms

Fixed window: cheap but leaky at the boundary

Split time into fixed slots (for example every minute), count requests in the slot, reject above the limit. When a new slot starts, the counter resets to 0.

The boundary hole with a limit of 100 requests/minute:

Time	Requests	Window	Result
00:59.5	100	minute 0 (count 0 → 100)	all allowed
01:00.0	100	minute 1 (count restarts at 0)	all allowed

Result: 200 requests within about 0.5 seconds, twice the per-minute limit, without breaking any rule of the algorithm.

Sliding window log: exact but RAM-hungry

Store the timestamp of each request (usually in a sorted set). On each new request: remove timestamps older than now - window, count the rest, compare to the limit.

Perfectly accurate, but a limit of 10,000 requests/hour means up to 10,000 elements for each key. Good for small, sensitive limits (login, sending OTPs), not for large quotas.

Sliding window counter: a cheap approximation

Keep counters for the current and previous window and estimate by the fraction of time elapsed:

rate ≈ previous_count × (window − elapsed) / window + current_count

Cloudflare’s example with a limit of 50/minute: 42 requests in the previous minute, 15 seconds into this minute with 18 requests → 42 × 45/60 + 18 = 49.5. The next request will be blocked.

It assumes the previous minute’s requests were evenly spread, so it is an approximation. Cloudflare reported over 400 million requests: about 0.003% of requests were wrongly allowed or blocked.

Token bucket: controlled bursts

The bucket holds at most capacity tokens and is refilled evenly at rate tokens/second. Each request takes 1 token (or more if the request is expensive); when tokens run out, reject.

No timer is needed to refill tokens: when handling a request, compute tokens = min(capacity, tokens + elapsed × rate). The two parameters separate two questions: maximum burst (capacity) and long-term rate (rate).

Token bucket with capacity 10, refill 10/second blocks the second burst

Enlarge diagram

Token bucket

◀ Prev▶ PlayNext ▶↺ RestartStep 1/5

The client has been quiet for a while, so the bucket is full: 10 tokens. That is exactly the maximum allowed burst.

Leaky bucket: smoothing the output

Requests go into a “bucket” and leak out at a fixed rate; when the bucket is full it overflows (reject). There are two interpretations: a queue (requests are delayed, then processed) or a meter (it only measures, equivalent to a token bucket viewed in reverse).

NGINX limit_req uses the leaky bucket method: requests above rate are delayed until they exceed burst, then rejected; add nodelay to process requests within the burst immediately.

Note: the default rejection status of limit_req_status is 503, so change it to 429 if you want clients to tell overload apart from quota exhaustion.

Demo: the same burst, two algorithms

A simulation with a fake clock, no Redis needed. Limit of 10 requests/second for both: fixed window of 1,000 ms, token bucket with capacity 10, refill 10/second. The client fires 10 requests at 990 ms, 10 at 1,000 ms, 10 at 1,500 ms.

npx --prefix examples ts-node examples/src/rate-limiting/burst-demo.ts

limit: 10 req/s | fixed window 1000 ms | token bucket capacity 10, refill 10/s
t(ms)  sent  fixed-window  token-bucket  tokens-left
  990    10    10 allowed    10 allowed          0.0
 1000    10    10 allowed     0 allowed          0.1
 1500    10     0 allowed     5 allowed          0.1
accepted in 990..1000 ms (10 ms): fixed-window=20, token-bucket=10
total accepted out of 30: fixed-window=20, token-bucket=15

Reading the output:

• Fixed window lets 20 requests through in 10 ms, twice the limit, because 1,000 ms is a window boundary.
• Token bucket never allows more than capacity in one burst, yet after 500 ms it lets 5 requests through again: it does not punish the client longer than necessary.
• Fixed window blocks the entire 1,500 ms round even though the client waited half a second; token bucket distributes more fairly over time.

Where state lives: per instance or shared Redis

Storage	Pros	Cons	Use when
Per-instance RAM	No extra network hop, no store dependency	Effective limit ≈ limit × number of instances; resets on Pod restart; skewed when the load balancer distributes unevenly	Local overload protection (protecting that instance itself)
Shared Redis	One source of truth for all instances	+1 round-trip per request; Redis becomes a dependency on the hot path	Quotas per user/API key, limits sold by plan
Gateway / edge (NGINX, API gateway, CDN)	Blocks before spending application resources	No business context (tenant, cost)	Coarse IP-based layer, flood protection

Atomicity: read-compute-write must be one step

A common mistake: GET the tokens, compute in the app, then SET. Two instances both read “1 token left” and both allow the request.

• INCR + EXPIRE is enough for fixed window, because INCR is atomic on its own.
• MULTI/EXEC batches commands, but does not let you read results midway to decide; you must combine it with WATCH and retry on conflict. Redis also does not roll back commands that already ran inside a transaction.
• A Lua script is the cleanest option: Redis guarantees the script runs atomically, blocking all other server activity while it runs.

A token bucket sketch in Lua. Tested on Redis 7.4 with capacity 10 and refill 10 tokens/second: of 12 back-to-back requests, 10 were accepted and 2 rejected with retry_ms = 99. You still need load tests and failover tests in your own system before using it:

-- KEYS[1] = bucket key, e.g. rl:{apikey:abc}
-- ARGV[1] = capacity, ARGV[2] = refill tokens/second, ARGV[3] = request cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

-- cost larger than capacity can never have enough tokens: return -1 so the app reports an error instead of 429 + Retry-After
if cost > capacity then
  return { 0, 0, -1 }
end

local t   = redis.call('TIME')                      -- Redis's clock, not the app's
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + math.max(0, now - ts) / 1000 * rate)

local allowed, retry_ms = 0, 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) / rate * 1000)
end

redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', tostring(now))
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)
return { allowed, math.floor(tokens), retry_ms }

Deliberate choices in the sketch:

• Key names go through KEYS, not string concatenation inside the script; Redis requires this for the script to work correctly on Cluster as well.
• TIME inside the script is safe because since Redis 5.0 scripts are replicated by effects (Redis 7.0 dropped verbatim mode entirely), so replicas receive the HSET command with the computed value instead of re-running the script.
• PEXPIRE so keys of inactive clients disappear on their own once the bucket has refilled.
• retry_ms is used to fill Retry-After.
• A value of -1 means cost exceeds capacity: the request can never succeed no matter how long it waits. Return a configuration error or another 4xx instead of 429, otherwise the client will retry forever.
• capacity must be at least the largest cost (for example, if export costs 50 tokens, capacity is at least 50).
• Call it with EVALSHA; the script cache does not survive restart/failover, and client libraries usually reload it automatically on NOSCRIPT.

The script blocks the whole server while it runs, so keep it short and O(1); a slow script makes every other Redis client wait (Redis single-threaded).

Clocks: pick one source

• Use Redis’s clock (TIME) instead of each instance’s Date.now(). Clock skew between Pods makes elapsed negative or inflated, refilling the wrong number of tokens. The math.max(0, ...) above guards against the negative case.
• Clock for local in-RAM limiters: use a monotonic clock (performance.now() or process.hrtime.bigint() in Node), not a wall clock that NTP may move backward.
• What if Redis goes down? Decide in advance: fail open (allow, preserve availability, add a local limit as a safety net) or fail closed (reject, for sensitive endpoints such as login). Set a short timeout on Redis commands so the rate limiter does not become a source of latency.

How to reject: 429, Retry-After and RateLimit headers

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 2
RateLimit-Policy: "burst";q=10;w=1
RateLimit: "burst";r=0;t=2

{
  "type": "https://api.example.com/problems/rate-limited",
  "title": "Too many requests",
  "status": 429,
  "detail": "API key abc has used all 10 requests in the current window."
}

Component	Source	What to remember
429 Too Many Requests	RFC 6585 §4	The client sent too many requests in a given amount of time. The RFC does not specify how to identify the user or how to count. A 429 response MUST NOT be stored by a cache.
Retry-After	RFC 9110 §10.2.3	The value is an HTTP-date or a non-negative number of seconds (Retry-After: 120). RFC 6585 says a 429 MAY include this header.
Body	RFC 9457	Use application/problem+json with a dedicated rate-limit type so clients don’t have to parse detail.
RateLimit, RateLimit-Policy	IETF draft	Not an RFC yet, see below.

IETF draft status (checked 2026-10-18): draft-ietf-httpapi-ratelimit-headers-11 (2026-05-23) from the HTTPAPI working group is still an Internet-Draft, expiring 2026-11-24. The draft defines two fields:

• RateLimit-Policy: the policy, with parameters q (quota), w (window, seconds), qu (quota unit, default requests), pk (partition key).
• RateLimit: the current state, with parameters r (remaining quota), t (effective window, seconds), pk.

The X-RateLimit-Limit/-Remaining/-Reset headers are popular but not standard; each provider interprets Reset differently (seconds remaining or epoch). If you use the draft, state clearly in the API docs that it follows a draft and may change. When both are present, the draft specifies that Retry-After takes precedence.

A client receiving 429 should wait per Retry-After, add jitter, and not retry indefinitely: see retry, backoff and jitter.

What to count by

Key	Pros	Traps
User id / tenant	Fair per customer, tied to the service plan	Only available after authentication; anonymous endpoints need another key
API key / client id	Clear for B2B, easy to sell quota per plan	One customer with many keys → aggregate per tenant
IP	Available right at the edge, blocks anonymous floods	NAT: a whole company or mobile network shares one IP, so blocking one person blocks hundreds. IPv6: a subnet is usually a /64, attackers rotate addresses at will; group by prefix. Behind a proxy, take the IP from a header set by a trusted proxy, never trust an X-Forwarded-For sent by the client.

Rate limiting does not replace authorization. An attacker enumerating IDs in BOLA/IDOR style is only slowed down; data still leaks if permission checks are missing.

Several layers, each with one job

Loading diagram…

• Gateway: flood protection by IP, with generous limits so NAT users are not blocked by mistake.
• Service: quotas per user/API key/tenant, with business context.
• Expensive endpoints: limit the number of requests running concurrently, not just requests per second.

Cost-based limits

Not every request costs the same. GET /orders/42 and POST /reports/export over a year of data should not both take 1 token.

• Assign a cost to each request type (for example export costs 50 tokens), using ARGV[3] in the script.
• GraphQL: compute cost from query depth and size before executing.
• The RateLimit draft supports this through the qu parameter (a quota unit other than “requests”).

Protecting the login endpoint

Login needs its own rules because attackers actively evade limits:

1. Count failures per account, not only per IP: OWASP notes that with per-IP counting an attacker only has to spread attempts across many addresses.
2. Add a per-IP limit to stop password spraying (one IP trying many accounts).
3. Lockout can be abused to lock other people’s accounts: use progressively increasing delays instead of a hard lock, and still allow password reset.
4. CAPTCHA is only an additional layer of defense; MFA is the primary measure.
5. Return the same error message for “wrong password” and “no such account”.

Per-Pod quotas give a customer 6 times their plan

A B2B API sells a plan of 600 requests/minute per API key, counted with an in-RAM token bucket. At low load it runs 2 Pods, so the customer effectively gets 1,200/minute; after autoscaling to 6 Pods they get about 3,600/minute and their sync job overwhelms the database.

The fix:

1. Move the per-API-key bucket to Redis, one atomic EVALSHA per request.
2. Keep a local per-instance limit as a safety net when Redis fails (bounded fail open).
3. Return 429 with Retry-After and problem+json; the customer’s SDK reads the header instead of retrying immediately.
4. Set a cost of 20 for the export endpoint.

The numbers in this example are an illustrative scenario to show the multiplication, not measurements.

When to use it, when not

Use	Don’t use / not enough
Public APIs, B2B with quotas per plan	As a substitute for authorization or validation
Expensive endpoints (export, search, AI)	As the only overload protection: you also need timeouts, concurrency limits, load shedding
Login, OTP, password reset	Internal service-to-service traffic that already has its own backpressure
Protecting downstreams with quotas (SMS, payment)	When per-Pod local limits are sold as a global quota

Benefits

• One customer cannot bring down the experience for everyone.
• Downstream costs (database, metered providers) get a predictable ceiling.
• Slows down brute force and scraping.

Costs

• A shared store adds a round-trip and a dependency on the hot path.
• Blocks legitimate users behind NAT if the per-IP limit is too tight.
• Needs operating: per-plan configuration, dashboards, exceptions for large customers.

🎮 Try it

• Scale Lab: URL shortener, round 4: a botnet spams the link-creation API.
• Scale Lab: concert ticketing, round 3: scalper bots compete with real people for row locks.

Production checklist

1. Each limit documents its key (user, API key, tenant, IP/prefix), algorithm and parameters (capacity, rate, window).
2. Global quotas use a shared store with atomic operations (Lua/INCR); local limits are only for instance self-protection.
3. Reject with 429 + Retry-After + problem+json; if you use NGINX limit_req, change limit_req_status from the default 503.
4. Decide in advance between fail open and fail closed when Redis fails, with a short timeout on Redis commands.
5. IPs come from a trusted proxy; IPv6 is grouped by prefix; IP limits are wide enough for NAT.
6. Login/OTP endpoints have limits per account and per IP, with progressive delays instead of hard locks.
7. Metrics: requests blocked per key/route, top keys close to the limit, rate limiter latency; alert when the 429 rate spikes.
8. Test with bursts at window boundaries and with many instances running in parallel.

Common mistakes

Common pitfall

Counting in RAM and selling it as a global quota. The real limit multiplies by the number of Pods and changes on every autoscale. Contractual quotas must live in a shared store.

Common pitfall

GET then SET from the application. Two instances read the same value and both allow the request. Wrap read-compute-write in one Lua script or use an atomic command such as INCR.

Common pitfall

Returning 200 or 503 when the quota is exceeded. The client cannot tell “you sent too much” from “the server is broken”, and retries the wrong way. Use 429 with Retry-After.

Common pitfall

Trusting a client-sent X-Forwarded-For. An attacker who changes the header on every request gets a fresh limit. Only read the IP set by your own trusted proxy.

Summary

Key takeaways

• Fixed window allows up to 2× the limit around a boundary; the demo measured 20 requests in 10 ms with a limit of 10/second.
• Token bucket is a good default: capacity sets the burst, rate sets the long-term rate, and it needs only 2 numbers per key.
• Global quotas need a shared store and atomic operations; a Lua script on Redis using Redis’s TIME is the clean way.
• Reject with 429 (RFC 6585) + Retry-After (RFC 9110); the RateLimit headers are still an IETF draft.
• Choose keys carefully: NAT, IPv6 and spoofed X-Forwarded-For make IP-based limits wrong in both directions.

Self-check:

1. With a 100/minute fixed-window limit, how many requests can get through in 1 second at most?
2. Why is an in-RAM token bucket on 4 Pods not a 100/minute limit for one API key?
3. Should a login endpoint count failures per IP or per account, and why do you need both?

References

• RFC 6585 §4 — 429 Too Many Requests
• RFC 9110 §10.2.3 — Retry-After
• draft-ietf-httpapi-ratelimit-headers — IETF Datatracker
• Scripting with Lua — Redis
• Transactions — Redis
• ngx_http_limit_req_module — NGINX
• Authentication Cheat Sheet — OWASP
• Counting things, a lot of different things — Cloudflare