Rate Limiter

What it is

A rate limiter protects a service from too many requests. Each caller gets its own allowance. It allows a short burst but limits traffic over time. API gateways use this to keep one caller from slowing everyone else down.

The core idea

Give every key a small amount of allowance that starts full, at the burst size. Allowance refills smoothly over time, at ratePerSec per second, up to that same burst size and never past it. An allowed request spends one unit of allowance. When none is left, deny the request. Elapsed time controls how much allowance comes back since the last check. Concurrent callers must share that allowance safely, without two callers spending the same unit. This design is called a token bucket. It needs only a small amount of state per key, but tracking many keys still costs memory, so old keys need to be dropped eventually.

Other designs

GCRA tracks the next moment a request is allowed, instead of counting units of allowance. It lands on the same behavior as a token bucket through different bookkeeping. A sliding log keeps a short list of recent request times per key and counts how many fall inside the latest stretch of time, as long as that stretch and its size are scaled correctly to the burst and rate. A fixed window, a counter that resets to zero every time the clock crosses a fixed point such as the start of a new second, is not enough. A caller can send a burst just before the reset and another burst just after it, letting close to double the promised amount through in that short stretch.

Real time, not simulated time

The grader runs your limiter against the real system clock, in real workers, and measures how much real time your run actually took. The pass and fail ranges it checks are worked out from that real time, not from a fixed, idealized duration, so ordinary timing jitter from a busy machine will not unfairly fail an honest limiter.

The heavy traffic stage also checks short rounds with 8 callers sharing one key. The key starts with an allowance of 1,000 and refills at 1 per second. Each caller keeps asking until denied. Exactly 1,000 requests should get through before a whole unit can refill. The tester only uses rounds shorter than half a second for this check. A longer round is inconclusive, not a failure. Each time the tester runs this check, it runs at least 400 rounds and at least 10 seconds, so a fast limiter gets many more rounds. If your limiter is slow, the tester checks fewer rounds in the time it has, but always at least 100.

Where you meet this

• Stripe wrote in 2017 that it uses "the token bucket algorithm" for its API rate limits, one bucket per user. (Scaling your API with rate limiters)
• Amazon API Gateway throttles with a token bucket. You set a rate (tokens added per second) and a burst (the bucket size), and too many requests get 429 Too Many Requests. (API Gateway throttling)
• nginx limit_req limits requests per key, usually the client address, with a burst setting. It uses the leaky bucket method, so requests inside the burst allowance wait in line, and requests past it are refused. (ngx_http_limit_req_module)
• Cloudflare described in 2017 how it counts with two fixed windows, the current one and the one before, and weighs the old one by how much of it still overlaps the last minute. That fixes most of the double burst of a plain fixed window and needs only two numbers per counter. (Counting things)

When to choose a token bucket: you want to allow short bursts but hold a steady average, and you want small, fixed memory per key.

When not to: you must never allow more than N requests in any window at all, even across a burst. A sliding log (one timestamp per request) is exact but uses much more memory. If extra requests should wait instead of failing, a leaky bucket that queues them, like nginx, fits better.

Common bugs

• Sharing one allowance across all keys.
• Mixing milliseconds and seconds.
• Using a calendar clock that can jump backward.
• Dropping small refill amounts by rounding too early.
• Letting two callers spend the same unit of allowance.
• Doing slow work inside Allow.

Check it yourself

Try a burst, then evenly spaced requests. Test two keys at the same time. Neither should use the other's allowance. Keep per-key storage bounded.

Learn more

GCRA descriptions explain the arrival-time design. Redis rate-limiting guides show how this logic can be shared across servers.

Go to the Rate Limiter challenge