Leaky Bucket Algorithm — Complete Traffic Shaping Guide

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 constant, fixed rate. Excess requests are queued (or dropped). Unlike token bucket which allows bursts, leaky bucket enforces a strict output rate.

What You'll Learn

You'll learn how the leaky bucket algorithm works, how it differs from token bucket, and when to use each.

Why It Matters

Leaky bucket is ideal for stabilizing traffic to downstream systems that cannot handle bursts, such as legacy databases or third-party APIs with strict rate limits.

Real-World Use

A data pipeline writes to a legacy database that can only handle 100 writes per second. A leaky bucket queue processes writes at exactly 100/sec, smoothing out any input bursts to protect the database.

flowchart LR
    A[Bursty Input] --> B[(Queue)]
    B -->|Leak at Constant Rate| C[Steady Output]
    D[Queue Full] --> E[Drop Requests]

Implementation

import time
import asyncio

class LeakyBucket:
    def __init__(self, rate_per_sec, queue_size):
        self.rate = rate_per_sec
        self.queue = asyncio.Queue(maxsize=queue_size)
        self.last_leak = time.time()
        self.interval = 1.0 / rate_per_sec

    async def add_request(self, request):
        if self.queue.full():
            return False
        await self.queue.put(request)
        return True

    async def process_requests(self):
        while True:
            request = await self.queue.get()
            await self.handle_request(request)
            await asyncio.sleep(self.interval)

    async def handle_request(self, request):
        print(f"Processing: {request}")

async def main():
    bucket = LeakyBucket(rate_per_sec=10, queue_size=100)
    asyncio.create_task(bucket.process_requests())
    for i in range(50):
        added = await bucket.add_request(f"req-{i}")
        print(f"Added req-{i}: {added}")

asyncio.run(main())

Common Mistakes

| Mistake | Fix | |---------|-----| | No queue limit | Memory exhaustion from unlimited queuing | Set max queue size | | Large queue hides problems | Delayed processing for all clients | Keep queue small, return 429 fast | | Synchronous processing | Blocking I/O stops the leak | Use async processing | | Not dropping oldest requests | Stale requests processed after timeout | Drop expired requests from queue | | No timeout on queued requests | Users wait too long | Return 429 after queue delay threshold |

Practice Questions

1. How does leaky bucket differ from token bucket?
2. What happens when the queue is full?
3. When would you choose leaky bucket over token bucket?
4. How do you set the queue size?
5. What is the disadvantage of strict output rate?

Challenge

Implement a leaky bucket for a database write API. Set rate=10/sec, queue=50. Send 100 requests in 1 second. Verify that only 10/sec are processed.

What's Next

Learn about the fixed window algorithm.