Python Rate Limiting: Token Bucket for High-Throughput APIs

A fixed-window rate limiter — “100 requests per client per minute, reset on the minute” — has a boundary bug that will eventually page you at 2 a.m.: a client can send 100 requests at 0:59 and another 100 at 1:00, bursting 200 requests in two seconds while technically staying under the per-window cap. If your rate limiter exists to protect a database connection pool or an expensive downstream call, that burst is exactly the failure mode you built the limiter to prevent.

The token bucket algorithm doesn’t have this boundary problem, because it doesn’t think in windows at all — it thinks in a continuously refilling balance. This post builds one in Python, then makes it safe to run across multiple API instances with Redis.

Why token bucket over the alternatives

Four algorithms show up repeatedly in rate limiter implementations, and they trade off differently:

Token bucket wins for API rate limiting specifically because burst tolerance is a first-class, tunable parameter — not an artifact of window alignment. You get two independent knobs: the bucket’s capacity (how large a burst you’ll tolerate) and the refill rate (the sustained long-run rate). That maps directly onto how API providers actually describe their limits: “up to 100 requests, refilling at 10/second” is a token bucket description, and it’s how Stripe and Twitter document their own public API limits.

The core algorithm

A bucket holds tokens up to a maximum capacity. Every request consumes one token; the bucket refills continuously based on elapsed time. If there’s no token available, the request is rejected or queued.

import time
from dataclasses import dataclass, field
from threading import Lock

@dataclass
class TokenBucket:
    capacity: float          # max burst size
    refill_rate: float       # tokens added per second
    tokens: float = field(init=False)
    last_refill: float = field(init=False)
    lock: Lock = field(default_factory=Lock, init=False)

    def __post_init__(self):
        self.tokens = self.capacity
        self.last_refill = time.monotonic()

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

    def try_consume(self, cost: float = 1.0) -> bool:
        with self.lock:
            self._refill()
            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False

time.monotonic() matters here, not time.time() — the monotonic clock can’t jump backward on an NTP correction, which would otherwise let a client’s bucket refill to full instantly during a clock adjustment. This is a subtle bug that only shows up in production, intermittently, which makes it exactly the kind of thing worth getting right on the first pass.

Note also that _refill is lazy — it only recalculates when a request actually arrives, rather than running a background timer per client. For a system with thousands of distinct API keys, spawning a refill thread per bucket doesn’t scale; recalculating on read does, at zero idle cost.

Weighted costs for expensive endpoints

Not every request should cost the same token. A GET /users/:id and a POST /reports/generate that triggers a heavy aggregation query shouldn’t share a flat per-request cost — this is where the cost parameter above earns its place:

ENDPOINT_COSTS = {
    "GET /users/{id}": 1,
    "GET /search": 3,
    "POST /reports/generate": 10,
}

def check_rate_limit(bucket: TokenBucket, endpoint: str) -> bool:
    cost = ENDPOINT_COSTS.get(endpoint, 1)
    return bucket.try_consume(cost)

This turns your rate limiter from a blunt request counter into a rough proxy for actual backend load — which is usually what you’re trying to protect in the first place.

Scaling past a single process: Redis with an atomic Lua script

The in-memory TokenBucket above works for a single process. The moment you run more than one API instance behind a load balancer, per-process buckets stop being a shared source of truth — a client can get N instances’ worth of the limit by spreading requests across backends. You need the bucket state centralized, and the read-modify-write has to be atomic or you reintroduce a race condition under concurrent requests.

Redis with a Lua script solves both: Redis executes Lua scripts atomically, so the refill-and-consume logic can’t interleave with a concurrent request against the same key.

import redis
import time

TOKEN_BUCKET_LUA = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local now = tonumber(ARGV[4])

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

local elapsed = math.max(0, now - last_refill)
tokens = math.min(capacity, tokens + elapsed * refill_rate)

local allowed = 0
if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
end

redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) + 60)
return allowed
"""

class DistributedTokenBucket:
    def __init__(self, redis_client: redis.Redis, capacity: float, refill_rate: float):
        self.redis = redis_client
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.script = self.redis.register_script(TOKEN_BUCKET_LUA)

    def try_consume(self, client_key: str, cost: float = 1.0) -> bool:
        result = self.script(
            keys=[f"rate_limit:{client_key}"],
            args=[self.capacity, self.refill_rate, cost, time.time()],
        )
        return bool(result)

The EXPIRE call is a deliberate cost-control decision: a bucket that’s been at full capacity and untouched doesn’t need to live in Redis forever. Setting TTL to roughly the time it’d take to refill from empty, plus a buffer, means idle clients’ keys age out on their own instead of accumulating indefinitely across millions of API keys.

Wiring it into FastAPI middleware

The limiter should reject before your handler does any real work — that’s the entire point of putting it in middleware rather than inside each endpoint function:

from fastapi import FastAPI, Request, HTTPException

app = FastAPI()
limiter = DistributedTokenBucket(redis.Redis(), capacity=100, refill_rate=10)

@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
    api_key = request.headers.get("X-API-Key", request.client.host)
    if not limiter.try_consume(api_key):
        raise HTTPException(
            status_code=429,
            detail="Rate limit exceeded",
            headers={"Retry-After": "1"},
        )
    return await call_next(request)

Returning Retry-After isn’t cosmetic — well-behaved clients (and most HTTP libraries) back off automatically when they see it, which reduces the retry storm you’d otherwise get from clients immediately re-hammering a 429.

Testing the boundary behavior, not just the happy path

The whole reason to prefer token bucket is burst behavior at boundaries — so that’s what the test suite needs to actually exercise, not just “10 requests succeed, 11th fails”:

def test_burst_then_sustained_rate():
    bucket = TokenBucket(capacity=10, refill_rate=1.0)  # burst of 10, then 1/sec

    # Burst: first 10 succeed immediately
    assert all(bucket.try_consume() for _ in range(10))
    assert not bucket.try_consume()  # 11th fails, bucket empty

    # After 1 second, exactly 1 token has refilled
    bucket.last_refill -= 1.0  # simulate elapsed time deterministically
    assert bucket.try_consume()
    assert not bucket.try_consume()

Mutating last_refill directly instead of calling time.sleep(1) keeps this test deterministic and fast — sleeping in a test suite to validate time-based logic is a common source of flaky CI runs.

Related Reading

• The Circuit Breaker pattern in Python
• Designing a backpressure-aware job queue
• The Bulkhead pattern for isolating AI inference failures
• RFC 6585, which defines the 429 status code
• Redis’s documentation on Lua scripting with EVAL

The takeaway

Rate limiting isn’t really about counting requests — it’s about deciding what burst tolerance you’re willing to trade for average throughput, and token bucket is the algorithm that makes that trade-off an explicit, tunable parameter instead of an accident of window alignment. The in-memory version is enough for a single-process prototype; the Redis + Lua version is what makes the limit actually mean something once you’re running more than one instance behind a load balancer.