Token Bucket Rate Limiter: Smooth Traffic with Token Buckets

Overview

Token bucket is the rate limiting algorithm behind most API quotas you’ll meet in production. Imagine a bucket that drips new tokens at a constant rate — say 10 per second. Every incoming request takes one token; if the bucket is empty, the request gets rejected or queued. The bucket’s capacity caps how many tokens can pile up, which is what gives the algorithm its burst tolerance: an idle client can fire off a sudden burst up to the full capacity, then settle back to the sustained refill rate.

That burst behavior is the key difference from window-based limiters. A fixed-window counter resets at hard boundaries, so a clever client can fire 2× the limit right at the edge between two windows. Token bucket has no edges — the refill is continuous. For a broader look at when rate limiting belongs in your stack, see the API rate limiting guide.

When to Use

• API rate limiting per client or per API key
• Protecting downstream services from traffic spikes
• Controlling outbound call rate to external APIs
• Multi-tenant systems where each tenant has a rate quota
• Scenarios where bursts should be allowed but average rate controlled

When NOT to Use

• Strict per-second limits with no burst tolerance (use fixed window)
• When you need exact counts per time period (use sliding window)
• Simple internal throttling where precision doesn’t matter

Solution

Basic token bucket (Python)

# rate_limiter/token_bucket.py — In-memory token bucket rate limiter
import time
import threading
from collections import defaultdict

class TokenBucket:
    """Single token bucket with configurable rate and capacity."""

    def __init__(self, rate, capacity):
        """
        Args:
            rate: tokens per second (refill rate)
            capacity: max tokens in bucket (burst size)
        """
        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
        new_tokens = elapsed * self.rate
        self._tokens = min(self.capacity, self._tokens + new_tokens)
        self._last_refill = now

    def try_consume(self, tokens=1):
        """Try to consume tokens. Returns True if allowed, False if rejected."""
        with self._lock:
            self._refill()
            if self._tokens >= tokens:
                self._tokens -= tokens
                return True
            return False

    def consume(self, tokens=1, timeout=None):
        """Consume tokens, blocking until available or timeout."""
        while True:
            with self._lock:
                self._refill()
                if self._tokens >= tokens:
                    self._tokens -= tokens
                    return True

            if timeout is not None:
                wait_time = (tokens - self._tokens) / self.rate
                if wait_time > timeout:
                    return False
                timeout -= wait_time
                time.sleep(wait_time)
            else:
                time.sleep(tokens / self.rate)

    @property
    def available_tokens(self):
        with self._lock:
            self._refill()
            return self._tokens


class RateLimiter:
    """Manages per-key token buckets.
    Each API key, user, or IP gets its own bucket."""

    def __init__(self, default_rate=10, default_capacity=20):
        self.default_rate = default_rate
        self.default_capacity = default_capacity
        self._buckets = {}
        self._lock = threading.Lock()

    def configure(self, key, rate, capacity):
        """Configure a custom rate for a specific key."""
        with self._lock:
            self._buckets[key] = TokenBucket(rate, capacity)

    def allow(self, key, tokens=1):
        """Check if request is allowed for the given key."""
        with self._lock:
            if key not in self._buckets:
                self._buckets[key] = TokenBucket(
                    self.default_rate, self.default_capacity
                )
            bucket = self._buckets[key]

        return bucket.try_consume(tokens)

    def get_info(self, key):
        """Get bucket info for a key."""
        with self._lock:
            if key not in self._buckets:
                return None
            bucket = self._buckets[key]

        return {
            "available": bucket.available_tokens,
            "rate": bucket.rate,
            "capacity": bucket.capacity
        }


# Usage
limiter = RateLimiter(default_rate=10, default_capacity=20)

# Custom rate for premium API key
limiter.configure("premium-key", rate=100, capacity=200)

def api_request(api_key):
    if not limiter.allow(api_key):
        return {"error": "Rate limit exceeded"}, 429
    return {"data": "success"}, 200

Distributed token bucket with Redis (Python)

In-memory buckets die the moment you scale past one instance — each server keeps its own count, so N instances allow N× the intended rate. The fix is a shared store: Redis with a Lua script makes refill + consume atomic across every instance. For a production-ready version of this approach, see Rate Limiting with Redis.

# rate_limiter/redis_token_bucket.py — Distributed rate limiter using Redis
import redis
import time

class RedisTokenBucket:
    """Distributed token bucket using Redis.
    Works across multiple server instances."""

    def __init__(self, redis_url="redis://localhost:6379"):
        self._redis = redis.from_url(redis_url)

    def allow(self, key, rate, capacity, tokens=1):
        """Atomically consume tokens using Redis Lua script.
        Returns (allowed, remaining_tokens, retry_after_seconds)."""
        script = """
        local key = KEYS[1]
        local rate = tonumber(ARGV[1])
        local capacity = tonumber(ARGV[2])
        local tokens_requested = tonumber(ARGV[3])
        local now = tonumber(ARGV[4])
        local ttl = math.ceil(capacity / rate * 2)

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

        -- Refill tokens
        local elapsed = math.max(0, now - last_refill)
        local new_tokens = elapsed * rate
        current_tokens = math.min(capacity, current_tokens + new_tokens)

        -- Try to consume
        local allowed = 0
        if current_tokens >= tokens_requested then
            current_tokens = current_tokens - tokens_requested
            allowed = 1
        end

        -- Save state
        redis.call('HMSET', key, 'tokens', current_tokens, 'last_refill', now)
        redis.call('EXPIRE', key, ttl)

        local retry_after = 0
        if allowed == 0 then
            retry_after = math.ceil((tokens_requested - current_tokens) / rate)
        end

        return {allowed, math.floor(current_tokens), retry_after}
        """

        now = time.time()
        result = self._redis.eval(
            script, 1, f"ratelimit:{key}",
            rate, capacity, tokens, now
        )

        allowed = bool(result[0])
        remaining = int(result[1])
        retry_after = int(result[2])

        return allowed, remaining, retry_after


# Usage — shared across multiple server instances
limiter = RedisTokenBucket("redis://redis:6379")

def handle_request(api_key):
    allowed, remaining, retry_after = limiter.allow(
        api_key, rate=10, capacity=20
    )
    if not allowed:
        return {"error": "Rate limit exceeded",
                "retry_after": retry_after}, 429
    return {"data": "ok", "remaining": remaining}, 200

Java token bucket with Guava

// ApiRateLimiter.java — Java rate limiting with Guava RateLimiter
import com.google.common.util.concurrent.RateLimiter;
import java.util.concurrent.ConcurrentHashMap;

public class ApiRateLimiter {

    private final ConcurrentHashMap<String, RateLimiter> limiters = new ConcurrentHashMap<>();
    private final double defaultRate;

    public ApiRateLimiter(double defaultRate) {
        this.defaultRate = defaultRate;
    }

    public boolean allow(String key) {
        RateLimiter limiter = limiters.computeIfAbsent(
            key, k -> RateLimiter.create(defaultRate)
        );
        return limiter.tryAcquire();
    }

    public boolean allow(String key, int permits) {
        RateLimiter limiter = limiters.computeIfAbsent(
            key, k -> RateLimiter.create(defaultRate)
        );
        return limiter.tryAcquire(permits);
    }

    public void configure(String key, double rate) {
        limiters.put(key, RateLimiter.create(rate));
    }

    public void acquire(String key) {
        RateLimiter limiter = limiters.computeIfAbsent(
            key, k -> RateLimiter.create(defaultRate)
        );
        limiter.acquire(); // Blocks until permit available
    }
}

Express middleware (JavaScript)

// rate_limiter/express-middleware.js — Token bucket middleware for Express
const express = require("express");

class TokenBucket {
    constructor(rate, capacity) {
        this.rate = rate;
        this.capacity = capacity;
        this.tokens = capacity;
        this.lastRefill = Date.now();
    }

    tryConsume(tokens = 1) {
        this._refill();
        if (this.tokens >= tokens) {
            this.tokens -= tokens;
            return true;
        }
        return false;
    }

    _refill() {
        const now = Date.now();
        const elapsed = (now - this.lastRefill) / 1000;
        this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.rate);
        this.lastRefill = now;
    }

    get available() {
        this._refill();
        return Math.floor(this.tokens);
    }
}

class RateLimiterMiddleware {
    constructor(defaultRate = 10, defaultCapacity = 20) {
        this.defaultRate = defaultRate;
        this.defaultCapacity = defaultCapacity;
        this.buckets = new Map();
    }

    middleware() {
        return (req, res, next) => {
            const key = req.headers["x-api-key"] || req.ip;
            let bucket = this.buckets.get(key);

            if (!bucket) {
                bucket = new TokenBucket(this.defaultRate, this.defaultCapacity);
                this.buckets.set(key, bucket);
            }

            if (bucket.tryConsume(1)) {
                res.setHeader("X-RateLimit-Remaining", bucket.available);
                res.setHeader("X-RateLimit-Limit", this.defaultCapacity);
                next();
            } else {
                const retryAfter = Math.ceil((1 - bucket.tokens) / bucket.rate);
                res.setHeader("X-RateLimit-Remaining", 0);
                res.setHeader("X-RateLimit-Limit", this.defaultCapacity);
                res.setHeader("Retry-After", retryAfter);
                res.status(429).json({
                    error: "Rate limit exceeded",
                    retryAfter
                });
            }
        };
    }
}

// Usage
const app = express();
const limiter = new RateLimiterMiddleware(10, 20);
app.use("/api/", limiter.middleware());

Explanation

How it works. Every request calls try_consume(1), and before consuming anything the limiter runs _refill() — it adds elapsed × rate tokens to the bucket (capped at capacity), then subtracts one if it’s available. The lazy refill — computed on each request rather than by a timer — is why the implementation stays simple and cheap: no background thread, just arithmetic on monotonic() time.

Mechanics of a request:

Edge cases worth knowing:

• Clock drift (distributed): the Redis version uses time.time() from the caller. If app servers disagree by a few seconds, limits drift — use redis.call('TIME') inside the Lua script for a single authoritative clock.
• Atomicity: the Lua script runs as one Redis command, so refill + consume can’t interleave with another request — this is what makes the distributed version correct.
• consume() blocking: the blocking variant sleeps tokens / rate, which is the expected wait — under contention it may need several rounds. For request paths, prefer try_consume + 429 over blocking.
• Retry-After calculation: don’t hardcode it — compute (tokens_needed - available) / rate like the Redis version does, so clients back off for the right amount of time.

Choosing rate and capacity. rate is your sustained throughput (e.g., 10 req/s); capacity is your burst budget. capacity = 2-3× rate is a sane default — capacity 30 at rate 10 lets a client fire 30 requests instantly, then 10/s sustained. Setting capacity = rate kills burst tolerance entirely.

How it compares to the other algorithms:

Algorithm	Burst tolerance	Boundary edge case	Memory per key	Precision
Token bucket	Yes (capacity)	None — continuous refill	2 values	Average rate exact
Fixed window	No	Yes — 2× burst at window edges	1 counter	Approximate
Sliding window (counter)	Partial	Smoothed, not exact	2 counters	Near-exact
Leaky bucket	No — queues and drains at fixed rate	None	Queue size	Strictest

Token bucket is the default choice for API rate limiting: simple, cheap, burst-tolerant. If you need exact request counts per period — billing, audit, hard quota enforcement — use sliding window instead. For the wider protection strategy around this pattern, see Rate Limiting Security.

Variants

Sliding window counter — the precise alternative (Python)

When exact counts matter more than burst tolerance — e.g., hard quotas or billing — a sliding window counter gives near-exact accounting at similar memory cost. It weights the previous window’s count by how much of it still overlaps the current moment:

# rate_limiter/sliding_window.py — Sliding window rate limiter
import time
import threading
from collections import defaultdict

class SlidingWindowRateLimiter:
    """Sliding window counter: combines current and previous window.
    More accurate than fixed window, less memory than sliding log."""

    def __init__(self, window_size=60, max_requests=100):
        self.window_size = window_size
        self.max_requests = max_requests
        self._current = defaultdict(int)
        self._previous = defaultdict(int)
        self._window_start = time.time()
        self._lock = threading.Lock()

    def allow(self, key):
        with self._lock:
            now = time.time()
            elapsed = now - self._window_start

            # Rotate windows if needed
            if elapsed >= self.window_size:
                self._previous = self._current.copy()
                self._current = defaultdict(int)
                self._window_start = now
                elapsed = 0

            # Weighted count: current window + weighted previous window
            weight = 1 - (elapsed / self.window_size)
            count = self._current[key] + self._previous[key] * weight

            if count >= self.max_requests:
                return False

            self._current[key] += 1
            return True

Per-tier rate limiting

# rate_limiter/tiers.py — Different rates per subscription tier
# Uses RateLimiter from the basic token bucket implementation above.
class TieredRateLimiter:
    """Rate limits based on subscription tier.
    Free: 10 req/s, Pro: 100 req/s, Enterprise: 1000 req/s."""

    TIER_CONFIG = {
        "free": {"rate": 10, "capacity": 20},
        "pro": {"rate": 100, "capacity": 200},
        "enterprise": {"rate": 1000, "capacity": 2000},
    }

    def __init__(self):
        self._limiter = RateLimiter()

    def allow(self, api_key, tier="free"):
        config = self.TIER_CONFIG.get(tier, self.TIER_CONFIG["free"])
        # Configure on first use
        info = self._limiter.get_info(api_key)
        if info is None:
            self._limiter.configure(api_key, config["rate"], config["capacity"])
        return self._limiter.allow(api_key)

Rate limiter with queue

# rate_limiter/queued.py — Queue excess requests instead of rejecting
# Uses TokenBucket from the basic implementation above.
import queue
import threading

class QueuedRateLimiter:
    """Instead of rejecting, queues requests and processes at the configured rate."""

    def __init__(self, rate, capacity, max_queue=100):
        self._bucket = TokenBucket(rate, capacity)
        self._queue = queue.Queue(maxsize=max_queue)
        self._running = True

        self._worker = threading.Thread(target=self._process, daemon=True)
        self._worker.start()

    def _process(self):
        while self._running:
            item = self._queue.get()
            self._bucket.consume(1)
            item["callback"](item["request"])
            self._queue.task_done()

    def submit(self, request, callback):
        """Submit a request. Returns False if queue is full."""
        try:
            self._queue.put_nowait({"request": request, "callback": callback})
            return True
        except queue.Full:
            return False

    def stop(self):
        self._running = False

Best Practices

• Set rate headers — X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After help clients self-regulate
• Use distributed rate limiting for multi-instance deployments — Redis-based, not in-memory
• Return 429 with Retry-After — standard HTTP status for rate limiting
• Allow bursts — token bucket’s capacity handles legitimate bursts without rejecting
• Use per-key buckets — per API key, per user, per IP, not global
• Set bucket TTL — clean up inactive buckets to prevent memory growth
• Monitor rejection rate — high rejection rates indicate misconfigured limits
• Test under load — verify the limiter behaves correctly at the rate boundary

Common Mistakes

• Global rate limit: all clients share one bucket. One noisy client exhausts the limit for everyone.
• No Retry-After header: clients don’t know when to retry and poll aggressively.
• In-memory only in multi-instance: every instance keeps its own counter, so N servers let through N× the intended rate.
• Capacity equals rate: no burst tolerance. Set capacity to 2-3× the rate for burst handling.
• No cleanup of old buckets: memory grows indefinitely. Set TTL on inactive buckets.

Further Reading

• IETF — RateLimit header fields for HTTP (draft)
• Redis documentation — Lua scripting
• Guava RateLimiter — concurrency utilities
• Stripe Engineering — Rate limiters