Qu'est-ce qu'un bon algorithme de limitation de débit?

Question

Je pourrais utiliser de pseudo-code, ou mieux, Python. Je suis en train de mettre en œuvre une limitation de vitesse de la file d'attente pour un Python bot IRC, et il fonctionne partiellement, mais si quelqu'un déclenche moins de messages que la limite (par exemple, le taux limite est de 5 messages par 8 secondes, et la personne ne se déclenche que 4), et le prochain déclenchement est de plus de 8 secondes (par exemple, 16 secondes plus tard), le bot envoie le message, mais la file d'attente est pleine et le bot attend les 8 secondes, même s'il n'est pas nécessaire puisque le 8 deuxième période a expiré.

Answer 1

Ici, le plus simple algorithme, si vous voulez juste pour déplacer des messages quand ils arrivent trop vite (au lieu de la mise en attente, ce qui fait du sens parce que la file d'attente peut obtenir arbitrairement grand):

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;

Il n'existe pas de structures de données, les minuteries, etc. dans cette solution et ça fonctionne correctement :) Pour voir ce, 'allocation' se développe à une vitesse de 5/8 unités par secondes, c'est à dire à plus de cinq unités par huit secondes. Chaque message est transmis déduit une unité, de sorte que vous ne pouvez pas envoyer plus de cinq messages par toutes les huit secondes.

Notez que rate doit être un entier, c'est à dire sans non nulle partie décimale, ou l'algorithme ne fonctionne pas correctement (taux réel ne sera pas rate/per). E. g. rate=0.5; per=1.0; ne fonctionne pas car allowance ne sera jamais pousser à 1.0. Mais rate=1.0; per=2.0; fonctionne très bien.

Answer 2

L'utilisation de ce décorateur @RateLimited(ratepersec) avant de votre fonction qui place en file d'attente.

En gros, il vérifie si 1/taux de secondes se sont écoulées depuis la dernière fois et si non, attend le reste du temps, sinon, il n'attend pas. Effectivement cela vous limite à taux/sec. Le décorateur peut être appliquée à toute fonction que vous voulez limitée dans le taux.

Dans votre cas, si vous voulez un maximum de 5 messages par 8 secondes, utilisez @RateLimited(0.625) avant votre sendToQueue fonction.

import time

def RateLimited(maxPerSecond):
    minInterval = 1.0 / float(maxPerSecond)
    def decorate(func):
        lastTimeCalled = [0.0]
        def rateLimitedFunction(*args,**kargs):
            elapsed = time.clock() - lastTimeCalled[0]
            leftToWait = minInterval - elapsed
            if leftToWait>0:
                time.sleep(leftToWait)
            ret = func(*args,**kargs)
            lastTimeCalled[0] = time.clock()
            return ret
        return rateLimitedFunction
    return decorate

@RateLimited(2)  # 2 per second at most
def PrintNumber(num):
    print num

if __name__ == "__main__":
    print "This should print 1,2,3... at about 2 per second."
    for i in range(1,100):
        PrintNumber(i)

Answer 3

Un Token Bucket est assez simple à mettre en œuvre.

Commencez avec un seau avec 5 jetons.

Chaque 5/8 secondes: Si le seau a moins de 5 jetons, pour en ajouter un.

Chaque fois que vous voulez envoyer un message: Si le seau a ≥1 jeton, prendre un jeton et d'envoyer le message. Sinon, attendez/supprimer le message/whatever.

(évidemment, dans le code, vous pouvez utiliser un compteur de nombre entier au lieu d'un vrai jetons et vous pouvez optimiser les toutes les 5/8s étape en stockant les horodatages)

---

La lecture de la question à nouveau, si la limite de taux est entièrement remis à zéro chaque 8 secondes, puis ici, c'est une modification:

Commencez avec un timestamp, last_send, à un moment il y a longtemps (par exemple, à l'époque). Aussi, les mêmes 5-token bucket.

Grève de la chaque 5/8 secondes de la règle.

Chaque fois que vous envoyez un message à: tout d'Abord, vérifiez si last_send ≥ 8 secondes auparavant. Si oui, remplir le seau (5 jetons). Deuxièmement, si il y a des jetons dans le seau, envoyer le message (sinon, drop/attendre/etc.). Troisièmement, ensemble last_send maintenant.

Cela devrait fonctionner pour ce scénario.

---

En fait, j'ai écrit un bot IRC en utilisant une stratégie qui ressemble à ceci (la première approche). Son en Perl, pas en Python, mais voici un peu de code pour illustrer:

La première partie ici, gère l'ajout de jetons dans le seau. Vous pouvez voir l'optimisation de l'ajout de jetons en fonction du temps (de la 2e à la dernière ligne) et puis la dernière ligne de pinces contenu du seau au maximum (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 est une structure de données qui est passé autour. C'est à l'intérieur d'une méthode qui fonctionne régulièrement (il calcule quand la prochaine fois qu'il aura quelque chose à faire, et dort que soit longue ou jusqu'à ce qu'il obtient le trafic réseau). La partie suivante de la méthode se charge de l'envoi. Il est plutôt compliqué, parce que les messages ont des priorités qui leur sont associés.

    # 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] = [];

C'est la première de la file d'attente, qui est géré n'importe quoi. Même si elle obtient notre connexion tuées par les inondations. Utilisé pour extrêmement important pense, comme la réponse du serveur PING. Ensuite, le reste de la file d'attente:

    # 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}});
                    }
            }
    }

Enfin, le seau d'état est enregistré à l' $conn structure de données (en fait, un peu plus tard dans la méthode; il calcule combien de temps il faudra plus de travail)

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

Comme vous pouvez le voir, le seau code de traitement est très faible, environ quatre lignes. Le reste du code est la priorité de la file d'attente de la manipulation. Le bot a des files d'attente de priorité, de sorte que, par exemple, quelqu'un de bavarder avec elle ne peut pas l'empêcher de faire son important kick/ban fonctions.

Answer 4

bloquer le traitement jusqu'à ce que le message puisse être envoyé, mettant ainsi en file d'attente d'autres messages, la belle solution d'antti peut également être modifiée comme suit:

 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):
    time.sleep( (1-allowance) * (per/rate))
    forward_message();
    allowance = 0.0;
  else:
    forward_message();
    allowance -= 1.0;
 

il attend juste que suffisamment d’allocation soit disponible pour envoyer le message. pour ne pas commencer avec deux fois le taux, l’allocation peut également être initialisée avec 0.

Answer 5

Gardez l'heure à laquelle les cinq dernières lignes ont été envoyées. Tenez les messages en file d'attente jusqu'à ce que le cinquième message le plus récent (s'il existe) soit au moins 8 secondes dans le passé (avec last_five comme tableau de fois):

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