Algoritmos de ventana deslizante

El desborde en el límite de la ventana fija viene de dividir el tiempo en bloques. Una solicitud cae en un bloque u otro, y un tramo del reloj que cruza la unión puede acarrear el doble del límite.

Si dejas de usar bloques, el problema desaparece. Ambos algoritmos de esta sección miden contra una ventana que termina en la solicitud que se está evaluando, y solo se diferencian en cuánto recuerdan.

Registro de ventana deslizante

Guarda una marca de tiempo por cada solicitud aceptada. Cuando llega una nueva, mira hacia atrás la duración de una ventana, cuenta lo que hay ahí y decide.

La ventana se calcula de nuevo cada vez, así que se desliza detrás de cada solicitud. Mismo estacionamiento, ventana de treinta segundos, límite de cinco:

Tiempo	Llegan	La ventana mira hasta	Cantidad en la ventana	Resultado
0s	1	0s	0	Aceptada
5s	2	0s	1	Ambas aceptadas, el contador ahora es 3
15s	2	0s	3	Ambas aceptadas, el contador ahora es 5
25s	1	0s	5	Rechazada, en el límite
35s	1	5s	4	Aceptada, la solicitud de 0s ya venció
40s	3	10s	3	Dos aceptadas, la tercera rechazada

A los 35 segundos la ventana empieza en 5, así que la solicitud de 0 queda fuera de ella y ya no cuenta. Ese vencimiento es todo el mecanismo: la capacidad vuelve gradualmente conforme las solicitudes viejas salen, en lugar de recuperarse toda de golpe con un reinicio.

Ningún tramo de treinta segundos contiene jamás más de cinco solicitudes. Esa es la garantía que una ventana fija no puede ofrecer.

JunoRegistro de ventana deslizante La diferencia con una ventana fija está en dónde queda el borde de la ventana. El borde de una ventana fija está fijo en el reloj, en el mismo lugar para todos.

Aquí el borde queda detrás de la solicitud que se está evaluando, así que se mueve cada vez. Nadie recibe un reinicio, y tampoco nadie tiene que esperar uno.

JunoRegistro de ventana deslizante Esto también soluciona la sequía. Un cliente que gasta todo su presupuesto de una vez recupera capacidad de a una solicitud por vez, conforme cada una va venciendo, en lugar de esperar a que termine un bloque.

Eso se parece mucho más a lo que la gente espera que sienta un límite de tasa, y por eso vale la pena pagar el costo de esta precisión en endpoints donde rechazar a un cliente legítimo sale caro.

JunoRegistro de ventana deslizante Lo que pagas es memoria proporcional al límite, por cliente. Un límite de 5 guarda cinco marcas de tiempo; un límite de 10,000 guarda diez mil, para cada cliente, y las entradas viejas necesitan podarse o la lista crece sin fin.

En Redis esto suele ser un conjunto ordenado por cliente, indexado por marca de tiempo, con el rango vencido recortado en cada solicitud.

Son varias operaciones donde una ventana fija es un solo incremento atómico, y aun así tiene que ser atómico, o las solicitudes concurrentes leerán cada una un conteo que ya está desactualizado.

Con límites pequeños es barato y claramente correcto. Con límites grandes es el algoritmo que convierte tu limitador de tasa en la parte cara de la solicitud.

Contador de ventana deslizante

El costo del registro es la lista de marcas de tiempo. El contador logra casi la misma precisión con solo dos enteros.

Vuelve a las ventanas fijas, mantén un conteo para la ventana actual y otro para la anterior, y luego pondera el conteo anterior según cuánto de él todavía cae dentro de una mirada hacia atrás deslizante:

x         = qué tan avanzados estamos en la ventana actual, como fracción
ponderado = (1 - x) * conteoAnterior + conteoActual

aceptar si ponderado + 1 <= límite

Con una ventana de treinta segundos, un límite de 5, y una ventana anterior que se llenó por completo:

Tiempo	Dentro de la ventana	1 - x	Ponderado	Más esta solicitud	Resultado
35s	5s, o sea 1/6	5/6	5/6 × 5 + 0 = 4.17	5.17	Rechazada, supera 5
40s	10s, o sea 1/3	2/3	2/3 × 5 + 0 = 3.33	4.33	Aceptada
40s de nuevo	10s, o sea 1/3	2/3	2/3 × 5 + 1 = 4.33	5.33	Rechazada

El término (1 - x) * conteoAnterior es la estimación: conforme la ventana actual se llena, queda menos de la anterior a la vista, así que su contribución se va desvaneciendo de forma suave.

Dos contadores por cliente, y ninguna marca de tiempo.

JunoContador de ventana deslizante La fórmula hace algo sencillo. Al principio de una ventana, casi todo el conteo de la ventana anterior sigue contando en tu contra. Más tarde, cada vez menos.

En lugar de revisar qué solicitudes específicas siguen dentro del rango, asume que se repartieron parejo y toma una fracción. Más barato, y casi exacto.

JunoContador de ventana deslizante Fíjate en la tercera fila. Dos solicitudes en el mismo instante reciben respuestas distintas, porque la primera que se acepta incrementa conteoActual y la segunda se mide contra el nuevo total.

Eso es correcto, y vale la pena saberlo cuando estás probando: disparar solicitudes en un bucle apretado da resultados que dependen de cuántas ya se aceptaron en ese milisegundo.

JunoContador de ventana deslizante La aproximación es suficientemente buena para funcionar a escala de internet. Cloudflare publicó datos de 400 millones de solicitudes provenientes de 270,000 fuentes: 0.003% se permitieron o limitaron de forma distinta a un conteo exacto, sin falsos positivos.

Tres fuentes que superaban levemente el umbral fueron dejadas pasar, y la brecha promedio entre la tasa real y la aproximación fue de 6%.

Por ese margen de error obtienes dos enteros por cliente en vez de una lista, y ese es el intercambio que la convierte en la opción de producción más común.

Medido contra los 200 de una ventana fija en un límite, el registro permite exactamente 100 y el contador 101. Esa solicitud extra del contador es la aproximación asomándose, y no es lo que realmente te va a perjudicar.

Dónde discrepan

El contador asume que las solicitudes de la ventana anterior se repartieron parejo. Rara vez es así, y qué algoritmo resulta más permisivo depende de dónde se agruparon realmente.

Solicitudes cerca del inicio de la ventana anterior. El registro mira hacia atrás treinta segundos reales, ve que esas solicitudes tempranas quedan fuera de ese rango, y permite más. El contador igual les cobra una fracción, así que rechaza.

Aquí el registro es más permisivo, porque el contador está tratando la capacidad como más restringida de lo que en realidad es.

Solicitudes cerca del final de la ventana anterior. Ahora el registro todavía las tiene a la vista y rechaza, mientras que el contador ya desvaneció casi todo el conteo anterior. Aquí el contador es más permisivo, porque subestima qué tan reciente fue ese tráfico.

Así que el error va en ambas direcciones, y eso es lo que lo hace aceptable. No es un sesgo sistemático a favor de los clientes ni del servidor.

JunoDónde discrepan El contador no lleva registro de cuándo pasó algo. Solo sabe cuántas veces, y adivina cuándo.

A veces esa suposición es generosa y a veces es estricta, y eso depende por completo de cuándo llegaron realmente las solicitudes.

JunoDónde discrepan Vale la pena conocer la dirección del error al elegir. En un endpoint donde dejar pasar un poco de más es peligroso, la permisividad del contador ante tráfico concentrado al final es el caso que hay que tener en cuenta.

En uno donde rechazar a un cliente legítimo sale caro, su rigidez ante tráfico concentrado al inicio es la que va a generar tickets de soporte.

JunoDónde discrepan En principio, ambos se pueden explotar moldeando el tráfico según la ventana, y el contador más aún, porque su punto ciego es predecible: agrupa solicitudes al final de una ventana y la estimación de la siguiente las subestimará.

En la práctica, esto exige que el atacante conozca la duración de tu ventana y la alineación de sus límites, algo que se puede inferir pero cuesta trabajo, y la ganancia es apenas un puñado de solicitudes extra. No vale la pena defenderse de esto directamente.

Vale la pena defenderse no dependiendo de un único limitador. Un límite por segundo junto con uno por minuto cierra la mayoría de estos juegos de moldeo de ventana, porque una ráfaga diseñada contra una ventana sigue siendo una ráfaga contra la otra.

Ponlo a prueba

Una ventana de treinta segundos, un límite de 5, y una ventana anterior que aceptó 5 solicitudes. Todavía no hay solicitudes en la ventana actual.

1. Usando el contador, ¿se acepta una solicitud a los 33 segundos?
2. ¿En qué punto de la ventana actual se vuelve aceptable la primera solicitud?
3. Mismo tráfico, pero las 5 solicitudes de la ventana anterior llegaron todas en su primer segundo. ¿Qué algoritmo permite la solicitud a los 33 segundos, y por qué?

Compara tus respuestas

1. Rechazada. A los 33 segundos estás 3 segundos dentro de una ventana de 30 segundos, así que x es 1/10. El conteo ponderado es 0.9 × 5 + 0 = 4.5, y al sumar esta solicitud da 5.5, por encima del límite de 5.

2. A los 36 segundos. Necesitas que (1 - x) × 5 + 1 <= 5, así que (1 - x) × 5 <= 4, así que 1 - x <= 0.8 y x >= 0.2. Un quinto de una ventana de treinta segundos son 6 segundos, lo que ubica la primera solicitud aceptable a los 36 segundos.

3. El registro la permite; el contador todavía la rechaza. El registro mira hacia atrás hasta los 3 segundos. Las cinco solicitudes anteriores llegaron antes de eso, así que ya vencieron y el conteo es 0.

El contador no tiene idea de cuándo llegaron, asume una distribución pareja, y aun así les cobra 4.5 en contra. Ese es el costo concreto de la aproximación: el cliente no envió absolutamente nada en los últimos treinta segundos y de todos modos es rechazado.

Hacia dónde va esto

Ambos algoritmos hacen cumplir un promedio, y ambos tratan una ráfaga como algo que hay que prevenir. Sin embargo, mucho tráfico es legítimamente irregular: una página que carga seis recursos a la vez no es abuso.

Token bucket toma la postura opuesta: permite una ráfaga a propósito y luego hace que el cliente espere para ganarse otra.