Pattern 6: Token Bucket Rate Limiting

The Problem: Smooth vs Burst Limiting

Semaphore (Pattern 1): Limits N things in flight. But doesn't account for time.

Rate Limiting: Allow N requests per second. If a user sends 100 requests instantly, they wait until tokens refill.

Use case: API rate limits (e.g., "10 requests/sec"), database query throttling, bandwidth limiting.

Semaphore vs Token Bucket

timeline title Semaphore vs Token Bucket Over Time section Semaphore(5) t=0s: 5 in flight, 95 waiting t=0.5s: 5 in flight, 95 waiting t=1s: 5 in flight, 95 waiting section Token Bucket (10/sec) t=0s: 5 sent, 5 tokens left, 95 queued t=0.5s: 5 more sent, 5 tokens left, 85 queued t=1s: 5 more sent, 5 tokens left, 75 queued

Key difference: Semaphore cares about *concurrency*. Token bucket cares about *rate* (requests per time unit).

How Token Bucket Works

stateDiagram-v2 [*] --> Empty Empty --> Refilling: Time passes Refilling --> Full: Bucket full (max capacity) Full --> Refilling: Request consumes token Refilling --> Empty: All tokens consumed
no requests note right of Empty No tokens available Requests must wait end note note right of Refilling Tokens added periodically (e.g., 10 per second) end note note right of Full Bucket at capacity Can handle burst end note

Timeline Example: 10 requests/sec limit

sequenceDiagram participant User as User participant Bucket as Token Bucket participant Handler as Handler User->>Bucket: Request 1 Bucket->>Bucket: Check: 10 tokens available? Bucket-->>Handler: YES, consume 1 token Handler->>Handler: Process User->>Bucket: Request 2-10 (instantly) Bucket->>Bucket: Check tokens Bucket-->>Handler: YES x9, consume tokens Handler->>Handler: All 10 processing User->>Bucket: Request 11 Bucket->>Bucket: Check: 0 tokens! Bucket-->>User: WAIT, no tokens Note over Bucket: 100ms passes Bucket->>Bucket: +1 token (10/sec) User->>Bucket: Request 11 (retry) Bucket->>Bucket: Check: 1 token! Bucket-->>Handler: YES, process

Implementation: asyncio Token Bucket

import asyncio
import time

class TokenBucket:
    def __init__(self, rate: float, capacity: int):
        """
        rate: tokens per second (e.g., 10)
        capacity: max tokens in bucket (e.g., 10 for 1-second burst)
        """
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last_update = time.monotonic()

    async def acquire(self, count: int = 1) -> None:
        """Wait until `count` tokens are available, then consume."""
        while True:
            self._refill()
            if self.tokens >= count:
                self.tokens -= count
                return
            # Wait before trying again
            wait_time = (count - self.tokens) / self.rate
            await asyncio.sleep(wait_time)

    def _refill(self) -> None:
        """Add tokens based on elapsed time."""
        now = time.monotonic()
        elapsed = now - self.last_update
        self.tokens = min(
            self.capacity,
            self.tokens + elapsed * self.rate
        )
        self.last_update = now

async def main():
    bucket = TokenBucket(rate=10, capacity=10)  # 10 req/sec

    async def make_request(i):
        await bucket.acquire(1)
        print(f"Request {i} proceeding at {time.time():.2f}")

    # Send 20 requests
    tasks = [make_request(i) for i in range(20)]
    await asyncio.gather(*tasks)

asyncio.run(main())

Real-World: API Rate Limiting

from fastapi import FastAPI, HTTPException
import time

app = FastAPI()
bucket = TokenBucket(rate=100, capacity=100)  # 100 req/sec limit

@app.get("/api/data")
async def get_data():
    try:
        # Non-blocking check: fail fast if no tokens
        bucket._refill()
        if bucket.tokens >= 1:
            bucket.tokens -= 1
            return {"data": "here"}
        else:
            # Return 429 Too Many Requests
            raise HTTPException(status_code=429, detail="Rate limit exceeded")
    except Exception as e:
        raise HTTPException(status_code=429)

# OR: blocking approach (wait for tokens)
@app.get("/api/data-queued")
async def get_data_queued():
    await bucket.acquire(1)
    return {"data": "here"}

Semaphore vs Token Bucket vs Queue

Pattern	Controls	Use Case
Semaphore	Concurrency (N in flight)	Connection pooling, cap parallel work
Token Bucket	Rate (N per second)	API limits, bandwidth, smooth flow
Queue	Job buffering	Backpressure, worker pools