Che cosa è un buon tasso di limitazione algoritmo?

StackOverflow https://stackoverflow.com/questions/667508

  •  21-08-2019
  •  | 
  •  

Domanda

ho potuto usare un po 'di pseudo-codice, o meglio, Python. Sto cercando di implementare una coda di fattore limitante per un bot Python IRC, e funziona in parte, ma se qualcuno fa scattare meno messaggi al limite (ad esempio, limite di velocità è di 5 messaggi al 8 secondi, e la persona che si innesca solo 4), e la prossima trigger è nel corso degli 8 secondi (ad esempio, 16 secondi dopo), il bot invia il messaggio, ma la coda diventa piena e il bot attende 8 secondi, anche se non è necessaria in quanto il secondo periodo di 8 è estinto.

È stato utile?

Soluzione

Qui il semplice algoritmo , se si vuole solo far cadere i messaggi quando arrivano troppo in fretta ( invece di fare la coda, che ha un senso in quanto la coda potrebbe ottenere arbitrariamente grande): 

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;

Non ci sono strutture di dati, timer ecc in questa soluzione e funziona in modo pulito :) Per vedere questo, 'assegno' cresce a velocità 5/8 unità per secondi al massimo, vale a dire al massimo cinque unità per otto secondi. Ogni messaggio che viene inoltrato deduce una sola unità, quindi non è possibile inviare più di cinque messaggi per ogni otto secondi.

Si noti che rate dovrebbe essere un intero, cioè senza diverso da zero parte decimale, o l'algoritmo non funziona correttamente (tasso effettivo non sarà rate/per). Per esempio. rate=0.5; per=1.0; non funziona perché allowance non crescerà mai a 1,0. Ma rate=1.0; per=2.0; funziona bene.

Altri suggerimenti

Utilizzare questa decoratore @RateLimited (ratepersec) prima della funzione che accoda.

In sostanza, questo controlla se sec 1 / tassi sono passati dall'ultima volta e se no, aspetta il resto del tempo, altrimenti non aspetta. In questo modo si limita in modo efficace per votare / sec. Il decoratore può essere applicato a qualsiasi funzione che si desidera tasso limitato.

Nel tuo caso, se si vuole un massimo di 5 messaggi ogni 8 secondi, utilizzare @RateLimited (0,625) prima della funzione di sendToQueue. 

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)

A Token Bucket è abbastanza semplice da implementare.

Inizia con un secchio con 5 gettoni.

Ogni 5/8 secondi:. Se il secchio ha meno di 5 gettoni, aggiungere un

Ogni volta che si desidera inviare un messaggio: se il secchio ha ≥1 modo, prendere un gettone e inviare il messaggio. In caso contrario, attendere / cadere il messaggio / qualunque cosa.

(ovviamente, in codice vero e proprio, utilizza un contatore intero invece di gettoni reali e è possibile ottimizzare il ogni passo 5 / 8s memorizzando timestamp)

La lettura di nuovo la questione, se il limite di velocità viene resettato completamente ogni 8 secondi, poi qui è una modifica:

Inizia con un timestamp, last_send, in un momento molto tempo fa (per esempio, all'epoca). Inoltre, iniziare con lo stesso secchio da 5 token.

Colpisci la regola di ogni 5/8 secondi.

Ogni volta che si invia un messaggio: In primo luogo, verificare se <=> ≥ 8 secondi fa. Se è così, riempire il secchio (impostarlo a 5 gettoni). In secondo luogo, se ci sono gettoni nel secchio, inviare il messaggio (in caso contrario, goccia / wait / etc.). In terzo luogo, impostare <=> ad oggi.

Questo dovrebbe funzionare per quello scenario.

In realtà ho scritto un bot IRC utilizzando una strategia di questo tipo (il primo approccio). La sua in Perl, Python non, ma qui è un codice di illustrare:

La prima parte qui gestisce l'aggiunta di gettoni per il secchio. Si può vedere l'ottimizzazione di aggiungere gettoni in base al tempo (secondo all'ultima riga) e poi l'ultima riga morsetti contenuti secchio al massimo (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 è una struttura dati che viene passata in giro. Questo è all'interno di un metodo che viene eseguito di routine (si calcola quando la prossima volta che si avrà a che fare, e dorme o che lungo o fino a quando non ottiene il traffico di rete). La parte successiva del metodo maniglie di invio. E 'piuttosto complicato, perché i messaggi sono priorità ad essi associati. 

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

Questa è la prima coda, che viene eseguito non importa quale. Anche se ottiene la nostra connessione uccise per le inondazioni. Usato per le cose estremamente importanti, come rispondere al PING del server. Successivamente, il resto delle code: 

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

Infine, lo stato secchio viene salvato di nuovo alla struttura di dati $ conn (in realtà un po 'più tardi nel metodo, ma prima calcola quanto tempo si avrà più lavoro) 

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

Come si può vedere, il codice che gestisce secchio reale è molto piccola - circa quattro linee. Il resto del codice è la gestione della coda di priorità. Il bot ha code di priorità in modo che per esempio, qualcuno chiacchierando con essa non può impedire che fare i suoi importanti compiti calcio / ban.

per bloccare l'elaborazione fino a quando il messaggio può essere inviato, in coda in tal modo fino ulteriori messaggi, bella soluzione di Antti può anche essere modificato in questo modo: 

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;

semplicemente attende che sufficiente assegno è lì per inviare il messaggio. per non iniziare con due volte il tasso, indennità può anche inizializzato con 0.

Tenere il tempo che le ultime cinque righe sono stati inviati. Tenere i messaggi in coda fino al momento il quinto-più-recente messaggio (se esiste) è prima di 8 secondi in passato (con last_five come una matrice di volte): 

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

Una soluzione è quella di allegare un timestamp a ciascun elemento della coda e scartare l'oggetto dopo 8 secondi sono passati. È possibile eseguire questo controllo ogni volta che la coda si aggiunge al.

Questo funziona solo se si limita la dimensione della coda a 5 e scartare eventuali integrazioni, mentre la coda è piena.

Se qualcuno ancora interessato, io uso questo semplice classe richiamabile in combinazione con un temporizzato memorizzazione valore chiave LRU per limitare richiesta di velocità per IP. Utilizza un deque, ma può riscritto per essere utilizzato con una lista, invece. 

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

Solo un'implementazione pitone di un codice dalla risposta accettata. 

import time

class Object(object):
    pass

def get_throttler(rate, per):
    scope = Object()
    scope.allowance = rate
    scope.last_check = time.time()
    def throttler(fn):
        current = time.time()
        time_passed = current - scope.last_check;
        scope.last_check = current;
        scope.allowance = scope.allowance + time_passed * (rate / per)
        if (scope.allowance > rate):
          scope.allowance = rate
        if (scope.allowance < 1):
          pass
        else:
          fn()
          scope.allowance = scope.allowance - 1
    return throttler

Che ne dite di questo: 

long check_time = System.currentTimeMillis();
int msgs_sent_count = 0;

private boolean isRateLimited(int msgs_per_sec) {
    if (System.currentTimeMillis() - check_time > 1000) {
        check_time = System.currentTimeMillis();
        msgs_sent_count = 0;
    }

    if (msgs_sent_count > (msgs_per_sec - 1)) {
        return true;
    } else {
        msgs_sent_count++;
    }

    return false;
}

Avevo bisogno di una variazione di Scala. Eccolo: 

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

}

Ecco come può essere utilizzato: 

val f = Limiter((5d, 8d), { 
  _: Unit ⇒ 
    println(System.currentTimeMillis) 
})
while(true){f(())}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top