Was ist eine gute rate-limiting-Algorithmus?

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ß):

rate = 5.0; // unit: messages
per  = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
  current = now();
  time_passed = current - last_check;
  last_check = current;
  allowance += time_passed * (rate / per);
  if (allowance > rate):
    allowance = rate; // throttle
  if (allowance < 1.0):
    discard_message();
  else:
    forward_message();
    allowance -= 1.0;

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 nicht rate/per). E. g. rate=0.5; per=1.0; funktioniert nicht, weil allowance wird nie wachsen zu 1.0. Aber rate=1.0; per=2.0; funktioniert einwandfrei.

InformationsquelleAutor der Antwort Antti Huima

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_sendin 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 Sie last_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)

    my $start_time = time;
    ...
    # Bucket handling
    my $bucket = $conn->{fujiko_limit_bucket};
    my $lasttx = $conn->{fujiko_limit_lasttx};
    $bucket += ($start_time-$lasttx)/MESSAGE_INTERVAL;
    ($bucket <= MESSAGE_BURST) or $bucket = 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.

    # Queue handling. Start with the ultimate queue.
    my $queues = $conn->{fujiko_queues};
    foreach my $entry (@{$queues->[PRIORITY_ULTIMATE]}) {
            # Ultimate is special. We run ultimate no matter what. Even if
            # it sends the bucket negative.
            --$bucket;
            $entry->{code}(@{$entry->{args}});
    }
    $queues->[PRIORITY_ULTIMATE] = [];

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:

    # Continue to the other queues, in order of priority.
    QRUN: for (my $pri = PRIORITY_HIGH; $pri >= PRIORITY_JUNK; --$pri) {
            my $queue = $queues->[$pri];
            while (scalar(@$queue)) {
                    if ($bucket < 1) {
                            # continue later.
                            $need_more_time = 1;
                            last QRUN;
                    } else {
                            --$bucket;
                            my $entry = shift @$queue;
                            $entry->{code}(@{$entry->{args}});
                    }
            }
    }

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)

    # Save status.
    $conn->{fujiko_limit_bucket} = $bucket;
    $conn->{fujiko_limit_lasttx} = $start_time;

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

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

now = time.time()
if len(last_five) == 0 or (now - last_five[-1]) >= 8.0:
    last_five.insert(0, now)
    send_message(msg)
if len(last_five) > 5:
    last_five.pop()

InformationsquelleAutor der Antwort Pesto

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.

from collections import deque
import time


class RateLimiter:
    def __init__(self, maxRate=5, timeUnit=1):
        self.timeUnit = timeUnit
        self.deque = deque(maxlen=maxRate)

    def __call__(self):
        if self.deque.maxlen == len(self.deque):
            cTime = time.time()
            if cTime - self.deque[0] > self.timeUnit:
                self.deque.append(cTime)
                return False
            else:
                return True
        self.deque.append(time.time())
        return False

r = RateLimiter()
for i in range(0,100):
    time.sleep(0.1)
    print(i, "block" if r() else "pass")

InformationsquelleAutor der Antwort sanyi

Brauchte ich eine variation in der Scala. Hier ist es:

case class Limiter[-A, +B](callsPerSecond: (Double, Double), f: A ⇒ B) extends (A ⇒ B) {

  import Thread.sleep
  private def now = System.currentTimeMillis / 1000.0
  private val (calls, sec) = callsPerSecond
  private var allowance  = 1.0
  private var last = now

  def apply(a: A): B = {
    synchronized {
      val t = now
      val delta_t = t - last
      last = t
      allowance += delta_t * (calls / sec)
      if (allowance > calls)
        allowance = calls
      if (allowance < 1d) {
        sleep(((1 - allowance) * (sec / calls) * 1000d).toLong)
      }
      allowance -= 1
    }
    f(a)
  }

}

Hier ist, wie es verwendet werden kann:

val f = Limiter((5d, 8d), { 
  _: Unit ⇒ 
    println(System.currentTimeMillis) 
})
while(true){f(())}

InformationsquelleAutor der Antwort Landon Kuhn