A payments gateway promises downstream at most one request per second. At t = 0 a client retries five times in the same millisecond. The intern fills a token bucket to capacity 3. The five arrivals spend three tokens at once. Downstream sees a spike of three, then two rejections. The SLA was a steady drain, not a stored burst spent in one shot.
A leaky bucket queues work as water and leaks at a constant rate. Overflow is dropped or the caller waits. The output is a steady drain, not a stored burst you can spend at once. Capacity is how much water the bucket holds. The leak is the only way work leaves. A burst that does not fit is not a delayed spike of the same shape — it is overflow.
This post is that drain. Families and the catalog live on the Algorithms Roadmap. The queue layout is a Queue. It is not the token-bucket lab, not a sliding-window array scan, not retry-with-jitter, and not an nginx product tutorial.
The job is a steady drain, not a stored burst
Two knobs.
- Capacity — how much water (queued work) the bucket may hold.
- Leak rate — how many units leave per second. Constant. Not “as fast as the CPU can poll.”
Arrivals add water. Time subtracts water. If an arrival would push the level past capacity, that unit overflows: reject it, or make the caller wait until a leak has made room. Downstream only ever sees the leak. A burst of five into a bucket of three does not become a burst of three on the wire.
The leak is the output. Capacity is a buffer in front of that leak, not a license to dump the buffer. Token bucket stores permission you can spend at line rate. Leaky bucket stores work that can leave only at the leak rate. Same word “bucket.” Opposite burst shape.
The water level is the queue length. You can keep an ArrayDeque of that size and poll on each leaked unit, or you can store a counter and treat “admitted” as “queued for the drain.” The algorithm is the level, the leak, and the overflow rule — not the collection type.
Note: Overflow-reject is policing (drop the excess). Overflow-wait is shaping (the caller blocks until a slot leaks open). Pick one at the method boundary. Mixing them in one path is how a timeout and a 429 fire for the same retry.
Leak by elapsed time, then offer
You do not need a background thread that sleeps one second and decrements. On each offer, compute how much should have leaked since the last visit, lower the water, then try to add one.
- Leak
elapsedSeconds * leakPerSec(floor at empty). - Offer one unit if
water + 1 ≤ capacity. - Overflow otherwise — return false, or wait and leak again.
Elapsed time is the clock. A tick loop is optional. If nobody calls offer for three seconds at 1/s, the next call drains three units in one arithmetic step, then admits. The water does not remember a burst that already overflowed.
Empty bucket: every offer succeeds until you hit capacity. Full bucket and no elapsed leak: every offer overflows. A later arrival after a leak succeeds even if the earlier overflowed siblings never retry — those units are gone.
One unit of work is one request in the walk below. A packet of size n is the same procedure with + n and a leak in the same units. This post keeps the unit at 1 so the overflow count is the request count.
A walk: drain 1/s, burst of 5, capacity 3
Empty bucket. Leak rate 1 per second. Capacity 3. Five requests A B C D E arrive together at t = 0. Overflow rejects.
t=0.0 water=0 room=3
offer A → accept water=1
offer B → accept water=2
offer C → accept water=3
offer D → overflow water=3
offer E → overflow water=3
queued: A B C dropped: D E emitted so far: nothing
(token bucket with 3 tokens would emit A B C at t=0)
t=1.0 leak 1 → emit A water=2
t=2.0 leak 1 → emit B water=1
t=3.0 leak 1 → emit C water=0
downstream: 1 at t=1, 1 at t=2, 1 at t=3
not a spike of 3 at t=0Two overflowed. Three drained at 1/s. The accepted burst was flattened. A token bucket that started with three tokens would have spent them in one shot — same three admissions, different output shape.
If F arrives at t = 0.5 while water is still 3, it overflows too: half a second has leaked 0.5, not a whole slot. At t = 1.0 a slot is open. Wait-on-overflow would park D until that leak, then queue it; reject-on-overflow does not.
offer(0) true water 1
offer(0) true water 2
offer(0) true water 3
offer(0) false water 3 overflow 1
offer(0) false water 3 overflow 2
offer(1000) true water 3 leaked 1, then +1The two false results are the two overflowed units from the title walk. The offer(1000) is a new arrival using the slot A leaked — not D coming back to life.
Not token bucket, not a sliding-window scan
Token Bucket stores tokens. Tokens refill at an average rate, up to a burst capacity. A caller who arrives when the bucket is full may spend all of those tokens immediately. The output can be a burst of the same shape as the stored credit. That is the point of that lab: allow bursts, then enforce an average. Do not re-lecture it here.
This page stores water. Water leaves at a constant leak. You cannot spend the whole bucket in one nanosecond. A burst is smoothed or it overflows.
Sliding Window is an array scan: grow right, shrink left, each index added and dropped at most once. A rate-limit “sliding window” that counts requests in the last N seconds is a time policy. It shares a name with the Wave 1 scan. It is not this drain, and it is not that scan.
| Job | What is stored | A burst of 5 vs capacity 3 |
|---|---|---|
| Token bucket | Tokens (permission) | Up to 3 can fire at once; 2 denied |
| Leaky bucket | Water (queued work) | Up to 3 queue; they leak 1/s; 2 overflow |
| Sliding window (array) | Indices on a layout | Not a time policy |
Do not emit the whole queue the moment it is full and call that a leaky bucket. That is a token-bucket burst wearing a queue. The leak rate is a ceiling on output, not only on how many you accepted.
Note: Some production limiters mix the names. If the implementation can dump capacity requests in one tick, you are spending stored credit. If it can only release leakPerSec per second no matter how full the buffer is, you are here.
Java: water level, leak, offer
No java.util.LeakyBucket. Water is a double for the lab. Pass nowMillis so the walk above is a test, not Thread.sleep. leak is arithmetic. offer is leak-then-add.
final class LeakyBucket {
final int capacity;
final double leakPerSec;
double water;
long lastMillis;
LeakyBucket(int capacity, double leakPerSec, long nowMillis) {
this.capacity = capacity;
this.leakPerSec = leakPerSec;
this.lastMillis = nowMillis;
}
void leak(long nowMillis) {
double elapsed = (nowMillis - lastMillis) / 1000.0;
water = Math.max(0.0, water - elapsed * leakPerSec);
lastMillis = nowMillis;
}
boolean offer(long nowMillis) {
leak(nowMillis);
if (water + 1.0 <= capacity) {
water += 1.0;
return true;
}
return false; // overflow — caller rejects (or waits and retries)
}
}water is the queue length. To hold the work, keep an ArrayDeque of that size: poll once per leaked unit instead of subtracting a double, offer the item when there is room. Same overflow rule. The Queue post owns the layout; this sketch owns the clock.
Wait-on-overflow is while (!offer(now)) { park until the next whole slot; now = clock; }. Compute the wait from (water + 1 - capacity) / leakPerSec after leak — do not spin. This post does not implement the park. Reject is the return value above.
Note: double water drifts. Production often keeps integer milliliters, or a last-tick plus a remainder. The algorithm does not change. Do not leak in a while (true) { sleep(1000); water--; } unless you are actually emitting work on that cadence; offer can catch up from elapsed time.
Complexity
Each offer is a constant amount of arithmetic. The interesting bound is the bucket, not the stream length.
| What | Cost | Why |
|---|---|---|
| Leak | O(1) | Subtract elapsed * rate; clamp at 0 |
| Offer (reject) | O(1) | Leak, then compare water + 1 to capacity |
| Extra space (counter) | O(1) | One level and a timestamp |
| Extra space (real queue) | O(capacity) | At most capacity queued items |
| Naive rival | O(n) per tick | Scanning every arrival to “smooth” without a level |
Quoting a loop over the day’s requests as the cost of the limiter hides the point: you do not rescan history. You store the water.
One level, one timestamp, no JDK limiter type. Replaying the last N seconds of timestamps on every call is a different policy (a request-count window), not this drain.
When not to use a leaky bucket
Skip this drain when the job is not “smooth arrivals into a constant output, and overflow the rest.”
- You needed a stored burst. Product wants the client to dump
capacityrequests the instant tokens are full, then wait for a refill. That is Token Bucket. Do not leak-smooth that SLA. - You needed an array window. Rolling sum, longest range with at most
kdistinct keys — Sliding Window. Time is not an index on that array. - You needed retries to spread out. A 429 or a timeout is not a leak rate. Jittered backoff is the next named job, not a flag on
offer. - You needed an nginx (or API-gateway) tutorial. This page is the water-level procedure. Product knobs, config files, and mesh sidecars are out of scope.
- You needed to empty the queue at CPU speed. A worker that
polls until dry is a queue, not a leaky bucket. The leak is the ceiling. - You needed fairness across keys. One bucket is one stream. Per-client buckets are many copies of this object, not a different algorithm.
Constant drain — that is the job. Consistent hashing, 2PC, Raft, and sketches are other systems procedures. Do not open those labs here. Do not open the full token-bucket refill walk here either; that sibling owns bursts-then-average.
Cheat sheet
Job: smooth bursts into a steady output; overflow the rest
Procedure: water level (queue size); leak elapsed*rate; offer +1 or overflow
Overflow: reject, or wait until a leak makes room
Output: at most leakPerSec, even when the bucket is full
Cost: O(1) per offer (counter); O(capacity) space if you queue items
JDK: none; ArrayDeque if you hold the work
Not this: token bucket (stored burst), sliding-window array scan,
exponential backoff, nginx tutorialsDo:
- Leak by elapsed time, then offer. Clamp water at 0.
- Treat capacity as a buffer in front of a constant drain, not as tokens to dump.
- Pick reject or wait at the boundary. Count overflow as dropped units.
- Use a counter, or a queue of length
water— same rule.
Don’t:
- Spend the whole bucket in one tick and call the output a leak.
- Re-lecture token-bucket refill, sliding-window indices, or jittered retries here.
- Sleep in a decrement loop when
offercan catch up from the clock. - Configure nginx (or any product limiter) and call that this algorithm.
Wrap-up
A leaky bucket is a water level that leaves at a constant rate. Arrivals queue until capacity; the rest overflow — dropped, or the caller waits. A burst of five into capacity three at 1/s is three queued and two overflowed, then a drain of one per second, not a spike of three. Token bucket stores a burst you can spend at once. Sliding window is an array scan. This page is the drain. Build the level, leak from elapsed time, offer or overflow.
The layout was already a queue. The procedure is this leak. When the job is to allow a burst and then enforce an average, that is the token-bucket sibling. When the next named job is a herd of failures retrying in lockstep, that is jittered backoff.