Token bucket

A token bucket holds up to a fixed number of tokens. Tokens refill at a steady rate. Each request takes one token, or several for an expensive request. If the bucket is empty, the request is rejected. Two numbers control it: how fast tokens refill, and how many the bucket holds.

The big idea

Think of a water tank with a slow tap. The tap refills it at a steady rate. You can draw a big cup at once if the tank is full, but after that you are limited to the flow from the tap.

The two dials match product language. The refill rate is the sustained throughput you promise. The capacity is the burst you tolerate. A client that has been idle for a while has a full bucket and can spike. A client that keeps pushing is held to the refill rate.

The analogy breaks at one point. A tank is physical, but a bucket in a rate limiter is just two numbers and a timestamp. You never run a timer. You compute the refill from the time elapsed when a request arrives.

Walking through it

This version takes the time as an input so the output is repeatable:

class TokenBucket {
  private tokens: number
  private last = 0

  constructor(private capacity: number, private refillPerSec: number) {
    this.tokens = capacity
  }

  take(nowMs: number, cost = 1): boolean {
    const elapsedSec = (nowMs - this.last) / 1000
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSec * this.refillPerSec)
    this.last = nowMs
    if (this.tokens < cost) return false
    this.tokens -= cost
    return true
  }
}

const bucket = new TokenBucket(50, 10) // burst of 50, sustained 10 per second
let burst = 0
for (let i = 0; i < 55; i++) if (bucket.take(0)) burst++
console.log("t=0s allowed:", burst)

let later = 0
for (let i = 0; i < 15; i++) if (bucket.take(1000)) later++
console.log("t=1s allowed:", later)

Output:

t=0s allowed: 50
t=1s allowed: 10

At t=0 the bucket starts full, so 50 requests pass and the rest are rejected. One second later, 10 tokens have refilled, so exactly 10 more pass. Over any interval of length T, at most capacity + rate × T requests get through.

A leaky bucket is the same idea seen from the output side. Requests drain at a fixed rate, and overflow is dropped. The token bucket lets bursts through immediately. The leaky bucket smooths them out.

Common mistakes

• Setting capacity equal to the average rate. Clients that batch their calls get throttled even though their average is fine. Give the bucket room for a burst.
• Making the burst too large. One client can drain a shared backend in a single spike.
• Charging every request the same. Use cost for expensive requests, so one heavy call uses more tokens.

Check yourself

1. A bucket holds 50 tokens and refills 10 per second. It is empty at t=0. How many requests pass at t=2 s?

   Answer: 20. Two seconds of refill at 10 per second is 20 tokens.

2. Why does the bucket need no timer?

   Answer: it works out the refill from the elapsed time whenever a request arrives.

Key takeaways

• A token bucket has two dials: a sustained rate (refill) and a burst size (capacity).
• It allows bursts up to the capacity, then holds the client to the refill rate.
• Refill is computed lazily from elapsed time, so no background timer is needed.
• Use cost to make expensive requests draw more tokens.

Further learning

Next, see what changes when many servers share one bucket. The distributed limiter on Redis covers the race condition and the atomic script that fixes it.