Rate limiting

The big picture: words you will meet

A rate limiter is a small gatekeeper placed in front of a service. For every request it asks one question: 'has this client already used its share?'. If not, the request goes in. If yes, the request is turned away. Everything in this summary is about how the gatekeeper counts, and about what happens to the ones it turns away.

Words you will meet

• Key: the name the limiter counts under. It can be an IP address, a user, an API key or a customer company. Each key has its own count.
• Limit: the largest number of requests allowed, for example 100.
• Window: the stretch of time the limit is about, for example 'per minute'. So '100 per minute' means limit 100, window 60 seconds.
• Rate: how many requests per unit of time, for example 5 per second.
• [[Burst|a lot of requests that arrive almost at the same moment]]: many requests together. Some limiters allow a small burst, others do not.
• Admit and reject: to admit a request is to let it through. To reject it is to refuse it (for example, with the answer 429).
• Throughput: how many requests per second really get done.

The two questions every limiter answers

A rule like '10 requests per second' does not say what happens when 20 requests arrive in 200 milliseconds. Each algorithm answers that in its own way, and that answer is what you really choose when you pick an algorithm.

Why and where to limit

Why would a service refuse requests on purpose? Because a server has a fixed amount of work it can do each second. If one client takes too much, the others wait or get errors. A limiter gives four things: it keeps the service available, it keeps clients fair with each other, it keeps the cost under control (some requests cost real money), and it slows down brute force (trying thousands of passwords) and scraping (copying a whole site by machine).

Which key do we count?

Be careful with the header X-Forwarded-For. It is an ordinary line in the request, and whoever sends the request writes whatever they like in it. It can be trusted only when a proxy that you control filled it in. If a service is open to the Internet with no proxy in front, it must use the address of the real connection. If it uses the header, an attacker just changes the header each time and gets endless fresh keys.

Stacking limits

A limiter only controls the total of the key it counts. If every user may send 100 per minute and one customer company has 400 users, that company can send up to 40,000 per minute. So big systems stack keys: one limit per user, one per tenant, sometimes one global. A request must pass all of them. Also, a different limit for each endpoint helps: POST /login and SMS sending should have very low limits, because every attempt is a risk or costs money, while a cheap read can have a high one. One loose limit for everything ends up far too loose for the sensitive endpoints.

Where does the limiter live?

client --> CDN/edge --> gateway --> application --> dependency
  (1)       (2)          (3)         (4)           (5)

(1) in the client itself (polite, not enforced)
(2) at the edge: cheap to reject, little context
(3) in the API gateway or reverse proxy
(4) in the application: knows user and operation
(5) right before a costly dependency (SMS, database)

The closer to the origin of the traffic, the cheaper it is to say no, but the less the limiter knows about the request. So layers are combined: a coarse and cheap limit at the edge, and fine limits per user and per operation in the application. To protect a dependency with limited capacity or cost (for example an SMS provider that charges per message), put the limiter right before it, count in the unit it charges (messages, not requests), and share it between every code path, because a nightly job may reach the provider without passing the gateway.

Fair is not the same as safe

Imagine a service that can handle 400 requests per second, and 10 clients that are each allowed 100 per second. The limits are fair, but together they allow 1,000 per second, which is more than 400. Per-client limits are normally sold above the capacity, hoping that not everybody uses the maximum at once. To protect the service you also need a global limit or load shedding. And a flood from 200,000 different addresses, each below its limit, still brings the service down, because the damage comes from the sum. A limiter inside the application also decides late: the request already used a connection and some work.

Fixed window

The simplest way to count is to cut time into equal slices, like the pages of a calendar, and keep one tally per slice. Each slice is a window of size W. Window number k covers the time from k times W up to (but not including) k+1 times W. For W = 10 seconds the windows are [0,10), [10,20), [20,30) and so on. The round bracket means 'not included'. So an instant exactly at 10 belongs to the window that is starting.

The rule: when a request arrives, find its window, look at the counter of that window, and admit the request if the counter is below the limit. Then add one. At every boundary the counter starts from zero. The state is tiny: one counter and the window number per client. That is the great quality of the algorithm. The memory does not depend on the limit or on the window size, so going from a limit of 500 to 5,000 costs nothing extra.

The weak point: the boundary

  window [0,10)            window [10,20)
|------------------------|------------------------|
                   8 9 9 | 10 11 12
                   ^^^^^   ^^^^^^^^
                   3 admitted  3 admitted

counter: 0 .. 1 2 3      | 0 -> 1 2 3  (back to zero)

A client can spend its whole limit at the very end of one window and again at the very start of the next. In a span much shorter than W it gets up to 2 times the limit through. The rule seems to promise L per window but allows twice that around a boundary. This is the classic flaw of the fixed window.

Where do the windows begin?

There are two usual ways to build it on Redis. In the first, the window number goes in the key name (for example rl:client42:7), so the windows are aligned to the clock and the same for everybody. In the second there is one key per client, the key gets a time to live with EXPIRE only when INCR returns 1, and the window begins at the client's first request:

local n = redis.call('INCR', KEYS[1])
if n == 1 then
	redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return n

Both forms still allow a double burst, just at different places. With the second form the first burst is held to the limit, but there is still a boundary when the key expires. The two lines sit together in one script so that the key is never left without an expiry.

Small details that change the numbers

• Same average, different window. '600 per minute' as one window of 60 s allows up to 1,200 around a boundary. '10 per second' as 1-second windows keeps the burst small, but rejects a good client that sends a small batch at once. The window size chooses how big a burst you tolerate.
• Counting rejected requests. In a fixed window it does not change who is admitted, because the counter is zeroed at the boundary anyway. It only changes the stored number, which can be a useful measure of the excess.
• Synchronised clients. With windows aligned to the clock, everybody gets their limit back at the same instant. Clients that wait for the renewal then all try again together, a stampede at the boundary. A random delay on the client (jitter) or an algorithm without a boundary helps.

Sliding log and sliding counter

The fixed window forgets everything at the boundary. What if the window moved along with each request? Instead of 'this calendar hour', ask 'in the last W seconds before now, how many requests were admitted?'. That window slides forward all the time, so it has no boundary to exploit. There are two ways to do it.

Sliding log: exact, but heavy

The sliding log keeps the timestamp of every admitted request, like a notebook where the doorman writes the time each guest came in. When a request arrives at time t, he rubs out the entries that are too old, counts what is left, and admits the newcomer if the count is below the limit L. The convention used here: an entry exactly W seconds old has already expired, so the window is (t - W, t]. Only admitted requests are written down.

The log forgets each request on its own, exactly W seconds after admitting it, so in any interval of W seconds there are never more than L admitted requests. The price is memory: up to L timestamps per client. A limit of 10,000 per hour can mean 10,000 entries for one client. On Redis this is usually one sorted set per client, with the timestamp as the score.

Sliding counter: cheap, and almost exact

The sliding counter keeps only two numbers per client: the count of the previous fixed window (prev) and the count of the current one (cur). To estimate the last W seconds it uses part of the previous window plus all of the current one:

estimate = prev * (1 - elapsed / W) + cur
admit when estimate < limit   (estimate is computed before counting the new request)

Example: limit 100, W = 60 s, prev = 80, cur = 30, and the request comes 15 s into the window. Three quarters of the previous window still count (1 - 15/60 = 0.75), so the estimate is 80 x 0.75 + 30 = 90, which is below 100: admitted. The weight of the previous window falls steadily from 1 to 0, so a client that used up its limit gets the slots back little by little, not all at once.

The estimate relies on a guess: that the previous window's requests were spread evenly over it, because the counter only knows how many there were, not when. When the guess is wrong, the answer is wrong, in a bounded way:

• Previous requests bunched at the end of the window: they are all still inside the last W seconds, but only a fraction is counted. The counter underestimates and may admit more than the limit.
• Previous requests bunched at the start: none of them is still inside the last W seconds, but a fraction is still counted. The counter overestimates and rejects requests that the exact log would admit.

The three window algorithms side by side

Token bucket

Picture a bucket of play tokens. To make a request you must pay one token. A tap drops new tokens into the bucket at a steady speed, but the bucket can hold only so many, and extra tokens spill over. If the bucket is empty, you wait for the next token. This is the token bucket.

The two knobs

Having two knobs is the strength of the algorithm: the burst you tolerate and the average you sustain stop being the same number. An empty bucket means the client has used its burst: the request is refused (in an API limiter) or delayed (in a traffic shaper) until a token appears. While the bucket stays empty, the throughput is exactly r.

The balance and the cap

// balance = min(B, balance + r * elapsed)
function allow(b: { tokens: number; last: number }, now: number): boolean {
	const elapsed = now - b.last;
	b.tokens = Math.min(B, b.tokens + elapsed * r);
	b.last = now;
	if (b.tokens >= 1) { b.tokens -= 1; return true; }
	return false;
}

Nobody needs a timer that drops a token each moment. Because tokens come at a constant speed, the previous balance and the time of the last update are enough to compute the balance now. This is called lazy refill, and the state per client is just two fields. Fractions of a token count: with r = 0.5 per second, two seconds give one whole token.

How many can pass?

In any interval of T seconds a token bucket admits at most B + r x T requests: the saved burst plus what the tap produced meanwhile. The longer the interval, the less the B term matters, and the average approaches r.

This is why you cannot choose r from the ceiling alone. If an API tolerates at most N requests in any T seconds, you need B + r x T <= N, not only r x T <= N. Example: at most 100 per 10 seconds and a burst of 40 means r x 10 <= 60, so r = 6 per second. Every token given to the burst is one less for the sustained rate.

More ideas

• Time to wait. If the balance is s (below 1), the next request will be admitted after (1 - s) / r seconds. This is the number a server can send in Retry-After.
• Weighted cost. A request can cost more than one token. An export may cost 25 tokens and a read 1. The rule is: admit when balance >= cost, with no partial payment. When the balance is low, cheap calls keep passing while expensive ones wait.
• Traffic shaping with bytes. Tokens can be bytes. With bucket B = 16 MB, token rate R = 2 MB/s and a link that sends at most M = 10 MB/s, a full bucket lets the host send at full speed for B / (M - R) = 16 / 8 = 2 seconds, then it drops to R.

Leaky bucket

Now turn the picture around. Imagine a bucket with a small hole in the bottom. Water can be poured in as fast as you like, but it drips out of the hole at one steady speed. If you pour too much, the bucket overflows. That is the leaky bucket, and it has two readings that use the same picture.

Reading 1: a queue (a shaper)

Requests enter a waiting line of limited size. They leave the line at a constant rate, one every fixed interval. A burst is not refused: it waits in the queue and comes out evenly. If the queue is full, the arriving request is dropped, like water over the rim.

arrivals (9 at once)
       |
       v
  +---------+
  | 6 slots |  3 requests do not fit: dropped
  +----+----+
       | one every 0.5 s
       v
  out: 0.5  1.0  1.5  2.0  2.5  3.0 s

The system behind the bucket never gets more than the output rate, no matter how bursty the input is. The price is delay: if the queue drains at r requests per second, the request with k - 1 ahead of it waits k / r seconds (the first departure is one interval after the arrival at an empty queue). The worst possible wait is capacity / r, so the queue size is also a choice of maximum latency.

Reading 2: a meter (a policer)

As a meter, the bucket holds no requests at all. It keeps just one number, the level. Each admitted request adds 1 to the level, and the level drains at a constant rate. A request is admitted when level + 1 <= capacity, and the decision is immediate: nothing waits.

The meter is the mirror image of the token bucket. With tokens = capacity - level, the rules of one turn into the rules of the other. Both admit exactly the same requests and both allow a burst of up to the capacity with an average rate r. Only the queue reading behaves differently, because it holds and delays requests.

Shaping and policing

In Tanenbaum's words, shaping regulates the average rate and the burst size of a flow before it enters the network, usually by delaying packets. Policing is the network checking that the flow keeps the agreed pattern, and dropping or marking the excess.

Token bucket or leaky bucket?

After a long quiet time a client sends 10 requests at once. A token bucket of capacity 10 saved tokens while idle, so it lets all 10 through immediately. A leaky bucket as a queue saves no credit at all: it keeps the 10 in the queue and releases them at its constant rate, say one per second. Idle time earns tokens in one and earns nothing in the other.

Distributed limiting with Redis and atomicity

So far there was one program with one counter. Real services run on several copies, called instances, behind a load balancer. If every instance counts in its own memory, a client can get N times the limit through N instances: with 3 instances and a limit of 100 per minute, up to 300 per minute.

The fix is to move the counter out of the instances into one shared store that all of them read and write. Redis is the usual choice. Redis then becomes the single source of truth, and the instances stay simple and can be added or removed without changing the limit.

Why INCR does not lose counts

Redis runs commands one at a time and never mixes two commands on the data. So INCR (add one to a number) is an atomic read, add and write. If two instances send INCR for the same key at the same instant, neither add is lost. Atomic means 'all in one piece, nothing can come in the middle'.

The trap: check, then act

counter = 9, limit = 10

instance A: GET   -> 9
instance B: GET   -> 9   (A has not written yet)
instance A: 9 < 10, INCR, admit  -> 10
instance B: 9 < 10, INCR, admit  -> 11   <- over the limit

Reading, deciding in the application and then writing is a race condition (a bug that depends on who is faster). In this repository's test, two instances received 400 concurrent requests for a limit of 50 per minute. The version with one Lua script admitted exactly 50 in each of five rounds. The naive version admitted up to 192 in the measured rounds, and exactly 50 in a few of them, which is why such bugs are hard to catch.

The cure: a Lua script

Redis can run a small program written in Lua with EVAL. A script runs from start to end and no other command is served in the middle, so the read, the decision and the write become one atomic step. It can also set the expiry in the same step as the first increment, so a client that crashes cannot leave a counter that never expires.

Clocks and failures

Windows only agree if every instance agrees on the time. Clocks of different machines drift apart (clock skew). If instance B is 20 seconds ahead, it builds a different window key than instance A for the same instant, and the shared counter is split in two. The fix is to read the time inside the script with the Redis TIME command, so every instance uses one clock.

Two more things can go wrong. First, Redis copies data to a replica asynchronously: the primary confirms to the client and sends to the replica after. If the primary crashes and the replica takes over, the last increments may be lost and the limit is briefly exceeded. This small, rare deviation is usually accepted. Second, Redis may be unreachable, and the limiter must decide beforehand what to do:

A common middle road is a rough local limit in each instance's memory while Redis is away.

HTTP 429, headers and client backoff

When a limiter says no, it must say so in a way the client understands. On the web this is done with an HTTP status code, a number at the start of the answer (200 means OK, 404 means not found). For 'you sent too many', the code is 429 Too Many Requests, added by RFC 6585. The RFC does not say how the server finds out who you are or how it counts. The answer should explain the situation and may say when to try again.

429 or 503?

A per-client limiter answers 429. A server that sheds load because it is overloaded answers 503. A 429 should never be stored by a cache, because it describes one client at one instant: if a shared cache (such as a CDN) kept it, other clients, or the same client after waiting, would be refused for no reason. RFC 6585 says 429 responses must not be stored.

Telling the client when to return

HTTP/1.1 429 Too Many Requests
Retry-After: 30
Content-Type: application/json

{"error":"rate limit exceeded"}

The Retry-After header tells the client how long to wait. RFC 9110 allows two forms: a whole number of seconds counted from receiving the answer, or an absolute HTTP-date. The seconds form does not depend on the client and server clocks agreeing. This repository's limiter sends whole seconds, rounded up.

Many APIs also send headers about the limit itself, such as X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset. These spread by imitation and have no standard. The worst case is Reset: some services mean 'seconds from now' and others mean a Unix timestamp such as 1791374400. A client that reads a timestamp as seconds would sleep for decades. The IETF is working on an Internet-Draft (not yet an RFC when this was written) with the fields RateLimit-Policy and RateLimit. A generic client should prefer Retry-After, which is standard, and read the documentation before trusting the X- fields.

What a polite client does

A 429 asks the client to slow down, not to insist and not to give up forever. If Retry-After is present, wait at least that long. It comes from whoever controls the limit, so it beats the client's own guess. If there is no Retry-After, use exponential backoff: the wait doubles at each failure. With the convention that the first retry is n = 1:

wait(n) = min(cap, base * 2^(n-1))
base = 0.5 s, cap = 10 s

The 6th retry would be 0.5 x 32 = 16 s, but the cap cuts it to 10 s. Always say whether you count attempts from 0 or from 1, because the numbers shift. Also set a maximum number of attempts, so a client is never stuck retrying forever.

Jitter: add some randomness

Imagine 200 clients all refused at the same instant, all using the same doubling waits. They retry together at 1 s, 3 s, 7 s, in waves, and the server is hit again and again (a thundering herd). Jitter makes each wait random. With full jitter the wait is drawn between 0 and min(cap, base x 2^attempt). The retries spread out and the server can serve a share of them at each moment.

no jitter:  |200|    |200|        |200|
             1s      3s           7s      (waves)

jitter:     |12|31|18|25|9|41|22|...      (spread out)

Retries can hurt

Immediate retries multiply the load at the worst moment. If a service gets 100 requests per second and every client repeats a refused request up to 3 times at once, the service sees up to 400 per second while it is already failing. This is a retry storm. Backoff, jitter, a limit of attempts and respect for Retry-After break the cycle.

There is one more safety rule. Retrying is only safe when running a request twice has the same effect as running it once, which is called being idempotent. A 429 says nothing was processed, but after a timeout the client does not know. For something like POST /charges, which creates a charge, the client sends an idempotency key, a unique code that lets the server recognise the repeat and not charge twice.

Quotas, throttling and load shedding

Rate limiting has neighbours that protect a system in other ways. Knowing which one does what is half the work.

Three different limits

One API often has all three, and a request must pass each. They are checked separately. A client that obeys the rate limit all the time can still use up its monthly quota early: with a quota of 500,000 per day and a steady 10 requests per second, the quota is gone after 50,000 seconds, about 13.9 hours. That is why APIs tell clients how much of the quota is left.

Why a concurrency limit is special

The average number of requests in progress equals the arrival rate times the time each one spends in the system. This is Little's law. If 120 requests arrive per second and each takes 0.5 s, about 60 are in progress at once. If the service gets twice as slow, 120 are in progress at the same arrival rate, and a rate limit notices nothing.

A concurrency limit C with service time S lets through at most C / S requests per second. With C = 30 and S = 0.25 s that is 120 per second. If the service slows down and S grows, the admitted throughput falls in the same proportion, which protects a server that is already struggling. A fixed rate limit would keep admitting the same rate and requests would pile up.

Congestion control, from slow to fast

Tanenbaum orders the answers to congestion from the slowest to the fastest: add capacity, choose routes that avoid the busy spots, admission control, traffic throttling and load shedding. Admission control refuses new work before it starts, which is cheaper than accepting it and then throwing it away half-way. The word throttling is used loosely in API documentation for either delaying (shaping) or refusing (policing).

Backpressure

Imagine a producer writing into a queue of 1,000 slots that a slower consumer empties. When the queue is full, the producer's write call simply waits until there is room, and nothing is thrown away. This is backpressure: the full part tells the sender to slow down, with a signal or by a call that blocks. The delay travels back to the source. When the source cannot wait, as with users on the Internet, backpressure ends as a rejection at the entrance, which is rate limiting or load shedding.

Load shedding

Load shedding is the last defence: the server refuses work on purpose, normally with 503, so the work it accepted finishes in time. It differs from rate limiting because it looks at the health of the server, not at the behaviour of one client. Good shedding is done early and by priority, with the least important work first.

request --> [reject here: 1 ms] --> parse --> auth --> database
                                             [reject here: 40 ms]

A server that rejects late may spend all its capacity saying no and stay overloaded. So shed before parsing the body, before authenticating, before touching a dependency.

When overload is not handled

Suppose a server serves 100 requests per second but gets 150, with an unbounded first-in-first-out queue, and clients give up after 2 seconds. The queue grows, every answer is late, and the server keeps serving requests whose clients have already left. Its throughput is at the maximum but its goodput (answers that arrive in time) falls to almost zero. The cure: a bounded queue, a deadline for each request (drop what is already past its timeout) and refusing the excess at the entrance.

Who to drop? The noisy neighbour

Tanenbaum describes two policies for choosing packets to drop. The wine policy prefers to keep the old packets, because old wine is better. It fits file transfer, where losing an old packet forces everything after it to be sent again. The milk policy prefers to keep the new ones, because old milk is bad. It fits real-time media, where late data is useless. Servers have the same idea: to shed by priority you must know what each request is worth.

In a shared service, one big tenant can hurt all the small ones, the noisy neighbour. With random shedding everyone loses in the same proportion, so 30 small tenants lose half of their requests because of one big one. Fair shedding serves the small tenants in full and takes the excess from whoever went past their share. That needs counting per tenant, which is why quotas and plan limits go with load shedding.

Circuit breaker

A circuit breaker is the opposite side of the same idea. Service A calls service B. After 5 calls in a row fail, A stops calling B for 30 seconds and answers with a fallback, then lets one trial call through. It sits on the caller's side and watches results, to protect against a sick dependency. A rate limiter sits on the called side and watches volume, to protect against a client that asks too much.

Putting it all together

In this repository's burst experiment, all five algorithms got the same 80 requests with the same settings (limit 10, window 1 s, so capacity 10 and rate 10 per second for the buckets). The chart shows the largest number of admitted requests found in any 1-second interval.

The fixed window let 20 through around a boundary. The sliding log never went above 10. The sliding counter reached 11, a small error. The token bucket reached 19 because it spends its saved tokens first and then earns more while the burst goes on. The leaky bucket's output stayed at 10 because it releases requests at a constant pace.

Common mistakes

• Thinking a limiter is authentication, encryption, a cache or a load balancer. It only counts.
• Counting by an IP address behind NAT, or by X-Forwarded-For with no trusted proxy.
• Using one limit for every endpoint, or only per-client limits and no global protection.
• Forgetting the cap in a token bucket, so an idle client saves unlimited tokens.
• Doing read, decide, write as separate Redis commands (a race), or INCR and EXPIRE as two commands (a key that never expires).
• Reading the time on each instance instead of on Redis, so windows disagree.
• Retrying at once with no jitter, no cap on attempts and no respect for Retry-After.
• Rejecting late, after the request has already used the expensive parts of the server.

How the ideas connect

The algorithm decides who is admitted. Redis and an atomic script make that decision hold across many servers. The status 429 with Retry-After tells the client what happened. The client's backoff with jitter keeps its retries from becoming a new problem. Quotas, concurrency limits and load shedding protect the long term and the whole service when per-client limits are not enough.