Was ist eine gute rate-limiting-Algorithmus?
Ich könnte etwas pseudo-code, oder besser, Python. Ich bin versucht zu implementieren ein rate-limiting in die Warteschlange für ein Python IRC bot, und es teilweise funktioniert, aber wenn es jemand löst weniger Nachrichten als der Grenzwert (zB, limit ist 5 Nachrichten pro 8 Sekunden, und der Mensch löst nur 4), und der nächste trigger ist über die 8 Sekunden (z.B., 16 Sekunden später), der bot sendet die Nachricht, aber die Warteschlange voll ist und der bot wartet 8 Sekunden, auch wenn es nicht benötigt wird, da die 8-Sekunden-Zeitraum abgelaufen ist.
InformationsquelleAutor der Frage miniman | 2009-03-20
Schreibe einen Kommentar Antworten abbrechen
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier die einfachste Algorithmuswenn Sie wollen, um die drop-Meldungen, wenn Sie kommen zu schnell (statt der Schlange, die Sinn macht, weil die Warteschlange könnte beliebig groß):
Gibt es keine Datenstrukturen, Timer usw. in diese Lösung und es funktioniert sauber 🙂 um dies Zu sehen, 'Taschengeld' wächst schnell 5/8 Einheiten pro Sekunden, also maximal fünf Einheiten pro acht Sekunden. Jede Nachricht, die weitergeleitet wird, zieht eine Einheit, so dass Sie können nicht senden mehr als fünf Nachrichten pro alle acht Sekunden.
Beachten Sie, dass
rate
sollte eine ganze Zahl sein, d.h. ohne nicht-null Nachkommastellen, oder der Algorithmus nicht korrekt arbeitet (tatsächliche rate wird nichtrate/per
). E. g.rate=0.5; per=1.0;
funktioniert nicht, weilallowance
wird nie wachsen zu 1.0. Aberrate=1.0; per=2.0;
funktioniert einwandfrei.InformationsquelleAutor der Antwort Antti Huima
Verwendung dieser Dekorator @RateLimited(ratepersec), bevor Sie Ihre Funktion, die Warteschlange einreiht.
Grundsätzlich, diese überprüft, ob 1/rate Sekunden vergangen seit dem letzten mal und wenn nicht, wartet der Rest der Zeit, sonst nicht warten. Diesem effektiv Grenzen, die Sie zu rate/Sek. Der Dekorateur kann angewendet werden, um jede Funktion, die Sie möchten, rate-begrenzt.
In Ihrem Fall, wenn Sie wollen, maximal 5 Nachrichten pro 8 Sekunden @RateLimited(0.625), bevor Ihr sendToQueue Funktion.
InformationsquelleAutor der Antwort Carlos A. Ibarra
Einen Token Bucket ist relativ einfach zu implementieren.
Beginnen Sie mit einem Eimer mit 5 Jetons.
Jedem 5/8 Sekunden: Wenn der Eimer hat weniger als 5 Zeichen, hinzufügen.
Jedes mal, wenn Sie eine Nachricht senden wollen: Wenn der Eimer hat ≥1 token, nehmen Sie einen token aus und senden Sie die Nachricht. Ansonsten warten/löschen der Nachricht/was auch immer.
(offensichtlich in der tatsächlichen Codes, die Sie verwenden würden, ein integer-Zähler anstelle von echten Jetons und optimieren Sie heraus die alle 5/8s Schritt durch Speicherung von Zeitstempel)
Lesen der Frage wieder, wenn der Preis das limit ist voll reset jeweils 8 Sekunden, dann ist hier eine änderung:
Beginnen mit einem timestamp,
last_send
in einer Zeit lange vor (z.B. in der Epoche). Auch, beginnen mit der gleichen 5-token bucket.Streik der jedes 5/8 Sekunden-Regel.
Jedes mal, wenn Sie eine Nachricht senden: prüfen Sie Zunächst, ob
last_send
≥ 8 Sekunden. Wenn dem so ist, füllen Sie den Eimer (5 tokens). Zweitens, wenn es gibt Steine in die Eimer, die Nachricht zu senden (andernfalls drop/warten/etc.). Drittens, stellen Sielast_send
jetzt.Diese Arbeit sollte für dieses Szenario.
Habe ich das wirklich geschrieben ein IRC-bot mit einer Strategie wie dieser (der erste Ansatz). Seine in Perl, Python nicht, aber hier ist etwas code zur Veranschaulichung:
Den ersten Teil hier verarbeitet hinzufügen Token, um den Eimer. Sehen Sie die Optimierung der Zugabe von tokens basierend auf Zeit (2. bis Letzte Zeile) und dann die Letzte Zeile Klemmen Eimer Inhalt für die maximale (MESSAGE_BURST)
$conn ist eine Daten-Struktur, die herum. Dies ist innerhalb einer Methode, die ausgeführt wird routinemäßig (errechnet Sie, Wann der nächste Zeit haben werde, etwas zu tun, und schläft entweder, oder lange, bis es bekommt, Netzwerk-Datenverkehr). Der nächste Teil behandelt die Methode senden. Es ist ziemlich kompliziert, da die Nachrichten Prioritäten zugeordnet.
Das ist die erste Warteschlange, wird ausgeführt, egal was. Auch wenn es bekommt unsere Verbindung für die überschwemmungen getötet. Verwendet für extrem wichtige Dinge, wie reagiert werden, um den server ANPINGEN. Weiter, der rest der Warteschlangen:
Schließlich, den Eimer-status wird gespeichert zurück zum $conn-Daten-Struktur (eigentlich ein bisschen später, in der Methode; er zuerst berechnet, wie bald es werde mehr Arbeit haben)
Wie Sie sehen können, die tatsächliche Eimer-handling-code ist sehr klein — etwa vier Zeilen. Der rest des Codes ist die priority queue-handling. Der bot hat priority-queues, so dass z.B. jemand im Chat mit kann es nicht verhindern, dass Sie tun, Ihre wichtigen kick/ban Pflichten.
InformationsquelleAutor der Antwort derobert
blockieren Verarbeitung, bis die Nachricht gesendet werden kann, so Schlange, weitere Nachrichten, antti schönen Lösung kann auch geändert werden, wie dies:
es, der nur darauf wartet, bis genug Zulage ist es, die Nachricht zu senden. nicht beginnen Sie mit zweimal der rate, Unterhalt kann auch mit 0 initialisiert.
InformationsquelleAutor der Antwort san
Halten Sie die Zeit, die die letzten fünf Zeilen gesendet wurden. Halten Sie die Nachrichten in der Warteschlange, bis die Zeit, die fünfte-die meisten-die Letzte Nachricht (wenn Sie existiert), ist eine mindestens 8 Sekunden in die Vergangenheit (mit last_five eine Reihe von Zeiten):
InformationsquelleAutor der Antwort Pesto
Eine Lösung ist das anbringen eines Zeitstempels zu jedem Eintrag der Warteschlange und verwerfen der Artikel nach 8 Sekunden vergangen sind. Sie können diese überprüfung durchzuführen, jedes mal, wenn die Warteschlange Hinzugefügt wird.
Funktioniert dies nur, wenn Sie beschränken die Größe der Warteschlange zu 5 und zu verwerfen, Ergänzungen, während die Schlange voll ist.
InformationsquelleAutor der Antwort jheriko
Wenn noch jemand interessiert, ich benutze dieses einfache callable-Klasse in Verbindung mit einer zeitlich LRU key-value-storage zu begrenzen Anfrage Preis pro IP. Verwendet eine deque, kann aber umgeschrieben, um verwendet werden, mit einer Liste statt.
InformationsquelleAutor der Antwort sanyi
Wie wäre es damit:
InformationsquelleAutor der Antwort
Brauchte ich eine variation in der Scala. Hier ist es:
Hier ist, wie es verwendet werden kann:
InformationsquelleAutor der Antwort Landon Kuhn
Nur eine python-Implementierung eines code, der von der akzeptierten Antworten.
InformationsquelleAutor der Antwort Anton Shelin