Token bucket
On the roadmap:Intermediate · step 6: Protecting services
A bucket that fills with tokens at a steady rate. Each request spends a token, so short bursts are allowed but the long-run rate is capped.
In plain words
Picture a bucket that fills with tokens at a steady pace. Every request must take a token out. If the bucket is empty the request waits or is refused. After a quiet spell the bucket is full, so a burst can go through at once.
Why it matters
Real traffic arrives in bursts. A token bucket lets a short burst pass while still holding the average to the refill rate, which is gentler on users than a hard per-second cut-off. Two numbers, the burst size and the refill rate, describe the whole policy.
Where you meet it
- Amazon API Gateway throttling: the rate is the refill and the burst is the bucket size
- API gateways and cloud services that answer 'too many requests'
- Network equipment that shapes traffic to a fixed rate
You will be able to
- Explain burst size and refill rate
- Refill from elapsed time instead of running a timer
- Charge different costs for different requests
In interviews
A standard answer to 'design a rate limiter'. Be ready to compare it with fixed and sliding windows.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- A bucket with a capacity and a refill rate
- Refilling by the time that has passed, never above the capacity
- take(cost) that spends tokens or says how long to wait
- An injectable clock so tests control time
export type Decision = { allowed: boolean; tokens: number; retryAfterMs: number };
export class TokenBucket {
private tokens: number;
private last: number;
/** capacity: the biggest burst. refillPerSec: how fast tokens come back. */
constructor(private capacity: number, private refillPerSec: number, private now: () => number = Date.now) {
this.tokens = capacity;
this.last = now();
}
private refill(): void {
const t = this.now();
this.tokens = Math.min(this.capacity, this.tokens + ((t - this.last) / 1000) * this.refillPerSec); // never above capacity
this.last = t;
}
/** Spend `cost` tokens if there are enough. Otherwise say how long until there will be. */
take(cost = 1): Decision {
this.refill();
if (this.tokens >= cost) {
this.tokens -= cost;
return { allowed: true, tokens: this.tokens, retryAfterMs: 0 };
}
return { allowed: false, tokens: this.tokens, retryAfterMs: Math.ceil(((cost - this.tokens) / this.refillPerSec) * 1000) };
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints token-bucket ok when everything passes. You need Node.js installed.
mkdir token-bucket && cd token-bucket
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Production keeps the bucket in a shared store such as Redis and updates it atomically, so every server sees the same tokens.
- Refilling from the time since the last request avoids a timer for every user. This lab does the same.
- Limits are layered: a bucket per user or key, one per endpoint, and a global one that protects the service.
- Responses carry the retry delay (a 429 with Retry-After), and clients should back off with some randomness.
Token bucket or something else?
| Allows bursts? | Memory per user | Smoothness | Pick it when | |
|---|---|---|---|---|
| Token bucket | Yes, up to the capacity | A number and a time | Holds the average, allows bursts | You want short bursts to pass |
| Leaky bucket | No: steady output | A queue | Perfectly smooth | You need a steady rate downstream |
| Fixed window counter | Up to twice the limit at a boundary | One counter | Coarse | A rough limit is enough |
| Sliding window log | No more than the limit | One entry per request | Exact | Strict limits on small numbers |
What it cannot do
A full bucket lets a burst through at once
If the service cannot take the whole burst, set the capacity lower.
It trusts the clock
A clock that jumps forwards refills the bucket early.
There is state per key
Every user or key needs its own bucket, and idle ones have to be cleaned up.
One bucket per server is not a global limit
Without a shared store, N servers allow N times the rate.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add a second bucket for a per-user limit and a shared one for the whole service
- Keep the bucket in Redis and refill it inside one atomic script
- Compare its burst behaviour with the sliding window limiter lab