Ratenlimits mit Python und Redis

In diesem Artikel werden einige Python- und Redis-basierte Ratenbegrenzungsalgorithmen vorgestellt, von der einfachsten Implementierung bis zum erweiterten generischen Zellratenalgorithmus (GCRA ). Wir werden redis-py verwenden,



um mit Redis ( pip install redis) zu interagieren . Ich schlage vor, mein Repository zu klonen , um mit Abfrageeinschränkungen zu experimentieren.

Zeitlimit

Der erste Ansatz zur Begrenzung der Anzahl von Anforderungen pro Periode besteht in der Verwendung eines zeitlich begrenzten Algorithmus: Für jeden Begrenzungsschlüssel (Ratenschlüssel, etwas Einzigartiges wie ein Spitzname oder eine IP-Adresse) werden ein Zähler (anfänglich Festlegen des Grenzwerts) und ein Ablaufdatum separat gespeichert (Zeitraum), die sich verringern, wenn Anfragen eingehen.



Mit Python und Redis können Sie diesen Algorithmus wie folgt implementieren:

1. Überprüfen der Existenz des Einschränkungsschlüssels.
2. Wenn es existiert, initialisieren Sie es mit einem Grenzwert ( Redis SETNX ) und einem Ablaufdatum ( Redis EXPIRE ).
3. Wir verringern diesen Wert bei jeder nachfolgenden Anfrage ( Redis DECRBY ).
4. Abfragen werden nur gestoppt, wenn der Wert unter Null fällt.
5. Nach einer bestimmten Zeit wird der Schlüssel automatisch gelöscht.

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

Sie können sehen, wie dieser Code funktioniert, wenn Sie das Limit von 20 Anforderungen in 30 Sekunden emulieren (um es klarer zu machen, habe ich die Funktion in ein Modul eingefügt).

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

Nur die ersten 20 Anfragen werden nicht eingeschränkt. Danach müssen Sie 30 Sekunden warten, damit neue Anfragen erneut gesendet werden können.



Der Nachteil dieses Ansatzes besteht darin, dass er nicht die Häufigkeit, sondern die Anzahl der vom Benutzer über einen bestimmten Zeitraum gestellten Anforderungen begrenzt. Wenn das gesamte Limit sofort erschöpft ist, müssen Sie auf das Ende des Zeitraums warten.

Leaky-Bucket-Algorithmus

Es gibt einen Ansatz, bei dem wir die Frequenz sehr sorgfältig begrenzen können: Dies ist der aktuelle Bucket-Algorithmus . Das Funktionsprinzip ist das gleiche wie bei einem echten undichten Eimer: Wir gießen Wasser (Anfragen) bis an die Ränder in den Eimer, während ein Teil des Wassers ständig durch das Loch im Boden herausfließt (normalerweise im Hintergrundverfahren). Wenn die in den Eimer gegossene Wassermenge größer ist als die ausströmende Wassermenge, wird der Eimer gefüllt, und wenn er voll ist, werden neue Anforderungen nicht mehr akzeptiert.



Funktionsweise des Algorithmus



Sie können diesen Ansatz überspringen, um eine elegantere Lösung zu erhalten, für die kein separater Prozess zum Emulieren des Lecks erforderlich ist: der generische Zellratenalgorithmus.

Verallgemeinerter Algorithmus zur Steuerung der Zellrate

GCRA wurde in der Telekommunikationsbranche entwickelt und dort als Asynchronous Transfer Mode (ATM) bezeichnet. Es wurde von ATM-Netzwerkmanagern verwendet, um Zellen - kleine Datenpakete fester Größe - zu verzögern oder zu verwerfen, die eine Rate erreichten, die über einem bestimmten Grenzwert lag.



GCRA verfolgt das verbleibende Limit anhand der sogenannten theoretischen Ankunftszeit (TAT) jeder Anfrage:

tat = current_time + period

und begrenzt die nächste Anforderung, wenn die Ankunftszeit kleiner als die aktuelle TAT ist. Dies funktioniert gut, wenn die Häufigkeit 1 Anforderung / Periode beträgt, wenn Anforderungen in Perioden unterteilt sind. In der Realität werden Frequenzen jedoch normalerweise als Grenze / Periode berechnet. Wenn die Häufigkeit beispielsweise 10 Anfragen / 60 Sekunden beträgt, kann der Benutzer in den ersten 6 Sekunden 10 Anfragen stellen. Und mit einer Häufigkeit von 1 Anfrage / 6 Sekunden muss er 6 Sekunden zwischen den Anfragen warten.



Um eine Gruppe von Anfragen innerhalb eines kurzen Zeitraums senden zu können und die Begrenzung ihrer Anzahl für einen Zeitraum mit einem Limit> 1 beizubehalten, muss jede Anfrage durch das Verhältnis von Periode zu Limit geteilt werden, und dann wird die nächste theoretische Ankunftszeit ( new_tat) anders berechnet. Geben Sie die Ankunftszeit der Anfrage wie folgt an t:

• new_tat = tat + period / limitwenn Anfragen gruppiert sind ( t <= tat)
• new_tat = t + period / limitwenn Anfragen nicht gruppiert sind ( t > tat)

Daher:

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

Die Anfrage wird begrenzt, wenn sie new_tatgrößer ist als die Summe der aktuellen Zeit und des Zeitraums : new_tat > t + period. Wenn new_tat = tat + period / limitwir bekommen tat + period / limit > t + period. Daher müssen Sie Abfragen nur dann einschränken, wenn tat - t > period - period / limit.

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

In diesem Fall müssen wir die TAT nicht aktualisieren, da begrenzte Anforderungen keine theoretische Ankunftszeit haben.



Stellen wir nun die endgültige Version des Codes zusammen!

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

Wir haben Redis TIME verwendet, da GCRA zeitabhängig ist und wir sicherstellen müssen, dass die aktuelle Zeit über mehrere Bereitstellungen hinweg konsistent ist (Zeitunterschiede zwischen verschiedenen Computern können zu Fehlalarmen führen).



Dieser Code demonstriert die GCRA-Leistung bei 10 Anforderungen / 60 Sekunden.

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

Der Algorithmus beschränkt die ersten 10 Anforderungen nicht, Sie müssen jedoch mindestens 6 Sekunden warten, um die nächste Anforderung zu stellen. Versuchen Sie, das Skript nach einiger Zeit auszuführen und den Wert des Grenzwerts und des Zeitraums (z. B. limit = 1und period=timedelta(seconds=6)) zu ändern .



Um die Implementierung sauber zu halten, habe ich keine Sperre zwischen dem Empfangen und Senden von Anrufen hinzugefügt. Es wird jedoch für mehrere Anfragen mit demselben Schlüssel und zur gleichen Zeit benötigt. Mit Lua können Sie Sperren als Kontextmanager hinzufügen.

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

Der vollständige Code befindet sich auf GitHub .