什么是一個好的速率限制算法？我可以使用一些偽代碼，或者更好的Python。我正在嘗試為Python IRC機器人實現速率限制隊列，它部分工作，但如果有人觸發的消息少于限制（例如，速率限制是每8秒5條消息，而此人只觸發4條消息），并且下一個觸發器超過8秒（例如，16秒后），機器人發送消息，但是隊列變滿并且機器人等待8秒，即使自8秒時間段已經過去也不需要它。
3 回答
慕沐林林
TA貢獻2016條經驗 獲得超9個贊
這里是最簡單的算法，如果您只想在消息到達太快時丟棄它們（而不是排隊它們，這是有道理的，因為隊列可能會變得任意大）：
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;
在這個解決方案中沒有數據結構，定時器等，它干凈利落地工作:)為了看到這一點，'allowance'最多以每秒5/8單位的速度增長，即每8秒最多5個單位。轉發的每條消息都會扣除一個單元，因此每八秒鐘不能發送五條以上的消息。
請注意，rate應該是一個整數，即沒有非零小數部分，否則算法將無法正常工作（實際速率不會rate/per）。例如rate=0.5; per=1.0;不起作用，因為allowance永遠不會增長到1.0。但rate=1.0; per=2.0;工作正常。
慕桂英4014372
TA貢獻1871條經驗 獲得超13個贊
在排隊的函數之前使用此裝飾器@RateLimited（ratepersec）。
基本上，這會檢查自上次以來是否已經過1 /速率秒，如果沒有，則等待剩余的時間，否則它不會等待。這實際上限制了你的速率/秒。裝飾器可以應用于您想要的速率限制的任何功能。
在您的情況下，如果您希望每8秒最多發送5條消息，請在sendToQueue函數之前使用@RateLimited（0.625）。
import timedef 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 mostdef PrintNumber(num): print numif __name__ == "__main__": print "This should print 1,2,3... at about 2 per second." for i in range(1,100): PrintNumber(i)
Qyouu
TA貢獻1786條經驗 獲得超11個贊
令牌桶實現起來相當簡單。
從帶有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;如您所見，實際的鏟斗處理代碼非常小 - 大約四行。其余代碼是優先級隊列處理。機器人具有優先級隊列，例如，與之聊天的人不能阻止它執行其重要的啟動/禁令職責。
添加回答
舉報
0/150
提交
取消