Token bucket

Every algorithm so far treats a burst as a problem. Plenty of bursts are ordinary: a page loading six things at once, or a client that has sat idle for a minute and now has work to do.

The token bucket allows those on purpose. Tokens accumulate at a steady rate, a request spends one, and a client who has been quiet has some saved up.

Leaves and caterpillars

A plant holds at most five leaves and grows three a day. Each caterpillar that arrives eats one leaf, and a caterpillar with no leaf left doesn't make it.

Day	Leaves grow	Caterpillars	Outcome	Leaves left
1	3	2	Both eat	1
2	3, so 4 total	5	4 eat, 1 doesn't	0
3	3	0	Nothing happens	3
4	2, capped at 5	0	Nothing happens	5

Three ideas in that table:

• A leaf is a token, and one request spends one.
• Tokens arrive at a fixed rate, whether anyone is asking or not.
• The plant cannot hold more than its capacity, so day four grows two rather than three.

The capacity is what allows the burst. A full bucket can be spent all at once, so a client who has been quiet can send five requests in an instant and then has to wait for more to grow.

The refill rate sets the long-run average. The capacity sets how big a burst you tolerate.

JunoLeaves and caterpillars Day four is the one worth pausing on. Three leaves would normally grow and only two do, because the plant is already at four and cannot hold six.

That cap is the whole reason a burst has a size limit. Without it, a client idle for an hour would come back able to send an hour's worth all at once.

JunoLeaves and caterpillars Two knobs, and they do different jobs. Refill rate is the sustained throughput you're willing to serve. Capacity is how much of it a client may save up and spend at once.

So a bucket of 10 refilling 6 every 3 seconds averages 2 per second and tolerates 10 at once. Same average, very different feel from 2 refilling 2 every second.

JunoLeaves and caterpillars Capacity is also your worst case, and it should be sized against what the endpoint can actually absorb. A bucket of 10,000 averages out fine and can still land 10,000 requests in one instant, which is the number your database sees.

The other cost is state: a bucket per client means a token count and a last-refill timestamp for every client you have seen, which is more than a fixed window's counter and less than a sliding log's list of timestamps.

Production implementations usually skip the timer entirely and compute tokens lazily on read, from the elapsed time since the last refill. No background job, and buckets for idle clients cost nothing until they come back.

Building the bucket

The state is two numbers, and the logic is two decisions.

class TokenBucket {
  constructor(capacity, refillRate, refillInterval) {
    this.capacity = capacity
    this.refillRate = refillRate
    this.refillInterval = refillInterval
    this.tokens = capacity          // start full
    this.secondsSinceLastRefill = 0
  }

  processRequests(numRequests) {
    this.secondsSinceLastRefill += 1

    if (this.secondsSinceLastRefill >= this.refillInterval) {
      this.tokens = Math.min(this.capacity, this.tokens + this.refillRate)
      this.secondsSinceLastRefill = 0
    }

    const accepted = Math.min(numRequests, this.tokens)
    const rejected = numRequests - accepted

    this.tokens -= accepted

    return { accepted, rejected }
  }
}

Both Math.min calls are doing the real work.

The first caps the refill at capacity, so tokens never exceed the ceiling. The second caps acceptance at the tokens available, so a request for nine tokens against a bucket holding one accepts one and rejects eight.

>= on the refill check rather than == is deliberate. If a tick is ever missed, an exact comparison would skip the refill and the bucket would never fill again.

JunoBuilding the bucket Starting the bucket full is a choice, and a friendly one. A new client can act immediately instead of waiting for their first tokens to appear.

Starting empty would be stricter and would make anyone's first visit feel broken.

JunoBuilding the bucket Notice that a partially served round is possible: nine requests against one token gives one accepted and eight rejected, rather than refusing the lot.

That matters for how a client should respond. Some of their work succeeded, so retrying everything duplicates the part that already went through.

JunoBuilding the bucket This version advances time by counting rounds, which suits a turn-based game and not a server. Real traffic does not arrive on a tick, so production code stores a timestamp and computes accrual on read: elapsed time times rate, added to the current count, capped at capacity.

That also lets tokens be fractional, which matters at low rates. With integer accrual and a rate below one token per interval, a client can round down to zero forever and never recover.

Concurrency is the other difference. Two simultaneous requests both reading this.tokens before either writes will both be accepted against the same token, which is the same read-decide-write race that let 400 concurrent requests through a limit of 100 in a Redis counter. The check has to be atomic.

Parameters change everything

Two configurations, the same algorithm.

Capacity 10, refill 6 every 3 seconds. Roughly two per second sustained, with room for ten at once. Playing it out one second at a time:

Round	Requested	Accepted	Rejected	Tokens left
1	3	3	0	7
2	5	5	0	2
3	7	7	0	1, after refilling to 8
4	9	1	8	0

Generous. Bursts are absorbed, and running dry takes deliberate effort.

Capacity 8, refill 2 every 10 seconds. Now the first eight requests are free and then almost nothing is. Send five, then five more, and you're empty with eight seconds to wait for two tokens.

Same algorithm, completely different experience. A client under the second configuration has to think about when to spend, because tokens are scarce and slow to return.

JunoParameters change everything Worth trying the second configuration mentally before reading on. Eight tokens, then two more every ten seconds.

That's not a rate limit that shapes traffic. It's one that makes a client ration every request, and the algorithm did not change at all.

JunoParameters change everything The refill interval is the parameter people set carelessly, and it decides how the limit feels. Six tokens every three seconds and two every second average the same and behave nothing alike.

Long intervals mean long dry spells followed by a lump. Short intervals feel smooth. Prefer the shortest interval your storage can handle.

JunoParameters change everything Measured against a token bucket, 13 requests arriving at once against a bucket of 10 accepted exactly 10 and rejected 3, returning retryAfterMs: 500. Left idle for 3 seconds, the same bucket accrued 6 tokens.

That retryAfterMs is the thing to expose. A token bucket can compute precisely when the next token arrives, which a fixed window cannot, so a client can be told exactly how long to wait instead of guessing.

Return it in Retry-After and a well-behaved client stops hammering you. Omit it and their only strategy is to retry immediately, which is what you were trying to prevent.

Try it

A bucket with capacity 5, refilling 2 tokens every 2 seconds, starting full.

1. A client sends 5 requests at once. How many are accepted, and what's left?
2. Two seconds later they send 3. What happens?
3. The client then waits 10 seconds. How many tokens do they have?
4. What's the sustained rate this bucket allows, and what's the largest burst?

Compare your answers

1. All 5 accepted, 0 left. The bucket starts full and a request spends one token. Emptying it in one instant is the burst the capacity exists to allow.

2. Two accepted, one rejected. Two seconds have passed, so the bucket refills by 2. Three requests arrive against 2 tokens, so Math.min(3, 2) accepts two and the third is refused.

3. Five, not ten. Ten seconds would accrue 10 tokens, and capacity caps it at 5. This is the day-four rule: idle time does not bank indefinitely, which is what stops a long-quiet client returning with an enormous burst.

4. One per second sustained, five at once. Two tokens every two seconds is the long-run average, and capacity 5 is the largest instantaneous burst.

Question four is the pair worth remembering. Refill rate and capacity answer two different questions, and quoting a token bucket as a single number loses one of them.

Where this goes next

The token bucket lets a client decide when to spend, so traffic reaching your server stays uneven. Bounded, but uneven.

Leaky bucket takes the other approach: accept the burst, then release it at a steady rate, so what the server sees is smooth no matter how it arrived.