Leaky Bucket Algorithm

1. One-Liner

The Leaky Bucket algorithm queues incoming requests and processes them at a constant rate — like water leaking from a bucket at a steady drip.

2. The Problem It Solves

Token Bucket allows bursts — if the bucket is full, many requests can go through at once. But sometimes you need a perfectly smooth, constant output rate:

Video streaming — data must flow at a steady bitrate, no spikes

Network traffic shaping — packets must be sent at a fixed rate

API output smoothing — downstream services can only handle N requests/second, no more

Leaky Bucket guarantees that no matter how bursty the input is, the output is always smooth and constant.

3. The Core Idea

Imagine a real bucket with a hole at the bottom:

Water (requests) pours in from the top — at any rate, even a flood

Water leaks out from the hole at a constant, fixed rate

If you pour in too much and the bucket overflows, that water (request) is lost (rejected)

Key difference from Token Bucket:

Token Bucket controls the input rate (how fast you can send)

Leaky Bucket controls the output rate (how fast the server processes)

4. How It Works (Step-by-Step)

Step	What Happens
1. Request arrives	A new request comes to the rate limiter
2. Drain first	Calculate how many items have leaked (been processed) since last check
3. Remove drained	Remove those items from the front of the queue (FIFO)
4. Check capacity	Is there room in the queue? (queue_size < capacity)
5a. YES → Accept	Add the request to the back of the queue
5b. NO → Reject	Queue is full — overflow — reject the request
6. Processing	Items at the front are constantly being drained at the leak rate

Key insight: The leak rate is constant. Even if 100 requests arrive at once, the server only processes them at the fixed leak rate. The queue absorbs the burst.

5. Dry Run Example

Setup: capacity = 4, leak_rate = 2/sec

Time	Action	Queue Before	Result	Queue After
0.0s	Request	0	✅ Accept	1
0.1s	Request	1	✅ Accept	2
0.2s	Request	2	✅ Accept	3
0.3s	Request	3	✅ Accept	4
0.4s	Request	4 (0 leaked)	❌ Reject	4
0.5s	Request	4 → 3 (1 leaked)	✅ Accept	4
1.0s	Request	4 → 3 (1 leaked)	✅ Accept	4
2.0s	Request	4 → 0 (4 leaked)	✅ Accept	1

Notice: at t=0.4s the queue is full so the request is rejected. But by t=0.5s, one item has leaked out, making room for a new request. The output is always steady at 2/sec.

6. Key Properties

Property	Value
Allows burst traffic?	No — output is always at constant rate
Smooth output?	Yes — perfectly constant, no spikes
Memory	O(capacity) — stores the queue
Background timer needed?	No — uses lazy evaluation like Token Bucket
Queue type	FIFO (First In, First Out)

7. Where It Is Used

Company / System	How They Use It
ATM Networks	Original use case — smoothing bursty traffic to constant rate
Linux tc	Traffic shaping with `tbf` (Token Bucket Filter) uses leaky bucket concepts
Cisco routers	Traffic policing and shaping
Video codecs	Ensure constant bitrate output
Message queues	Rate-limited consumers process at fixed speed

8. Interview Tips

What interviewers want to hear:

1. You understand the difference from Token Bucket (input vs output control)

2. You know it guarantees constant output rate (no bursts)

3. You can explain the bucket + hole analogy

4. You know the trade-off: no burst tolerance vs smooth output

5. You can discuss when to use Leaky vs Token Bucket

Common follow-up questions:

"When would you choose Leaky Bucket over Token Bucket?" → When the downstream system needs a constant, smooth rate and cannot handle any bursts.

"What’s the main disadvantage?" → No burst tolerance. Even if the server can handle a short burst, Leaky Bucket won’t allow it. Requests queue up or get rejected.

"How is this implemented in practice?" → Usually as a FIFO queue with a timer or lazy drain. In networking, it’s often combined with Token Bucket (two-rate policing).

"Can you combine Token Bucket and Leaky Bucket?" → Yes! Token Bucket controls input rate, Leaky Bucket smooths output. Many real systems use both.

9. Comparison with Other Algorithms

Algorithm	Burst Handling	Output Rate	Memory	Best For
Leaky Bucket	❌ No bursts	Constant	O(cap)	Smooth, constant output
Token Bucket	✅ Allows bursts	Variable	O(1)	APIs needing burst tolerance
Fixed Window	⚠️ Edge burst	Variable	O(1)	Simple use cases
Sliding Window Log	✅ Precise	Variable	O(n)	High accuracy needed
Sliding Window Counter	✅ Good	Variable	O(1)	Balance of accuracy & efficiency

10. Complexity

Metric	Value
Time Complexity	O(1) per request (amortized drain)
Space Complexity	O(capacity) for the queue
Drain Calculation	O(1) — simple multiplication

Implementation Example (PYTHON)

import time
from collections import deque

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.leak_rate = leak_rate
        self.queue = deque()
        self.last_leak = time.monotonic()

    def _leak(self):
        now = time.monotonic()
        elapsed = now - self.last_leak
        leaked = int(elapsed * self.leak_rate)
        for _ in range(min(leaked, len(self.queue))):
            self.queue.popleft()
        self.last_leak = now

    def allow(self, request):
        self._leak()
        if len(self.queue) < self.capacity:
            self.queue.append(request)
            return True   # ACCEPT
        return False       # REJECT