Token bucket, leaky bucket y ventana deslizante: en qué se diferencian los algoritmos de limitación de tasa

Qué es

La parte de política (qué clave, qué cabeceras, qué código de estado) se trata en otro lugar; este artículo compara los algoritmos de conteo.

• Ventana fija: un contador por clave e intervalo, que se reinicia en el límite de la ventana. Es la opción más barata, pero un cliente puede gastar el límite completo al final de una ventana y otro límite completo al principio de la siguiente: el doble de la tasa nominal en un lapso corto.
• Registro deslizante (sliding log): se guarda la marca de tiempo de cada petición y se cuentan las que caen dentro del intervalo más reciente. Es exacto, pero la memoria crece con el volumen.
• Contador de ventana deslizante (sliding-window counter): se conservan los contadores de la ventana actual y de la anterior, y el intervalo más reciente se estima como previous * (1 - elapsed / window) + current. Es aproximado, usa memoria constante y no produce ráfagas en el límite de ventana.
• Token bucket: un bucket contiene como máximo un número determinado de tokens y se recarga a un ritmo fijo; cada petición consume un token y se rechaza si no queda ninguno. La configuración TokenBucket de Envoy nombra exactamente estos parámetros: max_tokens, tokens_per_fill y fill_interval, y el bucket comienza lleno.
• Leaky bucket: las peticiones entran en una cola que se vacía a un ritmo fijo; la cola tiene una capacidad máxima, y las peticiones que la superan se rechazan. nginx documenta limit_req como una implementación de este método, con rate, un tamaño burst y las opciones nodelay o delay para elegir si las peticiones en exceso dentro de la ráfaga se retrasan hasta ajustarse a la tasa o se atienden de inmediato.

Por qué importa

El algoritmo determina la tolerancia a ráfagas, la memoria por clave y si los clientes reciben un rechazo o una latencia añadida. Los clientes que reintentan justo en el reinicio de una ventana fija llegan todos juntos; un token bucket absorbe una ráfaga corta y después hace cumplir el promedio; un leaky bucket con retraso suaviza la carga del backend a costa de tiempo en cola.

Cómo aplicarlo

• Usa por defecto un token bucket por clave: guarda el número de tokens y el momento de la última recarga, recarga de forma perezosa en cada petición y haz que la actualización sea atómica (un único script de Redis o un bloqueo en el proceso).
• Fija el tamaño del bucket en la ráfaga que aceptas y la tasa de recarga en el límite sostenido; documenta ambos valores.
• Usa un contador de ventana deslizante cuando la promesa sea un simple "N peticiones por minuto" y las ráfagas en el límite de ventana sean inaceptables.
• Usa un leaky bucket con retraso delante de un backend, no en el borde, donde los clientes interactivos prefieren un 429 rápido con Retry-After.
• En un despliegue distribuido, centraliza el estado por clave o asume que los límites por instancia se multiplican por el número de instancias; usa un reloj monotónico para la aritmética de recarga.

Trampas

Los saltos del reloj de pared corrompen la aritmética de recarga. Un bucket que empieza vacío bloquea toda clave nueva hasta que se llena. Los registros deslizantes son una superficie de ataque por consumo de memoria. Usar la IP del cliente como clave detrás de NAT o de un CDN limita a la población equivocada. Las reglas de ráfaga sin documentar obligan a los clientes que se comportan bien a adivinar.