API Rate Limiting Explained (2026): Token Bucket, GCRA and 429s

Every API I have run eventually met the same client: a loop with no sleep in it. Ten years ago it was a forgotten cron job. In 2026 it is as often an agent retrying a tool call until it works. API rate limiting is the boring control that stops that loop becoming your outage. This post explains the rate limiting algorithms (fixed window, sliding window, token bucket, leaky bucket and GCRA), how to choose what to key a limit on, how distributed limits work in Redis, what a correct 429 response looks like under the IETF RateLimit header draft, and why AI agent traffic pushes you toward limiting tokens and concurrency rather than requests.

What is API rate limiting, and what does it protect?

Rate limiting caps how much work one client can ask for in a period of time. Production APIs enforce at least three different limits, and mixing them up is where most designs go wrong.

A rate limit counts requests (or tokens, or bytes) per unit of time. A concurrency limit counts requests in flight at one moment, regardless of how fast they arrive. A quota is a rate limit with a long window, usually a day or a billing month, and is a commercial control more than a protective one.

Stripe's rate limits page is a good example of all three living together: a global limit of 100 requests per second per account in live mode (25 in a sandbox), most individual endpoints at 25 per second, a separate global concurrency limit of 50 in-progress requests, and read allocations measured per transaction over a rolling 30 days. A Stripe-Rate-Limited-Reason header tells you which one you hit. Concurrency limits exist because a slow list request costs far more than a fast lookup, and a per-second rate cannot see that.

So decide what you are protecting first. A database that falls over under parallel queries needs a concurrency limit. Fairness between tenants needs per-tenant rates. Your bill needs quotas on the expensive unit, which for LLM backends is tokens.

Rate limiting algorithms compared

There are five algorithms you will meet, plus one approximation that deserves its own row.

Fixed window keeps one counter per key per window (say, per minute) and resets it when the window rolls over. It is a single INCR and EXPIRE in Redis. Its flaw is the boundary: a client can spend the whole limit in the last second of one window and again in the first second of the next, getting twice what you intended.

Sliding window log stores a timestamp for every accepted request and counts how many fall in the last N seconds. It is exact, and its memory grows with the limit, so it suits low limits on expensive calls (password resets, payouts) rather than 10,000 requests a minute.

Sliding window counter keeps the current and previous fixed-window counters and weights the previous one by how much of it still overlaps the rolling window. Cloudflare described this approach with a worked example: 42 requests in the previous minute, 18 in the current one, 15 seconds in, gives 42 x 0.75 + 18 = 49.5. Across 400 million requests from 270,000 sources they measured 0.003% of requests wrongly allowed or limited, which is accurate enough for nearly everyone.

Token bucket gives each key a bucket of capacity B that refills at R tokens per second. A request spends a token or is refused. It allows a burst up to B and then a sustained R, which matches how real clients behave. Envoy's local rate limit filter is configured exactly this way (max_tokens, tokens_per_fill, fill_interval) and returns 429 when the bucket is empty. Anthropic's API documentation says its limits use the token bucket algorithm, so capacity "is continuously replenished" instead of resetting at fixed intervals.

Leaky bucket queues requests and drains them at a constant rate. Excess requests wait rather than fail, until the queue is full. nginx's limit_req module documents that it uses the leaky bucket method; burst sets the queue depth, and nodelay turns it into something that behaves like a token bucket.

GCRA (Generic Cell Rate Algorithm) came from ATM networking and gives token bucket behaviour with a single timestamp per key.

Algorithm	State per key	Burst behaviour	Where you see it	Source
Fixed window	1 counter + TTL	Up to 2x limit across a boundary	GitHub REST hourly limits with x-ratelimit-reset	GitHub docs
Sliding window log	1 entry per accepted request	None, exact	Small limits on costly endpoints	(pattern; see the guide)
Sliding window counter	2 counters	Approximate, 0.003% wrong in Cloudflare's test	Cloudflare edge	Cloudflare blog
Token bucket	Token count + last refill time	Up to capacity, then refill rate	Envoy local rate limit, Anthropic API	Envoy, Anthropic
Leaky bucket	Queue level	Smoothed; excess delayed, then rejected	nginx limit_req	nginx
GCRA	1 timestamp (TAT)	Same as token bucket	redis-cell, Go Throttled	brandur.org, redis-cell

If you want a default: token bucket (or GCRA) per client for burst-friendly fairness, plus a concurrency cap in front of anything slow. Fixed windows are fine for daily quotas, where nobody cares about a doubled burst at midnight.

How does GCRA work, and why do people like it?

GCRA tracks one value per key, the theoretical arrival time (TAT): when the next request would arrive if the client sent at exactly the allowed rate. Brandur Leach's 2015 write-up walks through it: each allowed request pushes the TAT forward by the emission interval T (period divided by limit), and a request is refused if the TAT minus the burst tolerance is still in the future. He reported the Go library Throttled, which implements it, was taking production traffic at Stripe.

The appeal: no token count to drift, just a timestamp, and time does the refilling. Brandur's redis-cell module exposes it as a single CL.THROTTLE command, but it is no longer actively developed and many managed services will not load modules. A Lua script is more portable. I tested this one against a local Redis 7.2 server; it uses only core commands, so it also runs on current Redis 8.10.3 and Valkey 9.1.3, both released on 26 October 2026 (Redis releases, Valkey releases).

-- gcra.lua: Generic Cell Rate Algorithm, one integer per key
-- KEYS[1] = rl:{api-key:abc}:gcra
-- ARGV[1] = emission interval T in ms (period / limit, e.g. 60000/100 = 600)
-- ARGV[2] = burst B (how many requests may arrive back to back)
local T = tonumber(ARGV[1])
local B = tonumber(ARGV[2])

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

-- TAT = theoretical arrival time of the next request if traffic were smooth
local tat      = math.max(tonumber(redis.call('GET', KEYS[1])) or now, now)
local new_tat  = tat + T
local allow_at = new_tat - B * T

if now < allow_at then
  return { 0, 0, allow_at - now }          -- denied, retry after N ms
end

redis.call('SET', KEYS[1], new_tat, 'PX', new_tat - now)
return { 1, math.floor((now - allow_at) / T), 0 }  -- allowed, remaining

-- $ redis-cli --eval gcra.lua 'rl:{api-key:abc}:gcra' , 600 3   (five times)
-- 1 2 0 / 1 1 0 / 1 0 0 / 0 0 583 / 0 0 577   (retry ms vary with timing)

That is 100 requests a minute with a burst of three: three allowed, then refusals that say "come back in 583 ms". Calling TIME inside a script that writes is safe on Redis 7 and later because scripts replicate their effects, not their source; the Redis scripting docs note that verbatim script replication was removed in 7.0.

Per-user vs per-IP vs per-API-key: what should the limit key be?

Per-IP limiting is the only option for anonymous traffic, and it is blunt: a mobile carrier puts thousands of users behind one address, while an IPv6 client can rotate through a /64 for free, so key IPv6 on the prefix. GitHub's REST docs show the usual tiering: 60 requests an hour for unauthenticated callers, tied to the IP, against 5,000 an hour for an authenticated user and up to 12,500 for a GitHub App installation (15,000 on Enterprise Cloud).

For authenticated traffic, limit per API key, with a per-tenant limit above it so one customer's 200 keys do not add up to 200 times the capacity, and a global safety limit above that. Also make sure the IP you key on is the client's, not your load balancer's; trusting X-Forwarded-For from anyone is a classic way to let attackers pick their own key.

Distributed rate limiting: Redis, local buckets and consistency

With twenty replicas behind a load balancer, each sees a twentieth of the traffic, so you need shared state or an agreed split.

The shared-state answer is almost always Redis (or Valkey). The trap is doing read, decide, write as three round trips from the app: under concurrency every request reads the same old count. In the companion guide I fired 200 concurrent requests at a limit of 10; a naive GET then SET admitted all 200, the Lua script admitted exactly 10. Redis guarantees a script runs atomically, blocking other commands while it executes, which is precisely the property a limiter needs.

Two caveats. First, in Redis Cluster every key a script touches must be passed in KEYS and live in the same hash slot, so per-user and per-tenant keys need a shared hash tag such as {tenant:7}. Second, the cluster spec is explicit that replication is asynchronous and writes can be lost in a failover. For a limiter that means slightly generous limits for a few seconds after a primary dies, which is almost always acceptable. If it is not, you are building a billing system.

The alternative is local buckets on each proxy, such as Envoy's local rate limit filter, which applies limits per Envoy process. No network hop and no shared dependency, but the effective global limit is the per-instance limit times the replica count, which shifts whenever you autoscale. A common compromise is a generous local limit plus a shared Redis limit per tenant. Decide what happens when Redis is unreachable: I fail open with an alert for general traffic and fail closed only for abuse-sensitive endpoints like login.

429 Too Many Requests, Retry-After and the IETF RateLimit headers

The status code is RFC 6585 (April 2012): 429 Too Many Requests, which MAY include Retry-After and MUST NOT be stored by a cache. Note that nginx's limit_req returns 503 by default; set limit_req_status 429; or clients will treat your rate limit as an outage.

Telling clients their budget before they hit the wall is the job of the IETF HTTPAPI working group's RateLimit header fields draft. The current revision is draft-11, dated 23 May 2026, still an Internet-Draft rather than an RFC. It defines two fields. RateLimit-Policy advertises quota policies, for example "permin";q=50;w=60, with an optional quota unit qu of requests, content-bytes or concurrent-requests. RateLimit reports the current state, for example "default";r=50;t=30, where r is remaining quota and t the seconds until it resets. If you have seen RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset, those came from older revisions such as draft-06 from December 2022. The draft also says clients must let Retry-After win, and servers should add jitter so throttled clients do not all return in the same second.

Real APIs have not waited. GitHub sends x-ratelimit-limit, -remaining, -used, -reset and -resource; OpenAI's rate limit guide lists separate x-ratelimit-remaining-requests and x-ratelimit-remaining-tokens; Anthropic uses an anthropic-ratelimit-* family plus retry-after.

# nginx: per-client-IP leaky bucket, 10 r/s with a burst of 20, answering 429
http {
    limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;

    server {
        location /api/ {
            limit_req zone=api burst=20 nodelay;  # serve the burst now, then 10 r/s
            limit_req_status 429;                 # default is 503
            proxy_pass http://app_upstream;
        }
    }
}

On the client side, the LLM API 429 guide covers backoff and header parsing.

How should you rate limit AI agent traffic?

Agents break two assumptions behind request-per-second limits: that requests cost roughly the same, and that a human will eventually give up. One agent call might be 200 tokens or 200,000, and an agent with a retry policy and no budget will keep trying all night.

The LLM providers already limit on the expensive unit. Anthropic's Messages API enforces requests per minute, input tokens per minute and output tokens per minute separately, and counts only uncached input tokens toward the input limit, so prompt caching effectively raises your ceiling. It also warns about "acceleration limits" on sharp usage increases, which is a rate limit on your rate. OpenAI tracks requests and tokens per minute and per day.

If you are serving agents, do the same. Use a token bucket where the cost of a request is its estimated token count, settle the difference after the response, and add a concurrency cap per agent identity, because long-running streaming calls are a concurrency problem first. The RateLimit draft's concurrent-requests and content-bytes units let you advertise those policies honestly. Give each agent its own key (an agent identity, not the human's API key it borrowed) so you can throttle one runaway loop without cutting off the person. For outbound calls, an AI gateway is the usual place to put budgets.

(Disclosure: I run PandaStack, a microVM cloud for agent code execution, so I spend more time than most thinking about agents that do not know when to stop.) The DevOps lesson carries over unchanged: limits are part of the API contract, so document them, emit them in headers, and alert when a tenant lives at the ceiling.

FAQ

What is the difference between token bucket and leaky bucket?

A token bucket allows a burst up to the bucket size, then the refill rate, and rejects the excess immediately. A leaky bucket smooths traffic into a constant outflow, queueing the excess until the queue is full. nginx limit_req is a leaky bucket; adding nodelay makes it behave like a token bucket.

Which rate limiting algorithm is best?

For most APIs, token bucket or GCRA keyed per client, because they allow natural bursts while enforcing a long-run rate. Use a sliding window log for small limits on expensive actions, a fixed window for daily quotas, and a concurrency limit for slow endpoints.

Should a rate-limited API return 429 or 503?

Return 429 Too Many Requests when a specific client has exceeded its limit, with a Retry-After header. 503 means the server itself is overloaded, and monitors treat it as an outage. nginx defaults to 503 for limit_req.

Are the RateLimit headers an RFC yet?

No. As of November 2026 the latest version is draft-ietf-httpapi-ratelimit-headers-11 from 23 May 2026, still an Internet-Draft in the HTTPAPI working group. Field names changed between revisions, so expect small changes.

This quarter, on any API I owned, I would put a token bucket per key and per tenant in Redis with one Lua script (the step-by-step Redis guide has the code), switch every 503 that really means "slow down" to a 429 with Retry-After, and add a token-weighted limit and concurrency cap in front of anything an agent can call. None of it is clever; all of it is cheaper than the incident.

Related: How to Fix LLM API 429 Rate Limit and 529 Overloaded Errors (2026), Redis vs Valkey in 2026: Licenses, Valkey 9.1 vs Redis 8.10, Which to Pick and AI Gateways in 2026: Six Options Compared After LiteLLM's 40-Minute Backdoor.