Distributed systems · 10 min

Token bucket

A rate limit with two knobs: how fast permits come back, and how many can pile up. Set both and a real app’s burst gets through while a flood does not.

Your public API promises each user 5 requests a second. Then your own mobile app ships a new home screen. When it opens, it fires 10 calls in the same instant: profile, feed, settings, notifications and six more.

Half of them come back with an error, and the home screen is blank. Nobody misbehaved. The app made 10 calls once and then went quiet. Yet a script hammering you in a loop also has to be stopped. How does one limit tell those two apart?

The wrong way first: count per clock second

This is the wrong way, but it is the first one everybody writes. Keep a counter per user. Allow the call if the counter is under 5, and reset the counter to 0 whenever the clock ticks over to a new whole second. This is called a fixed window.

It fails the app: 10 calls at once means 5 allowed and 5 refused, every time the app opens. And it fails the other way too.

So the fixed window is too strict for the honest app and too loose for anyone who times their requests around the edge. What we want is one rule that forgives a short burst but still holds everyone to 5 a second over time.

A bucket of permits

Give each user a bucket of tokens. A token is a permit for one request. Each request takes one token out. No token left means 429.

Tokens drip back in at a steady speed, but the bucket has a size, and tokens that arrive when it is full spill over and are lost. That gives you exactly two knobs:

• Refill rate, r: how many tokens come back per second. This is the long-run speed limit.
• Bucket size, b: the most tokens the bucket can hold. This is the biggest burst you forgive. The demo calls it Capacity.

Walk the app through a bucket with b = 5 and r = 5. It starts full, with 5 tokens. The 10 calls arrive at once: the first 5 take the 5 tokens, and the other 5 find it empty and get 429. A tenth of a second later, 0.1 × 5 = 0.5 tokens have dripped back: still not enough for one request.

Yes, half a token. Tokens drip in smoothly rather than one at a time, so the bucket can hold a fraction. A request needs one whole token, and a refused request costs nothing.

The server does not need a timer ticking for every user. It stores just two numbers per user: tokens left, and the time it last looked. When a request arrives, it works out how much dripped in since then (seconds passed × r), adds it, caps the total at b, and then decides.

Turn the bucket size all the way down

With b = 1, the bucket holds a single token. One request passes, and any request in the next 1/r seconds (0.2 s at r = 5) is refused, not queued. Only perfectly evenly spaced callers get everything through.

That sounds tidy, but real clients don’t send evenly spaced requests. You saw the app get 1 success and 9 refusals. A web page that fires four API calls at once to fill its widgets breaks the same way. A tiny bucket refuses every burst, even from callers who stay well under 5 a second on average.

Turn it all the way up

Now make b = 1,000. Your app is happy: its 10 calls barely dent the bucket. But a user who has been quiet for a few minutes now has 1,000 tokens saved up, and a script can spend all of them in the same second.

Your servers sized for “5 a second per user” just got 1,000 requests from one caller at once. A huge bucket does nothing against a short flood. It only starts refusing once all 1,000 are spent, and by then the damage is done.

The refill rate is the promise

The other knob is simpler. However big the bucket, tokens only come back at r a second, so over a long run nobody gets more than r a second. That is why, at r = 1, the steady caller got only 1 request in 3 once its stored tokens ran out.

Put the two knobs together and you can say exactly the most a user can get through. Take b = 10 and r = 5. In any 1-second stretch, starting at any moment, not just on the clock’s whole seconds: at most the 10 already in the bucket plus 5 that drip in, so 15. In any 60 seconds: 10 + 5 × 60 = 310, barely above the 300 that “5 a second” promises.

In general, in any T seconds a user gets at most b + r × T requests. Over short stretches the b part dominates: that is the burst. Over long ones the r × T part dominates: that is the rate. The fixed window has no such cap on short stretches, which is why it allowed 10 in 0.05 s.

Where to set the dial

Set r from what you can afford: the steady load your servers can carry per user, or what the customer’s plan pays for. Set b from the biggest burst an honest client really makes, with a little room above it. Your app opens with 10 calls, so b = 15 lets it through with room to spare, and a script still can’t get more than 15 in one go.

Then sanity-check the busiest single second: b + r requests, 20 here. If one user sending that many at once would hurt your servers, the bucket is too big.

The whole limiter in a few lines

Look for the refill line: it is the only clever part, and it runs only when a request arrives.

b = 15                        # bucket size: biggest burst
r = 5                         # refill: tokens per second
buckets = {}                  # user -> (tokens, last_seen)

allow(user, now):
    tokens, last = buckets.get(user, (b, now))
    tokens = min(b, tokens + r * (now - last))   # drip in, cap at b
    if tokens >= 1:
        buckets[user] = (tokens - 1, now)
        return ALLOW
    buckets[user] = (tokens, now)
    return REFUSE(429, retry_after = (1 - tokens) / r)

The reply tells the client when to try again in a Retry-After header, so a well-behaved app waits instead of retrying straight away. If 5 refused calls all retry at exactly 0.20 s, only 1 token is there, so good clients also add a small random delay to spread them out.