En este artículo, veremos algunos algoritmos de límite de velocidad basados en Python y Redis, desde la implementación más simple hasta el algoritmo de velocidad de celda genérico avanzado (GCRA ). Usaremos redis-py
para interactuar con Redis (
pip install redis) . Sugiero clonar mi repositorio para experimentar con restricciones de consulta.
Límite de tiempo
El primer enfoque para limitar el número de solicitudes por período es utilizar un algoritmo de tiempo limitado: para cada clave de limitación (clave de tasa, algo único, como un apodo o dirección IP), un contador (que establece inicialmente el valor límite) y una fecha de vencimiento se almacenan por separado. (período), que disminuyen a medida que se reciben las solicitudes.
Con Python y Redis, puede implementar este algoritmo de la siguiente manera:
- Comprobando la existencia de la clave de restricción.
- Si existe, inicialícelo con un valor límite ( Redis SETNX ) y una fecha de vencimiento ( Redis EXPIRE ).
- Disminuimos este valor con cada solicitud posterior ( Redis DECRBY ).
- Las consultas se detienen solo cuando el valor cae por debajo de cero.
- Después de un período de tiempo especificado, la clave se elimina automáticamente.
from datetime import timedelta
from redis import Redis
def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
if r.setnx(key, limit):
r.expire(key, int(period.total_seconds()))
bucket_val = r.get(key)
if bucket_val and int(bucket_val) > 0:
r.decrby(key, 1)
return False
return True
Puedes ver cómo funciona este código al emular el límite de 20 solicitudes en 30 segundos (para que quede más claro, pongo la función en un módulo).
import redis
from datetime import timedelta
from ratelimit import time_bucketed
r = redis.Redis(host='localhost', port=6379, db=0)
requests = 25
for i in range(requests):
if time_bucketed.request_is_limited(r, 'admin', 20, timedelta(seconds=30)):
print ('Request is limited')
else:
print ('Request is allowed')
Solo las primeras 20 solicitudes no estarán limitadas, después de ellas tendrás que esperar 30 segundos para que se puedan enviar nuevas solicitudes nuevamente.
La desventaja de este enfoque es que no limita la frecuencia, sino el número de solicitudes realizadas por el usuario durante un período determinado. Si el límite completo se agota inmediatamente, tendrá que esperar hasta el final del período.
Algoritmo de balde con fugas
Existe un enfoque en el que podemos limitar con mucho cuidado la frecuencia: este es el algoritmo de cubo actual . El principio de funcionamiento es el mismo que el de un balde con fugas real: vertimos agua (pedidos) en el balde hasta los bordes, mientras que una parte del agua fluye constantemente a través del orificio en el fondo (generalmente implementado mediante un proceso de fondo). Si la cantidad de agua vertida en el balde es mayor que la cantidad de agua vertida, entonces el balde se llena y, cuando está lleno, ya no se aceptan nuevas solicitudes.
Cómo funciona el algoritmo
Puede omitir este enfoque para obtener una solución más elegante que no requiera un proceso separado para emular la fuga: el algoritmo genérico de velocidad de celda.
Algoritmo de control de velocidad de celda generalizado
GCRA se creó en la industria de las telecomunicaciones, donde se denomina Modo de transferencia asincrónica (ATM). Los administradores de redes de cajeros automáticos lo usaban para retrasar o eliminar celdas (paquetes de datos pequeños y de tamaño fijo) que llegaban a una velocidad superior a un límite especificado.
GCRA rastrea el límite restante utilizando el llamado Tiempo de llegada teórico (TAT) de cada solicitud:
tat = current_time + period
y limita la siguiente solicitud si la hora de llegada es menor que el TAT actual. Esto funciona bien si la frecuencia es 1 solicitud / período, cuando las solicitudes se dividen en períodos. Pero, en realidad, las frecuencias se suelen calcular como límite / período. Por ejemplo, si la frecuencia es de 10 solicitudes / 60 segundos, el usuario puede realizar 10 solicitudes en los primeros 6 segundos. Y con una frecuencia de 1 solicitud / 6 segundos, tendrá que esperar 6 segundos entre solicitudes.
Para poder enviar un grupo de solicitudes en un período corto y mantener la limitación de su número por un período con un límite> 1, cada solicitud debe dividirse por la relación período / límite, y luego la próxima hora teórica de llegada (
new_tat) se calculará de manera diferente. Denotemos la hora de llegada de la solicitud como t:
new_tat = tat + period / limitsi las solicitudes están agrupadas (t <= tat)new_tat = t + period / limitsi las solicitudes no están agrupadas (t > tat)
Por lo tanto:
new_tat = max(tat, t) + period / limit
La solicitud será limitado, si es
new_tatmayor que la suma de la hora actual y el período: new_tat > t + period. Cuando new_tat = tat + period / limitlleguemos tat + period / limit > t + period. Por lo tanto, debe restringir las consultas solo cuando tat - t > period - period / limit.
period — period / limit
<----------------------->
--|----------------------------|--->
t TAT
En este caso, no necesitamos actualizar el TAT, porque las solicitudes limitadas no tienen una hora de llegada teórica.
¡Ahora construyamos la versión final del código!
from datetime import timedelta
from redis import Redis
def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
period_in_seconds = int(period.total_seconds())
t = r.time()[0]
separation = round(period_in_seconds / limit)
r.setnx(key, 0)
tat = max(int(r.get(key)), t)
if tat - t <= period_in_seconds - separation:
new_tat = max(tat, t) + separation
r.set(key, new_tat)
return False
return True
Usamos Redis TIME porque GCRA depende del tiempo, y debemos asegurarnos de que la hora actual sea coherente en múltiples implementaciones (las discrepancias de reloj entre diferentes máquinas pueden generar falsos positivos).
Este código demuestra el rendimiento de GCRA a 10 solicitudes / 60 seg.
import redis
from datetime import timedelta
from ratelimit import gcra
r = redis.Redis(host='localhost', port=6379, db=0)
requests = 10
for i in range(requests):
if gcra.request_is_limited(r, 'admin', 10, timedelta(minutes=1)):
print ('Request is limited')
else:
print ('Request is allowed')
El algoritmo no limita las primeras 10 solicitudes, pero tendrá que esperar al menos 6 segundos para realizar la siguiente solicitud. Intente ejecutar el script después de un tiempo y cambie el valor del límite y el período (por ejemplo,
limit = 1y period=timedelta(seconds=6)).
Para mantener limpia la implementación, no agregué un bloqueo entre recibir y enviar llamadas. Pero es necesario para múltiples solicitudes con la misma clave y al mismo tiempo. Con Lua, puede agregar bloqueo como administrador de contexto.
def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
period_in_seconds = int(period.total_seconds())
t = r.time()[0]
separation = round(period_in_seconds / limit)
r.setnx(key, 0)
try:
with r.lock('lock:' + key, blocking_timeout=5) as lock:
tat = max(int(r.get(key)), t)
if tat - t <= period_in_seconds - separation:
new_tat = max(tat, t) + separation
r.set(key, new_tat)
return False
return True
except LockError:
return True
El código completo está en GitHub .