Rate limiter simulator

Each row is one rate limiter, and all five receive exactly the same requests. A green dot is a request that was let through, drawn at the moment it was let through; a short red mark is a request that was rejected. For the leaky bucket, a dashed line joins a request's arrival to the moment it leaves the queue. The panel beside the rows explains what each limiter decided about the most recent request.

The limit applies to all five. With "5 per second", the token bucket gains 5 tokens a second, the leaky bucket lets out 5 requests a second, and the window-based limiters allow 5 requests in each one-second window. The bucket size sets how many tokens the token bucket can hold and how many requests the leaky bucket can queue.

Try these:

• Press Send 10 in 0.1 s. The token bucket lets through as many as it has tokens and rejects the rest; the leaky bucket queues them and lets them out one at a time; the window limiters allow up to the limit.
• Press Burst across a window edge. It sends a full limit's worth just before a whole second and another just after. The fixed window allows both, and its "most in any 1 s" figure goes to twice the limit. The sliding window log never goes above the limit.
• Turn on Background traffic at 6 or 12 per second, which sends requests at random moments at that average rate, and compare where each limiter rejects.
• Set the bucket size to 20 and send a few bursts. The token bucket now lets much larger bursts through, while its long-run average stays at the limit.

"Most in any 1 s" is measured from the run: it is the largest number of requests let through within any one-second stretch so far. The clock stops while the page is hidden, and Pause stops it too.

Rate limiting is a way of controlling how many requests a client may make in a period of time, such as 100 requests per minute per API key. Requests over the limit are rejected, usually with the HTTP status 429 Too Many Requests, or held back until they fit.

Services limit request rates for several reasons. A limit stops one client from using up capacity that others need, whether by accident (a script stuck in a loop) or on purpose (scraping, password guessing, a denial-of-service attack). It protects systems that are slow or expensive to call, such as a database or a paid third-party API. And it turns a service's capacity into a published allowance that clients can plan around.

Every rate limiter answers the same question for each request: has this client already used its allowance for the current period? The algorithms differ in what "the current period" means and in how much they remember, and those differences show up as different behaviour with bursts.

A token bucket holds up to B tokens and gains new tokens at a steady rate of r per second; when it is full, new tokens are thrown away. Each request takes one token. If the bucket is empty, the request is rejected.

The two numbers mean different things. The rate r is the long-run average the client can keep up. The bucket size B is how large a burst can be: a client that has been quiet for a while has a full bucket and can send B requests at once. Over any period of T seconds, a token bucket lets through at most B + r × T requests.

A token bucket needs only two values per client: the number of tokens and the time they were last counted. No timer is needed to add tokens. When a request arrives, the limiter works out how many tokens would have been added since the last request, adds them (up to B) and then checks for a token. The simulator does it this way.

The name leaky bucket is used for two different designs, which causes some confusion.

As a queue

Requests join a queue of fixed size and leave it at a steady rate, like water dripping from a hole in a bucket. If the queue is full when a request arrives, the request is rejected. The output never bursts: it is at most r requests per second however the input arrives. The cost is delay, since a request that joins the back of a full queue of B waits about B / r seconds. This is the version in the simulator. It suits a service behind the limiter that needs a steady flow, such as a payment provider or an SMS gateway with limits of its own.

As a meter

Here nothing is queued. The limiter keeps a level that drains at rate r; each request adds one, and a request that would make it overflow is rejected. This version makes exactly the same decisions as a token bucket with the same rate and size; it counts used capacity instead of remaining capacity. NGINX's limit_req module, which its documentation calls a leaky bucket, works this way, with an optional queue for requests over the rate.

GCRA

The generic cell rate algorithm (GCRA), from ATM networks, is a compact form of the meter. It stores a single timestamp per client, the "theoretical arrival time" at which the client would be exactly on schedule. A request is allowed if it does not arrive too far ahead of that time, and each allowed request moves the time forward by 1/r. Brandur Leach's redis-cell module and several rate limiting libraries use it.

A fixed window limiter divides time into windows of equal length, such as each whole minute, and keeps a counter per client per window. Each request adds one to the counter for the current window; once it reaches the limit, further requests are rejected until the next window starts and the count goes back to zero. It is the easiest limiter to write. With a shared store such as Redis it is one increment on a key named after the client and the window, set to expire when the window ends.

Its weakness is the boundary between windows. A client can send the full limit at the end of one window and the full limit again at the start of the next, so twice the limit passes in a short time even though neither window went over. With a limit of 100 per minute, 200 requests can pass within a couple of seconds either side of 12:01:00.

A sliding window limiter counts requests over the period just before each request, for example the last 60 seconds, instead of over calendar windows. There are two common ways to do it.

Sliding window log

The limiter stores the time of every allowed request. For each new request it drops the times older than the window and counts the rest; if the count has reached the limit, the request is rejected. This is exact: the limit holds over every stretch of time of the window's length. The cost is memory in proportion to the limit, one timestamp per request, so a limit of 5,000 requests per hour means up to 5,000 timestamps for each client. In Redis it is usually built on a sorted set, removing old entries with ZREMRANGEBYSCORE and counting with ZCARD.

Sliding window counter

This version keeps only two counters per client: the count for the current fixed window and the count for the previous one. It estimates the number of requests in the last full window by assuming the previous window's requests were spread evenly, and counting only the part that still overlaps:

estimate = previous × (1 − elapsed fraction of the current window) + current

For example, with a limit of 50 per minute, 15 seconds into the current minute, 42 requests in the previous minute and 18 so far in this one, the estimate is 42 × 0.75 + 18 = 49.5. Cloudflare described this method in 2017 and reported that, across 400 million requests from 270,000 sources, only 0.003% were wrongly allowed or rate limited. Because it is an estimate, it can let through somewhat more than the limit when the previous window's requests were bunched at its end, which the simulator's "most in any 1 s" figure can show.

An HTTP service that rejects a request for exceeding a rate limit normally responds with status 429 Too Many Requests, defined in RFC 6585 in 2012. The response can include a Retry-After header giving the number of seconds to wait, or a date. Before 429 existed, services used other codes such as 503 Service Unavailable or 403 Forbidden, and some still do.

Many APIs also report the client's remaining allowance on every response, so that clients can slow down before they are rejected. GitHub's REST API, for example, sends x-ratelimit-limit, x-ratelimit-remaining and x-ratelimit-reset. An IETF draft, RateLimit header fields for HTTP, aims to standardise headers of this kind.

How clients retry matters as much as the limit. If every rejected client waits exactly the time in Retry-After, they all come back at the same moment and are rejected together again. Clients should wait longer after each rejection and add a random amount, called jitter, to each wait, as Marc Brooker of AWS described in 2015. The retry strategy simulator shows the difference.

A limit applies per key, and the choice of key decides what the limit protects against.

• API key or user. The most precise choice, but it only works for requests that are authenticated.
• IP address. Works before login, which is where password guessing and scraping happen. Many people can share one address behind an office or mobile network gateway, and an attacker can use many addresses. With IPv6 one customer usually has a whole block of addresses, so limits are applied to a prefix such as a /64 rather than to single addresses.
• Endpoint. Expensive operations, such as a report export or a login attempt, get tighter limits than cheap ones.
• Account or tenant. In a service sold to businesses, one limit can cover all of a customer's users.

Real services usually combine several of these, and a request has to pass all of them. Some also give requests different costs, so that one bucket covers a mix of cheap and expensive calls.

The simulator's limiters each live in one place. A real service usually runs on many servers behind a load balancer, and a limit kept separately on each of ten servers lets a client through ten times over. There are three common answers.

• A shared store. Every server checks and updates the same counters, usually in Redis. The check must be atomic, so that two servers cannot both take the last token; a Lua script or a single command such as INCR does this. Each request then waits for a network round trip to the store.
• Local limits with a share each. Each server enforces part of the limit on its own, for example a tenth of it with ten servers. There is no extra network call, but the limit is only right when traffic is spread evenly.
• Both. A generous local limit absorbs floods cheaply, and a shared limit enforces the real quota. Envoy offers both: a local rate limit filter that runs a token bucket in each proxy, and a global rate limit filter that asks a separate service backed by Redis.

A shared limiter is also a dependency that can fail. If the store cannot be reached, the limiter can fail open and allow every request, or fail closed and reject them all. Most services fail open, because rejecting all traffic is an outage of its own; Envoy's global rate limit filter allows requests by default when its rate limit service is unavailable.

Redis is the usual shared store for rate limits because its commands are atomic and fast, and keys can expire on their own. The simplest version is a fixed window: one counter per client per window, created with an expiry so that old windows clean themselves up. The two commands run as one transaction.

“Design a rate limiter” is a common system design interview question. A good answer covers these points in roughly this order:

• Requirements. What is limited (users, API keys, IP addresses), the limits themselves, whether a limit must be exact, and how much latency the check may add. A limiter that runs on every request usually has to answer in about a millisecond.
• Where it runs. In an API gateway or reverse proxy in front of the services, in a shared library inside each service, or both.
• The algorithm. Usually a token bucket, for its burst handling and tiny state; a sliding window if the limit must hold over every period. Explain the fixed window’s boundary problem and why you avoid it.
• Storage. Counters in Redis, updated atomically with single commands or a Lua script, with keys that expire. Estimate the memory: a token bucket needs only two numbers per client, so even ten million clients take roughly a gigabyte of Redis memory, most of it per-key overhead.
• Many servers and regions. A central store is accurate but adds a network round trip; local limits are fast but approximate. Many designs combine a local limit with a shared one, and accept that limits are approximate across regions.
• The response. Return 429 with Retry-After and remaining-allowance headers, and expect clients to back off with jitter.
• Failure. Decide whether to fail open or closed when Redis is down, and monitor how many requests are rejected per key so that a badly set limit is noticed.

Rate limiting began in packet networks, where a network had to check that each sender kept to the traffic rate it had agreed. Jonathan Turner described the leaky bucket in 1986, in an article on future communication networks in IEEE Communications Magazine. In the ATM networks of the 1990s, the ATM Forum and the ITU defined the generic cell rate algorithm to police traffic cell by cell.

The token bucket became the standard way to describe traffic in IP quality-of-service work: RFC 2212 (1997) describes traffic by a token bucket rate and size, and RFC 2697 and RFC 2698 (1999) define packet markers built on token buckets.

On the web, rate limits became common as public APIs grew in the 2000s. The 429 status code was added in 2012 by RFC 6585. In 2017 Stripe and Cloudflare each published detailed descriptions of their limiters, which are still widely cited.