Leaky Bucket Algorithm — Deterministic Traffic Shaping for APIs

In this tutorial, you will learn about Leaky Bucket Algorithm. We cover key concepts, practical examples, and best practices to help you master this topic.

The leaky bucket algorithm processes requests at a fixed, deterministic rate by placing incoming requests into a queue (bucket) that leaks at a constant rate, dropping requests when the queue is full for strict traffic shaping.

What You'll Learn

• How the leaky bucket algorithm enforces a fixed processing rate
• Differences from token bucket: no burst capability
• Use cases for strict rate enforcement

Why It Matters

Some systems cannot handle bursts at all. A payment processor must handle exactly 100 transactions per second — no more. A database with a fixed connection pool cannot accept sudden spikes. Leaky bucket guarantees a maximum processing rate.

Real-World Use

Durga Antivirus Pro's database write endpoint uses leaky bucket rate limiting. The database can handle 500 writes per second. Even if 2000 writes arrive in one second, the leaky bucket queues them and processes 500 per second, dropping excess.

flowchart LR
    Requests["Incoming Requests"] --> Queue["Queue (Bucket)\nCapacity: 100"]
    Queue -->|"Leak at fixed rate"| Processor["Processor\n10 req/sec"]
    Queue -->|"Queue full"| Drop["Drop Request\n429"]
    style Queue fill:#dbeafe,stroke:#2563eb
    style Drop fill:#fecaca,stroke:#dc2626

Leaky Bucket Implementation

import time
import threading

class LeakyBucket:
    def __init__(self, rate, capacity):
        self.rate = rate
        self.capacity = capacity
        self.water = 0
        self.last_leak = time.monotonic()
        self.lock = threading.Lock()

    def _leak(self):
        now = time.monotonic()
        elapsed = now - self.last_leak
        leaked = elapsed * self.rate
        self.water = max(0, self.water - leaked)
        self.last_leak = now

    def allow_request(self):
        with self.lock:
            self._leak()
            if self.water < self.capacity:
                self.water += 1
                return True
            return False

    def get_queue_size(self):
        with self.lock:
            self._leak()
            return int(self.water)

Usage Example

bucket = LeakyBucket(rate=10, capacity=50)

def handle_request(request_id):
    if bucket.allow_request():
        print(f"Request {request_id}: Processing. Queue: {bucket.get_queue_size()}")
        time.sleep(0.1)  # Simulate processing time
        return True
    else:
        print(f"Request {request_id}: Dropped. Queue full.")
        return False

# Simulate burst: 80 requests arrive in 1 second
import random
for i in range(80):
    handle_request(i)
    time.sleep(random.uniform(0.005, 0.02))

Expected output:

Request 1: Processing. Queue: 1
...
Request 50: Processing. Queue: 50
Request 51: Dropped. Queue full.
...
Request 80: Dropped. Queue full.

Leaky Bucket vs. Token Bucket

Queue-Based Leaky Bucket

For more precise control, implement with an actual queue:

from collections import deque
import asyncio

class QueueLeakyBucket:
    def __init__(self, rate, capacity):
        self.queue = deque(maxlen=capacity)
        self.rate = rate
        self.capacity = capacity

    async def process_queue(self, handler):
        while True:
            if self.queue:
                request = self.queue.popleft()
                await handler(request)
            await asyncio.sleep(1 / self.rate)

    def enqueue(self, request):
        if len(self.queue) < self.capacity:
            self.queue.append(request)
            return True
        return False

Common Mistakes

1. Using Leaky Bucket When Burst Support Is Needed

If your API benefits from bursts (most do), use token bucket instead. Leaky bucket rejects bursts.

2. Not Accounting for Processing Time

The rate is the processing rate, not the arrival rate. If processing takes longer than the leak interval, the queue grows.

3. Setting Queue Capacity Too Small

Very small queues drop requests during normal traffic variations. Size the queue for expected peak traffic.

4. Single-Threaded Queue Processing

The leak mechanism can be a bottleneck. Ensure the processor can handle the rate. If rate=1000, each request must Process in under 1ms.

5. Confusing Water Level with Requests

The water level represents queued requests, not a separate counter. Each incoming request adds water. The leak drains a fixed amount per second.

Practice Questions

1. What is the key difference between leaky bucket and token bucket?
2. When would you choose leaky bucket over token bucket?
3. How does the queue prevent system overload?
4. What happens when the queue is full?
5. How do you calculate the leak rate for a given backend capacity?

Answers:

1. Leaky bucket enforces a strict fixed rate with no burst support. Token bucket allows bursts up to capacity.
2. Choose leaky bucket when the backend has a hard capacity limit (database connections, payment processor transactions, hardware rate limits).
3. The queue absorbs short spikes up to capacity, while the fixed leak rate prevents overload of the backend processor.
4. New requests are dropped (429). The client must retry later. The queue never exceeds its configured capacity.
5. The leak rate should match the backend's maximum sustainable throughput. If the database handles 500 writes/sec, set rate=500.

Challenge: Design a leaky bucket system for a rate-limited SMS API where the carrier processes 10 messages per second. The queue should hold 100 pending messages. Simulate a burst of 500 messages.

FAQ

Mini Project

Build a leaky bucket rate limiter for an SMS API. The carrier processes 5 messages per second. The bucket holds 20 queued messages. Simulate 100 incoming messages in 2 seconds, showing which are queued, processed, and dropped. Display queue size over time.

What's Next

Continue with Fixed Window Algorithm for simpler rate limiting, or explore Sliding Window Algorithm for more accurate counting.