Warum ist Rate Limiting (Nutzungsbegrenzung) notwendig?
- In einem Twitch-Chat mit vielen Teilnehmenden kann ein einzelner Spammer das Gespräch dominieren, wenn es keine Nutzungsbegrenzung gibt.
- Durch Nutzungsbegrenzung erhält jede Person eine faire Chance zur Teilnahme.
- Ein Rate Limiter steuert den Traffic eines Dienstes, indem er Anfragen blockiert, die ein festgelegtes Limit innerhalb eines bestimmten Zeitraums überschreiten. Das ist nicht nur zur Spam-Kontrolle in Chats nützlich.
- Zum Beispiel kann auf einem Login-Formular durch Nutzungsbegrenzung ein Brute-Force-Angriff eingedämmt werden, während eine kleine Zahl falscher Versuche weiterhin erlaubt bleibt.
- Auch API-Endpunkte werden oft mit Nutzungsbegrenzung versehen, damit nicht ein einzelner Nutzer alle Ressourcen monopolisiert.
- Wenn ein Nutzer einen teuren API-Endpunkt nur 100-mal pro Minute aufrufen darf, kann man mit einem Zähler 100 Hits pro Minute erfassen und danach weitere Anfragen blockieren.
- Das ist einer der einfachsten Algorithmen zur Nutzungsbegrenzung: der Fixed Window Limiter.
- Er ist eine gängige Methode zur Steuerung von Service-Traffic.
Fixed-Window-Algorithmus
- Die Anzahl der Anfragen ist innerhalb eines festen Zeitfensters begrenzt.
- Zu Beginn jedes Zeitfensters wird der Anfragezähler auf 0 zurückgesetzt.
- Vorteile
- Einfach zu implementieren und zu verstehen
- Für Nutzer gut vorhersehbar
- Nachteile
- Wenn Anfragen kurz vor dem Ende eines Zeitfensters beginnen, kann ein Burst von bis zu doppelt so vielen Anfragen wie vorgesehen zugelassen werden.
- Praxisbeispiel: Die GitHub API verwendet einen Fixed-Window-Rate-Limiter, der 5.000 Anfragen pro Stunde erlaubt.
- Statt den Startzeitpunkt jedes Zeitfensters in festen Intervallen zu setzen, kann jedes Zeitfenster auch beim ersten Request eines Nutzers innerhalb dieses Fensters erzeugt werden.
- Bei diesem Ansatz ist es besonders wichtig, dem Nutzer mitzuteilen, wie viel Zeit bis zum nächsten Zeitfenster verbleibt.
Sliding-Window-Algorithmus
- Statt die gesamte Kapazität auf einmal zu erneuern, füllt ein Sliding Window die Kapazität jeweils um genau eine Anfrage auf.
- Vorteile
- Glättet die Verteilung des Anfrage-Traffics
- Geeignet für hohe Last
- Nachteile
- Für Nutzer weniger vorhersehbar als ein festes Zeitfenster
- Das Speichern des Zeitstempels jeder Anfrage ist ressourcenintensiv
- Da Sliding Windows vor allem in Szenarien mit hohem Traffic nützlich sind, wirkt die Ressourcenintensität des Grundalgorithmus kontraproduktiv.
- Deshalb verwenden die meisten Sliding-Window-Rate-Limiter in der Praxis eine Approximation.
- Diese Approximation berechnet die Zahl der erlaubten Anfragen im vorherigen festen Zeitfenster und im aktuellen festen Zeitfenster und gewichtet die erlaubten Anfragen des vorherigen Fensters proportional zu deren Überlappung mit dem gleitenden Zeitfenster, das in der aktuellen Zeit endet.
- Diese Näherung begrenzt Anfragen nahezu mit derselben Rate, ist dabei aber deutlich effizienter.
- Praxisbeispiel: Der konfigurierbare Rate Limiter von Cloudflare verwendet ein approximiertes Sliding Window.
Token-Bucket-Algorithmus
- Anstelle der Dauer eines Zeitfensters stellt man sich einen Bucket vor, der mit konstanter Geschwindigkeit mit „Tokens“ gefüllt wird.
- Jede Anfrage entnimmt diesem Bucket ein Token; ist der Bucket leer, wird die nächste Anfrage blockiert.
- Die Kapazität des Buckets steht für die maximale Anzahl an Anfragen, die ein Burst unterstützen kann.
- Das Refill-Intervall steht für den langfristig erlaubten durchschnittlichen Abstand zwischen Anfragen.
- Einer der Hauptvorteile dieses Algorithmus ist, dass sich getrennte Burst- und Durchschnittskapazitäten ohne mehrere Rate Limiter abbilden lassen.
- Vorteile
- Erlaubt Bursts mit hohem Traffic und setzt zugleich eine langfristige durchschnittliche Anfragerate durch
- Flexibler für Nutzer, da Traffic-Spitzen innerhalb des erlaubten Rahmens möglich sind
- Nachteile
- Schwieriger als bei festen Zeitfenstern, Nutzern die Limits und Refill-Zeiten zu vermitteln
- Praxisbeispiele
- Stripe verwendet einen Token Bucket mit einem Limit von 500 und einem Refill-Intervall von 0,01 Sekunden pro Nutzer. Dadurch sind dauerhaft 100 Anfragen pro Sekunde möglich, während Bursts bis zu 500 Anfragen erlaubt sind.
- Das kostenlose Tier von OpenAI GPT-3.5 verwendet einen Token Bucket mit einem Limit von 200 und einem Refill-Intervall von 86400 Sekunden / 200 und ist damit auf 200 Anfragen pro Tag begrenzt.
Punkte, die bei der Einführung von Rate Limits zu beachten sind
- Für den Rate Limiter sollte ein persistenter Speicher eingerichtet werden.
- Falls die Verbindung des Servers zu diesem persistenten Speicher fehlschlägt, sollten alle Anfragen zugelassen werden, statt sie zu blockieren.
- Optional kann Burst-Traffic zusätzlich reguliert werden.
- Es muss ein geeigneter Schlüssel gewählt werden (User-ID, API-Key usw.).
- Sinnvolle Fehler bei Überschreitung des Rate Limits sollten angezeigt werden (Wartezeit bis zur nächsten Anfrage, HTTP-Statuscode 429, Response-Header wie
x-ratelimit-* usw.).
2 Kommentare
Ich habe die auf Koreanisch zusammengefasste Version gelesen und dachte: „Okay, ich verstehe, worum es geht, aber ist das nicht alles dasselbe?“ Dann habe ich den verlinkten Originalartikel gelesen, und er erklärt es wirklich hervorragend; auch die Visualisierungen sind äußerst gelungen! 👍👍👍
Hacker-News-Kommentare
Zusammenfassung der Hacker-News-Kommentare
Zusätzliche Überlegungen aus langjähriger Erfahrung:
In Multi-Tenant-Umgebungen ist Fair Queuing der beste Ansatz, um DoS-Angriffe zu verhindern: Jedem Client wird eine eigene Queue zugewiesen, und eine Hintergrundroutine durchläuft die Queues wiederholt und verarbeitet die Anfragen. Clients, die Spam-Anfragen senden, überlasten dadurch nur ihre eigene Queue.
Erfahrungen bei der Implementierung von Client-Verarbeitungscode: Ich habe mich immer gefragt, welche Backoff-Strategie optimal ist, wenn ein Rate Limit erreicht wird. Es war interessant, die Trade-offs aus Sicht des Dienstes zu lesen.
Glückwunsch-Nachricht: Für einen kurzen Inhalt ist dies die beste Visualisierung überhaupt; der Beitrag ist sehr informativ und bringt die Kernaussagen gut auf den Punkt.
GCRA-Algorithmus: Ich halte ihn für einen besseren Algorithmus für Rate Limiting. Ich wünschte, er wäre bekannter und würde häufiger verwendet.
Großartige Arbeit: Man merkt, wie viel Zeit und Mühe in diesen Beitrag geflossen sind. Gut gemacht.
Probleme mit Rate Limiting in AWS Lambda: Ich habe versucht, Rate Limiting in NodeJS zu implementieren, aber in AWS Lambda verhielten sich Timer seltsam, sodass das Ziel überschritten wurde. Lokal bestand der Test, in Lambda jedoch nicht. Es ist unklar, ob es an den Timern oder an der Bibliothek liegt.
Umgang mit einer gesättigten Rate-Limiting-Schicht: Ich frage mich, ob es außer CF noch andere Optionen gibt. Außerdem würde mich interessieren, wie effektiv nftable-Regeln zur Abwehr von DoS-Angriffen auf einem kleinen VPS sind.
Ein Moment, in dem ich diese Ressource gebraucht hätte: Eine Ressource, die ich im Lauf meiner Karriere mehrfach gebraucht hätte. Ich bin froh, dass sie jetzt existiert.
Fan von Datenvisualisierung: Ich frage mich, ob dafür D3 verwendet wird.