Что такое хороший алгоритм ограничения скорости?

155

Я мог бы использовать некоторый псевдокод или, лучше сказать, Python. Я пытаюсь реализовать очередь ограничения скорости для бота Python IRC, и она частично работает, но если кто-то запускает меньше сообщений, чем предел (например, ограничение скорости составляет 5 сообщений в 8 секунд, а человек запускает только 4), и следующий триггер более 8 секунд (например, 16 секунд спустя), бот отправляет сообщение, но очередь заполняется, и бот ждет 8 секунд, даже если это не нужно, так как истек 8-секундный период.

Miniman
источник

Ответы:

231

Вот самый простой алгоритм , если вы хотите просто отбрасывать сообщения, когда они приходят слишком быстро (вместо того, чтобы ставить их в очередь, что имеет смысл, потому что очередь может стать произвольно большой):

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;

В этом решении нет структур данных, таймеров и т. Д., И оно работает чисто :). Чтобы увидеть это, «допуск» растет со скоростью не более 5/8 единиц в секунду, то есть не более пяти единиц в восемь секунд. Каждое пересылаемое сообщение удерживает одну единицу, поэтому вы не можете отправлять более пяти сообщений каждые восемь секунд.

Обратите внимание, что это rateдолжно быть целое число, т.е. без ненулевой десятичной части, иначе алгоритм не будет работать правильно (фактическая скорость не будет rate/per). Например rate=0.5; per=1.0;, не работает, потому allowanceчто никогда не будет расти до 1,0. Но rate=1.0; per=2.0;работает отлично.

Антти Уима
источник
4
Также стоит указать, что размер и масштаб time_passed должны быть такими же, как per, например, секунды.
Скаффман
2
Привет, скаффман, спасибо за комплименты - я выбросил его из рукава, но с вероятностью 99,9% кто-то ранее придумал подобное решение :)
Antti Huima
52
Это стандартный алгоритм - это набор токенов, без очереди. Ведро есть allowance. Размер ковша есть rate. allowance += …Линия является оптимизацией добавления маркеров каждой скорости ÷ за секунды.
Дероберт
5
@zwirbeltier То, что вы пишете выше, не соответствует действительности. «Allowance» всегда ограничен «rate» (посмотрите на строку «// throttle»), поэтому он разрешит только
серию
8
Это хорошо, но может превышать ставку. Допустим, в момент времени 0 вы пересылаете 5 сообщений, затем в момент N * (8/5) для N = 1, 2, ... вы можете отправить еще одно сообщение, в результате чего за 8 секунд будет
получено
48

Используйте этот декоратор @RateLimited (ratepersec) перед вашей функцией, которая ставит в очередь.

По сути, он проверяет, прошло ли 1 / скорость в секундах с последнего раза, и если нет, ждет оставшуюся часть времени, в противном случае он не ждет. Это эффективно ограничивает вас, чтобы оценить / сек. Декоратор может быть применен к любой функции, которую вы хотите ограничить по скорости.

В вашем случае, если вы хотите максимум 5 сообщений за 8 секунд, используйте @RateLimited (0.625) перед функцией 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)
Карлос А. Ибарра
источник
Мне нравится идея использования декоратора для этой цели. Почему lastTime называется списком? Кроме того, я сомневаюсь, что это будет работать, когда несколько потоков вызывают одну и ту же функцию RateLimited ...
Stephan202
8
Это список, потому что простые типы, такие как float, являются постоянными при захвате замыканием. Делая это списком, список постоянен, но его содержимое не является. Да, это не потокобезопасно, но это можно легко исправить с помощью замков.
Карлос А. Ибарра
time.clock()в моей системе недостаточно разрешения, поэтому я адаптировал код и переключился на использованиеtime.time()
mtrbean
3
Для ограничения скорости вы определенно не хотите использовать time.clock(), который измеряет истекшее время процессора. Процессорное время может работать намного быстрее или намного медленнее, чем «фактическое» время. Вы хотите использовать time.time()вместо этого, который измеряет время стены («фактическое» время).
Джон Уайзман
1
Кстати, для реальных производственных систем: реализация ограничения скорости с помощью вызова sleep () может быть не очень хорошей идеей, поскольку она собирается заблокировать поток и, следовательно, помешать другому клиенту использовать его.
Maresh
28

Token Bucket довольно прост в реализации.

Начните с ведра с 5 жетонов.

Каждые 5/8 секунд: если в ведре меньше 5 жетонов, добавьте один.

Каждый раз, когда вы хотите отправить сообщение: если в корзине есть токен ≥1, выньте один токен и отправьте сообщение. В противном случае, подождите / отбросьте сообщение / что угодно.

(очевидно, в реальном коде вы использовали бы целочисленный счетчик вместо реальных токенов, и вы можете оптимизировать каждый шаг 5/8, сохраняя временные метки)


Повторное чтение вопроса, если ограничение скорости полностью сбрасывается каждые 8 ​​секунд, то вот модификация:

Начните с отметки last_sendвремени, давно, например, в эпоху. Кроме того, начните с того же ведра с 5 жетонами.

Ударьте правило каждые 5/8 секунд.

Каждый раз, когда вы отправляете сообщение: сначала проверьте, если last_send≥ 8 секунд назад. Если так, заполните ведро (установите это к 5 жетонам). Во-вторых, если в корзине есть токены, отправьте сообщение (в противном случае отбросьте / подождите / и т.д.). В-третьих, установить last_sendсейчас.

Это должно работать для этого сценария.


Я на самом деле написал бот IRC, используя такую ​​стратегию (первый подход). Это на Perl, а не на Python, но вот некоторый код для иллюстрации:

Первая часть здесь посвящена добавлению токенов в корзину. Вы можете увидеть оптимизацию добавления токенов на основе времени (от 2-й до последней строки), а затем последняя строка ограничивает содержимое сегмента до максимума (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 - это структура данных, которая передается. Это внутри метода, который выполняется регулярно (он рассчитывает, когда в следующий раз ему будет что-то делать, и спит либо так долго, либо до тех пор, пока не получит сетевой трафик). Следующая часть метода обрабатывает отправку. Это довольно сложно, потому что сообщения имеют приоритеты, связанные с ними.

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

Это первая очередь, которая запускается несмотря ни на что. Даже если это приведет к тому, что наше соединение погибнет от наводнения. Используется для чрезвычайно важных вещей, например, для ответа на PING сервера. Далее остальные очереди:

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

Наконец, статус корзины сохраняется обратно в структуру данных $ conn (на самом деле чуть позже в методе; сначала он вычисляет, как скоро у него будет больше работы)

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

Как видите, реальный код обработки сегментов очень мал - около четырех строк. Остальная часть кода является приоритетной обработкой очереди. У бота есть приоритетные очереди, так что, например, кто-то, общаясь с ним, не может помешать ему выполнять свои важные обязанности по кик-бану.

derobert
источник
Я что-то упустил ... похоже, это ограничит вас одним сообщением каждые 8 ​​секунд после того, как вы пройдете первые 5
chills42
@ chills42: Да, я неправильно прочитал вопрос ... см. вторую половину ответа.
Дероберт
@chills: если last_send <8 секунд, вы не добавляете токены в корзину. Если ваше ведро содержит токены, вы можете отправить сообщение; иначе вы не можете (вы уже отправили 5 сообщений за последние 8 секунд)
derobert
3
Я был бы признателен, если бы люди, проголосовавшие за это, объяснили бы почему ... Я хотел бы исправить любые проблемы, которые вы видите, но это сложно сделать без обратной связи!
Дероберт
10

чтобы заблокировать обработку, пока сообщение не может быть отправлено, таким образом, помещая в очередь дальнейшие сообщения, красивое решение antti также может быть изменено следующим образом:

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;

он просто ждет, пока не будет достаточно разрешения для отправки сообщения. чтобы не начинать с двухкратной ставки, скидка также может быть инициализирована с 0.

Сан -
источник
5
Когда вы спите (1-allowance) * (per/rate), вы должны добавить ту же сумму last_check.
Алп
2

Сохраните время, когда были отправлены последние пять строк. Удерживайте сообщения в очереди до тех пор, пока пятое самое последнее сообщение (если оно существует) не пройдет как минимум 8 секунд в прошлом (с last_five в виде массива раз):

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()
Песто
источник
Не с тех пор, как вы его пересмотрели, я не
Песто
Вы храните пять временных меток и неоднократно перемещаете их по памяти (или выполняете операции со связанным списком). Я храню один счетчик целых чисел и одну временную метку. И только занимаюсь арифметикой и присваиваю.
Дероберт
2
За исключением того, что мой будет работать лучше, если попытаться отправить 5 строк, но только 3 разрешены в течение периода времени. Ваши позволят отправить первые три и заставят ждать 8 секунд перед отправкой 4 и 5. Мои позволят отправлять 4 и 5 через 8 секунд после четвертой и пятой самых последних строк.
Песто
1
Но по этому вопросу производительность может быть улучшена с помощью кругового связного списка длиной 5, указывающего на пятую самую последнюю отправку, перезаписывающего его при новой отправке и перемещающего указатель вперед на одну.
Песто
для irc бота с ограничителем скорости скорость не является проблемой. Я предпочитаю решение списка, поскольку это более читабельно. Ответ, который был дан, является сбивающим с толку из-за пересмотра, но в этом также нет ничего плохого.
Джерико
2

Одним из решений является прикрепление метки времени к каждому элементу очереди и удаление элемента по истечении 8 секунд. Вы можете выполнять эту проверку каждый раз, когда очередь добавляется.

Это работает, только если вы ограничите размер очереди до 5 и откажетесь от любых добавлений, пока очередь заполнена.

jheriko
источник
1

Если кто-то все еще заинтересован, я использую этот простой вызываемый класс в сочетании с временным хранилищем значений ключа LRU, чтобы ограничить частоту запросов на IP. Использует deque, но может быть переписан для использования со списком.

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")
Сани
источник
1

Просто реализация Python кода из принятого ответа.

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
Hodza
источник
Было предложено мне , что я предлагаю вам добавить пример использования вашего кода .
Люк
0

Как насчет этого:

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

источник
0

Мне нужна была вариация в Scala. Вот:

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

}

Вот как это можно использовать:

val f = Limiter((5d, 8d), { 
  _: Unit  
    println(System.currentTimeMillis) 
})
while(true){f(())}
Лэндон Кун
источник