Learn CybersecurityToken bucket
Todos los algoritmos vistos hasta ahora tratan una ráfaga como un problema. Pero muchas ráfagas son completamente normales: una página que carga seis cosas a la vez, o un cliente que estuvo inactivo un minuto y ahora tiene trabajo pendiente.
El token bucket permite esas ráfagas a propósito. Los tokens se acumulan a un ritmo constante, cada solicitud gasta uno, y un cliente que ha estado en silencio tiene algunos guardados.
Hojas y orugas
Una planta sostiene como máximo cinco hojas y crece tres al día. Cada oruga que llega se come una hoja, y una oruga que no encuentra hoja disponible no sobrevive.
| Día | Hojas que crecen | Orugas | Resultado | Hojas restantes |
|---|---|---|---|---|
| 1 | 3 | 2 | Ambas comen | 1 |
| 2 | 3, entonces 4 en total | 5 | 4 comen, 1 no | 0 |
| 3 | 3 | 0 | No pasa nada | 3 |
| 4 | 2, con tope de 5 | 0 | No pasa nada | 5 |
Tres ideas en esa tabla:
- Una hoja es un token, y una solicitud gasta uno.
- Los tokens llegan a un ritmo fijo, sin importar si alguien los está pidiendo o no.
- La planta no puede sostener más de su capacidad, así que el día cuatro crece dos en lugar de tres.
La capacidad es lo que permite la ráfaga. Un bucket lleno puede gastarse todo de una vez, así que un cliente que ha estado en silencio puede enviar cinco solicitudes en un instante y luego tiene que esperar a que crezcan más.
El ritmo de recarga define el promedio a largo plazo. La capacidad define qué tan grande puede ser la ráfaga que toleras.
Ese tope es la razón por la que una ráfaga tiene un límite de tamaño. Sin él, un cliente inactivo por una hora regresaría pudiendo enviar de golpe todo lo acumulado en esa hora.
Construyendo el bucket
El estado son dos números, y la lógica son dos decisiones.
class TokenBucket {
constructor(capacity, refillRate, refillInterval) {
this.capacity = capacity
this.refillRate = refillRate
this.refillInterval = refillInterval
this.tokens = capacity // empieza lleno
this.secondsSinceLastRefill = 0
}
processRequests(numRequests) {
this.secondsSinceLastRefill += 1
if (this.secondsSinceLastRefill >= this.refillInterval) {
this.tokens = Math.min(this.capacity, this.tokens + this.refillRate)
this.secondsSinceLastRefill = 0
}
const accepted = Math.min(numRequests, this.tokens)
const rejected = numRequests - accepted
this.tokens -= accepted
return { accepted, rejected }
}
}Las dos llamadas a Math.min son las que hacen el trabajo real.
La primera limita la recarga a la capacidad, así que los tokens nunca superan el tope. La segunda limita las aceptaciones a los tokens disponibles, así que una solicitud de nueve tokens contra un bucket que tiene solo uno acepta uno y rechaza ocho.
Usar >= en lugar de == en la verificación de recarga es deliberado. Si alguna vez se salta un tick, una comparación exacta se saltaría la recarga y el bucket nunca volvería a llenarse.
Empezar vacío sería más estricto y haría que la primera visita de cualquiera se sintiera como si algo estuviera roto.
Los parámetros lo cambian todo
Dos configuraciones, el mismo algoritmo.
Capacidad 10, recarga de 6 cada 3 segundos. Aproximadamente dos por segundo de forma sostenida, con espacio para diez de golpe. Viéndolo segundo a segundo:
| Ronda | Solicitadas | Aceptadas | Rechazadas | Tokens restantes |
|---|---|---|---|---|
| 1 | 3 | 3 | 0 | 7 |
| 2 | 5 | 5 | 0 | 2 |
| 3 | 7 | 7 | 0 | 1, tras recargar a 8 |
| 4 | 9 | 1 | 8 | 0 |
Generoso. Las ráfagas se absorben, y quedarse sin tokens requiere un esfuerzo deliberado.
Capacidad 8, recarga de 2 cada 10 segundos. Ahora las primeras ocho solicitudes son gratis y luego casi nada lo es. Envía cinco, luego cinco más, y te quedas vacío con ocho segundos de espera para conseguir dos tokens.
Mismo algoritmo, experiencia completamente distinta. Un cliente bajo la segunda configuración tiene que pensar cuándo gastar, porque los tokens son escasos y tardan en volver.
Ese no es un límite de tasa que moldea el tráfico. Es uno que obliga al cliente a racionar cada solicitud, y el algoritmo no cambió en absoluto.
Ponlo a prueba
Un bucket con capacidad 5, que se recarga con 2 tokens cada 2 segundos, empezando lleno.
- Un cliente envía 5 solicitudes de golpe. ¿Cuántas se aceptan y cuántas quedan?
- Dos segundos después envía 3. ¿Qué pasa?
- El cliente luego espera 10 segundos. ¿Cuántos tokens tiene?
- ¿Cuál es el ritmo sostenido que permite este bucket, y cuál es la ráfaga más grande posible?
Compara tus respuestas
1. Las 5 se aceptan, quedan 0. El bucket empieza lleno y cada solicitud gasta un token. Vaciarlo en un instante es precisamente la ráfaga que la capacidad existe para permitir.
2. Dos aceptadas, una rechazada. Pasaron dos segundos, así que el bucket se recarga con 2. Llegan tres solicitudes contra 2 tokens, así que Math.min(3, 2) acepta dos y la tercera se rechaza.
3. Cinco, no diez. Diez segundos acumularían 10 tokens, pero la capacidad lo limita a 5. Esta es la regla del día cuatro: el tiempo inactivo no se acumula indefinidamente, y eso es lo que impide que un cliente que estuvo mucho tiempo en silencio regrese con una ráfaga enorme.
4. Uno por segundo de forma sostenida, cinco de golpe. Dos tokens cada dos segundos es el promedio a largo plazo, y la capacidad de 5 es la ráfaga instantánea más grande posible.
La pregunta cuatro es el par que vale la pena recordar. El ritmo de recarga y la capacidad responden dos preguntas distintas, y describir un token bucket con un solo número deja fuera una de ellas.
Hacia dónde va esto
El token bucket le permite al cliente decidir cuándo gastar, así que el tráfico que llega a tu servidor sigue siendo desparejo. Acotado, pero desparejo.
Leaky bucket toma el enfoque contrario: acepta la ráfaga y luego la libera a un ritmo constante, de modo que lo que ve el servidor es parejo sin importar cómo llegó.