Leaky Bucket

"Leaky bucket" names two different algorithms, and mixing them up is one of the commonest mistakes in rate-limiting write-ups. Both picture a bucket with a hole: requests pour in as water, and the water leaks out at a fixed rate. The difference is what the bucket holds. In this lesson your gateway becomes the second kind, a traffic shaper that makes bursts wait instead of refusing them.

Variant 1: the meter

The bucket holds a number, the water level. It drains continuously at leak_rate; each request adds 1 unit if the level stays at or under capacity, and is refused on the spot otherwise. Substitute tokens = capacity - water and every line maps onto the token bucket: adding water is spending a token, leaking is refilling. The meter makes decisions identical to a token bucket with the same parameters. It admits a burst up to capacity instantly and does not smooth anything. You already built it last lesson.

Variant 2: the queue (the shaper)

The bucket is a real queue of waiting requests. Arrivals join the back, or are dropped if the queue is full, and a worker releases one request every interval seconds. However bursty the input, the output is perfectly even: never more than one request per interval. The price is latency, because queued requests wait. This is the classic telecom formulation (ATM networks standardised it as the generic cell rate algorithm), and it is what nginx's limit_req does: rate=1r/s burst=5 queues up to five excess requests and releases them on the one-per-second tick. Add nodelay and nginx serves the burst slots immediately, which turns it back into a meter.

One number per client

You do not need a real queue. Because the queue is first-in first-out and drains at a fixed rate, one number describes it completely: next_free, the earliest instant the next request may be released. When a request arrives at now:

release = the later of now and next_free
delay   = release - now
if delay > burst * interval: refuse
else: next_free = release + interval, and the request is held until release

A client that has been idle has next_free in the past, so its request is released at once and idle time is not banked. That is the real difference from the token bucket: an idle client gets one immediate request, then one per interval. A refused request changes nothing, so it does not push the schedule back.

A worked trace with interval = 2, burst = 2 (limit on the delay: 4 seconds), different numbers from your exercise:

What the client sees

A held request is simply answered late, so the response carries the moment it was released in the Date header, in the fixed format of RFC 9110, section 5.6.7: Tue, 14 Nov 2023 22:13:20 GMT. A refused request gets 429 with a Retry-After: the seconds until the queue has room again, which is release - burst * interval - now, rounded up.

The trap: an oversized queue

Smoothing works by making requests wait. With a burst of 10,000 on a 1 per second zone, a spike means "successful" responses that arrive hours later, which is worse than an honest 429 because the client's timeout fired long ago. Size the queue in seconds of delay (burst * interval), not in raw request counts.

Common mistakes

• Building the meter again. If the second request at the same instant is answered immediately, you made a token bucket.
• Releasing from now instead of from the later of now and next_free, so queued requests overlap.
• Moving next_free when you refuse, which makes the block grow with every retry.
• Letting next_free stay in the past and then crediting the client for the idle time.

Your exercise

Release at most 1 request per second per client, allow up to 3 to wait, and answer each released request with the Date it went out at.