Leaky bucket

Un balde con un agujero en el fondo. El agua entra al ritmo que sea, y sale por el agujero a un ritmo constante. Si la viertes más rápido de lo que drena, el balde se llena; si sigues así, se desborda.

El agua son las solicitudes. El agujero es tu tasa de procesamiento.

El leaky bucket guarda las solicitudes que llegan en una cola y las procesa a un ritmo fijo, así que lo que llega al servidor es parejo sin importar qué tan desiguales fueron las llegadas.

Observando cómo se llena y se drena

Capacidad de cinco solicitudes, procesadas de a dos por segundo, empezando vacío:

Segundo	Llegan	En cola	Procesadas	En cola después	Descartadas
1	4	4	2	2	0
2	4	3, así que 5 en cola	2	3	1
3	0	0	2	1	0
4	0	0	1	0	0

En el segundo dos es donde la capacidad se hace sentir. Llegan cuatro solicitudes contra una cola que ya tiene dos, y solo entran tres. La octava solicitud se descarta directamente.

De ahí surgen dos propiedades:

• La tasa de salida nunca varía. Dos por segundo, hayan llegado ocho solicitudes o ninguna.
• La cola es primero en entrar, primero en salir. La solicitud que llegó primero se procesa primero.

Un token bucket dice: gasta tus tokens cuando quieras. Un leaky bucket dice: haz la fila, yo te proceso a mi ritmo.

JunoObservando cómo se llena y se drena La diferencia con todos los algoritmos anteriores: una solicitud que llega cuando hay mucho movimiento no se rechaza, espera.

Las solicitudes solo se descartan cuando la cola misma está llena, así que el balde absorbe una ráfaga en lugar de rechazarla.

JunoObservando cómo se llena y se drena Esperar tiene un costo real y lo paga el cliente. Una solicitud encolada detrás de otras cuatro, a dos por segundo, espera dos segundos antes de que empiece a procesarse.

Desde el punto de vista de quien llama, eso es indistinguible de un servidor lento.

Por eso una solicitud en cola igual necesita un timeout. Sin un límite en el tiempo de espera, una ráfaga se convierte en un montón de clientes que ya se rindieron pero siguen manteniendo la conexión abierta.

JunoObservando cómo se llena y se drena Comportamiento medido, para un balde de 20 que drena 5 por segundo: al llegar 25 solicitudes de golpe, se aceptaron 20 y se descartaron 5, y la vigésima esperó 4 segundos antes de ser procesada.

Ese último número es el que hay que tener en cuenta al diseñar. Una cola llena más un drenaje lento deja a las solicitudes del final esperando mucho tiempo, y 4 segundos ya está por encima del punto en el que la mayoría de los clientes reintentaron o se rindieron.

La capacidad no sale gratis solo porque esas solicitudes no fueron rechazadas.

Esto sugiere dimensionar la capacidad a partir de la latencia aceptable en lugar de la memoria disponible. A 5 por segundo, un peor caso de 2 segundos implica una cola de 10, no de 20.

En qué es bueno y en qué no

Fortalezas	Debilidades
Suaviza las ráfagas en una tasa de salida constante	No tiene flexibilidad para un pico legítimo
La cola evita la sobrecarga más adelante en el sistema	Prioriza la estabilidad del sistema por encima de la experiencia del usuario
Simple de entender e implementar	Los clientes esperan aunque el servidor pudiera haber respondido
Carga predecible, sin importar lo que llegue	La latencia crece con la profundidad de la cola

Las debilidades son la misma solución de compromiso vista desde distintos ángulos. Un leaky bucket protege al servidor haciendo esperar a los clientes, y lo hace incluso cuando el servidor tenía capacidad de sobra.

Esto es útil para gestionar el ancho de banda de una red, para streaming de video y para manejar solicitudes de servidor de forma constante, casos donde una tasa predecible vale más que una respuesta rápida ante una ráfaga.

JunoEn qué es bueno y en qué no Cada fila de esa tabla viene de la misma decisión: la tasa de salida es fija y no se adapta.

Esa es la fortaleza cuando necesitas una carga predecible, y la debilidad cuando un cliente está esperando algo que el servidor podría haber atendido de inmediato.

JunoEn qué es bueno y en qué no Usa esto cuando lo que estás protegiendo no puede absorber un pico: una API externa con su propio límite, una base de datos que se degrada con la concurrencia, un proveedor de pagos que cobra por llamada.

Usa un token bucket cuando lo que estás protegiendo puede manejar una ráfaga y quieres que los clientes sientan una respuesta ágil. La pregunta es qué hay detrás del limitador, no qué hay delante de él.

JunoEn qué es bueno y en qué no El orden estricto de primero en entrar, primero en salir es la parte que vale la pena cuestionar. Bajo sobrecarga sostenida produce head-of-line blocking, donde una solicitud lenta retrasa todo lo que viene detrás, por más económicas que estas fueran.

También implica que un cliente que inundó la cola mantiene prioridad sobre otro que llegó después con una sola solicitud, así que un leaky bucket por sí solo no da ninguna equidad entre clientes. Los buckets por cliente resuelven eso y multiplican tu estado.

Vale la pena notar el parecido también: un leaky bucket es una cola de trabajo acotada con un límite de tasa sobre el worker.

Si ya manejas una cola de tareas con límites de concurrencia, ya tienes la mayor parte de uno, y la pregunta pasa a ser si el limitador debería estar ahí en lugar de en el camino de las solicitudes.

Pruébalo

Un leaky bucket con capacidad 5, que drena 2 solicitudes por segundo, empezando vacío.

1. Llegan seis solicitudes al mismo tiempo. ¿Qué le pasa a cada una?
2. ¿Cuánto tiempo espera la sexta solicitud antes de ser procesada, si es que llega a entrar?
3. Las mismas seis llegan, pero distribuidas de a una por segundo. ¿Qué pasa?
4. ¿Qué algoritmo le conviene a un endpoint que llama a un proveedor de pagos que cobra por solicitud, y por qué?

Compara tus respuestas

#	Respuesta	Por qué
1	Cinco se encolan, una se descarta	La cola tiene capacidad para cinco y todavía no ha drenado nada, ya que la ráfaga es instantánea
2	Nunca llega a entrar	La sexta es la que se descarta. La quinta es la última aceptada, y a dos por segundo espera dos segundos y medio
3	Las seis se procesan, ninguna se descarta, ninguna espera	Una por segundo es más lento que el drenaje de dos por segundo, así que la cola nunca se acumula
4	Leaky bucket	La restricción está más adelante en el sistema y cuesta dinero por llamada, así que lo que quieres es una tasa de salida predecible. Un token bucket convertiría una ráfaga de solicitudes en una ráfaga de cobros

La pregunta tres es la que vale la pena recordar: ninguno de estos algoritmos le hace nada al tráfico que está dentro del límite. Solo se vuelven visibles en los bordes.

Hacia dónde va esto

Cinco algoritmos, y todos terminan una solicitud que se pasa de la raya con un rechazo o una espera impuesta en silencio.

Throttling hace que la espera sea deliberada y visible, frenando a un cliente a medida que se acerca a un límite en lugar de rechazarlo justo al llegar a él, y después combina ambas cosas en una sola estrategia.