Token bucket algorithm: an interactive rate limiter

A token bucket rate limiter gives each client a bucket that holds up to b tokens and refills at r tokens a second. Every request spends one token. When the bucket is empty, requests are rejected with 429 Too Many Requests until it refills. The client gets r requests a second on average, and can burst up to b at once after a quiet spell.

The playground runs the same requests through four limiters set to the same rate and burst: a token bucket, a leaky bucket, a fixed window and a sliding window. They agree on steady traffic and disagree on bursts. Try a burst, then a burst at a window edge.

How the token bucket works

1. The bucket starts full, with b tokens.
2. It refills continuously at r tokens a second, and never holds more than b. In code there is no timer: on each request, add the time since the last refill times r, then cap at b.
3. A request takes one token and goes through. With fewer than one token left, it is rejected straight away, not queued.

So over any stretch of t seconds a client gets at most b + r × t requests: a burst of b and then r a second. A client that stays under r never notices it. The whole state is two numbers per client, the token count and the time of the last refill.

Token bucket vs leaky bucket

Both have a capacity and a rate, and both allow r a second over time. The difference is what comes out. A token bucket passes a burst through at once, so the traffic behind it can be bursty. A leaky bucket puts requests in a queue and lets one out every 1 / r seconds, so the traffic behind it is smooth, but requests wait, and when the queue is full new ones are rejected. In the playground, send a burst and watch the leaky bucket's dotted lines: each one is a request waiting its turn.

Use a token bucket to cap what a client may send to an API. Use a leaky bucket in front of something that needs a steady rate, such as a payment provider or an email sender with a strict per-second quota.

Token bucket vs fixed and sliding windows

A fixed window counts requests per block of time, say 10 per 2 seconds, and resets the count at each boundary. It is one counter per client and very cheap, but a client can send 10 just before a boundary and 10 just after it: twice the limit in a fraction of a second. The playground's “burst at a window edge” does exactly that.

A sliding window asks, at every moment, how many requests there were in the last 2 seconds, so it has no edge to exploit. The exact version keeps a timestamp per request; the usual production version, the sliding window counter, keeps the current and previous counts and weights the previous one by how much of it still overlaps.

Which to use

For an API, the token bucket is the usual answer: it is cheap, it forgives the occasional burst that real clients produce, and its two numbers map directly onto a product promise (“100 requests a second, bursts of 200”).

A token bucket in Redis

Across many API servers the bucket has to live in one place, and the refill, the check and the spend must happen as one step, or two servers can spend the same last token. A Lua script in Redis does all three atomically:

-- KEYS[1]: the client's bucket   ARGV: capacity, rate a second, now in ms
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])

local b      = redis.call('HMGET', KEYS[1], 'tokens', 'at')
local tokens = tonumber(b[1]) or capacity   -- a new client starts with a full bucket
local at     = tonumber(b[2]) or now

tokens = math.min(capacity, tokens + (now - at) / 1000 * rate)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'at', now)
-- idle for capacity / rate seconds, the bucket is full again: nothing worth keeping
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000))
return allowed and 1 or 0

Pass the time in from the caller, or read Redis’s own TIME so every server uses one clock. When Redis is unreachable, decide in advance whether to fail open (let traffic through) or closed; for most APIs, open is the kinder failure.

In a system design interview

Name the algorithm and the numbers in one sentence: “A token bucket per API key, refilling at 100 a second with room for 200, kept in Redis and updated by a Lua script so refill and spend are atomic; over the limit we return 429 with Retry-After.” Then expect the follow-ups: what happens when Redis is down, how limits work across regions (each region enforces its share, or buckets sync asynchronously), and how to stop one hot key from overloading a Redis shard.

Watch a strong candidate design a rate limiter, turn by turn, or read the rate limiting algorithms guide for running them across a fleet.

Questions people ask