Rate Limiter: System Design

A service that accepts requests from the outside world has no say in how many of them arrive. Its capacity is fixed by the machines it runs on, while the demand placed on it is decided by other people’s programs, and whenever demand exceeds capacity for more than a moment the service fails in a way that does not distinguish between the guilty and the innocent: the requests of a well-behaved client wait in the same queue as the requests of the client that caused the overload, and they time out together. A rate limiter gives the service back some of the control it lacks. It attaches an allowance to each caller, counts what each caller sends, and refuses whatever exceeds the allowance before the service has spent any work on it, so that a problem which would have been shared by everybody becomes a refusal addressed to the caller responsible.

Stated like this, the idea seems to leave little to design, and yet 2 parts of it turn out to be subtle. The first is the meaning of the allowance itself, because a phrase such as “5 requests per second” admits several readings that differ sharply in what they let through, and each reading leads to a different algorithm. The second is the counting, which is trivial on 1 machine and becomes a small distributed systems problem as soon as the limiter runs on several machines that each see only a part of a caller’s traffic. This chapter takes the 2 in that order. It examines 5 algorithms by following the same 11 requests through each of them, and then builds the system around the one we choose.

Why a service limits its callers

Consider an API server that can answer 1000 requests per second and serves 200 clients, each of which normally sends a few requests per second. One day a client is released with a defect in its error handling, so that a failed call is retried immediately and without pause, and this single client begins to send 5000 requests per second. The server has no means of setting these requests aside, since it cannot know who sent a request until it has accepted the connection and read the request, and by then the cost has been paid. Its queue lengthens and the response time of every client grows with it. Some of the other clients, finding their calls slow, give up and try again, which adds to the queue the very requests that were already in it. Within a minute or so the 199 clients that did nothing wrong are receiving errors on account of the 1 that did, and the operators of the service are looking at a failure whose cause lies in a program they do not own and cannot fix.

With a rate limiter in front of the server, the same defect has a very different outcome. The limiter recognises the caller, finds that it has exhausted its allowance, and answers with a short refusal that costs a small fraction of what a real response would have cost. The defective client receives a great many refusals, which is an accurate reflection of its behaviour, and the remaining clients are served as usual and never learn that anything was wrong.

Protection against overload is the best known reason for limiting callers, and there are 2 others that a design usually has to serve at the same time. One is fairness: a large customer running a nightly export may stay well within what the service can bear and still consume so much of it that smaller customers are crowded out, and an allowance per customer is the simplest way of dividing capacity among them. The other is the control of cost and abuse, where the concern is what each individual request makes possible. If every call costs money to answer, an unlimited caller is an unlimited bill, and if every call is a guess at a password, a login form that permits 5 attempts per minute for an account turns guessing into a hopeless undertaking, whereas a form without a limit will patiently evaluate millions of guesses a day. In this last case the limit is a security control as much as a protection, a distinction that matters later when we decide how the limiter should behave when it breaks.

It is worth separating the rate limiter from a neighbouring mechanism with which it is often confused. Load shedding is what a service does when it is close to overload and drops a share of its incoming requests, without regard to who sent them, in order to keep answering the rest. A rate limiter acts earlier and on different grounds, since it refuses a particular caller for exceeding that caller’s own allowance, and it does so even when the service has capacity to spare. The 2 complement each other, and large systems generally have both.

What “5 requests per second” can mean

The phrase “each client may send 5 requests per second” has the appearance of a complete specification, and the easiest way to see that it is incomplete is to imagine 3 clients and to ask of each whether it has kept to the limit.

Nobody would dispute that client A is within the limit. Client B has also sent 5 requests in a second, and in fact far fewer than 5 per second on average, although the server received all 5 at the same instant and had to work on them concurrently. Client C sent 5 requests in the first second of the clock and 5 in the next, so that each calendar second contains exactly the permitted number, and nevertheless the server received 10 requests within 200 ms.

Clients B and C expose 2 questions on which the phrase is silent. The first concerns the burst, by which we mean the number of requests that may arrive together. A limit of 5 per second does not say whether the 5 may come in the same instant or must be spread across the second, and there is no universally right answer, because services differ in what they can tolerate. A web API usually ought to permit short bursts, since that is how honest clients behave: a page is opened and issues 6 calls at once, and then nothing happens while a person reads. A service that feeds a device or a downstream system able to handle only one thing after another may need its requests evenly spaced, and would be harmed by exactly the burst that the web API welcomes.

The second question concerns the second itself. “Per second” may refer to the seconds of the clock, each beginning when the previous one ends, or it may refer to every span of 1000 ms regardless of where the span begins. Client C satisfies the first reading and violates the second, and the difference between the 2 readings is a factor of 2 in the load the server may have to carry.

Each of the 5 algorithms that follow amounts to a particular pair of answers to these 2 questions. They are best understood as different definitions of the limit that happen to be cheap to compute, and the reason no one of them has displaced the others is that the right definition depends on what is being protected.

A limit also depends on a third thing, which the phrase names without defining, namely the client. The limiter must count requests under some identity, and the identity under which requests are added together is called the key of the limit. It may be an API key, a user id, an IP address, or some combination of these. The choice of key deserves a section of its own after the algorithms, because a poorly chosen key will undo the work of a well chosen algorithm.

The traffic used in this chapter

So that the algorithms can be compared on equal terms, every one of them is given the same requests from a single client under the same limit of 5 requests per second. The client sends 11 requests within 650 ms, at the following times in milliseconds.

By any reading of the limit this client is sending too much, since it issues 11 requests in well under a second where 5 are permitted. The times have been chosen so that the requests lie across the 1 second mark of the clock, with 5 before it and 6 after it, because that is the arrangement on which the algorithms disagree most. One would expect a sound limiter to forward about 5 of the 11 and perhaps a few more as time goes by. The 5 algorithms forward 10, 5, 6, 8 and 9 of them respectively, and the reasons for these differences are the substance of the next 5 sections.

Each algorithm is accompanied by a picture that proceeds in steps, one step for each arriving request. The Next button advances to the following request and shows what the limiter has stored and what it decides. In these pictures a green dot marks a request that was forwarded to the API and a red cross marks a request that was refused.

Algorithm 1: the fixed window counter

The most direct way of enforcing 5 requests per second is to divide time into windows of 1 second, aligned with the clock, and to count the requests that arrive in the current window. The limiter then needs to remember only a single number for each client. Every forwarded request increases the number by 1, a request that finds the number already at 5 is refused, and when the clock passes into the next window the number begins again at 0.

At the end of the sequence 10 of the 11 requests have been forwarded. Requests 1 to 5 arrived between 600 and 950 ms and were counted in window 0, which they filled. At 1000 ms the clock moved into window 1, where the count stood at 0 again, so that requests 6 to 10 were forwarded as readily as the first 5 had been, and only request 11 met a full count.

The server therefore received 10 requests within 600 ms from a client whose limit is 5 per second, and it is important to see that the algorithm did precisely what it was defined to do. Each window contains exactly 5 forwarded requests. The rule is expressed in terms of the seconds of the clock, the client’s burst happened to fall across the boundary between 2 of them, and the rule has nothing to say about spans of time that do not coincide with its windows.

This behaviour is the defining weakness of the fixed window, and its extent can be stated exactly: a client can send up to twice the limit within an arbitrarily short span of time, by sending one full allowance at the end of a window and another at the start of the next. No ill intent is needed for this to occur. A great many programs do their work on a schedule, waking at the start of each minute or each hour, and a limit that is reset on the minute or the hour will meet such a program exactly at its boundary, day after day.

The synchronised reset has a second consequence that is less often noticed. Because the counts of all clients return to 0 at the same instant, all the clients that had been refused and were retrying succeed together at the start of the next window, and the server experiences a surge of traffic at every boundary that the limiter itself has organised.

These properties make the fixed window a poor choice for protecting a server against overload, since the boundary admits twice the load that the limit appears to promise. They matter much less when the window is long and the purpose is to meter usage, and this is where the algorithm is properly at home. Daily and monthly quotas are almost always fixed windows, for the good reason that customers readily understand a quota that “resets at midnight”, and a doubling of the daily quota around midnight is spread over enough time to be harmless. The cost is as low as a limiter’s can be: a count and the number of the window to which it belongs.

Algorithm 2: the sliding window log

The fixed window goes wrong because its windows are fastened to the clock, and the obvious remedy is to fasten the window to the request: when a request arrives, the limiter should look back exactly 1 second from that moment and count what it forwarded during that span, wherever the span happens to begin.

To do this the limiter has to know when each recent request arrived, and so it keeps a log, a list of the arrival times of the requests it has forwarded. On each new request it first discards the times that lie more than 1 second in the past. If fewer than 5 times then remain, the request is forwarded and its own arrival time is appended to the log, and otherwise the request is refused.

This time only 5 requests are forwarded. From 1000 ms onwards each arriving request looks back over the preceding second and finds the 5 entries from 600 to 950 ms still within it, and the fact that the clock has passed the 1 second mark is of no significance to the rule. The oldest entry, 600, leaves the log at 1600 ms, and until then nothing more can pass.

The sliding window log is exact in a sense that none of the other algorithms can match. Whichever span of 1 second one chooses to examine, beginning at any instant whatever, it contains at most 5 forwarded requests, and this is surely what most people have in mind when they say “5 per second”.

Exactness is paid for in memory. Where the fixed window stores 1 number for a client, the log stores a timestamp for every forwarded request up to the limit. For a limit of 5 per second that is 5 timestamps and of no concern. For a limit of 10000 requests per hour it is as many as 10000 timestamps for a single client, about 80 KB, and for a million active clients about 80 GB. The cost thus rises in proportion to the size of the limit, with the awkward result that the most generous limits are the most expensive to enforce.

The description above contains a decision that is easily overlooked, in the words “the requests it has forwarded”. One has to decide whether a refused request should also be entered in the log. In the version shown it is left out, so that a client which keeps on sending is served again as soon as its old entries expire. Some implementations record refused requests as well, and under that rule a client that never stops sending is never served again, since its own refused requests keep the log permanently full. That is a much harsher policy, and occasionally it is the one intended, for instance as a defence against password guessing. What must be avoided is arriving at it unintentionally, which is what happens in an implementation that appends every request to the log first and checks the count afterwards.

The log is therefore the natural choice for limits that are small and must be strict, such as 5 login attempts per minute or 3 password resets per hour, where its memory cost is negligible and its exactness is valuable. It is a poor choice for large limits applied to a large number of clients.

Algorithm 3: the sliding window counter

We now have one algorithm that is cheap and wrong at the boundary and another that is exact and expensive, and it is natural to look for something between them. The sliding window counter keeps the 2 counts that a fixed window limiter would have kept for 2 consecutive windows, and from them it estimates what the log would have reported.

The limiter stores the count of the current window and the count of the window before it. When a request arrives, the second that precedes it overlaps both windows: it includes the whole of the current window up to now, together with the final portion of the previous window. If the current window began 250 ms ago, the preceding second extends 750 ms back into the previous window and so covers 75% of it.

The limiter cannot know how the requests of the previous window were distributed within that window, having kept only their number, and so it makes the simplest assumption available, which is that they were spread evenly. On that assumption 75% of the window contains 75% of its requests, and the number of requests in the preceding second is estimated as

estimate = previous count × share of the previous window still covered + current count

A request is forwarded when the estimate, with the request itself included, does not exceed the limit.

Requests 6 to 10 are refused, as they were by the log. Immediately after the boundary the preceding second still covers nearly all of the previous window, so that nearly all of its 5 requests are counted, and the burst that the fixed window admitted across the boundary does not get through.

Request 11, at 1250 ms, is forwarded, and it is in this decision that the estimate shows what it is. The limiter calculates 5 × 0.75 + 0 = 3.75 and concludes that there is room for another request. In reality all 5 of the earlier requests arrived between 600 and 950 ms and therefore lie entirely within the preceding second, so that the true count is 5, and the log, which knew this, refused the same request. The estimate came out too low because the requests were concentrated at the end of their window, while the formula took them to be evenly spread.

The error can equally fall on the other side. When the requests of the previous window were concentrated at its beginning, the formula continues to count some of them after they have become more than 1 second old, and the limiter then refuses a request that the log would have forwarded. For traffic that is reasonably smooth the error is small in either direction, typically a few percent of the limit, and the worst case is the kind of burst at the very end of a window that we constructed deliberately. Even in the worst case the client gains a fraction of one allowance, where the fixed window would have given it a whole additional allowance.

In exchange for this modest inaccuracy the algorithm needs 2 counts per client whatever the size of the limit. For a limit of 10000 per hour that is 2 numbers where the log requires up to 10000 timestamps, and this trade explains why the sliding window counter is so often chosen for public APIs with large limits and many clients. It should not be used where a small limit has to be enforced exactly.

Algorithm 4: the token bucket

The 3 algorithms considered so far all count requests within a window, and they treat the burst only by implication. The remaining 2 start from a different picture, in which the burst is represented explicitly.

Imagine a bucket that holds tokens, each token being a permission to send 1 request. Tokens are added to the bucket at a steady rate, which in our case is 1 every 200 ms or 5 per second. The bucket has a capacity, here 5 tokens, and a token that arrives when the bucket is already full is discarded. A request is forwarded if it can remove 1 token from the bucket, and it is refused if the bucket is empty.

The 2 numbers that describe a token bucket correspond directly to the 2 questions that a limit has to answer. The rate determines how many requests per second a client can go on sending indefinitely, since over a long period it cannot spend tokens faster than they arrive. The capacity determines how many requests a client can send in the same instant after a period of quiet, since a client that has been silent finds the bucket full and is free to empty it at once. After such a burst the bucket is empty and the client is held to the rate until it pauses long enough for the bucket to fill again.

That the rate and the capacity can be chosen independently is the particular strength of this algorithm. An API whose clients typically open a page with 20 calls and then fall silent can be given a rate of 5 per second and a capacity of 20, which serves those clients well and still bounds what they can sustain. A window counter has a single number at its disposal and cannot express such a limit.

Here 8 requests are forwarded. The first 5 consume the contents of the full bucket. While they are arriving, and in the 300 ms that follow, 650 ms elapse in all, during which 3 further tokens are added, and requests 6, 7 and 10 each find one of them.

This result repays some attention, because it regularly surprises people who have configured a token bucket and then measured it. The limit is described as “5 per second”, and the limiter forwarded 8 requests in 600 ms. The explanation is that a token bucket with rate r and capacity b forwards at most b + r × t requests in any span of t seconds, namely the contents of the bucket together with whatever arrives during the span. Over 1 second, with the numbers used here, this comes to 5 + 5 = 10. Whoever sets the capacity equal to the rate and expects a strict limit of 5 in every second will therefore observe up to twice that number in the second following a quiet period. If the server truly cannot bear more than 5 requests in any second, then the capacity must be made smaller, or the rate lower, or the algorithm of the next section is the one to use.

How the bucket is stored

The picture suggests a timer that drops a token into every bucket every 200 ms. For a million clients that would mean 5 million updates per second, almost all of them applied to the buckets of clients that are sending nothing at all, and no practical limiter works in this way.

The timer can be dispensed with entirely. The limiter stores 2 numbers for each client: the number of tokens in the bucket, and the time at which that number was last brought up to date. When a request arrives, the limiter works out how much time has passed since that moment, adds the tokens that would have arrived in the interval, and caps the result at the capacity. It then removes 1 token if one is available and stores the new number together with the present time. The steps of the picture show this arithmetic in captions such as “50 ms have passed, which adds 0.25 tokens”.

The same captions show why the number of tokens has to be a fraction. A request that arrives 50 ms after its predecessor has earned a quarter of a token, and if that quarter were rounded down to nothing on every request, a client sending every 50 ms would never accumulate a token at all.

Storing the bucket in this way has a welcome consequence for memory. A bucket that has not been touched for capacity ÷ rate seconds, which is 1 second in our example, must be full, and a full bucket is indistinguishable from a bucket that has never been used. The limiter may therefore delete the entry of any client that has been silent for that long and create a full bucket when the client next appears, so that memory is occupied only by the clients that are active at the moment.

With 2 numbers of state, a few arithmetic operations per request and a burst that the operator sets directly, the token bucket is the usual choice for the general protection of an API. It is unsuitable only where the traffic reaching the service must be evenly spaced.

Algorithm 5: the leaky bucket

The token bucket passes a burst through to the service, within the bound set by its capacity. The leaky bucket does the opposite: it accepts a burst and releases it slowly.

The name comes from a bucket with a small hole in its base. However quickly water is poured in, it leaves through the hole at a constant rate, and if water continues to be poured in faster than it leaks, the bucket eventually fills and the excess runs over the side.

Applied to requests, the bucket is a queue. An arriving request joins the back of the queue, and requests leave the front of it at a fixed pace, 1 every 200 ms, to be forwarded to the API. The queue has a fixed number of places, 5 in this example, and a request that arrives when all of them are occupied is refused.

The leaky bucket accepts 9 of the 11 requests, more than any algorithm except the fixed window, and yet it places a lighter burden on the API than any of the others. The lower axis of the picture explains the apparent paradox. The requests arrived bunched together within 650 ms, and they departed at intervals of 200 ms over a period of 1.6 seconds, so that the API at no time received 2 requests less than 200 ms apart.

This is what the leaky bucket is for. The other 4 algorithms decide only whether a request is forwarded, and a request that is forwarded goes on its way at the instant of its arrival. The leaky bucket decides in addition when the request is forwarded, and in doing so it alters the shape of the traffic as well as its volume.

The smoothing has a price, and it is the client who pays it. A request that joins the queue behind 4 others waits 800 ms before it so much as reaches the API. For a person waiting on a web page such a delay is worse than a prompt refusal followed by a retry. For a background job that sends email through a provider which accepts exactly 5 messages per second it is ideal, since nothing is refused, nothing has to be retried, and the provider’s limit is observed to the letter.

A queue of waiting requests also holds resources, because each waiting request keeps a connection open and occupies memory in the limiter. For this reason the leaky bucket is found more often inside a system, between a service and something slower that it feeds, than at the public edge of an API.

The leaky bucket as a meter

The literature uses the name “leaky bucket” for a second algorithm as well, and the 2 are frequently confused. In this other version nothing waits. The bucket has a level, which rises by 1 with each accepted request and falls at a constant rate, and a request that would raise the level above the capacity is refused, while every accepted request is forwarded immediately.

This “leaky bucket as a meter” makes exactly the same decisions as a token bucket. The level of the water is the number of tokens missing from a full token bucket, and the one drains at the rate at which the other fills. When a document speaks of a leaky bucket and nothing is being queued, what it describes is a token bucket seen upside down, and everything said in the previous section applies to it, the burst included.

How the queue is stored

The queueing version, too, needs less state than its picture suggests. Because requests depart at a fixed pace, the limiter does not have to consult a list of them in order to reach a decision. It is enough to keep 1 number, the time of the next free turn to depart. An arriving request is assigned that turn, and the number is advanced by 200 ms. If the turn lies 1 second or more in the future, then 5 requests must already be waiting, and the new arrival is refused. The captions of the picture report this number at each step, as in “the next free turn to leave is at 1400 ms”.

Deciding from a single stored time in this manner is an old technique. It was standardised in the 1990s for telephone and data networks under the name generic cell rate algorithm, usually abbreviated GCRA, and it is used in present-day rate limiters for the same reason it was attractive then, which is that it requires 1 number of state per client.

The algorithms compared

The table below collects the results for the 11 requests of this chapter under the limit of 5 per second.

The simulation in the book’s repository sends 3 further kinds of traffic through the same 5 algorithms. In its results the column “most in any second” gives the largest number of requests that reached the API within any span of 1000 ms, which is the quantity the server actually has to withstand.

The first block of this table carries a warning for anyone who tests a limiter. A single burst does not distinguish the algorithms at all, since every one of them forwards 5 requests out of 20. Their differences emerge only when traffic continues for a while or crosses a boundary, and a limiter that has passed a quick test with one burst may therefore still behave quite differently from what its author expects once it is in production.

The second and third blocks show, as measurements, the 2 effects described earlier. The fixed window alone admits 10 requests in a second when they are arranged around the boundary. The token bucket admits 9 in the first second of sustained traffic, which is its full bucket of 5 and the 4 tokens that arrived meanwhile. In the third block the sliding window counter forwards 13 requests where the exact log forwards 15, its estimate having erred on the strict side on this occasion.

The properties of the 5 algorithms can be summarised as follows.

In choosing among them it is usually enough to consider what the limit is for. If whatever stands behind the limiter can work only at a fixed pace, the leaky bucket is the appropriate choice, with the understanding that requests will wait. If the limit is small and has to be exact, as with a handful of attempts per minute on something sensitive, the sliding window log should be used, its memory cost being negligible at that size. If the limit is a long quota that customers read about in a price list, a fixed window that resets at a predictable time is both the simplest and the easiest to explain. For the general protection of an API, which is the commonest case, the choice lies between the token bucket, when clients are bursty and a bounded burst does no harm, and the sliding window counter, when the limit is meant to hold over every window to within a small error.

The design in the remainder of this chapter uses a token bucket with a rate of 5 per second and a capacity of 10 for each client. This is the most widespread arrangement at an API gateway, being cheap, well suited to the way real clients behave, and equipped with a burst that the operator controls directly.

Use cases

The limiter has 2 kinds of user. Clients encounter it on every call they make, usually without noticing, and operators set the limits it enforces.

Functional requirements

Non-functional requirements

Non-functional requirement 2 calls for some justification, since in it we deliberately choose the weaker of the consistency models introduced in chapter 1. The limiter is a protective layer, and the consequences of its being slightly wrong are mild: if a limit of 100 requests per second occasionally admits 103, the API is still protected and no data anywhere is incorrect. To make every count exact, all the limiter nodes would have to agree on a client’s count before any of them answered a request, and agreement of that kind is what chapters 3 and 4 obtain by means of a leader and a majority, at the cost of a disk write and a network round trip. Incurring that cost on every call to the API would make the protection more expensive than much of what it protects. We therefore accept counts that are slightly wrong for short periods, and concentrate on bounding how wrong they can be.

Non-functional requirement 1 is likewise a decision that could have gone the other way, and for certain limits it does. The section on failures takes it up again.

Core entities

The 2 entities differ in character, and the difference shapes the design. A Limit is configuration. It changes when an operator changes it, perhaps a few times a day, it must survive restarts, and it is read enormously more often than it is written, so each limiter node keeps a copy of the limits in memory and refreshes it periodically. A Bucket is running state that changes with every request and can be lost without real harm, since a bucket that has been lost is created again full, and the only effect is that 1 client is granted 1 additional burst.

Capacity estimate

Arithmetic ahead. The buckets of 1 million clients need about 64 MB of memory. They fit on 1 node, and we run 3 for availability.

Skip to the high-level design

Show the calculation

Quantity	Calculation	Result
Memory per bucket	client id 40 bytes + tokens 8 + time 8 + overhead 8	64 bytes
Memory for all clients	1000000 × 64 bytes	64 MB
Checks per second	1 per request	50000
The same clients with a sliding window log and a limit of 10000 per hour	1000000 × 10000 × 8 bytes	80 GB

The last row of the calculation is included for contrast. It shows that the choice of algorithm can change the memory required by a factor of more than 1000.

The API

A rate limiter offers clients no API of its own. It makes itself known through the responses of the API it protects, by means of 1 status code and a small number of headers.

A request within the limit

GET /v1/orders HTTP/1.1
Host: api.example
Authorization: Bearer client-42

HTTP/1.1 200 OK
RateLimit-Limit: 5
RateLimit-Remaining: 3
RateLimit-Reset: 1

The 3 headers inform the client of its rate, of the number of requests it could still send at this moment, and of the number of seconds after which its allowance will be full again, so that a client which reads them can slow down before it is ever refused. The names of such headers differ from one API to another, and an API should document the ones it sends.

A request over the limit

GET /v1/orders HTTP/1.1
Host: api.example
Authorization: Bearer client-42

HTTP/1.1 429 Too Many Requests
Retry-After: 2
Content-Type: application/problem+json

{
  "type": "/problems/rate-limited",
  "title": "Too many requests",
  "status": 429,
  "detail": "5 requests per second are allowed"
}

429 Too Many Requests is the status code that HTTP provides for this situation, and Retry-After is the standard header for stating how many seconds the client should wait.

An operator sets a limit

PUT /v1/limits/client-42 HTTP/1.1
Host: limiter.internal
Content-Type: application/json

{ "rate": 5, "capacity": 10 }

HTTP/1.1 200 OK
Content-Type: application/json

{ "client": "client-42", "rate": 5, "capacity": 10 }

PUT replaces the whole limit of the named client, and repeating the request leaves the limit as it was after the first.

High-level design

One request, step by step

The steps follow the arrows of figure 7.12.

1. A client sends GET /v1/orders with its credentials. The gateway verifies the credentials and obtains the client id, client-42, from them.
2. The gateway asks the rate limiter whether client-42 may make 1 request to this route now.
3. The limiter finds the limit of client-42 in its own memory. It then asks the counter store to bring the client’s bucket up to date for the time that has passed and to remove 1 token, as a single operation, and the store replies with the decision and the number of tokens remaining.
4. If a token was removed, the gateway forwards the request to an API server and adds the RateLimit headers to the response. If the bucket was empty, the gateway answers 429 itself, and the API servers never see the request.

The order of the first 2 steps is deliberate. The gateway authenticates the caller before consulting the limiter because the limiter needs to know whose request it is counting. It follows that requests which fail authentication must be limited in some other way, usually by IP address, since otherwise an attacker could submit login attempts without limit and never come within reach of a limit that is keyed by client.

Where the limiter runs

The design places the limiter at the gateway. A limiter can in fact run in any of 3 places, and the 3 protect against different things.

These are complements, and a mature system uses all of them. A carefully written client library paces its own calls with a leaky bucket so that it seldom sees a 429. The gateway enforces the limit regardless, because a service cannot make its safety depend on the good conduct of its clients. And an expensive operation deep inside a service may carry a tighter limit of its own, based on knowledge that the gateway does not have.

Whose requests are counted together

The key of a limit determines which requests are added up, and a badly chosen key causes the limiter to penalise the wrong people while leaving the intended target untouched.

The IP address is the only identity available before a caller has authenticated, and it is a poor one in both directions. A university, a company or a mobile network may place thousands of people behind a single address, all of whom then share one allowance and are refused together when any one of them is busy. An attacker in control of 10000 addresses, on the other hand, enjoys 10000 allowances. A limit by IP address is therefore best kept generous and regarded as a coarse defence for unauthenticated traffic.

Once the caller is known, an API key or a user id is a far better key, since it identifies the party actually responsible for the traffic. Combining it with the route gives finer control, at the cost of 1 bucket for every pair of client and route. A limit keyed on nothing at all, which counts every request to a service, protects the service’s total capacity and provides no fairness whatever, because a single client is free to use it up.

In practice several limits are applied to each request, and the request is forwarded only if every one of them permits it. A representative set is shown below.

Layered limits introduce a subtlety of their own. Suppose a request is admitted by the second limit and then refused by the third. A token has already been removed from the client’s general bucket on behalf of a request that was never served, and a client that keeps running into the limit on exports will find that its general allowance drains away as well. The correct procedure is to examine all the applicable limits first and to remove tokens only when every one of them has room, which with a shared store means that all the buckets concerned are checked and updated within the same single operation.

Counting on many machines

Everything said so far has assumed that 1 limiter sees all the requests of a client. At 50000 requests per second, and for the sake of availability, there will be several limiter nodes behind a load balancer, and the requests of client-42 will be distributed among them. The question of where the buckets are to be kept has 3 answers in common use.

Each node keeps its own buckets

The simplest arrangement is for every limiter node to keep buckets in its own memory and to consult nobody. Nothing could be faster, and there is no dependency that might fail.

The arrangement is also wrong by a constant factor. With 3 nodes and traffic spread evenly among them, each node sees a third of the client’s requests and allows the full limit, so that the client obtains 3 times its allowance. One might give each node a third of the limit, but this is correct only for as long as the traffic is in fact evenly spread, which a load balancer does not undertake to ensure for any individual client: a client that keeps 1 connection open sends everything to 1 node and receives a third of what it is entitled to. The size of the error also changes whenever a node is added or removed.

The load balancer can be instructed to send all the requests of a client to the same node, for instance by hashing the client id as chapter 1 hashes keys. Local buckets are then exact. The weakness shows itself when a node is added or fails, since the clients that are moved to another node begin there with a fresh and full bucket. For a coarse protective limit this is often acceptable, and a number of large systems operate in exactly this way.

A shared counter store

In the second arrangement all the limiter nodes keep the buckets in 1 shared in-memory store, so that a request works on the same bucket whichever node it reaches. This is the arrangement our design adopts.

It brings with it a problem that did not exist on a single machine. Updating a token bucket consists of 3 steps: reading the bucket, computing the new number of tokens, and writing the result back. When 2 limiter nodes carry out these steps for the same client at the same time, the steps of one may be interleaved with the steps of the other.

Each node saw 1 token and forwarded a request, and the bucket lost only 1 token. No error is reported anywhere. The limit has been exceeded, and it will be exceeded more often the more traffic the client sends, so that the fault is at its worst in exactly the circumstances for which the limiter was installed.

The remedy is to make the 3 steps indivisible. The limiter sends the store a single request whose meaning is “bring this bucket up to date, remove 1 token if there is one, and report the outcome”, and the store carries out the whole of it before attending to any other request for the same bucket. In-memory stores provide for this in 2 ways: by executing a small script inside the store as one unit, or by offering a compare-and-set operation that writes a value only if it has not changed since it was read, as described in chapter 1. The fixed window is the easy case here, since its entire update is “add 1 and return the new value”, which every store of this kind offers as a single operation.

The same reasoning extends to time. If every limiter node supplies its own clock reading with its request, then 2 nodes whose clocks differ by 20 ms will cause the recorded time of a bucket to jump backwards and forwards, and the refill calculation will sometimes be presented with a negative interval and sometimes credit the same 20 ms twice. This is avoided by letting the store apply its own clock to every bucket, so that all the updates of a bucket are measured against a single clock.

What the shared store costs is 1 network round trip per request, well under 1 ms within a data centre, together with a new dependency, since the limiter can now do its work properly only while the store is reachable.

Local tokens obtained in batches

The third arrangement retains the shared store and avoids consulting it for every request. A limiter node asks the store for a batch of tokens on behalf of a client, say 10, and serves the next 10 requests of that client from its own memory, returning to the store only when the batch is spent.

The number of calls to the store is thereby divided by the batch size, and the price is a loss of accuracy at the margins. Tokens lying unused in the memory of one node are unavailable to the others, so that a client may be refused at one node while another still holds tokens for it, and a node that crashes takes its unspent tokens with it. The larger the batch, the fewer the calls and the coarser the count.

For this design we choose the shared store. A single in-memory store handles 50000 checks per second comfortably, and non-functional requirement 0 leaves room for the round trip.

What a refused caller should be told

A refusal is a message addressed to a program, and whether the limiter reduces the load on the system or multiplies it depends on what that program does next.

Consider a client that responds to 429 by retrying at once. It is refused again, and retries again, and the limiter finds itself answering many times more requests from this client than it did before the limit was reached. Each refusal is cheap, but the total is not negligible, and none of it is of any use. The Retry-After header exists to prevent this, by telling the client the earliest moment at which a further attempt can succeed. With a token bucket that moment is easily calculated, since the limiter knows how many tokens are lacking and how quickly they arrive.

A second effect arises when many clients are involved. Suppose that 1000 clients are refused within the same second, perhaps because a brief outage caused all of them to retry together, and that each is told Retry-After: 2. Exactly 2 seconds later 1000 requests arrive at the same instant. This is known as a thundering herd, and the remedy lies with the clients, which should wait for the stated time and then for an additional random interval, called jitter, so that their retries are spread out. Retries, lengthening pauses and jitter are treated in detail in chapter 13.

The limiter’s own boundary can also be made less abrupt. Some systems maintain 2 thresholds, adding a warning header to responses once the lower one is passed and refusing only at the higher. An operator who is about to introduce a new limit can first run it in a mode that merely records which requests it would have refused, and after a week the record will show whether the limit would have harmed legitimate clients, before any client has actually been turned away.

When the limiter itself fails

The limiter depends on the counter store, and the store may become unreachable. Each request then confronts the limiter with a decision for which no good answer exists: it cannot count, and it must nevertheless either forward the request or refuse it. To forward it is to fail open, which keeps the API available and leaves it unprotected for the duration. To refuse it is to fail closed, which keeps the API protected and makes it unavailable to everyone.

For the general protection of an API we fail open. The limiter exists in order to keep the API available, and if a fault in the limiter’s own store were to make the API unavailable, the limiter would have brought about the very outage it was installed to prevent. It should also be remembered that at most moments no client is misbehaving, so that an hour without limits will usually pass without incident.

Failing open need not mean having no limit at all. When the store cannot be reached, each limiter node can fall back on buckets in its own memory, in the manner of the first arrangement above, with every node enforcing its share of each limit. The count is coarser than usual, and a client that goes badly wrong is still contained.

For some limits the decision must be reversed. A limit on login attempts, on password resets, or on calls each of which costs money is a control on security or expenditure, and to forward requests without limit in those cases is worse than to refuse them. Such limits fail closed, and a sound design names them one by one, since a single switch for the whole limiter cannot serve both kinds.

The store itself can be run as a leader with followers, as in chapter 3, so that the loss of 1 machine does not make it unreachable. After a change of leader the new leader may lack the most recent updates, because an in-memory store commonly replicates without waiting for a majority to confirm. For buckets this is harmless, amounting to a few extra tokens for a few clients, and it is the eventual consistency of non-functional requirement 2 as it appears in practice.

The design, deployed

At 50000 requests per second, no component of the design is a single machine. Clients reach 1 of 3 zones, each with a pair of load balancers in front of 10 API gateways. Every gateway asks a limiter node in its own zone, and the 9 limiter nodes are interchangeable, since none of them holds a bucket. All of them read and update the buckets in a single counter store, which runs as a leader with 2 followers in the other zones. Only requests that pass reach the 100 API servers, which are the reason for the whole arrangement and by far the largest tier.

How real systems do it

The algorithms of this chapter are all in production somewhere, and the published accounts agree closely with what was said of each.

Stripe has described 4 limiters that it runs in front of its API. The most important is a request rate limiter for each user, built as a token bucket whose state is held in an in-memory store, as in this chapter. Beside it is a limiter on the number of requests a user may have in progress at once, which catches expensive requests that a rate alone would miss. The other 2 are load shedders, which act on the state of the whole system and reserve capacity for critical requests, and which are the load shedding that the opening section distinguished from rate limiting.

Cloudflare chose the sliding window counter for the limiter at its edge and published a measurement of its accuracy. Over 400 million requests from 270000 sources, the estimate from 2 counters wrongly allowed or refused 0.003% of requests, with an average difference of 6% between the estimated and the true rate. This supports the statement above that the error is small for real traffic, and it should be read with the caution that it describes 1 network’s traffic.

The generic cell rate algorithm comes from the standards for ATM networks of the 1990s, and it is the basis of several widely used limiter libraries. Envoy, a proxy commonly used as a gateway, offers both arrangements described under counting on many machines: a token bucket local to each proxy, and a call to a shared rate limit service, and the 2 can be combined, with the local one as a first line of defence in front of the shared one. The response headers shown in the API section follow a draft of the IETF, which has changed between versions and is not yet a standard, whereas the status 429 and the header Retry-After are standardised.

One technique in common use is missing from this chapter. A well-behaved client can limit itself adaptively, lowering its own rate when it sees refusals and raising it slowly when it does not, which the AWS client libraries do with a token bucket for retries. Chapter 13 describes the same idea from the side of the caller.

Mistakes to avoid

Failures

Trade-offs

The simulation

References

• P. Tarjan, “Scaling your API with rate limiters”, Stripe engineering blog, 2017.
• J. Desgats, “How we built rate limiting capable of scaling to millions of domains”, Cloudflare blog, 2017.
• ATM Forum, Traffic Management Specification Version 4.0, 1996, for the generic cell rate algorithm.
• RFC 6585, Additional HTTP Status Codes, 2012, for status 429.
• RFC 9110, HTTP Semantics, 2022, for Retry-After.
• IETF HTTP API working group, “RateLimit header fields for HTTP”, Internet-Draft.
• Envoy proxy documentation, “Global rate limiting” and “Local rate limiting”.

Terms introduced in this chapter