Rate Limiting and Backpressure: Token Bucket vs Leaky Bucket, Distributed Rate Limiters with Redis

Rate limiting protects your service from overload; backpressure prevents overload from cascading into collapse. They are complementary: rate limiting rejects excess work at the boundary, backpressure slows producers down when the system saturates. This guide covers the core algorithms, their trade-offs, and a production-grade distributed implementation with Redis.

Algorithm Comparison

Algorithm	Burst Behavior	Output Rate	Memory	Best For
Fixed window counter	Allows 2x burst at window edges	Uneven	O(1) per key	Simple quotas, low stakes
Sliding window log	No bursts	Precise	O(n) per key	Strict limits, low volume
Sliding window counter	Small edge bursts	Smooth approximation	O(1) per key	General-purpose API limits
Token bucket	Controlled bursts up to bucket size	Average rate enforced	O(1) per key	APIs that should tolerate bursts
Leaky bucket	No bursts	Constant output rate	O(1) per key	Smoothing traffic to downstreams

The two you will actually choose between are token bucket and leaky bucket.

Token Bucket: Bursts Allowed

A bucket holds up to capacity tokens, refilled at rate tokens per second. Each request consumes one token. Requests are rejected when the bucket is empty. Because tokens accumulate, a client that has been idle can burst up to capacity requests instantly.

import time

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity
        self.refill_rate = refill_rate  # tokens per second
        self.tokens = float(capacity)
        self.last_refill = time.monotonic()

    def allow(self) -> bool:
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now
        if self.tokens >= 1.0:
            self.tokens -= 1.0
            return True
        return False

Use token bucket when bursts are acceptable or desirable: user-facing APIs where a client syncing after being offline should not be throttled to a crawl.

Leaky Bucket: Constant Outflow

Requests enter a queue (the bucket) and are processed at a fixed rate. When the queue is full, new requests are rejected. The output rate is perfectly smooth regardless of input burstiness.

import time
from collections import deque

class LeakyBucket:
    def __init__(self, capacity: int, leak_rate: float):
        self.capacity = capacity
        self.leak_rate = leak_rate  # requests per second
        self.queue: deque[float] = deque()

    def allow(self) -> bool:
        now = time.monotonic()
        # Leak requests that have been "processed"
        while self.queue and self.queue[0] <= now - (1.0 / self.leak_rate) * len(self.queue):
            self.queue.popleft()
        if len(self.queue) < self.capacity:
            self.queue.append(now)
            return True
        return False

Use leaky bucket when protecting a downstream that cannot absorb bursts: a payment gateway with a hard TPS cap, a legacy database, or a third-party API with strict rate contracts.

Distributed Rate Limiting with Redis

In-memory buckets break the moment you run more than one instance. Redis plus a Lua script gives you an atomic check-and-update across your whole fleet. This is the standard token bucket Lua implementation:

-- rate_limit.lua
-- KEYS[1] = bucket key, ARGV = capacity, refill_rate, requested_tokens, now_seconds
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local requested = tonumber(ARGV[3])
local now = tonumber(ARGV[4])

local bucket = redis.call("HMGET", KEYS[1], "tokens", "updated_at")
local tokens = tonumber(bucket[1]) or capacity
local updated_at = tonumber(bucket[2]) or now

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

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

redis.call("HMSET", KEYS[1], "tokens", tokens, "updated_at", now)
redis.call("EXPIRE", KEYS[1], math.ceil(capacity / refill_rate) * 2)

return {allowed, math.floor(tokens)}

Calling it from Python:

import time
import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)
script = r.register_script(open("rate_limit.lua").read())

def allow_request(user_id: str, capacity: int = 100, refill_rate: float = 10.0) -> bool:
    key = f"rl:{user_id}"
    allowed, _remaining = script(
        keys=[key],
        args=[capacity, refill_rate, 1, time.time()],
    )
    return allowed == 1

Key details:

• Atomicity: the entire read-modify-write runs inside Redis, so concurrent instances cannot race.
• TTL: expiring idle keys keeps memory bounded; the TTL is set to twice the full-refill time.
• Clock: pass the client timestamp or use redis.call("TIME") inside the script for a server-side clock. Server time avoids skew between app instances.

Sliding Window Counter in Redis

When you need a smoother approximation of "N requests per minute" without storing a log, use the sliding window counter: weight the previous window's count by how much of it still overlaps.

def sliding_window_allow(key: str, limit: int, window_seconds: int = 60) -> bool:
    now = time.time()
    current_window = int(now // window_seconds)
    prev_key = f"{key}:{current_window - 1}"
    curr_key = f"{key}:{current_window}"

    pipe = r.pipeline()
    pipe.get(prev_key)
    pipe.incr(curr_key)
    pipe.expire(curr_key, window_seconds * 2)
    prev_count, curr_count, _ = pipe.execute()

    prev_count = int(prev_count or 0)
    elapsed_fraction = (now % window_seconds) / window_seconds
    estimated = prev_count * (1 - elapsed_fraction) + curr_count

    return estimated <= limit

This is O(1) memory per key and accurate enough for most API quotas.

Backpressure: Beyond Rejection

Rate limiting says "no". Backpressure says "slow down". Mechanisms, from client to server:

1. HTTP 429 with Retry-After: tell clients exactly when to retry instead of letting them hammer you with exponential guesswork.

from fastapi import FastAPI, Request
from fastapi.responses import JSONResponse

app = FastAPI()

@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
    user_id = request.headers.get("x-user-id", "anonymous")
    if not allow_request(user_id):
        return JSONResponse(
            status_code=429,
            content={"error": "rate_limit_exceeded"},
            headers={"Retry-After": "1"},
        )
    return await call_next(request)

2. Bounded queues: between pipeline stages, use queues with a maximum size. When full, producers block or drop. An unbounded queue is how a slow consumer turns into an OOM kill.

3. Concurrency limits: cap in-flight requests per dependency (bulkheads). A semaphore of 50 against your database means the 51st request waits instead of piling onto an already-saturated connection pool.

4. Load shedding: under extreme load, drop cheap-to-reject work early. Return 503 for non-critical endpoints while keeping the core path alive.

5. Stream backpressure: in reactive/streaming systems (gRPC streams, WebSockets, Kafka consumers), propagate demand signals upstream so producers slow down instead of buffering unboundedly.

Choosing Limits in Practice

• Set limits from measured capacity, not guesses: load test to find the knee where latency degrades, then set the limit at 60-70% of that.
• Limit per identity (API key, user, IP), not globally. A global limit lets one noisy tenant starve everyone.
• Return limit metadata in headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset) so well-behaved clients can self-throttle.
• Monitor rejection rates per key. A legitimate client hitting limits is a signal to raise their tier; a sudden spike from one key is abuse.

Implementation Checklist

1. Pick token bucket for user-facing APIs, leaky bucket for protecting fragile downstreams
2. Use Redis with a Lua script for atomic, fleet-wide enforcement
3. Set key TTLs so idle limiter state expires
4. Return 429 with Retry-After and rate limit headers
5. Add bounded queues and concurrency caps between internal stages
6. Load test to derive limits from real capacity curves

---

MatterAI builds frontier AI infrastructure for engineering teams — from inference-optimized models to autonomous coding agents and agentic code reviews.

Explore what we're building:

• Orbital IDE — Autonomous AI coding agent with background agents and deep codebase memory
• AI Code Reviews — Agentic pre-commit reviews across GitHub, GitLab, and Bitbucket
• Axon Models — Frontier-grade reasoning models at 70% lower inference cost

Get started free - https://app.matterai.so

• Read the docs
• View pricing

---

Follow us on X · LinkedIn · GitHub