Patrón Token Bucket: Rate Limiting con Ráfagas Controladas

Descripción General

Token bucket es el algoritmo de rate limiting detrás de la mayoría de las cuotas de API que vas a encontrar en producción. Imagina un cubo que gotea nuevos tokens a ritmo constante — digamos 10 por segundo. Cada petición entrante toma un token; si el cubo está vacío, la petición se rechaza o se encola. La capacidad del cubo limita cuántos tokens pueden acumularse, y eso es lo que le da tolerancia a ráfagas: un cliente inactivo puede disparar una ráfaga repentina hasta agotar la capacidad, y luego vuelve al ritmo sostenido de refill.

Esa tolerancia a ráfagas es la diferencia clave frente a los limiters basados en ventanas. Un contador de ventana fija se reinicia en fronteras duras, así que un cliente astuto puede disparar 2× el límite justo en el borde entre dos ventanas. Token bucket no tiene bordes — el refill es continuo. Para una visión más amplia de cuándo encaja el rate limiting en tu stack, mira la guía de API rate limiting.

Cuándo Usar

• Rate limiting de API por cliente o por API key
• Proteger servicios downstream de picos de tráfico
• Controlar el ritmo de llamadas salientes a APIs externas
• Sistemas multi-tenant donde cada tenant tiene una cuota de rate
• Escenarios donde las ráfagas deben permitirse pero el rate promedio controlarse

Cuándo NO Usar

• Límites estrictos por segundo sin tolerancia a ráfagas (usa ventana fija)
• Cuando necesitas conteos exactos por período (usa sliding window)
• Throttling interno simple donde la precisión no importa

Solución

Token bucket básico (Python)

# rate_limiter/token_bucket.py — Token bucket rate limiter en memoria
import time
import threading
from collections import defaultdict

class TokenBucket:
    """Token bucket individual con rate y capacidad configurables."""

    def __init__(self, rate, capacity):
        """
        Args:
            rate: tokens por segundo (ritmo de refill)
            capacity: máximo de tokens en el bucket (tamaño de ráfaga)
        """
        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):
        """Intenta consumir tokens. Devuelve True si se permite, False si se rechaza."""
        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, bloqueando hasta que estén disponibles o venza el 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:
    """Gestiona token buckets por clave.
    Cada API key, usuario o IP tiene su propio 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):
        """Configura un rate personalizado para una clave concreta."""
        with self._lock:
            self._buckets[key] = TokenBucket(rate, capacity)

    def allow(self, key, tokens=1):
        """Comprueba si la petición está permitida para la clave."""
        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):
        """Obtiene la info del bucket de una clave."""
        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
        }


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

# Rate personalizado para una API key premium
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

Token bucket distribuido con Redis (Python)

Los buckets en memoria mueren en cuanto escalas más allá de una instancia — cada servidor lleva su propio conteo, así que N instancias permiten N× el rate previsto. La solución es un store compartido: Redis con un script Lua hace atómico el refill + consume entre todas las instancias. Para una versión lista para producción de este enfoque, mira Rate Limiting con Redis.

# rate_limiter/redis_token_bucket.py — Rate limiter distribuido con Redis
import redis
import time

class RedisTokenBucket:
    """Token bucket distribuido usando Redis.
    Funciona a través de múltiples instancias de servidor."""

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

    def allow(self, key, rate, capacity, tokens=1):
        """Consume tokens atómicamente con un script Lua de Redis.
        Devuelve (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)

        -- Obtener el estado actual del bucket
        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 de tokens
        local elapsed = math.max(0, now - last_refill)
        local new_tokens = elapsed * rate
        current_tokens = math.min(capacity, current_tokens + new_tokens)

        -- Intentar consumir
        local allowed = 0
        if current_tokens >= tokens_requested then
            current_tokens = current_tokens - tokens_requested
            allowed = 1
        end

        -- Guardar el estado
        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


# Uso — compartido entre múltiples instancias de servidor
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

Token bucket en Java con Guava

// ApiRateLimiter.java — Rate limiting en Java con 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(); // Bloquea hasta que haya permiso disponible
    }
}

Middleware de Express (JavaScript)

// rate_limiter/express-middleware.js — Middleware de token bucket para 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
                });
            }
        };
    }
}

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

Explicación

Cómo funciona. Cada petición llama a try_consume(1). El limiter primero ejecuta _refill(): se añaden elapsed × rate tokens al bucket (tope en capacity), y luego se consume un token si hay disponible. El refill perezoso — calculado en cada petición en lugar de por un temporizador — es lo que mantiene la implementación simple y barata: sin hilo en segundo plano, solo aritmética sobre monotonic().

Mecánica de una petición:

Casos límite que conviene conocer:

• Desfase de reloj (distribuido): la versión Redis usa time.time() del llamador. Si los servidores de aplicación difieren unos segundos, los límites derivan — usa redis.call('TIME') dentro del script Lua para un reloj único y autoritativo.
• Atomicidad: el script Lua corre como un único comando de Redis, así que el refill + consume no puede intercalarse con otra petición — eso es lo que hace correcta la versión distribuida.
• consume() bloqueante: la variante bloqueante duerme tokens / rate, que es la espera esperada — bajo contención puede necesitar varias rondas. En rutas de peticiones, prefiere try_consume + 429 antes que bloquear.
• Cálculo de Retry-After: no lo fijes a mano — calcula (tokens_needed - available) / rate como hace la versión Redis, para que los clientes esperen el tiempo correcto.

Elegir rate y capacity. rate es tu throughput sostenido (p. ej., 10 req/s); capacity es tu presupuesto de ráfaga. capacity = 2-3× rate es un default sensato — capacity 30 con rate 10 permite que un cliente dispare 30 peticiones de golpe, y luego 10/s sostenido. Poner capacity = rate mata la tolerancia a ráfagas por completo.

Cómo se compara con los otros algoritmos:

Algoritmo	Tolerancia a ráfagas	Caso borde en fronteras	Memoria por clave	Precisión
Token bucket	Sí (capacity)	Ninguno — refill continuo	2 valores	Rate promedio exacto
Ventana fija	No	Sí — ráfaga 2× en bordes de ventana	1 contador	Aproximada
Sliding window (contador)	Parcial	Suavizado, no exacto	2 contadores	Casi exacta
Leaky bucket	No — encola y drena a rate fijo	Ninguno	Tamaño de cola	La más estricta

Token bucket es la opción por defecto para rate limiting de API: simple, barato, tolerante a ráfagas. Si necesitas conteos exactos por período — facturación, auditoría, cuotas duras — usa sliding window. Para la estrategia de protección más amplia alrededor de este patrón, mira Rate Limiting Security.

Variantes

Sliding window — la alternativa precisa (Python)

Cuando los conteos exactos importan más que la tolerancia a ráfagas — p. ej., cuotas duras o facturación — un contador de sliding window da contabilidad casi exacta con coste de memoria similar. Pondera el conteo de la ventana anterior según cuánto de ella todavía se solapa con el momento actual:

# rate_limiter/sliding_window.py — Rate limiter de sliding window
import time
import threading
from collections import defaultdict

class SlidingWindowRateLimiter:
    """Contador de sliding window: combina ventana actual y anterior.
    Más preciso que la ventana fija, menos memoria que 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

            # Rotar ventanas si hace falta
            if elapsed >= self.window_size:
                self._previous = self._current.copy()
                self._current = defaultdict(int)
                self._window_start = now
                elapsed = 0

            # Conteo ponderado: ventana actual + ventana anterior ponderada
            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

Rate limiting por niveles

# rate_limiter/tiers.py — Rates distintos por nivel de suscripción
# Usa RateLimiter de la implementación básica de arriba.
class TieredRateLimiter:
    """Rate limits según el nivel de suscripción.
    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"])
        # Configurar en el primer uso
        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 con cola

# rate_limiter/queued.py — Encola peticiones excedentes en vez de rechazar
# Usa TokenBucket de la implementación básica de arriba.
import queue
import threading

class QueuedRateLimiter:
    """En vez de rechazar, encola peticiones y las procesa al rate configurado."""

    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):
        """Envía una petición. Devuelve False si la cola está llena."""
        try:
            self._queue.put_nowait({"request": request, "callback": callback})
            return True
        except queue.Full:
            return False

    def stop(self):
        self._running = False

Mejores Prácticas

• Establece headers de rate — X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After ayudan a los clientes a autorregularse
• Usa rate limiting distribuido en despliegues multi-instancia — basado en Redis, no en memoria
• Devuelve 429 con Retry-After — el status HTTP estándar para rate limiting
• Permite ráfagas — la capacidad del token bucket absorbe ráfagas legítimas sin rechazar
• Usa buckets por clave — por API key, por usuario, por IP, no globales
• Establece TTL al bucket — limpia buckets inactivos para evitar crecimiento de memoria
• Monitoriza el rate de rechazos — tasas altas indican límites mal configurados
• Prueba bajo carga — verifica que el limiter se comporta correctamente en el borde del rate

Errores Comunes

• Rate limit global: todos los clientes comparten un bucket. Un cliente ruidoso agota el límite para todos.
• Sin header Retry-After: los clientes no saben cuándo reintentar y hacen polling agresivo.
• Solo en memoria en multi-instancia: cada instancia lleva su propio contador, permitiendo N× el rate.
• Capacity igual a rate: sin tolerancia a ráfagas. Pon capacity a 2-3× el rate para manejo de ráfagas.
• Sin limpieza de buckets viejos: la memoria crece indefinidamente. Pon TTL a los buckets inactivos.

Lectura Adicional

• IETF — RateLimit header fields for HTTP (borrador)
• Documentación de Redis — Scripting con Lua
• Guava RateLimiter — utilidades de concurrencia
• Stripe Engineering — Rate limiters