API Rate Limiting: Algorithms, Keys, and 429s

A rate limiter is a small amount of arithmetic sitting in front of an expensive thing. It answers one question per request, in a few microseconds, using a couple of numbers it remembers about the caller: has this identity already used its share.

The arithmetic is easy. The parts that go wrong are the ones around it. Teams pick an algorithm whose boundary behaviour lets double the stated limit through. They count on a value the client supplies. They put the limiter behind the work it was meant to protect. They deploy it on eight application servers with eight independent counters and ship a limit eight times looser than the one in the documentation. This guide covers the mechanism in order: the algorithms and what each one actually does to traffic, the key you count on, where the check belongs, what to return, and the ways the whole thing quietly stops working.

Rate limiting is a control. The abuse it contains is covered elsewhere: API Abuse Explained owns the authorization failures that limiting only blunts, DDoS Attacks Explained owns volumetric floods, which arrive as a capacity problem long before they arrive as a counting problem, and API Security Best Practices owns the wider defensive program that a limit budget sits inside.

The three decisions

Every limiter, from an nginx directive to a distributed quota service, is these three choices:

1. The key. The string you count against. An account ID, an API key, a source IP prefix, a session, or a composite of several.
2. The budget. How much that key may spend, expressed as a count over a window or as a refill rate with a burst allowance, optionally weighted by how expensive each request is.
3. The outcome. Reject, queue, or degrade, and what you tell the caller.

Choose the budget wrong and you either block paying customers or admit an attacker. The algorithm sits inside decision two, and it is the part most discussions start with, so start there and then correct the emphasis.

The algorithms

Fixed window counter

Store one integer per key per window. On each request, increment it, and reject when it exceeds the limit. At the window boundary the counter resets.

key: user:8812:2026-08-25T14:33
value: 47
TTL: 60s

It costs one counter and one expiry per key, and in Redis it is a single INCR followed by an EXPIRE on first write. The flaw is the boundary. With a limit of 100 per minute, a client that sends 100 requests at 14:33:59.900 and 100 more at 14:34:00.100 has delivered 200 requests in 200 milliseconds without ever breaking the stated rule. Any attacker who reads your documentation gets double the limit for free, on demand, every minute.

Sliding window log

Store a timestamp for every request. On each request, drop entries older than the window and count what remains. Exact, and the memory cost is the limit itself: a 1,000-per-hour limit across 200,000 keys is 200 million timestamps. Correct, and rarely worth what it costs.

Sliding window counter

Keep the current window's count and the previous window's count, then weight the previous one by how much of it is still inside the trailing window.

limit          = 100 per 60s
previous minute count = 90
current minute count  = 30
elapsed in current    = 15s   (so 45s of the previous window is still in view)

estimate = 90 * (45/60) + 30
         = 67.5 + 30
         = 97.5   ->  under 100, allow

Two integers per key, no boundary burst, and an error that only appears when traffic is wildly uneven inside a window. This is the practical answer when you want window semantics.

Token bucket

Each key owns a bucket with a capacity and a refill rate. A request spends one token. An empty bucket rejects.

No timer is involved. Store two values, the token count and the timestamp of the last update, and compute the refill lazily when the request arrives.

capacity   = 20 tokens
refill     = 5 tokens/second
stored     = (tokens, last_seen)

on request at time t:
  tokens = min(capacity, tokens + (t - last_seen) * refill)
  last_seen = t
  if tokens >= 1: tokens -= 1; allow
  else: deny, retry_after = (1 - tokens) / refill

Worked through with real numbers. A client has been idle, so its bucket sits full at 20. It fires 20 requests inside 50ms, the last of them at t = 0.050s: all 20 pass, the bucket lands on 0 and last_seen is 0.050. Request 21 arrives at t = 0.100s, so tokens = 0 + (0.100 - 0.050) * 5 = 0.25, which is under 1, and the limiter denies with Retry-After: 1 (0.75 tokens short, at 5 per second, is 0.15s, rounded up to the nearest second the header can express). From there the client is paced at exactly 5 requests per second, and if it goes quiet for 4 seconds it earns a full 20-request burst again.

That behaviour is the reason token bucket wins by default. Real clients are bursty (a page loads and fires eleven API calls at once), and a limiter that rejects a normal page load is a limiter someone will turn off.

Leaky bucket

Model the same bucket as a queue that drains at a constant rate. Requests enter the queue, the queue empties at the drain rate, and arrivals that overflow the queue are dropped. With capacity 20 and a drain of 5 per second, the same burst of 20 does not reach the backend in 50ms. It reaches it at 5 per second, with the last request served 4 seconds later.

The trade is explicit: the backend sees a perfectly flat load, and the caller pays in latency. Use it in front of something whose failure mode is concurrency rather than volume, such as a third-party API with a hard contractual rate, or a payment processor. GCRA (the generic cell rate algorithm, borrowed from ATM networking) is the same shape stored as a single timestamp per key, which is why several production limiters use it.

Concurrency limits

A separate control that is often what you actually needed. Instead of requests per second, cap the number of in-flight requests per key. Ten simultaneous report generations from one tenant will hurt a database that a hundred cheap reads per second would not touch. Rate and concurrency limit different resources, and expensive endpoints usually want both.

Comparison

What to count on

This is where limiters are actually defeated.

Account or tenant ID. The strongest key, because it costs an attacker a real identity to obtain another one. Use it wherever the caller is authenticated. Pair it with a limit on account creation, or the strength evaporates.

API key or client ID. Good, with the same caveat: if anyone can self-serve a hundred keys in a minute, you have a per-key limit and no per-attacker limit. Tie keys to an account and limit the account in aggregate. OAuth clients have the same property, covered in OAuth 2.0 Explained.

Source IP. The only option for unauthenticated endpoints such as login, signup and password reset. Two structural problems. Carrier-grade NAT and corporate egress place thousands of unrelated people behind one address, so a strict per-IP limit blocks an office to stop one script. And a single IPv6 host is handed a whole /64, which is 18 quintillion addresses, while a subscriber is typically allocated a /56 or a /48, so per-address counting is meaningless. Count IPv6 on the /64 (widen to the /48 for hosting ranges) and IPv4 on the /32, with a looser per-/24 ceiling behind it.

Composite keys. Login is the case where one key is not enough. Limit per account (to stop a targeted brute force), per IP prefix (to stop one host spraying many accounts), and globally per endpoint (to catch a distributed spray that stays under both). NIST SP 800-63B sets a concrete floor for the first of those: no more than 100 consecutive failed authentication attempts on a single account. The attack techniques these keys are sized against are covered in How Passwords Get Cracked.

Request cost. A flat request count prices a GET /health the same as a report export or a deeply nested GraphQL query, so an expensive endpoint spends more than one token from the same bucket. Choosing the unit and the number is budget design, covered in API Security Best Practices; for GraphQL the price has to be computed from the query itself, which is GraphQL Attacks Explained territory.

Where to enforce it

Rate limiting belongs at more than one layer, because each layer knows something the others do not.

The edge is the only place that can help against volume, because a flood that reaches your origin has already consumed the bandwidth. The application is the only place that knows this account is on a free plan and this query is expensive. Neither substitutes for the other.

Shared state is the operational catch. A per-process counter on eight application servers is eight independent budgets, so the effective limit is eight times what you documented, and it moves every time you autoscale. Centralise the counter in Redis or an equivalent, and make the read-modify-write a single atomic operation: INCR for windows, a Lua script or a compare-and-set loop for token buckets. That central store is now on the request path, so decide in advance what happens when it is unreachable.

Failure modes

The limiter itself gets raced. A limiter that reads the counter, compares it to the limit, and writes the increment as three separate steps is check-then-act on shared state, and a burst of concurrent requests can all read the same pre-increment value and all pass. This is the reason atomic operations matter here specifically, and it is also why rate limiting does not fix the underlying class of bug: TOCTOU Race Conditions Explained covers limit-overrun attacks in full, and a limiter is one more resource with a limit to overrun.

Counting after the expensive work. A limiter that runs after authentication, after the database lookup and after the template render has already spent everything it was protecting. Charge the budget as early in the request lifecycle as the key is known.

Fail-open silence. When the Redis holding the counters times out, the common default is to allow the request. That is a reasonable availability choice and a terrible one to make implicitly, because an attacker who can degrade your counter store has disabled your limiter. Choose deliberately per endpoint: fail open on read paths, fail closed on login, password reset, payment and account creation, and alarm on the transition either way.

Limiting only the front door. Teams limit POST /login and leave the token refresh endpoint, the mobile API, the GraphQL mutation that also authenticates, and the legacy v1 route unlimited. Enumeration then moves to whichever endpoint distinguishes a real account from a fake one, which is usually password reset or signup. Inventory every path that touches the same resource.

Uniform limits across a non-uniform API. One global limit has to be loose enough for the cheapest endpoint, which makes it useless for the most expensive one. Price by cost.

Low and slow. A distributed attacker with 5,000 hosts, each making one request every ten seconds, stays under any per-IP limit ever written while generating 500 requests per second in aggregate. Per-key limits do not see this. Only the global ceiling described above and anomaly detection on the aggregate rate catch it, and the residue is a bot-management problem.

Leaking through the response. A limiter that returns a different error for "no such account" than for "wrong password" hands an attacker an enumeration oracle that survives whatever the limit is. Also avoid returning the exact remaining count to unauthenticated callers on sensitive endpoints, since it tells a script precisely how hard it may push.

Retry storms. A limit with no Retry-After teaches every client to retry immediately, so a brief overload becomes a sustained one. Return the header, and require exponential backoff with jitter in your own SDKs.

What to return

Reject with 429 Too Many Requests (RFC 6585). Include:

HTTP/1.1 429 Too Many Requests
Retry-After: 30
RateLimit-Policy: "default";q=100;w=60
RateLimit: "default";r=0;t=30
Content-Type: application/json

{"error":"rate_limited","message":"Quota exhausted. Retry in 30 seconds."}

Retry-After is defined in RFC 9110 and takes either seconds or an HTTP date. The rate-limit hint headers let a well-written client pace itself before it is rejected. Two syntaxes are in circulation. The IETF HTTP API working group draft, still an Internet-Draft rather than an RFC, now defines exactly two Structured Fields, RateLimit and RateLimit-Policy, as shown above. Older draft versions defined three separate fields, RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset, and those are what most deployed APIs and client libraries still send and parse. Emitting both costs a few bytes and is the safe position today. Send them on successful responses too.

Two things to avoid. Do not answer with 403, which reads as a permanent authorization decision and tells a client nothing about waiting. Do not silently drop the connection on a normal user's overage, because a client that receives nothing retries.

Picking the number itself, and rolling it out without breaking legitimate traffic, belongs to budget design: API Security Best Practices covers observe-only rollout and how to choose the unit you count.

A worked configuration

For a login endpoint on a service with roughly 200,000 daily active users:

• Per account: token bucket, capacity 5, refill 1 token per 60 seconds, spent only on a failed attempt. A legitimate user who fumbles a password three times is unaffected. A guessing attack against one account gets 5 immediate tries then 1 per minute. NIST SP 800-63B caps consecutive failed attempts on a single account at 100, so the bucket is paired with a hard stop: after 100 consecutive failures the account requires a verified reset.
• Per IPv4 /32 and IPv6 /64: sliding window counter, 30 failed attempts per 10 minutes, then a hard block for 30 minutes. Loose enough for a NATed office, and it paces a single host at 30 attempts per half-hour cycle, so one guess against each of 5,000 accounts takes over 80 hours.
• Global on the endpoint: a ceiling set well above the measured peak of legitimate failed logins for this service, so only a distributed spray reaches it. Crossing it pages someone and turns on a challenge for unrecognised devices rather than blocking outright.
• Fail closed if the counter store is unavailable, with a 2-second timeout and an alert.

Verdict

Use a token bucket with lazy refill, keyed on the strongest identity the request carries, with a per-endpoint cost weight, enforced in shared atomic state at the gateway, backed by a crude per-prefix ceiling at the edge and a concurrency cap on anything expensive. Return 429 with Retry-After and rate-limit hint headers. Fail closed on the endpoints where an attacker benefits from your outage.

A perfectly implemented sliding window counted on a client-supplied header is a lookup that always returns "allow", and a fixed window keyed on a verified account ID, charged before the expensive work, will contain most of the abuse a public API actually receives. Fix the key first, then the placement, then argue about buckets. And keep the scope honest: limiting caps the rate of a request an attacker was already entitled to make, so the authorization checks in API Abuse Explained and the atomicity in TOCTOU Race Conditions Explained still have to be right underneath it.

Related guides

• API Abuse Explained
• API Security Best Practices
• TOCTOU Race Conditions Explained
• DDoS Attacks Explained
• GraphQL Attacks Explained
• Host Header Injection Explained
• OWASP Top 10 Explained
• How Passwords Get Cracked