Rate limiting

An alert service sends a message about every earthquake of magnitude 5 or more. Usually that is about five a day, and a subscriber asks for one thing: no more than five an hour. On 29 July 2025 at 23:24 UTC an earthquake of magnitude 8.8 struck, and over the next hour 38 events came in, and over two days 189. Which alerts should be sent and which dropped? Below are four methods on these two days. Coloured marks went through, grey ones were dropped, and the bracket above the timeline shows how many went through in the busiest 60 minutes.

Only the log keeps the promise “no more than five in any 60 minutes”. The clock-hour window lets nine through, two counters seven, the bucket nine. But the bucket breaks the limit not by accident: that is how it is built, and that is its value. Let us see who promises what.

The idea

A limiter stands between a stream and whatever must be protected: a server, a subscriber, a channel. To each request it answers “pass” or “reject”, remembering as little as possible. There are four simplest methods.

A clock-hour window. Time is divided into hour-long intervals, each with a counter that resets at the boundary. One number per client, but up to 2N pass at a boundary: N in the last seconds of one hour and N in the first seconds of the next. That is exactly what happens in the scene: on the first night of the burst nine alerts pass in 60 minutes at the junction of two hours.

A log. Remember the time of every request let through, and pass a request if fewer than N went through in the last 60 minutes. The promise is kept exactly, but the memory is N moments per client: with a million clients and a limit of a thousand, that is already a billion numbers.

Two counters. A compromise Cloudflare described in 2017: a counter for the previous hour and one for the current hour, the previous one weighted by the share of the window that has not yet passed: estimate = previous·(1 − elapsed/hour) + current. It is a log under the assumption that the previous hour was even. On their own data, 400 million requests from 270 thousand sources, 0.003% were wrongly passed or rejected. A sharp burst is not even, and in the scene seven go through instead of five.

A token bucket holds up to b tokens and is refilled at r per second; at the start it is full. A request passes if there is a token, and takes it. The bucket allows a burst of up to b requests at once and after that lets through r per second on average: exactly what live traffic needs. Quiet builds up a reserve, a burst spends it.

What the bucket promises

The first part is an honest statement of what the scene shows: with b = 5 and five an hour, at most ten pass in any 60 minutes. The second part answers the question of how big a reserve is needed to lose nothing. Put a_j = j/r − t_j: the condition becomes b ≥ r·(a_j − a_i) + 1, and the largest difference is found in one pass with a running minimum. On all 19,073 events of 2015–2025 this gives:

At five alerts an hour a bucket of 74 is needed. The requirement was set by that same July burst: 105 events in a little over six hours. Note: in any single hour there were at most 38, yet the bucket needs almost twice that: a long burst drains it gradually, and over six hours the refill gives only 30 tokens. A bucket of five tokens would have lost 197 alerts in eleven years, almost all of them on a few days like this one.

The bucket in integers

A fractional number of tokens and a refill timer are unnecessary. Network devices compute the bucket differently, by the GCRA algorithm from the ATM standards: they store one number tat, the moment when the bucket would be full again. With interval I = 1/r, a request at moment t passes if t ≥ tat − (b − 1)·I, and then tat ← max(tat, t) + I. Each request let through pushes the “full bucket time” one interval forward, and idle time catches up with it. One integer per client, no timers and no division: this is how the bucket is implemented in the listings.

The same bucket has a second name, “leaky”: if requests in it are not dropped but wait their turn and drain out at a constant rate, it becomes a smoothing queue. In the role of a counter, as in GCRA, the “leaky bucket” and the token bucket are one and the same; nginx calls its limit_req directive a leaky bucket, and with the burst parameter it queues extra requests, while without it it rejects them.

Code

Four limiters on the same two days of earthquakes, five alerts an hour, and the computation of the smallest bucket for all eleven years.

The clock-hour window and the bucket let the most through, 114 and 120 of 189, but both allow nine in an hour. The log let the fewest through, 107, but never exceeded five. This is not “better” and “worse” but different promises: the log promises the subscriber “no more than five in any hour”, the bucket “no more than five an hour on average, plus a burst of up to five on top”.

What it costs

The clock-hour window, two counters and the bucket take O(1) time per request and one or two numbers per client. The log takes O(N) memory per client and O(N) time per request in a simple implementation (or amortised O(1) with a queue from which stale moments are dropped). For millions of clients the numbers themselves are kept in shared memory, for example in Redis, where a clock-hour window is done with the INCR and EXPIRE commands and a bucket with a short script that atomically reads and writes tat.

If there are many limiters on different servers, accuracy is limited not by the algorithm but by consistency: each server has its own bucket, and together they let more through. Then the limit is divided among the servers, or a shared counter is kept and its delay tolerated.

Where it works

Web servers. In nginx limiting is set by a pair of directives: limit_req_zone describes an address zone and a rate, and limit_req enables it for a path and sets the burst reserve.

APIs. Public APIs almost always limit their clients: GitHub’s REST API, for example, allows 5000 requests an hour for an authenticated user and 60 without a key. The service reports the remaining limit in response headers so that the client slows down by itself instead of getting rejections. A rejected client does well to retry not immediately and not all at the same time; see the article on retries with jitter.

Networks. The bucket in integers came from asynchronous transfer mode (ATM) telephone networks: there GCRA checked that a subscriber did not exceed the agreed cell rate, and the standards describe it as “a finite-capacity bucket whose real-valued content drains out at a continuous rate”.

History

The leaky bucket as a way to police the rate of a stream was described in 1986 by Jonathan Turner for cell-switched networks; later the ATM Forum and the ITU-T I.371 standard fixed it in the form of GCRA. The token bucket in its present form became the common language for describing traffic in networks with guaranteed quality of service, and with the growth of public APIs in the 2000s the standard request limiter. Cloudflare described two counters in 2017 as a cheap replacement for a log across millions of domains.

Problems

The first problem asks you to compare the clock-hour window and the bucket on one stream and find how many each lets through in the busiest W seconds. The second asks for the smallest bucket that loses nothing, including for all earthquakes of 2015–2025.