Entwerfen eines Ratenbegrenzers

Hier sind meine Notizen zum Entwerfen eines Ratenbegrenzers.

Was ist ein Ratenbegrenzer?

• In Computernetzwerken wird Ratenbegrenzung verwendet, um die Rate von Anforderungen zu steuern, die von einem Netzwerkschnittstellencontroller gesendet oder empfangen werden .
• Begrenzt auf der HTTP-Seite die Anzahl der Clientanforderungen, die über einen bestimmten Zeitraum gesendet werden dürfen.

• Benutzer können alle 5 Minuten 1 Ticket erstellen
• Benutzer können 2 Konten pro Tag mit derselben IP-Adresse erstellen
• Benutzer können an einem Tag 5 fehlgeschlagene Anmeldeversuche pro Stunde mit derselben IP-Adresse versuchen

• Ein Ratenbegrenzer verhindert DoS-Angriffe
• Stoppen Sie den Systemmissbrauch
• Reduziert die Kosten
• Es verhindert eine Überlastung der Server. Reduziert auch die Serverlast
• Verbessern Sie die Benutzererfahrung mit weniger Verkehr

• Der Ratenbegrenzer sollte die HTTP-Antwortzeit Ihres Systems nicht verlangsamen.
• Verwenden Sie weniger Speicher
• Anzeigen von Ausnahmen für Benutzer, wenn ihre Anfragen aufgrund von Ratenbegrenzung blockiert sind.
• Ihr Ratenbegrenzer darf nicht das gesamte System beeinflussen. Wenn beispielsweise Ihr Cache-Server ausfällt, muss Ihr System verfügbar sein.

• Es gibt verschiedene Möglichkeiten, einen Ratenbegrenzer zu implementieren. Diese sind; Clientseitige Implementierung, serverseitige Implementierung und eine alternative Methode mit einem API-Gateway eines Drittanbieters.
• Im Allgemeinen ist die Clientseite ein unzuverlässiger Ort, um eine Ratenbegrenzung durchzusetzen
• Eine serverseitige Implementierung hat einige interne Vorteile, da Sie die Logik auf Ihrer Seite ändern können.
• Die Verwendung eines API-Gateways eines Drittanbieters ist manchmal nützlich, da die Implementierung einige Zeit in Anspruch nimmt.

1- Token-Bucket

• Zwei Hauptparameter; Eimergröße und Nachfüllrate.
• Bucket-Größe: maximal zulässige Anzahl von Token
• Nachfüllrate: Anzahl der Token, die in einem beliebigen Intervall wie jede Sekunde in den Eimer gelegt werden
• Unter der Annahme, dass wir einen Bucket haben, wird die Kapazität als die Anzahl der Token definiert, die er aufnehmen kann. Immer wenn ein Verbraucher auf einen API-Endpunkt zugreifen möchte, muss er ein Token aus dem Bucket abrufen. Das Token wird aus dem Bucket entfernt, wenn es verfügbar ist, und akzeptiert die Anfrage. Wenn das Token nicht verfügbar ist, lehnt der Server die Anfrage ab.
• In jedem festgelegten Intervall müssen wir nachfüllen.
• Wenn wir HTTP-Anfragen basierend auf IP-Adressen drosseln müssen, benötigt jede IP-Adresse einen Bucket.
• Kann Race Conditions in einer verteilten Umgebung verursachen (Nachteil)

2- Auslaufender Eimer

• Wenn eine HTTP-Anfrage eintrifft, überprüft das System die Warteschlange. Wenn die Warteschlange nicht voll ist, wird die Anforderung der Warteschlange hinzugefügt. Andernfalls wird die Anfrage blockiert.
• HTTP-Anforderungen werden aus der Warteschlange gezogen und in regelmäßigen Abständen verarbeitet.
• Die Verarbeitung für das erste Element in der Warteschlange erfolgt in regelmäßigen Abständen oder First In, First Out (FIFO).

• Unterteilt die Zeitleiste in Zeitfenster mit fester Größe
• Jede Anfrage inkrementiert den Zähler.
• Das Zeitfenster wird vom Beginn der Zeiteinheit bis zum Ende der Zeiteinheit betrachtet.
• Raumkomplexität: O(1) – Speichern der aktuellen Fensteranzahl. Zeitkomplexität : O(1) – Abrufen und einfache atomare Inkrementoperation

• Das größte Problem dabei ist, dass Verbraucher die Rücksetzzeit finden und die Anfrage in einem kurzen Zeitraum maximieren können, in dem sie sie bombardieren können.

• Der Fixed-Window-Algorithmus hat ein Problem, wie ich geschrieben habe. Es ermöglicht, dass mehr Anforderungen an den Rändern eines Fensters durchlaufen werden. Ein Sliding Window Log löst dieses Problem.
• hält die Anfragen zeitlich sortiert in einem Set oder einer Tabelle (Bsp.: Redis)
• Jede Minute suchen wir nach älteren Anfragen und filtern sie heraus. Dann berechnen Sie die Verfügbarkeit. Wenn die Anforderung die Schwellenrate überschreiten würde, wird sie gehalten, andernfalls wird sie bedient.
• Verbraucht viel Speicher.
• Kostspielig, eine unbegrenzte Anzahl von Protokollen für jede Anfrage zu speichern.
• Speicherplatzkomplexität: O(Max. Anfragen in einer Fensterzeit) – Speichert alle Zeitstempel der Anfragen in einem Zeitfenster.
• Zeitkomplexität: O (Maximale Anfragen in einer Fensterzeit) – Löschen einer Teilmenge von Zeitstempeln

1. Zähle die Gesamtzahl der Elemente in der sortierten Menge. Lehnen Sie die Anfrage ab, wenn diese Anzahl größer als unser Drosselungslimit von „3“ ist.
2. Fügen Sie die aktuelle Uhrzeit in die sortierte Menge ein und akzeptieren Sie die Anfrage.

• kombiniert die niedrigen Verarbeitungskosten des Festfensteralgorithmus und die verbesserten Randbedingungen des Gleitprotokolls.
• Raumkomplexität: O (Anzahl der Buckets)
• Zeitkomplexität: O(1) – Abrufen des letzten Buckets, Inkrementieren und Vergleichen mit der Gesamtsumme der Buckets (kann in einer totalCount-Variablen gespeichert werden).
• Einzelheiten zur Implementierung finden Sie in diesem Artikel.
• Noch ein Artikel zum besseren Verständnis.

1. Entfernen Sie alle Zähler, die älter als 1 Minute sind.
2. Erhöhen Sie den Zähler, wenn die Anforderung im aktuellen Bucket eintrifft.
3. Blockierte Anfrage, wenn der aktuelle Bucket bereits das Throat-Limit überschritten hat.

Verweise

• https://www.quinbay.com/blog/rate-limiter-implementation-token-bucket-algorithm
• https://betterprogramming.pub/4-rate-limit-algorithms-every-developer-should-know-7472cb482f48
• https://codeminion.hashnode.dev/rate-limiting-algorithms
• https://goalgorithm.wordpress.com/2019/06/08/designing-an-api-rate-limiter/