Limitación de tasa (rate limiting)

El panorama: palabras que vas a encontrar

Un limitador de tasa (rate limiter) es un pequeño portero colocado frente a un servicio. Para cada solicitud hace una pregunta: '¿este cliente ya usó su parte?'. Si no, la solicitud entra. Si sí, se rechaza. Todo este resumen trata de cómo cuenta el portero y de lo que pasa con los que rechaza.

Palabras que vas a encontrar

• Clave (key): el nombre bajo el cual cuenta el limitador. Puede ser una dirección IP, un usuario, una clave de API o una empresa cliente. Cada clave tiene su propia cuenta.
• Límite: el mayor número de solicitudes permitidas, por ejemplo 100.
• Ventana: el trozo de tiempo al que se refiere el límite, por ejemplo 'por minuto'. Así que '100 por minuto' significa límite 100 y ventana de 60 segundos.
• Tasa: cuántas solicitudes por unidad de tiempo, por ejemplo 5 por segundo.
• [[Ráfaga (burst)|muchas solicitudes que llegan casi en el mismo instante]]: muchas solicitudes juntas. Algunos limitadores permiten una ráfaga pequeña, otros no.
• Admitir y rechazar: admitir una solicitud es dejarla pasar. Rechazarla es negarla (por ejemplo, con la respuesta 429).
• Rendimiento (throughput): cuántas solicitudes por segundo se completan de verdad.

Las dos preguntas que responde todo limitador

Una regla como '10 solicitudes por segundo' no dice qué pasa cuando llegan 20 solicitudes en 200 milisegundos. Cada algoritmo responde eso a su manera, y esa respuesta es lo que de verdad eliges al elegir un algoritmo.

Por qué y dónde limitar

¿Por qué un servicio rechazaría solicitudes a propósito? Porque un servidor tiene una cantidad fija de trabajo que puede hacer por segundo. Si un cliente toma demasiado, los demás esperan o reciben errores. Un limitador da cuatro cosas: mantiene el servicio disponible, mantiene a los clientes justos entre sí, mantiene el costo bajo control (algunas solicitudes cuestan dinero de verdad) y frena la fuerza bruta (probar miles de contraseñas) y el scraping (copiar un sitio entero con una máquina).

¿Qué clave contamos?

Ten cuidado con el encabezado X-Forwarded-For. Es una línea común de la solicitud, y quien envía la solicitud escribe en ella lo que quiera. Solo es confiable cuando lo rellenó un proxy que tú controlas. Si un servicio está abierto a Internet sin proxy delante, debe usar la dirección de la conexión real. Si usa el encabezado, el atacante solo cambia el encabezado cada vez y consigue claves nuevas sin fin.

Apilando límites

Un limitador solo controla el total de la clave que cuenta. Si cada usuario puede mandar 100 por minuto y una empresa cliente tiene 400 usuarios, esa empresa puede mandar hasta 40.000 por minuto. Por eso los sistemas grandes apilan claves: un límite por usuario, uno por tenant, a veces uno global. Una solicitud debe pasar por todos. También ayuda tener un límite distinto para cada endpoint: POST /login y el envío de SMS deben tener límites muy bajos, porque cada intento es un riesgo o cuesta dinero, mientras que una lectura barata puede tener uno alto. Un solo límite holgado para todo termina siendo demasiado holgado para los endpoints sensibles.

¿Dónde vive el limitador?

cliente --> CDN/borde --> gateway --> aplicación --> dependencia
  (1)         (2)          (3)           (4)            (5)

(1) en el propio cliente (educado, pero no obligatorio)
(2) en el borde: barato para rechazar, poco contexto
(3) en el gateway de API o proxy inverso
(4) en la aplicación: conoce usuario y operación
(5) justo antes de una dependencia cara (SMS, base de datos)

Cuanto más cerca del origen del tráfico, más barato es decir que no, pero menos sabe el limitador de la solicitud. Por eso se combinan capas: un límite grueso y barato en el borde, y límites finos por usuario y por operación en la aplicación. Para proteger una dependencia de capacidad o costo limitados (por ejemplo un proveedor de SMS que cobra por mensaje), pon el limitador justo antes de ella, cuenta en la unidad que ella cobra (mensajes, no solicitudes) y compártelo entre todos los caminos de código, porque un job nocturno puede llegar al proveedor sin pasar por el gateway.

Justo no es lo mismo que seguro

Imagina un servicio que aguanta 400 solicitudes por segundo y 10 clientes que pueden mandar 100 por segundo cada uno. Los límites son justos, pero juntos permiten 1.000 por segundo, más que 400. Los límites por cliente normalmente se venden por encima de la capacidad, con la esperanza de que no todos usen el máximo a la vez. Para proteger el servicio también necesitas un límite global o descarte de carga. Y una avalancha de 200.000 direcciones distintas, cada una por debajo de su límite, igual tumba el servicio, porque el daño viene de la suma. Un limitador dentro de la aplicación además decide tarde: la solicitud ya usó una conexión y algo de trabajo.

Ventana fija

La manera más simple de contar es cortar el tiempo en rebanadas iguales, como las hojas de un calendario, y guardar un marcador por rebanada. Cada rebanada es una ventana de tamaño W. La ventana número k cubre desde el instante k veces W hasta (sin incluir) k+1 veces W. Para W = 10 segundos las ventanas son [0,10), [10,20), [20,30) y así sucesivamente. El paréntesis significa 'no incluido'. Así que un instante exactamente en 10 pertenece a la ventana que está empezando.

La regla: cuando llega una solicitud, busca su ventana, mira el contador de esa ventana y admite la solicitud si el contador está por debajo del límite. Luego suma uno. En cada frontera el contador vuelve a cero. El estado es mínimo: un contador y el número de ventana por cliente. Esa es la gran cualidad del algoritmo. La memoria no depende del límite ni del tamaño de la ventana, así que pasar de un límite de 500 a 5.000 no cuesta nada extra.

El punto débil: la frontera

  ventana [0,10)           ventana [10,20)
|------------------------|------------------------|
                   8 9 9 | 10 11 12
                   ^^^^^   ^^^^^^^^
                   3 admitidas  3 admitidas

contador: 0 .. 1 2 3     | 0 -> 1 2 3  (vuelve a cero)

Un cliente puede gastar todo el límite al final de una ventana y otra vez al comienzo de la siguiente. En un intervalo mucho menor que W consigue pasar hasta 2 veces el límite. La regla parece prometer L por ventana, pero permite el doble cerca de una frontera. Ese es el defecto clásico de la ventana fija.

¿Dónde empiezan las ventanas?

Hay dos maneras comunes de armarlo en Redis. En la primera, el número de ventana va en el nombre de la clave (por ejemplo rl:client42:7), así que las ventanas están alineadas con el reloj y son iguales para todos. En la segunda hay una clave por cliente, la clave recibe un tiempo de vida con EXPIRE solo cuando INCR devuelve 1, y la ventana empieza en la primera solicitud del cliente:

local n = redis.call('INCR', KEYS[1])
if n == 1 then
	redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return n

Las dos formas siguen permitiendo una ráfaga doble, solo que en lugares distintos. En la segunda forma la primera ráfaga queda limitada al límite, pero aún hay una frontera cuando la clave expira. Las dos líneas van juntas en un script para que la clave nunca quede sin expiración.

Pequeños detalles que cambian los números

• Mismo promedio, otra ventana. '600 por minuto' como una ventana de 60 s permite hasta 1.200 cerca de una frontera. '10 por segundo' como ventanas de 1 segundo mantiene la ráfaga pequeña, pero rechaza a un buen cliente que manda un lote pequeño de golpe. El tamaño de la ventana elige el tamaño de la ráfaga que toleras.
• Contar solicitudes rechazadas. En la ventana fija no cambia quién es admitido, porque el contador se pone en cero en la frontera de todos modos. Solo cambia el número guardado, que puede ser una buena medida del exceso.
• Clientes sincronizados. Con ventanas alineadas al reloj, todos recuperan su límite en el mismo instante. Los clientes que esperan la renovación vuelven a intentar todos juntos, una estampida en la frontera. Un retraso aleatorio en el cliente (jitter) o un algoritmo sin frontera ayuda.

Log deslizante y contador deslizante

La ventana fija lo olvida todo en la frontera. ¿Y si la ventana se moviera con cada solicitud? En vez de 'esta hora del calendario', pregunta: 'en los últimos W segundos antes de ahora, ¿cuántas solicitudes se admitieron?'. Esa ventana se desliza hacia adelante todo el tiempo, así que no hay frontera que explotar. Hay dos maneras de hacerlo.

Log deslizante: exacto, pero pesado

El log deslizante (sliding log) guarda la marca de tiempo de cada solicitud admitida, como un cuaderno donde el portero anota la hora a la que entró cada invitado. Cuando llega una solicitud en el instante t, borra las anotaciones demasiado viejas, cuenta lo que queda y admite a la recién llegada si la cuenta está por debajo del límite L. La convención usada aquí: una anotación de exactamente W segundos ya expiró, así que la ventana es (t - W, t]. Solo se anotan las solicitudes admitidas.

El log olvida cada solicitud por separado, exactamente W segundos después de admitirla, así que en cualquier intervalo de W segundos nunca hay más de L solicitudes admitidas. El precio es la memoria: hasta L marcas de tiempo por cliente. Un límite de 10.000 por hora puede significar 10.000 entradas para un solo cliente. En Redis suele ser un sorted set por cliente, con la marca de tiempo como score.

Contador deslizante: barato y casi exacto

El contador deslizante (sliding counter) guarda solo dos números por cliente: la cuenta de la ventana fija anterior (prev) y la de la actual (cur). Para estimar los últimos W segundos usa una parte de la ventana anterior más toda la actual:

estimación = prev * (1 - elapsed / W) + cur
admite cuando estimación < límite   (la estimación se calcula antes de contar la nueva solicitud)

Ejemplo: límite 100, W = 60 s, prev = 80, cur = 30, y la solicitud llega 15 s después de que empezó la ventana. Tres cuartos de la ventana anterior aún cuentan (1 - 15/60 = 0,75), así que la estimación es 80 x 0,75 + 30 = 90, por debajo de 100: admitida. El peso de la ventana anterior baja de forma continua de 1 a 0, así que un cliente que gastó su límite recupera los cupos poco a poco, no todos de golpe.

La estimación depende de una suposición: que las solicitudes de la ventana anterior estaban repartidas por igual en ella, porque el contador solo sabe cuántas fueron, no cuándo. Cuando la suposición falla, la respuesta falla, de manera acotada:

• Solicitudes anteriores concentradas al final de la ventana: todas siguen dentro de los últimos W segundos, pero solo se cuenta una fracción. El contador subestima y puede admitir más que el límite.
• Solicitudes anteriores concentradas al comienzo: ninguna sigue dentro de los últimos W segundos, pero aún se cuenta una fracción. El contador sobrestima y rechaza solicitudes que el log exacto admitiría.

Los tres algoritmos de ventana lado a lado

Token bucket (cubeta de tokens)

Imagina una cubeta de fichas de juguete. Para hacer una solicitud pagas una ficha. Un grifo suelta fichas nuevas en la cubeta a una velocidad constante, pero la cubeta solo guarda cierta cantidad, y las fichas de más se derraman. Si la cubeta está vacía, esperas la siguiente ficha. Este es el token bucket.

Las dos perillas

Tener dos perillas es la fuerza del algoritmo: la ráfaga que toleras y el promedio que sostienes dejan de ser el mismo número. Una cubeta vacía significa que el cliente gastó su ráfaga: la solicitud se rechaza (en un limitador de API) o se retrasa (en un modelador de tráfico) hasta que aparezca una ficha. Mientras la cubeta sigue vacía, el rendimiento es exactamente r.

El saldo y el tope

// saldo = min(B, saldo + r * transcurrido)
function allow(b: { tokens: number; last: number }, now: number): boolean {
	const elapsed = now - b.last;
	b.tokens = Math.min(B, b.tokens + elapsed * r);
	b.last = now;
	if (b.tokens >= 1) { b.tokens -= 1; return true; }
	return false;
}

Nadie necesita un temporizador que suelte una ficha en cada instante. Como las fichas llegan a velocidad constante, el saldo anterior y el instante de la última actualización bastan para calcular el saldo ahora. Esto se llama reposición perezosa (lazy refill), y el estado por cliente son solo dos campos. Las fracciones de ficha cuentan: con r = 0,5 por segundo, dos segundos dan una ficha entera.

¿Cuántas pueden pasar?

En cualquier intervalo de T segundos un token bucket admite como máximo B + r x T solicitudes: la ráfaga guardada más lo que produjo el grifo mientras tanto. Cuanto más largo el intervalo, menos pesa el término B, y el promedio se acerca a r.

Por eso no se puede elegir r solo por el techo. Si una API tolera como máximo N solicitudes en cualesquiera T segundos, necesitas B + r x T <= N, no solo r x T <= N. Ejemplo: como máximo 100 cada 10 segundos y una ráfaga de 40 significa r x 10 <= 60, así que r = 6 por segundo. Cada ficha dada a la ráfaga es una menos para la tasa sostenida.

Más ideas

• Tiempo de espera. Si el saldo es s (menor que 1), la próxima solicitud se admitirá después de (1 - s) / r segundos. Es el número que un servidor puede enviar en Retry-After.
• Costo ponderado. Una solicitud puede costar más de una ficha. Una exportación puede costar 25 fichas y una lectura 1. La regla es: admite cuando saldo >= costo, sin pago parcial. Con saldo bajo, las llamadas baratas siguen pasando mientras las caras esperan.
• Modelado de tráfico con bytes. Las fichas pueden ser bytes. Con cubeta B = 16 MB, tasa de fichas R = 2 MB/s y un enlace que envía como máximo M = 10 MB/s, una cubeta llena deja al host enviar a velocidad máxima durante B / (M - R) = 16 / 8 = 2 segundos, y luego cae a R.

Leaky bucket (cubeta con fugas)

Ahora da vuelta la imagen. Imagina una cubeta con un agujerito en el fondo. Puedes echar agua tan rápido como quieras, pero sale por el agujero a una velocidad constante. Si echas demasiada, la cubeta se desborda. Este es el leaky bucket, y tiene dos lecturas que usan la misma imagen.

Lectura 1: una fila (un modelador)

Las solicitudes entran en una fila de espera de tamaño limitado. Salen de la fila a una tasa constante, una cada intervalo fijo. Una ráfaga no se rechaza: espera en la fila y sale de forma pareja. Si la fila está llena, la solicitud que llega se descarta, como el agua por encima del borde.

llegadas (9 de golpe)
       |
       v
  +---------+
  | 6 cupos |  3 solicitudes no caben: descartadas
  +----+----+
       | una cada 0,5 s
       v
  salida: 0,5  1,0  1,5  2,0  2,5  3,0 s

El sistema detrás de la cubeta nunca recibe más que la tasa de salida, por muy llena de ráfagas que esté la entrada. El precio es el retraso: si la fila drena r solicitudes por segundo, la solicitud con k - 1 delante espera k / r segundos (la primera salida ocurre un intervalo después de la llegada a una fila vacía). La peor espera posible es capacidad / r, así que el tamaño de la fila también es una elección de latencia máxima.

Lectura 2: un medidor (un fiscalizador)

Como medidor (meter), la cubeta no guarda ninguna solicitud. Guarda solo un número, el nivel. Cada solicitud admitida suma 1 al nivel, y el nivel se drena a una tasa constante. Una solicitud se admite cuando nivel + 1 <= capacidad, y la decisión es inmediata: nada espera.

El medidor es la imagen en el espejo del token bucket. Con fichas = capacidad - nivel, las reglas de uno se vuelven las reglas del otro. Los dos admiten exactamente las mismas solicitudes y los dos permiten una ráfaga de hasta la capacidad con tasa media r. Solo la lectura como fila se comporta distinto, porque retiene y retrasa solicitudes.

Modelar y fiscalizar

En palabras de Tanenbaum, modelar regula la tasa media y el tamaño de la ráfaga de un flujo antes de que entre a la red, normalmente retrasando paquetes. Fiscalizar es la red comprobando que el flujo respete el patrón acordado, y descartando o marcando el exceso.

¿Token bucket o leaky bucket?

Después de mucho tiempo tranquilo, un cliente manda 10 solicitudes de golpe. Un token bucket de capacidad 10 juntó fichas mientras estaba inactivo, así que deja pasar las 10 de inmediato. Un leaky bucket como fila no junta ningún crédito: mantiene las 10 en la fila y las suelta a su tasa constante, digamos una por segundo. El tiempo inactivo rinde fichas en uno y no rinde nada en el otro.

Limitación distribuida con Redis y atomicidad

Hasta aquí había un programa con un contador. Los servicios reales corren en varias copias, llamadas instancias, detrás de un balanceador de carga. Si cada instancia cuenta en su propia memoria, un cliente puede pasar N veces el límite por N instancias: con 3 instancias y un límite de 100 por minuto, hasta 300 por minuto.

La solución es sacar el contador de las instancias y llevarlo a un almacén compartido que todas leen y escriben. Redis es la elección habitual. Redis pasa a ser la única fuente de verdad, y las instancias quedan simples y se pueden agregar o quitar sin cambiar el límite.

Por qué INCR no pierde cuentas

Redis ejecuta los comandos de uno en uno y nunca mezcla dos comandos sobre los datos. Así INCR (suma uno a un número) es una lectura, suma y escritura atómicas. Si dos instancias envían INCR para la misma clave en el mismo instante, ninguna suma se pierde. Atómico quiere decir 'todo de una pieza, nada se mete en medio'.

La trampa: comprobar y después actuar

contador = 9, límite = 10

instancia A: GET   -> 9
instancia B: GET   -> 9   (A todavía no escribió)
instancia A: 9 < 10, INCR, admite  -> 10
instancia B: 9 < 10, INCR, admite  -> 11   <- por encima del límite

Leer, decidir en la aplicación y luego escribir es una condición de carrera (race condition, un bug que depende de quién es más rápido). En la prueba de este repositorio, dos instancias recibieron 400 solicitudes concurrentes para un límite de 50 por minuto. La versión con un script Lua admitió exactamente 50 en cada una de cinco rondas. La versión ingenua admitió hasta 192 en las rondas medidas, y exactamente 50 en algunas, y por eso estos bugs son difíciles de atrapar.

La cura: un script Lua

Redis puede ejecutar un pequeño programa escrito en Lua con EVAL. Un script corre de principio a fin y no se atiende ningún otro comando en medio, así que la lectura, la decisión y la escritura se vuelven un solo paso atómico. También puede fijar la expiración en el mismo paso del primer incremento, y así un cliente que se cae no deja un contador que nunca expira.

Relojes y fallas

Las ventanas solo coinciden si todas las instancias coinciden en la hora. Los relojes de máquinas distintas se desfasan (clock skew). Si la instancia B está 20 segundos adelantada, arma una clave de ventana distinta a la de la instancia A para el mismo instante, y el contador compartido se parte en dos. La solución es leer la hora dentro del script con el comando TIME de Redis, para que todas las instancias usen un solo reloj.

Pueden salir mal dos cosas más. Primero, Redis copia los datos a una réplica de forma asíncrona: el primario confirma al cliente y envía a la réplica después. Si el primario se cae y la réplica toma el mando, los últimos incrementos pueden perderse y el límite se excede por un momento. Esta desviación pequeña y rara suele aceptarse. Segundo, Redis puede quedar inalcanzable, y el limitador debe decidir de antemano qué hacer:

Un punto medio común es un límite local aproximado en la memoria de cada instancia mientras Redis está ausente.

HTTP 429, headers y backoff del cliente

Cuando un limitador dice que no, debe decirlo de una forma que el cliente entienda. En la web esto se hace con un código de estado HTTP, un número al comienzo de la respuesta (200 es OK, 404 es no encontrado). Para 'mandaste demasiado', el código es 429 Too Many Requests, agregado por la RFC 6585. La RFC no dice cómo el servidor averigua quién eres ni cómo cuenta. La respuesta debe explicar la situación y puede decir cuándo volver a intentar.

¿429 o 503?

Un limitador por cliente responde 429. Un servidor que descarta carga porque está sobrecargado responde 503. Una respuesta 429 nunca debe guardarse en una caché, porque describe a un cliente en un instante: si una caché compartida (como una CDN) la guardara, otros clientes, o el mismo cliente tras esperar, serían rechazados sin motivo. La RFC 6585 dice que las respuestas 429 no deben almacenarse.

Decirle al cliente cuándo volver

HTTP/1.1 429 Too Many Requests
Retry-After: 30
Content-Type: application/json

{"error":"rate limit exceeded"}

El encabezado Retry-After le dice al cliente cuánto esperar. La RFC 9110 permite dos formas: un número entero de segundos contados desde que se recibe la respuesta, o una HTTP-date absoluta. La forma en segundos no depende de que los relojes del cliente y del servidor coincidan. El limitador de este repositorio envía segundos enteros, redondeados hacia arriba.

Muchas APIs también envían encabezados sobre el propio límite, como X-RateLimit-Limit, X-RateLimit-Remaining y X-RateLimit-Reset. Se extendieron por imitación y no tienen estándar. El peor caso es Reset: algunos servicios quieren decir 'segundos a partir de ahora' y otros un timestamp Unix como 1791374400. Un cliente que lea un timestamp como segundos dormiría por décadas. El IETF trabaja en un Internet-Draft (todavía no era una RFC cuando se escribió esto) con los campos RateLimit-Policy y RateLimit. Un cliente genérico debe preferir Retry-After, que es estándar, y leer la documentación antes de confiar en los campos X-.

Qué hace un cliente educado

Un 429 pide al cliente que afloje, no que insista ni que se rinda para siempre. Si hay Retry-After, espera al menos ese tiempo. Viene de quien controla el límite, así que vale más que la suposición del propio cliente. Si no hay Retry-After, usa backoff exponencial: la espera se duplica con cada fallo. Con la convención de que el primer reintento es n = 1:

espera(n) = min(tope, base * 2^(n-1))
base = 0,5 s, tope = 10 s

El 6.º reintento sería 0,5 x 32 = 16 s, pero el tope lo corta en 10 s. Di siempre si cuentas los intentos desde 0 o desde 1, porque los números se desplazan. Fija también un número máximo de intentos, para que un cliente nunca quede atascado reintentando para siempre.

Jitter: un poco de aleatoriedad

Imagina 200 clientes rechazados en el mismo instante, todos con las mismas esperas que se duplican. Reintentan juntos en 1 s, 3 s, 7 s, en oleadas, y el servidor recibe golpe tras golpe (una estampida, thundering herd). El jitter hace aleatoria cada espera. Con full jitter la espera se sortea entre 0 y min(tope, base x 2^intento). Los reintentos se reparten y el servidor puede atender una parte de ellos en cada momento.

sin jitter:  |200|    |200|        |200|
             1s      3s           7s      (oleadas)

con jitter:  |12|31|18|25|9|41|22|...      (repartidos)

Reintentar puede dañar

Los reintentos inmediatos multiplican la carga en el peor momento. Si un servicio recibe 100 solicitudes por segundo y cada cliente repite una solicitud rechazada hasta 3 veces de inmediato, el servicio ve hasta 400 por segundo mientras ya está fallando. Esto es una tormenta de reintentos (retry storm). El backoff, el jitter, un límite de intentos y el respeto a Retry-After rompen el ciclo.

Hay una regla de seguridad más. Reintentar solo es seguro cuando ejecutar una solicitud dos veces tiene el mismo efecto que ejecutarla una vez, lo que se llama ser idempotente. Un 429 dice que no se procesó nada, pero tras un timeout el cliente no lo sabe. Para algo como POST /charges, que crea un cobro, el cliente envía una clave de idempotencia, un código único que permite al servidor reconocer la repetición y no cobrar dos veces.

Cuotas, throttling y descarte de carga

El rate limiting tiene vecinos que protegen un sistema de otras maneras. Saber cuál hace qué es la mitad del trabajo.

Tres límites distintos

Una API suele tener los tres, y una solicitud debe pasar por cada uno. Se comprueban por separado. Un cliente que obedece el límite de tasa todo el tiempo aún puede gastar su cuota mensual temprano: con una cuota de 500.000 por día y 10 solicitudes por segundo constantes, la cuota se acaba después de 50.000 segundos, unas 13,9 horas. Por eso las APIs le dicen a los clientes cuánto queda de la cuota.

Por qué el límite de concurrencia es especial

El número medio de solicitudes en curso es igual a la tasa de llegada por el tiempo que cada una pasa en el sistema. Esta es la ley de Little. Si llegan 120 solicitudes por segundo y cada una tarda 0,5 s, unas 60 están en curso a la vez. Si el servicio se vuelve dos veces más lento, son 120 en curso con la misma tasa de llegada, y un límite de tasa no nota nada.

Un límite de concurrencia C con tiempo de servicio S deja pasar como máximo C / S solicitudes por segundo. Con C = 30 y S = 0,25 s son 120 por segundo. Si el servicio se vuelve lento y S crece, el rendimiento admitido cae en la misma proporción, lo que protege a un servidor que ya está sufriendo. Un límite de tasa fijo seguiría admitiendo la misma tasa y las solicitudes se acumularían.

Control de congestión, de lo lento a lo rápido

Tanenbaum ordena las respuestas a la congestión de la más lenta a la más rápida: aumentar la capacidad, elegir rutas que eviten los puntos saturados, control de admisión, estrangulamiento de tráfico (traffic throttling) y descarte de carga (load shedding). El control de admisión rechaza trabajo nuevo antes de que empiece, lo que es más barato que aceptarlo y tirarlo a mitad de camino. La palabra throttling se usa de forma laxa en la documentación de las APIs tanto para retrasar (modelar) como para rechazar (fiscalizar).

Contrapresión (backpressure)

Imagina un productor escribiendo en una fila de 1.000 cupos que un consumidor más lento vacía. Cuando la fila se llena, la llamada de escritura del productor simplemente espera hasta que haya lugar, y nada se tira. Esto es backpressure: la parte llena le dice al emisor que afloje, con una señal o con una llamada que bloquea. El retraso viaja de vuelta hasta el origen. Cuando el origen no puede esperar, como los usuarios de Internet, el backpressure termina como un rechazo en la entrada, que es rate limiting o descarte de carga.

Descarte de carga

El descarte de carga es la última defensa: el servidor rechaza trabajo a propósito, normalmente con 503, para que el trabajo que aceptó termine a tiempo. Se diferencia del rate limiting porque mira la salud del servidor, no el comportamiento de un cliente. Un buen descarte se hace temprano y por prioridad, con el trabajo menos importante primero.

solicitud --> [rechaza aquí: 1 ms] --> parse --> auth --> base de datos
                                               [rechaza aquí: 40 ms]

Un servidor que rechaza tarde puede gastar toda su capacidad diciendo que no y seguir sobrecargado. Por eso descarta antes de leer el cuerpo, antes de autenticar, antes de tocar una dependencia.

Cuando la sobrecarga no se maneja

Supón un servidor que atiende 100 solicitudes por segundo pero recibe 150, con una fila primero-en-llegar-primero-en-salir sin límite, y clientes que se rinden tras 2 segundos. La fila crece, toda respuesta llega tarde, y el servidor sigue atendiendo solicitudes cuyos clientes ya se fueron. Su rendimiento está al máximo, pero el goodput (respuestas que llegan a tiempo) cae casi a cero. La cura: una fila acotada, un plazo para cada solicitud (descartar lo que ya pasó su timeout) y rechazar el exceso en la entrada.

¿A quién descartar? El vecino ruidoso

Tanenbaum describe dos políticas para elegir qué paquetes descartar. La política del vino (wine) prefiere conservar los paquetes viejos, porque el vino añejo es mejor. Sirve para la transferencia de archivos, donde perder un paquete viejo obliga a reenviar todo lo que sigue. La política de la leche (milk) prefiere conservar los nuevos, porque la leche vieja se echa a perder. Sirve para medios en tiempo real, donde un dato tardío es inútil. Los servidores tienen la misma idea: para descartar por prioridad debes saber cuánto vale cada solicitud.

En un servicio compartido, un tenant grande puede perjudicar a todos los pequeños, el vecino ruidoso (noisy neighbour). Con descarte aleatorio todos pierden en la misma proporción, así que 30 tenants pequeños pierden la mitad de sus solicitudes por culpa de uno grande. El descarte justo atiende por completo a los tenants pequeños y le quita el exceso a quien se pasó de su parte. Eso exige contar por tenant, y por eso las cuotas y los límites por plan van de la mano con el descarte de carga.

Circuit breaker

Un circuit breaker (cortacircuitos) es el otro lado de la misma idea. El servicio A llama al servicio B. Tras 5 llamadas seguidas fallidas, A deja de llamar a B durante 30 segundos y responde con un valor alternativo (fallback), y luego deja pasar una llamada de prueba. Está del lado de quien llama y observa resultados, para proteger de una dependencia enferma. Un limitador de tasa está del lado de quien es llamado y observa el volumen, para proteger de un cliente que pide demasiado.

Juntando todo

En el experimento de ráfaga de este repositorio, los cinco algoritmos recibieron las mismas 80 solicitudes con la misma configuración (límite 10, ventana de 1 s, así que capacidad 10 y tasa de 10 por segundo para las cubetas). El gráfico muestra el mayor número de solicitudes admitidas encontrado en cualquier intervalo de 1 segundo.

La ventana fija dejó pasar 20 cerca de una frontera. El log deslizante nunca pasó de 10. El contador deslizante llegó a 11, un error pequeño. El token bucket llegó a 19 porque gasta primero las fichas guardadas y luego gana más mientras la ráfaga continúa. La salida del leaky bucket se quedó en 10 porque suelta las solicitudes a un ritmo constante.

Errores comunes

• Creer que un limitador es autenticación, cifrado, caché o balanceador de carga. Solo cuenta.
• Contar por dirección IP detrás de NAT, o por X-Forwarded-For sin un proxy confiable.
• Usar un solo límite para todos los endpoints, o solo límites por cliente y ninguna protección global.
• Olvidar el tope en un token bucket, de modo que un cliente inactivo junta fichas sin fin.
• Hacer leer, decidir y escribir como comandos separados en Redis (una carrera), o INCR y EXPIRE como dos comandos (una clave que nunca expira).
• Leer la hora en cada instancia en vez de en Redis, y que las ventanas no coincidan.
• Reintentar de inmediato, sin jitter, sin límite de intentos y sin respetar Retry-After.
• Rechazar tarde, después de que la solicitud ya usó las partes caras del servidor.

Cómo se conectan las ideas

El algoritmo decide quién es admitido. Redis y un script atómico hacen que esa decisión valga entre muchos servidores. El estado 429 con Retry-After le cuenta al cliente lo que pasó. El backoff del cliente con jitter evita que sus reintentos se vuelvan un nuevo problema. Las cuotas, los límites de concurrencia y el descarte de carga protegen el largo plazo y el servicio entero cuando los límites por cliente no bastan.