The leaky bucket algorithm: a bucket that drains at a constant rate
The leaky bucket algorithm pictures a bucket with a hole in the bottom. Requests pour in, the bucket drains at a constant rate, and whatever would make it overflow is refused or dropped. The picture hides a quarrel: some sources use the bucket as a counter that only judges traffic, others as a queue that holds it. Which one you mean decides whether a burst is admitted, delayed or turned away.
Quick facts
- Capacity
- How much the bucket holds before it overflows: a burst allowance, or the length of a queue
- Leak rate
- The constant rate at which the bucket drains, which is the sustained rate it allows
- State per client
- One fill level and the time it was last updated (meter), or a queue (queue form)
- Origin
- Networking: described for policing and shaping, and in ATM as the generic cell rate algorithm (Wikipedia)
- Refusal on the web
- HTTP 429 Too Many Requests, optionally with Retry-After (RFC 6585, section 4)
This page is about one algorithm. The wider comparison, with fixed and sliding windows, lives on rate limiting algorithms.
How the leaky bucket algorithm works
Start with the metaphor and take it literally. Water, meaning requests, is poured into a bucket. A hole lets it out at a fixed speed, whatever the pouring does. If water arrives faster than it leaks, the level rises. When the level reaches the rim, the next pour spills, and a spilled request is one the limiter refuses.
Wikipedia describes the idea as an algorithm that checks whether discrete events stay within limits on average rate and peak rate, or delays them until they do (Leaky bucket). Two numbers are enough: how fast the bucket drains, and how much it can hold.
- Each client has a bucket. Keyed by what the limit counts: address, user or API key.
- The level falls with time. Not by a timer, but by working out how much would have leaked since the last request.
- A request adds to the level. One unit each, or more for an expensive call.
- Over the rim means refused. The request does not change the level.
on request(key, cost = 1):
b = bucket[key] or {level: 0, last: now}
b.level = max(0, b.level - (now - b.last) * LEAK_RATE)
b.last = now
if b.level + cost <= CAPACITY:
b.level += cost
bucket[key] = b
return allow
excess = b.level + cost - CAPACITY
bucket[key] = b
return refuse(retry_after = ceil(excess / LEAK_RATE))
The refusal carries its own wait: the time the bucket needs to drain enough room for this request. That figure is what a Retry-After header can report.
Leaky bucket as a meter and as a queue
Here the sources part ways. Wikipedia separates two readings.
As a meter
The bucket is a counter or variable kept apart from the flow of traffic. An arrival raises it, time lowers it, and an arrival that would overflow it is nonconforming. The request that conforms is served immediately; nothing waits. This is the pseudocode above, and it is the form the ATM generic cell rate algorithm takes, specified in ITU-T Recommendation I.371 and the ATM Forum user network interface specification, as the same article records. A plain count per period is the fixed window approach.
As a queue
The bucket is a first-in, first-out queue standing in the path of the traffic. Requests join the back and leave the front at the leak rate. When the queue is full, a new arrival is dropped. The output is a steady stream, and the price of that is waiting: a burst of twenty requests does not fail, it leaves one at a time.
on request(key, job):
q = queue[key]
if len(q) < CAPACITY:
q.push(job)
return queued
return refuse(status = 429)
every 1 / LEAK_RATE seconds, for each queue q:
if q is not empty:
serve(q.pop())
The same article notes that terminology here is confusing, that the queue form does not always produce a rigid output (gaps appear when the queue empties), and that it presents the queue form as a special case of the meter. It also cites the request-limiting module of nginx as an example of the queue approach; how nginx expresses this is on rate limiting in nginx. When a document says only "leaky bucket", check which of the two it means before comparing numbers.
Leaky bucket vs token bucket
The token bucket algorithm has its own page, and the full mechanics are there. The short version is a difference of bookkeeping. A token bucket counts what a client may still spend; a leaky bucket counts what it has already poured in.
For the meter form the two are the same machine seen from opposite sides. Wikipedia calls the meter the mirror image of the token bucket and says that with equivalent parameters both see the same traffic as conforming or not. A token bucket with capacity 10 and a refill of 1 per second admits and refuses exactly what a meter with capacity 10 and a leak of 1 per second does. The names differ; the decisions do not.
The queue form is the real contrast. It never admits a burst to the service all at once, because it releases requests at the leak rate. A token bucket spends its stored tokens immediately. So the choice is rarely between two counters. It is between refusing a burst quickly and absorbing it slowly, and between a client that gets an answer now or an error now, and a client that waits.
Because the queue holds connections open while requests wait, it tends to suit background work better than interactive traffic. For interactive clients a short burst is normal, which is the argument on bursts and rate limits.
Capacity and leak rate
The leak rate is the sustained rate you are willing to serve one client, per second or per minute. Derive it from what a legitimate client needs over a long stretch, not from its busiest second.
The capacity means different things in the two readings. In the meter it is the burst allowance: how far above the leak rate a client may run for a short time before refusals begin. In the queue it is the longest wait you will impose, since a request that joins a full queue of N items leaves after about N divided by the leak rate seconds. Set the queue longer than a client will tolerate waiting and requests time out inside it.
A worked case. Leak rate 2 per second, capacity 10, meter form. A client sends 10 requests at once on an empty bucket: all pass and the level reads 10. One more arrives a moment later and is refused; the level would be 11. Half a second on, the level has fallen to 9, so one request fits again. A client that settles at 2 requests a second hovers near its level forever and is never refused. A client at 3 a second climbs by one unit a second and is refused after about ten seconds. Those numbers are a toy example to show the arithmetic, not a recommendation.
Measure before choosing. Record what a limit would refuse before it refuses anything, and read the list of who it would have caught. How to design that check is on testing a limit, and what a limit should key on is on limits by IP, user or key. With several servers the bucket has to be shared or divided, as discussed under distributed rate limits.
When the bucket overflows: 429 and Retry-After
An overflow in a web limiter becomes an HTTP response. The status for it is 429 Too Many Requests, defined in RFC 6585. That document says the response may include a Retry-After header indicating how long to wait before a new request; the word is "may", so a client cannot rely on it. What a good refusal says is on 429 Too Many Requests.
The header itself takes either a number of seconds or an HTTP date, as MDN documents. The meter gives a natural value: the excess divided by the leak rate, rounded up, which is the last line of the pseudocode above. The header and the value you should send are covered on Retry-After.
The queue form has a quieter overflow. While the queue has room, a request gets no error, only a delay, and a client sees nothing wrong until the queue fills. Log both events, the wait and the drop, or the first sign of trouble will be a timeout.
Where a WAF helps and where it does not
A WAF-side limit sees requests, not intent. It can count how many arrive for a key and apply a rule when the count is too high. It cannot tell whether twelve requests in a second are a script or a person opening a busy page, and it does not know which request is expensive for your application unless you tell it. A leaky bucket does not change that: it is a way of counting, not of understanding.
Bridge WAF applies rate limiting per domain, in three modes: off, monitor and block. Start with monitor. Matches are recorded in the activity log and every request is still served, so you see who a limit would have refused before it refuses anyone; monitor mode explains the habit. Move to block when the list holds only clients you meant to catch.
This page describes the algorithm in general. It does not say which algorithm Bridge WAF uses, and nothing here should be read as a statement about it. Neither does it describe an attack-volume defence; a limiter at the application layer is not a substitute for capacity planning, and the activity log is a record of what was flagged, not a measure of attack volume.
Questions
What is the leaky bucket algorithm?
A rate-limiting algorithm built on the picture of a bucket with a hole: arrivals add to the bucket, it drains at a constant rate, and anything that would overflow it is refused or dropped. It can run as a counter that only judges requests, or as a queue that holds them.
What is the difference between leaky bucket as a meter and as a queue?
As a meter, the bucket is a counter that sits beside the traffic; requests that would overflow it are refused and the rest pass at once. As a queue, the requests themselves wait in line and leave at a fixed rate, so the output is smooth and a burst turns into delay.
Is a leaky bucket the same as a token bucket?
Not in how it is usually described. Wikipedia presents the meter form as the mirror image of a token bucket, so with matching parameters both judge the same traffic the same way. The queue form differs because it delays requests instead of admitting them.
What should a service return when the bucket overflows?
The usual answer is HTTP 429 Too Many Requests, optionally with a Retry-After header saying how long to wait. RFC 6585 makes that header optional, so clients must cope without it.