Rate limiting: token buckets, sliding windows and global limits

A rate limiter answers one question, very often and very fast: may this caller do this now? The algorithms behind the answer are small, and each makes a different trade between precision, memory, burst tolerance and how hard it is to share across servers. Choosing between them, and choosing what to limit, matters more than the code.

This article covers the classic algorithms, the token bucket, the leaky bucket and its GCRA form, and the three window counters, then what changes when the limit has to hold across a fleet of servers, and how to tell clients they have been limited.

What a limit protects

Rate limits are used for several different jobs, and it helps to know which one a given limit is doing:

• Fairness: one noisy tenant shouldn’t degrade everyone else on shared infrastructure.
• Cost: an expensive downstream API, or a model call billed by the token, needs a ceiling per customer.
• Abuse: credential stuffing, scraping and spam are mostly about volume.
• Overload protection: keeping a service below the load it can handle. Rate limits alone do this poorly, because capacity changes from moment to moment. That job belongs to load shedding and concurrency limits, covered in the retries article and below.

Token bucket

The most widely used algorithm. Each key has a bucket that holds up to b tokens and refills at r tokens per second. A request takes one token, or more for expensive operations. If there isn’t one, the request is rejected.

Two parameters give two guarantees. The refill rate r bounds the long-run average. The capacity b bounds the burst: a client that has been idle can send b requests at once. Over any interval of length T, at most b + r·T requests get through.

Implementation needs no timer. Store two numbers per key, the token count and the time of the last update, and compute the refill lazily when the next request arrives, as the code at the end does.

Leaky bucket and GCRA

The name “leaky bucket” is used for two different things:

• As a queue: requests enter a bounded FIFO that drains at a fixed rate. The output is perfectly smooth, which suits traffic shaping, but every request now waits in the queue, and a full queue rejects.
• As a meter: requests are only counted against a bucket that leaks at a fixed rate, and rejected when it would overflow. This is mathematically equivalent to a token bucket viewed upside down.

The Generic Cell Rate Algorithm (GCRA), from ATM networks, is the meter in its most compact form. It stores a single timestamp per key, the theoretical arrival time (TAT) at which the next request would be perfectly on schedule. With emission interval T = 1/r and burst tolerance τ:

One number per key, one comparison, and an exact retry time on rejection (TAT − τ − now). It is what redis-cell and several API gateways implement.

Window counters

Limits are often stated as “100 requests per minute”, which suggests counting requests in a window. How the window is defined makes a large difference:

• Fixed window: one counter per key per calendar minute, reset at :00. Cheap, and trivially implemented with Redis INCR and EXPIRE. But a client can send the full limit at the end of one window and again at the start of the next: up to twice the limit in a short span.
• Sliding log: store the timestamp of every request in the last minute, for example in a Redis sorted set, and count them. Exact, but memory grows with the limit, which hurts for limits in the thousands.
• Sliding window counter: keep only the counts for the current and previous fixed windows, and estimate the sliding count by assuming the previous window’s requests were spread evenly:

Its error is bounded and small for real traffic. Cloudflare described using it for their rate limiting, where two counters per key mattered across millions of domains. It is a good default when a limit must be stated per window.

Limiting across many servers

On one server, a limiter is a hash map. Behind a load balancer, a client’s requests land on many servers, and the limit has to hold across all of them. The options trade accuracy against latency and availability:

• A central store such as Redis, with each check done atomically in one round trip: a Lua script, as in the code below, or INCR for fixed windows. Accurate, and the most common choice. It adds a network round trip to every request and makes the store a dependency of every request.
• Local limits: give each of N servers a limit of L/N. No coordination at all, but it is only accurate if load is spread evenly, and N changes with autoscaling.
• Local with periodic sync: count locally and push deltas to a shared store every few hundred milliseconds. Small, bounded overshoot, and no round trip on the hot path. Large edge networks work this way.
• Routing by key: consistent-hash each key to one limiter instance, so its state lives in one place without a shared store.

Keys, costs and concurrency

What you count matters as much as how:

• Choose the key by who should share a limit: API key, account, user, or IP address. IPs are the weakest key, because many users share one behind a corporate network or mobile carrier, and attackers rotate them.
• Weight by cost. A search that scans a million rows and a cached lookup shouldn’t cost the same token. Charge per unit of work, or keep separate limits for expensive endpoints. LLM APIs limit tokens per minute alongside requests per minute for exactly this reason.
• Limit concurrency, not only rate. Ten requests per second that each take 30 seconds is 300 requests in flight. Stripe’s description of its limiters (2017) pairs a request-rate limiter with a concurrent-request limiter for this reason, plus load shedders that protect the fleet as a whole.
• Adaptive limits go further and adjust the concurrency limit from measured latency, the way TCP congestion control adjusts its window. Netflix’s concurrency-limits library is an example.

Telling clients

A rejected request should be cheap for the server and unambiguous for the client. Return 429 Too Many Requests (RFC 6585), with a Retry-After header giving the seconds until a retry can succeed. It is easy to compute from the token bucket or GCRA state. Advertising the remaining budget on successful responses lets well-behaved clients slow down before they hit the wall. The X-RateLimit-Limit and X-RateLimit-Remaining conventions are widespread, and the IETF’s RateLimit header fields draft standardises the same idea.

Then make sure your own clients honour it, with jittered backoff, as covered in the retries article. A limiter in front of clients that retry immediately just converts requests into rejections at the same rate.

An atomic token bucket in Redis

A token bucket shared by every app server. The whole refill, check and take runs as one Lua script, so two servers can’t both spend the last token, and it returns the Retry-After value for rejections.

// A token bucket per key, stored in Redis. The read-refill-take-write sequence runs
// as one Lua script, so concurrent requests on different app servers can't race.
const SCRIPT = `
local key      = KEYS[1]
local capacity = tonumber(ARGV[1])   -- burst size
local rate     = tonumber(ARGV[2])   -- tokens per second
local now      = tonumber(ARGV[3])   -- milliseconds
local cost     = tonumber(ARGV[4])   -- tokens this request needs

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

-- Refill for the time elapsed since the last request, up to the capacity.
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)

local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call("HSET", key, "tokens", tokens, "ts", now)
-- Expire idle keys once they would have refilled completely anyway.
redis.call("PEXPIRE", key, math.ceil(capacity / rate * 1000))

-- When rejected, how long until enough tokens exist: the Retry-After value.
local wait = allowed and 0 or math.ceil((cost - tokens) / rate * 1000)
return { allowed and 1 or 0, math.floor(tokens), wait }
`;

export async function take(redis: Redis, key: string, capacity: number, rate: number, cost = 1) {
  // Use the Redis server's clock (TIME) instead if app servers' clocks may disagree.
  const [allowed, remaining, retryAfterMs] = (await redis.eval(SCRIPT, 1, `rl:${key}`, capacity, rate, Date.now(), cost)) as number[];
  return { allowed: allowed === 1, remaining, retryAfterMs };
}

// In a request handler:
//   const r = await take(redis, `user:${userId}`, 20, 5);
//   if (!r.allowed) return new Response("Too Many Requests", {
//     status: 429, headers: { "Retry-After": String(Math.ceil(r.retryAfterMs / 1000)) },
//   });

References

1. Turner, J. (1986). New directions in communications (or which way to the information age?). IEEE Communications Magazine. doi:10.1109/MCOM.1986.1092946
2. ITU-T Recommendation I.371. Traffic control and congestion control in B-ISDN (the Generic Cell Rate Algorithm). itu.int
3. Desgats, J. (2017). How we built rate limiting capable of scaling to millions of domains. Cloudflare blog. blog.cloudflare.com
4. Tarjan, P. (2017). Scaling your API with rate limiters. Stripe blog. stripe.com/blog/rate-limiters
5. Leach, B. (2015). Rate Limiting, Cells, and GCRA. brandur.org. brandur.org/rate-limiting
6. Nottingham, M. & Fielding, R. (2012). RFC 6585: Additional HTTP Status Codes. IETF. rfc-editor.org/rfc/rfc6585
7. IETF HTTPAPI Working Group. RateLimit header fields for HTTP. Internet-Draft. datatracker.ietf.org
8. Netflix. concurrency-limits. github.com/Netflix/concurrency-limits