Leaky Bucket

"Leaky bucket" is one name for two different algorithms, and confusing them is among the most common errors in rate-limiting write-ups. Both picture a bucket with a hole: requests pour in as water, and water leaks out at a fixed leak_rate. The difference is what the bucket holds.

Variant 1: leaky bucket as a queue (traffic shaper)

The bucket is a real queue of waiting requests. Arrivals join the queue — or are dropped if it's full; that's the capacity — and a worker drains it at exactly leak_rate requests per second. Output is perfectly smooth: however bursty the input, the downstream sees at most one request per 1/leak_rate seconds. The price is latency, because queued requests wait. This is the classic telecom formulation (ATM networks standardized it as the GCRA), 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 once-per-second tick. Add nodelay and nginx stops smoothing — burst slots are served immediately, which is meter behavior.

Variant 2: leaky bucket as a meter (admission controller)

No queue — just a number, the water level. The level drains continuously at leak_rate; each request adds 1 if it fits under capacity and is rejected on the spot otherwise:

Same lazy-update idiom as the token bucket: no timers, O(1) time and O(1) memory per client. Trace it with capacity=2, leak_rate=1, requests at t = 0, 0, 0, 1, 1.5, 2:

• t=0: water 0 → fits → ALLOW (water 1)
• t=0: fits → ALLOW (water 2) — two back-to-back ALLOWs: the meter admits bursts
• t=0: 2 + 1 > 2 → DENY (water stays 2)
• t=1: leaked 1 → water 1 → ALLOW (water 2)
• t=1.5: leaked 0.5 → water 1.5 → 2.5 > 2 → DENY
• t=2: leaked 0.5 → water 1.0 → ALLOW (water 2)

The insight most people miss

Look closely: an empty bucket admits capacity requests instantly. Substitute tokens = capacity − water and every line of the meter maps onto the token bucket — adding water is spending a token, leaking is refilling. The meter variant makes decisions identical to a token bucket with the same parameters. It does not smooth output; only the queue variant does. So the honest comparison is:

• Token bucket / leaky-bucket-as-meter: admit immediately, allow bursts up to capacity, add zero latency. Right for APIs.
• Leaky-bucket-as-queue: enforce a strictly smooth output rate, at the cost of queueing delay. Right for traffic shaping — pacing packets, feeding a fragile downstream that melts under spikes.

The trap: an unbounded (or oversized) queue. Smoothing works by making requests wait. Configure burst=10000 on a 1 r/s nginx zone and a traffic spike means "successful" responses arriving hours late — worse than an honest 429. Bound the queue, and size it in seconds of delay (burst / rate), not in raw request counts.

Your exercise

Implement the meter variant and reproduce the trace above exactly:

ALLOW ALLOW DENY ALLOW DENY ALLOW

Then prove the equivalence to yourself: run the previous lesson's TokenBucket with capacity=2, refill_rate=1 (starting full) against the same timestamps. The verdicts match request for request, because the two states always satisfy water + tokens = capacity — check it at t=1.5, where water 1.5 mirrors tokens 0.5. If your meter returns DENY on the second t=0 request, you've accidentally built rate-only admission: the meter's entire point is that the burst passes.