A payments API just recovered from a 400ms blip. Four clients retry at once. The intern’s limiter is if (callsThisSecond >= 1) reject. All four die. The next intern flips it: a counter that resets every minute, sixty allowed, then a cliff — the 61st waits until the wall clock rolls. Product wanted something else: let a short burst through after a stall, then settle to a known average.
A token bucket holds up to C tokens, refills at R per second, and admits a request when tokens ≥ cost — burst of C, then average rate R. Spend on allow. Reject or wait when the bucket is empty. The stored tokens are the burst.
This post is that admit check. Families and the catalog live on the Algorithms Roadmap. Leaky Bucket is the sibling that drains smoothly instead of storing the same burst. A rate-limit “window” is a time policy, not the array scan in Sliding Window. Exponential backoff is how you retry after a deny, not how you admit. This is not an nginx or Redis product.
The job is stored burst, then average R
A hard 1/s with no banked credit punishes a legitimate retry cluster. A fixed window of “60 per minute” still has a cliff: 60 at t=0.01 and 60 at t=60.01 is 120 in a hair over a minute, then silence.
Token bucket names three numbers:
- Capacity
C. How many tokens the bucket can hold. That is the largest burst you will ever dump in one instant. - Refill
R. Tokens added per second, capped atC. Over a long stretch the admit rate cannot beatR. - Cost. Usually
1per request. A heavy job can cost more than one token.
Current tokens sit between 0 and C. On each call you first add elapsed × R (still capped), then spend if tokens ≥ cost.
Empty means “not now.” Full means “you may burst up to C.” Starting full is the usual lab: the first callers get the burst without waiting to fill.
Note: Starting empty delays the first burst until C / R seconds of idle refill. Say so at the constructor if that is the product.
Refill, then spend — or refuse
allow(cost) is two steps, always in that order.
- Refill.
tokens = min(C, tokens + (now − lastRefill) × R). RecordnowaslastRefill. - Spend or refuse. If
tokens ≥ cost, subtractcostand allow. Else reject, or compute how long to wait:(cost − tokens) / R.
You do not add tokens on a timer thread. The next allow lazily credits idle time. A bucket that nobody called for ten seconds is as full as one that ticked ten times — same elapsed × R, still capped at C.
Wait is not a different algorithm. It is the same deficit, converted to time. Sleep that long (or return a retry-after) and call allow again. Do not busy-loop.
Do not refill after spending on the same call without using the new lastRefill. Double-credit is how a lab “accidentally” beats R.
A walk: capacity 4, refill 1/s
Start full. Four requests arrive together. A fifth is immediate. Then one second of idle.
C = 4 R = 1 token/s cost = 1 start full
t=0.00 tokens=4 allow → 3 ALLOW
t=0.00 tokens=3 allow → 2 ALLOW
t=0.00 tokens=2 allow → 1 ALLOW
t=0.00 tokens=1 allow → 0 ALLOW
t=0.00 tokens=0 allow DENY (deficit 1)
wait 1.0s
refill min(4, 0 + 1.0×1) = 1
t=1.00 tokens=1 allow → 0 ALLOWThe burst of four is the capacity. The fifth is the empty bucket, not a bug. After one second the average policy shows: you get one more admit, not another burst of four. Idle four seconds instead and min(4, 0 + 4×1) = 4 — full again, another burst of four is legal.
Same walk with wait instead of deny: at t=0 the fifth caller is told 1.0s. That is (1 − 0) / 1. A cost-2 job against 0.5 tokens waits (2 − 0.5) / 1 = 1.5s.
Not leaky bucket
Leaky Bucket also has a capacity and a rate. The shape of what leaves is different.
Token bucket stores permission. When tokens are in the bucket, that many requests can depart at once — a burst on the wire, then silence until refill. Downstream sees the spike, then the average.
Leaky bucket stores queued work (or drops overflow). It drains at a steady R. You cannot dump C onto the downstream in one instant; the leak is the limiter. Incoming bursts fill the bucket; a full bucket overflows. The output is a drip.
| Token bucket | Leaky bucket | |
|---|---|---|
| What you store | Tokens (credit) | Water / queue (work) |
| Burst on the wire | Yes, up to C | No — drain is smooth |
| Empty / full | Empty → deny or wait | Full → overflow |
| Long-run rate | R | R |
Same average R. Different burst shape. If the product is “catch-up after a stall, then average,” this post. If the product is “never spike the downstream,” the leaky sibling. This page does not walk that drain.
Not a sliding-window scan
People say “sliding window rate limit” and mean “count admits in the last T seconds.” That is a time policy — another admit check. It is not the algorithm in Sliding Window.
That post owns a contiguous array range: add on the right, drop on the left, each index at most once. Rolling sum of latencies. Longest SKU run with at most k distinct keys. Two indices on a layout you already have.
A rate-limit window is not that scan. Do not grow-and-shrink an array of request timestamps and call it the sliding-window post. Do not import this bucket into a max-sum window. The names collided. The jobs did not.
Out of scope here: implementing that time-window counter, nginx limit_req, Redis INCR+TTL as a product.
Java: tokens as double, lastRefill, allow(cost)
No java.util.TokenBucket. The hub’s library map points at Bucket4j for a JVM limiter you would actually ship — this post does not teach Bucket4j. The lab is capacity, refill rate, current tokens, and a timestamp.
tokens is a double so fractional refill over milliseconds is honest. lastRefill is nanos (millis is the same algorithm with a coarser tick). Start full. allow is the reject path; waitNanos is the wait path.
final class TokenBucket {
private final double capacity;
private final double refillPerSec;
private double tokens;
private long lastRefillNanos;
TokenBucket(double capacity, double refillPerSec) {
this.capacity = capacity;
this.refillPerSec = refillPerSec;
this.tokens = capacity;
this.lastRefillNanos = System.nanoTime();
}
synchronized boolean allow(double cost) {
refill();
if (tokens < cost) {
return false;
}
tokens -= cost;
return true;
}
synchronized long waitNanos(double cost) {
refill();
if (tokens >= cost) {
return 0L;
}
double missing = cost - tokens;
return (long) Math.ceil(missing / refillPerSec * 1_000_000_000.0);
}
private void refill() {
long now = System.nanoTime();
double elapsed = (now - lastRefillNanos) / 1_000_000_000.0;
tokens = Math.min(capacity, tokens + elapsed * refillPerSec);
lastRefillNanos = now;
}
}synchronized keeps one bucket honest on one JVM. It is not a cluster lock. Cost 0 is a no-op allow once you refill. Cost above C can never succeed — refuse at the boundary.
Note: Doubles drift over a long uptime. A production credit clock often stores integer nanos of token. The procedure does not change. Do not start a refill timer thread for the lab.
Cost per call
allow is a handful of arithmetic. No heap, no graph, no scan of past requests.
| What | Cost | Why |
|---|---|---|
allow / waitNanos | O(1) | Refill, compare, subtract |
| Extra space | O(1) | Four fields |
| History of requests | None | Idle time is now − lastRefill |
You do not keep a deque of timestamps to “know the last second.” That is a different policy, and it is still not the array sliding window.
One bucket, one clock, no request log. Quoting a sort or a window scan as the bill for this admit check is the wrong family.
When not to use token bucket
Skip this bucket when the job is not “burst up to C, then average R.”
- You needed a smooth drain. Downstream cannot take a spike of
C. That is Leaky Bucket, not a flag on this refill. - You needed retry spacing. After a 429, wait with jitter so the herd does not stampede. Exponential backoff is a retry policy, not an admit policy. Do not fold it into
allow. - You needed a contiguous array window. Rolling sums and “at most
kdistinct in a slice” live in Sliding Window. - You needed a mesh or gateway product. nginx, Redis, API-gateway quotas are deployment. This post is the in-process procedure. Bucket4j is the JVM pointer; it is not this lab.
- You needed a cluster-wide count. This sketch is one process. Sharing tokens across instances is a shared store plus the same refill math — a product problem, not a second algorithm to invent here.
- Cost exceeds
C. A single request that needs more tokens than the bucket can hold will never pass. Split the work or raise capacity. Do not wait forever in a loop.
Burst then average — that is the job. Leaky bucket, a time-window counter, and exponential backoff are other named procedures. This is an online admit check on each request, in the hub’s glossary sense of online vs offline.
Cheat sheet
Job: admit with burst up to C, then average rate R
State: tokens ∈ [0, C], lastRefill
On allow: refill min(C, tokens + elapsed×R); if tokens ≥ cost, spend
Else: reject, or wait (cost − tokens) / R
Start: full ⇒ first burst is immediate
Time/space: O(1) / O(1) per call; no request history
JVM: no JDK type; Bucket4j is a pointer, not this tutorial
Not this: leaky bucket drain, sliding-window array scan, backoff, nginx/RedisDo:
- Refill lazily on the next
allow, then spend. - Cap at
C. Empty is deny or wait, not a negative balance. - Name
Cas the burst andRas the long-run rate before you pick numbers. - Point at Bucket4j (or the gateway you already run) when you leave the lab.
Don’t:
- Treat a hard 1/s with no credit as this algorithm — that is a burst of one, forever.
- Call this leaky bucket. Smooth drain is the sibling post.
- Import Sliding Window’s add-right / drop-left scan and call it a rate limit.
- Hand-roll nginx or Redis here, or open a Bucket4j tutorial on this page.
Wrap-up
Token bucket banks permission: fill to C, drip in at R, spend on each admit. A burst of C is legal while tokens last. After that you wait for refill or you reject. The fifth request in the lab is empty, not unfair; one second later the average policy shows. It is not a smooth drain, not an array window, and not a retry loop. A counter and a clock. Two steps. Burst, then average.
The layout is a single counter plus a clock. The procedure is refill-then-spend. When the job is a steady drip instead of a stored burst, that is leaky bucket.