Token Bucket Algorithm — Gentle Rate Limiting with Burst Support

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

The token bucket algorithm maintains a bucket of tokens that refill at a fixed rate, allowing requests to consume tokens and supporting short bursts up to the bucket's capacity for flexible Rate Limiting.

What You'll Learn

• How the token bucket algorithm works
• Burst vs. sustained rate trade-offs
• Python implementation with Thread Safety

Why It Matters

Token bucket is the most popular rate limiting algorithm because it handles real-world traffic patterns well. APIs see natural bursts of traffic (user clicks refresh, page loads with 10 API calls). Token bucket allows these bursts while maintaining a sustained average.

Real-World Use

Durga Antivirus Pro uses token bucket for its scan API. Each API key gets a bucket of 100 tokens refilling at 10 tokens per second. When a user runs a full system scan, 20 scan requests can burst through immediately, but the sustained rate stays at 10 req/sec.

flowchart LR
    Bucket["Token Bucket\nCapacity: 100\nRefill: 10/s"] -->|"Has token"| Allow["Allow Request"]
    Bucket -->|"Empty"| Deny["Deny Request\n429"]
    Refill["Refill Timer\n+10 tokens/sec"] --> Bucket
    style Bucket fill:#dbeafe,stroke:#2563eb

Token Bucket Implementation

import time
import threading

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()

    def _refill(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last_refill = now

    def consume(self, tokens=1):
        with self.lock:
            self._refill()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

    def get_available_tokens(self):
        with self.lock:
            self._refill()
            return self.tokens

Usage Example

bucket = TokenBucket(rate=10, capacity=20)

def handle_request(client_id):
    if bucket.consume():
        print(f"[{client_id}] Request allowed. Tokens: {bucket.get_available_tokens():.1f}")
        return process_request()
    else:
        print(f"[{client_id}] Rate limited. No tokens available.")
        return ("Rate limit exceeded", 429)

# Simulate traffic
import random
for i in range(30):
    handle_request(f"client-{i % 3}")
    time.sleep(random.uniform(0.05, 0.2))

Expected output:

[client-0] Request allowed. Tokens: 19.0
[client-1] Request allowed. Tokens: 18.0
...
[client-0] Rate limited. No tokens available.

Burst Behavior

# Create a bucket with high capacity but low refill rate
burst_bucket = TokenBucket(rate=5, capacity=50)

# Empty the bucket quickly (burst)
for i in range(55):
    allowed = burst_bucket.consume()
    print(f"Request {i+1}: {'Allowed' if allowed else 'Blocked'}")

# Wait 2 seconds (10 tokens refilled)
time.sleep(2)
print(f"\nAfter 2s: {burst_bucket.get_available_tokens():.1f} tokens available")

Expected output:

Request 1: Allowed
...
Request 50: Allowed
Request 51: Blocked
...
Request 55: Blocked

After 2s: 10.0 tokens available

Per-Client Token Buckets

class PerClientTokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate
        self.capacity = capacity
        self.buckets = {}
        self.lock = threading.Lock()

    def get_bucket(self, client_id):
        with self.lock:
            if client_id not in self.buckets:
                self.buckets[client_id] = TokenBucket(self.rate, self.capacity)
            return self.buckets[client_id]

    def consume(self, client_id, tokens=1):
        bucket = self.get_bucket(client_id)
        return bucket.consume(tokens)

Common Mistakes

1. Not Using Thread-Safe Counters

Without locks, concurrent requests can both pass the check before either decrements, allowing more requests than the limit.

2. Refilling on Every Request

Checking elapsed time on every request is fine. Creating a background timer to refill is unnecessary complexity.

3. Allowing Negative Tokens

Ensure tokens never go below zero. A client that consumed more than available breaks the algorithm.

4. Setting Capacity Too High or Too Low

Capacity too high: bursts overwhelm the backend. Capacity too low: legitimate bursts are rejected. Test with real traffic patterns.

5. Not Isolating Client Buckets

A single global bucket means one client's burst affects another's limits. Use per-client buckets.

Practice Questions

1. How does the token bucket algorithm allow bursts?
2. What happens when the bucket is full?
3. How do you calculate the sustained rate from bucket parameters?
4. Why is thread safety important in token bucket implementations?
5. What is the relationship between rate and capacity?

Answers:

1. The bucket stores up to capacity tokens. A client can consume all available tokens at once, allowing a burst up to the capacity.
2. When the bucket is full, additional tokens are discarded. The bucket never exceeds its capacity.
3. The sustained rate equals the refill rate. For rate=10, the average is 10 req/sec over a long period.
4. Without synchronization, two threads can read the same token count and both decide requests are allowed, exceeding the limit.
5. rate controls the sustained throughput. capacity controls burst size. Higher capacity allows longer bursts but requires longer recovery.

Challenge: Implement a token bucket that supports different rates for different tiers (free: rate=1, cap=10; pro: rate=10, cap=100; enterprise: rate=100, cap=1000) with Redis persistence.

FAQ

Mini Project

Build a Flask middleware that uses the token bucket algorithm for rate limiting. Each client IP gets its own bucket (rate=5, cap=20). Return proper 429 responses with X-RateLimit-* headers showing available tokens and reset time.

What's Next

Continue with Leaky Bucket Algorithm for deterministic traffic shaping, or explore Fixed Window Algorithm for simpler rate limiting.