Leaky Bucket Algorithm

Picture a bucket with a small hole in the bottom. Water pours in from the top at varying rates: sometimes a trickle, sometimes a flood. But water always drips out the bottom at a constant rate, determined by the hole size. If water pours in faster than it drips out, the bucket fills up. If the bucket overflows, excess water is lost.

The leaky bucket algorithm models this exactly. Requests (water) arrive at variable rates. They are placed in a queue (bucket). The system processes requests at a fixed, constant rate (the leak). If the queue is full, new requests are rejected (overflow).

The key difference from token bucket: the output rate is perfectly smooth. Token bucket allows bursts, a user with accumulated tokens can send many requests at once. Leaky bucket never bursts. No matter how many requests queue up, they are processed one at a time at a fixed rate.

This smoothness makes leaky bucket ideal for traffic shaping, smoothing out bursty network traffic into a steady stream. It is used in network hardware (Cisco routers, Juniper switches), QoS systems, telecom networks (ATM cell scheduling), and anywhere constant output rate matters more than burst flexibility.

Nginx's limit_req module uses leaky bucket by default. When you write limit_req zone=api burst=20, you are configuring a leaky bucket with a queue of 20 and a constant drain rate. Requests exceeding the rate are queued (up to the burst limit), not immediately rejected.

Parameters:

• Bucket size: Maximum number of queued requests
• Leak rate: Requests processed per second (constant)

For each incoming request:

1. If the bucket (queue) is not full: add the request to the queue
2. If the bucket is full: reject the request (429 or drop the packet)
3. Process requests from the queue at the constant leak rate

Bucket size: 5, Leak rate: 2/sec

t=0.0: 4 requests arrive  -> queue: [r1, r2, r3, r4]
t=0.0: process r1 (first drip)
t=0.5: process r2
t=1.0: 3 more arrive      -> queue: [r3, r4, r5, r6, r7] (full!)
t=1.0: 1 more arrives     -> REJECTED (bucket full)
t=1.0: process r3
t=1.5: process r4
t=2.0: process r5
t=2.5: process r6
t=3.0: process r7

Notice: regardless of how requests arrive (bursty or steady), they are always processed at exactly 2 per second. The queue absorbs bursts. The leak rate smooths the output. The queue size is the only knob for burst tolerance: a larger queue absorbs longer bursts but adds more latency for queued requests.

Implementation:

class LeakyBucket {
  private queue: Array<() => void> = [];
  private processing = false;

  constructor(
    private capacity: number,  // max queue size
    private leakRate: number   // requests per second
  ) {}

  tryEnqueue(handler: () => void): boolean {
    if (this.queue.length >= this.capacity) {
      return false;  // Bucket full, reject
    }
    this.queue.push(handler);
    if (!this.processing) this.drain();
    return true;
  }

  private drain() {
    this.processing = true;
    const interval = 1000 / this.leakRate;
    const timer = setInterval(() => {
      const next = this.queue.shift();
      if (next) {
        next();  // Process one request
      } else {
        clearInterval(timer);
        this.processing = false;
      }
    }, interval);
  }
}

The critical difference from token bucket: token bucket is a counter (allow or reject immediately), leaky bucket is a queue (accept, hold, process later). This means leaky bucket adds latency. A request that enters the queue when 10 items are ahead of it waits 10 / leak_rate seconds before processing. At a leak rate of 2/sec, that is 5 seconds of waiting.

Here is a leaky bucket in Python. Requests arrive in a burst, but the "process" step drains at a constant rate. Watch the output timestamps, they are evenly spaced even though the inputs were not.