Explicá los principales algoritmos de rate limiting: token bucket, leaky bucket, ventana fija y ventana deslizante (log/contador)

#El problema que resuelve el rate limiting

Todo limitador de tasa responde la misma pregunta de fondo — "¿este cliente hizo demasiado, demasiado recientemente?" — pero "recientemente" es exactamente donde divergen los cuatro algoritmos. Un limitador tiene que comprimir todo un historial de peticiones en un estado pequeño y rápido de consultar, y el método de compresión que elija determina qué tan explosivo (bursty) puede ser el tráfico permitido, cuánta memoria cuesta cada cliente rastreado, y qué tan preciso es el limitador justo en el borde de una ventana de tiempo. No hay una elección universalmente correcta; solo hay la contrapartida que tu patrón de tráfico puede tolerar.

Sea cual sea el algoritmo detrás, un rate limiter bien comportado comunica su decisión a través de HTTP estándar: una petición rechazada recibe 429 Too Many Requests, idealmente con un header Retry-After que le diga al cliente cuánto esperar, y headers informativos X-RateLimit-Limit, X-RateLimit-Remaining y X-RateLimit-Reset en cada respuesta — permitida o no — para que un cliente bien escrito pueda autolimitarse antes de ser rechazado.

#Ventana fija (fixed window counter)

El enfoque más simple: dividir el tiempo en ventanas de tamaño fijo (digamos, una por minuto) y llevar un contador por cliente por ventana. Incrementar en cada petición; rechazar cuando el contador supera el límite; el contador se reinicia cuando cambia la ventana.

def is_allowed_fixed_window(redis_client, user_id, limit, window_seconds):
    window = int(time.time() // window_seconds)
    key = f"rate:{user_id}:{window}"
    count = redis_client.incr(key)
    if count == 1:
        redis_client.expire(key, window_seconds)
    return count <= limit

Es un INCR y un EXPIRE condicional — barato, O(1) de memoria por cliente, y trivial de razonar. Su falla está en el borde: un cliente que manda todo su límite en el último segundo de una ventana y todo su límite de nuevo en el primer segundo de la siguiente ventana efectivamente mandó el doble de la tasa prevista en unos dos segundos, y el contador nunca lo notó porque se reinició en el medio.

#Ventana deslizante con log (sliding window log)

La solución precisa: registrar el timestamp de cada petición individual en un sorted set, descartar todo lo más viejo que la ventana en cada chequeo, y contar lo que queda.

def is_allowed_sliding_log(redis_client, user_id, limit, window_seconds):
    now = time.time()
    key = f"rate:log:{user_id}"
    pipe = redis_client.pipeline()
    pipe.zremrangebyscore(key, 0, now - window_seconds)
    pipe.zadd(key, {str(now): now})
    pipe.zcard(key)
    pipe.expire(key, window_seconds)
    _, _, count, _ = pipe.execute()
    return count <= limit

Esto es exacto — no hay artefacto de borde, porque la "ventana" siempre son los N segundos anteriores relativos a ahora, no un intervalo de reloj alineado. El costo es memoria: un cliente activo con un límite generoso implica guardar una entrada por petición, que es O(n) por clave en vez de O(1). A alto volumen, con millones de clientes, esto se acumula rápido.

#Contador de ventana deslizante (sliding window counter)

Una aproximación más barata a la que realmente recurren la mayoría de los sistemas en producción: mantener dos contadores de ventana fija (la actual y la anterior) y combinarlos con un peso según cuánto avanzaste dentro de la ventana actual.

conteo_estimado = conteo_ventana_anterior * (1 - fraccion_transcurrida) + conteo_ventana_actual

Si estás 30% dentro de la ventana actual, contás el 70% del tráfico de la ventana anterior más el 100% de la ventana actual — suavizando el borde duro de una ventana fija hasta algo cercano a la precisión del log deslizante, con el costo de memoria O(1) de la ventana fija. Este es el algoritmo detrás de la mayoría de los limitadores de APIs públicas de alto volumen, porque logra el 95% de la precisión del log deslizante con una fracción minúscula de la memoria.

#Leaky bucket (cubo con fuga)

Leaky bucket modela una cola con una tasa de drenaje constante: las peticiones llenan un cubo de capacidad finita, y el cubo "gotea" — se procesa — a una tasa fija sin importar qué tan rápido lleguen las peticiones. Si el cubo está lleno, las peticiones nuevas se rechazan.

import time
import threading
from collections import deque

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.leak_rate = leak_rate  # procesadas por segundo
        self.queue = deque()
        self.last_leak = time.monotonic()
        self.lock = threading.Lock()

    def _leak(self):
        now = time.monotonic()
        elapsed = now - self.last_leak
        to_remove = int(elapsed * self.leak_rate)
        for _ in range(min(to_remove, len(self.queue))):
            self.queue.popleft()
        if to_remove > 0:
            self.last_leak = now

    def allow(self):
        with self.lock:
            self._leak()
            if len(self.queue) < self.capacity:
                self.queue.append(time.monotonic())
                return True
            return False

La característica que lo define es que leaky bucket suaviza la salida a una tasa estrictamente constante — es traffic shaping, no solo control de admisión. Este es el modelo correcto cuando lo que estás protegiendo (una base de datos downstream, un sistema legado, un recurso físico) genuinamente no puede tolerar ninguna ráfaga, solo un goteo constante. Token bucket, en cambio, permite ráfagas explícitamente.

#Token bucket (cubo de tokens)

Token bucket invierte el planteo de leaky bucket: en vez de una cola que drena a tasa constante, es un cubo que se llena de tokens a una tasa constante hasta cierta capacidad, y cada petición debe gastar un token para avanzar.

import time
import threading

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity          # tamaño máximo de ráfaga
        self.refill_rate = refill_rate    # tokens agregados por segundo
        self.tokens = capacity
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()

    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 allow(self, cost: float = 1.0) -> bool:
        with self.lock:
            self._refill()
            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False


# sostenido: 100 peticiones/minuto, ráfaga: hasta 20 de una vez
limiter = TokenBucket(capacity=20, refill_rate=100 / 60)

def handle_request() -> bool:
    return limiter.allow()

Como los tokens se acumulan mientras el cliente está inactivo, un cliente que no llamó en un rato puede legítimamente hacer una ráfaga de hasta capacity peticiones al instante, y después vuelve a la tasa sostenida refill_rate. Ese es exactamente el comportamiento que quieren la mayoría de las APIs públicas: no castigar a alguien por llamar una vez por minuto y después necesitar cinco llamadas en el mismo segundo para renderizar una pantalla.

#Lado a lado

🧠 Check your understanding
0/3 · 0/3 answered
1. Un rate limiter de ventana fija permite 100 peticiones por minuto. Un cliente manda 100 peticiones en el último segundo de la ventana A y 100 más en el primer segundo de la ventana B. ¿Qué pasó en realidad?
Esto es imposible con un limitador de ventana fijaEl limitador bloqueó correctamente el segundo loteEl limitador habría fusionado ambas ventanas automáticamenteEl cliente efectivamente mandó 200 peticiones en unos dos segundos sin nunca superar el contador en ninguna de las dos ventanas
2. ¿Cuál es la diferencia estructural clave entre token bucket y leaky bucket?
Token bucket no tiene límite de capacidadToken bucket permite ráfagas hasta su capacidad porque la capacidad no usada se acumula como tokens; leaky bucket suaviza la salida a una tasa constante sin importar las ráfagas de llegadaSon matemáticamente idénticos, solo con nombres distintosLeaky bucket permite ráfagas ilimitadas mientras que token bucket no
3. ¿Por qué un token bucket ingenuo en memoria se rompe cuando un servicio escala a varias instancias detrás de un load balancer?
Los token buckets no se pueden implementar en memoria de ninguna formaLos load balancers rechazan peticiones con headers de rate limitingCada instancia rastrea su propio conteo de tokens independiente, así que el límite efectivo pasa a ser aproximadamente el límite configurado multiplicado por el número de instanciasLos token buckets requieren una GPU para calcular las tasas de relleno