Limites de taux avec Python et Redis

Dans cet article, nous examinerons certains algorithmes de limite de débit basés sur Python et Redis, de l'implémentation la plus simple à l' algorithme avancé de débit cellulaire générique (GCRA ). Nous utiliserons redis-py



pour interagir avec Redis ( pip install redis) . Je suggère de cloner mon référentiel pour expérimenter les limites de requête.

Limite de temps

La première approche pour limiter le nombre de requêtes par période consiste à utiliser un algorithme limité dans le temps: pour chaque clé de limitation (clé de débit, quelque chose d'unique, comme un pseudo ou une adresse IP), un compteur (fixant initialement la valeur limite) et une date d'expiration sont stockés séparément (période), qui diminue à mesure que les demandes sont reçues.



Avec Python et Redis, vous pouvez implémenter cet algorithme comme suit:

1. Vérification de l'existence de la clé de contrainte.
2. S'il existe, initialisez-le avec une valeur limite ( Redis SETNX ) et une date d'expiration ( Redis EXPIRE ).
3. Nous diminuons cette valeur à chaque requête ultérieure ( Redis DECRBY ).
4. Les requêtes sont arrêtées uniquement lorsque la valeur tombe en dessous de zéro.
5. Après une période de temps spécifiée, la clé est automatiquement supprimée.

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

Vous pouvez voir le travail de ce code en émulant la limite de 20 requêtes en 30 secondes (pour être plus clair, j'ai mis la fonction dans un module).

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')

Seules les 20 premières demandes ne seront pas limitées, après elles vous devrez attendre 30 secondes pour que les nouvelles demandes puissent être renvoyées.



L'inconvénient de cette approche est qu'elle ne limite pas la fréquence, mais le nombre de requêtes effectuées par l'utilisateur sur une certaine période. Si toute la limite est immédiatement épuisée, vous devrez attendre la fin de la période.

Algorithme de seau qui fuit

Il existe une approche où l'on peut limiter très soigneusement la fréquence: c'est l'algorithme actuel du bucket . Le principe de fonctionnement est le même que pour un vrai seau qui fuit: nous versons de l'eau (demandes) dans le seau jusqu'aux bords mêmes, tandis qu'une partie de l'eau s'écoule constamment par le trou dans le fond (généralement mis en œuvre en utilisant un processus d'arrière-plan). Si la quantité d'eau versée dans le seau est supérieure à la quantité d'eau qui s'écoule, le seau est rempli et, lorsqu'il est plein, les nouvelles demandes ne sont plus acceptées.



Comment fonctionne l'algorithme



Vous pouvez ignorer cette approche pour une solution plus élégante qui ne nécessite pas de processus séparé pour émuler la fuite: l'algorithme de débit cellulaire générique.

Algorithme de contrôle du débit cellulaire généralisé

GCRA a été créé dans l'industrie des télécommunications, où il est appelé mode de transfert asynchrone (ATM). Il était utilisé par les gestionnaires de réseau ATM pour retarder ou rejeter des cellules - de petits paquets de données d'une taille fixe - qui arrivaient à un débit supérieur à une limite spécifiée.



GCRA suit la limite restante en utilisant ce que l'on appelle l'heure d'arrivée théorique (TAT) de chaque demande:

tat = current_time + period

et limite la demande suivante si l'heure d'arrivée est inférieure au TAT actuel. Cela fonctionne bien si la fréquence est de 1 demande / période, lorsque les demandes sont divisées en périodes. Mais en réalité, les fréquences sont généralement calculées comme une limite / période. Par exemple, si la fréquence est de 10 demandes / 60 secondes, l'utilisateur peut alors faire 10 demandes dans les 6 premières secondes. Et avec une fréquence de 1 requête / 6 secondes, il devra attendre 6 secondes entre les requêtes.



Pour pouvoir envoyer un groupe de demandes dans un délai court et maintenir la limitation de leur nombre pendant une période avec une limite> 1, chaque demande doit être divisée par le rapport période / limite, puis la prochaine heure d'arrivée théorique ( new_tat) sera calculée différemment. Notons l'heure d'arrivée de la demande comme suit t:

• new_tat = tat + period / limitsi les demandes sont groupées ( t <= tat)
• new_tat = t + period / limitsi les demandes ne sont pas groupées ( t > tat)

Par conséquent:

new_tat = max(tat, t) + period / limit

La demande sera limitée, si new_tatsupérieure à la somme du temps en cours et la période: new_tat > t + period. Quand new_tat = tat + period / limitnous obtenons tat + period / limit > t + period. Par conséquent, vous devez limiter les requêtes uniquement lorsque tat - t > period - period / limit.

      period — period / limit
      <----------------------->
--|----------------------------|--->
  t                           TAT

Dans ce cas, nous n'avons pas besoin de mettre à jour le TAT, car les demandes limitées n'ont pas d'heure d'arrivée théorique.



Construisons maintenant la version finale du code!

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

Nous avons utilisé Redis TIME car GCRA dépend du temps, et nous devons nous assurer que l'heure actuelle est cohérente sur plusieurs déploiements (les écarts d'horloge entre différentes machines peuvent conduire à des faux positifs).



Ce code démontre les performances GCRA à 10 requêtes / 60 s.

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')

L'algorithme ne limite pas les 10 premières requêtes, mais vous devrez attendre au moins 6 secondes pour faire la requête suivante. Essayez d'exécuter le script après un certain temps et modifiez la valeur de la limite et de la période (par exemple, limit = 1et period=timedelta(seconds=6)).



Pour garder la mise en œuvre propre, je n'ai pas ajouté de verrou entre la réception et l'envoi d'appels. Mais il est nécessaire pour plusieurs demandes avec la même clé et en même temps. Avec Lua, vous pouvez ajouter un verrouillage en tant que gestionnaire de contexte.

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

Le code complet est sur GitHub .