什么是一个好的速率限制算法？

Question

什么是一个好的速率限制算法？

我可以使用一些伪代码，或者更好的Python。我正在尝试为Python IRC机器人实现速率限制队列，它部分工作，但如果有人触发的消息少于限制（例如，速率限制是每8秒5条消息，而此人只触发4条消息），并且下一个触发器超过8秒（例如，16秒后），机器人发送消息，但是队列变满并且机器人等待8秒，即使自8秒时间段已经过去也不需要它。

Answer 1

这里是最简单的算法，如果您只想在消息到达太快时丢弃它们（而不是排队它们，这是有道理的，因为队列可能会变得任意大）：rate = 5.0; // unit: messagesper&nbsp; = 8.0; // unit: secondsallowance = rate; // unit: messageslast_check = now(); // floating-point, e.g. usec accuracy. Unit: secondswhen (message_received):&nbsp; current = now();&nbsp; time_passed = current - last_check;&nbsp; last_check = current;&nbsp; allowance += time_passed * (rate / per);&nbsp; if (allowance > rate):&nbsp; &nbsp; allowance = rate; // throttle&nbsp; if (allowance < 1.0):&nbsp; &nbsp; discard_message();&nbsp; else:&nbsp; &nbsp; forward_message();&nbsp; &nbsp; 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;工作正常。

Answer 2

在排队的函数之前使用此装饰器@RateLimited（ratepersec）。基本上，这会检查自上次以来是否已经过1 /速率秒，如果没有，则等待剩余的时间，否则它不会等待。这实际上限制了你的速率/秒。装饰器可以应用于您想要的速率限制的任何功能。在您的情况下，如果您希望每8秒最多发送5条消息，请在sendToQueue函数之前使用@RateLimited（0.625）。import&nbsp;timedef&nbsp;RateLimited(maxPerSecond): &nbsp;&nbsp;&nbsp;&nbsp;minInterval&nbsp;=&nbsp;1.0&nbsp;/&nbsp;float(maxPerSecond) &nbsp;&nbsp;&nbsp;&nbsp;def&nbsp;decorate(func): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lastTimeCalled&nbsp;=&nbsp;[0.0] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def&nbsp;rateLimitedFunction(*args,**kargs): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elapsed&nbsp;=&nbsp;time.clock()&nbsp;-&nbsp;lastTimeCalled[0] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leftToWait&nbsp;=&nbsp;minInterval&nbsp;-&nbsp;elapsed&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;leftToWait>0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;time.sleep(leftToWait) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ret&nbsp;=&nbsp;func(*args,**kargs) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lastTimeCalled[0]&nbsp;=&nbsp;time.clock() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ret&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;rateLimitedFunction&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;decorate@RateLimited(2)&nbsp;&nbsp;#&nbsp;2&nbsp;per&nbsp;second&nbsp;at&nbsp;mostdef&nbsp;PrintNumber(num): &nbsp;&nbsp;&nbsp;&nbsp;print&nbsp;numif&nbsp;__name__&nbsp;==&nbsp;"__main__": &nbsp;&nbsp;&nbsp;&nbsp;print&nbsp;"This&nbsp;should&nbsp;print&nbsp;1,2,3...&nbsp;at&nbsp;about&nbsp;2&nbsp;per&nbsp;second." &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(1,100): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PrintNumber(i)

Answer 3

令牌桶实现起来相当简单。从带有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）&nbsp;&nbsp;&nbsp;&nbsp;my&nbsp;$start_time&nbsp;=&nbsp;time; &nbsp;&nbsp;&nbsp;&nbsp;... &nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Bucket&nbsp;handling &nbsp;&nbsp;&nbsp;&nbsp;my&nbsp;$bucket&nbsp;=&nbsp;$conn->{fujiko_limit_bucket}; &nbsp;&nbsp;&nbsp;&nbsp;my&nbsp;$lasttx&nbsp;=&nbsp;$conn->{fujiko_limit_lasttx}; &nbsp;&nbsp;&nbsp;&nbsp;$bucket&nbsp;+=&nbsp;($start_time-$lasttx)/MESSAGE_INTERVAL; &nbsp;&nbsp;&nbsp;&nbsp;($bucket&nbsp;<=&nbsp;MESSAGE_BURST)&nbsp;or&nbsp;$bucket&nbsp;=&nbsp;MESSAGE_BURST;$ conn是一种传递的数据结构。这是在一个常规运行的方法中（它计算下次有什么事情要做，并且长时间睡眠或直到它获得网络流量）。该方法的下一部分处理发送。它相当复杂，因为消息具有与之相关的优先级。&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Queue&nbsp;handling.&nbsp;Start&nbsp;with&nbsp;the&nbsp;ultimate&nbsp;queue. &nbsp;&nbsp;&nbsp;&nbsp;my&nbsp;$queues&nbsp;=&nbsp;$conn->{fujiko_queues}; &nbsp;&nbsp;&nbsp;&nbsp;foreach&nbsp;my&nbsp;$entry&nbsp;(@{$queues->[PRIORITY_ULTIMATE]})&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Ultimate&nbsp;is&nbsp;special.&nbsp;We&nbsp;run&nbsp;ultimate&nbsp;no&nbsp;matter&nbsp;what.&nbsp;Even&nbsp;if &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;it&nbsp;sends&nbsp;the&nbsp;bucket&nbsp;negative. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;--$bucket; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$entry->{code}(@{$entry->{args}}); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;$queues->[PRIORITY_ULTIMATE]&nbsp;=&nbsp;[];这是第一个队列，无论如何都会运行。即使它让我们的连接因洪水而死亡。用于非常重要的事情，比如响应服务器的PING。接下来，其余的队列：&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Continue&nbsp;to&nbsp;the&nbsp;other&nbsp;queues,&nbsp;in&nbsp;order&nbsp;of&nbsp;priority. &nbsp;&nbsp;&nbsp;&nbsp;QRUN:&nbsp;for&nbsp;(my&nbsp;$pri&nbsp;=&nbsp;PRIORITY_HIGH;&nbsp;$pri&nbsp;>=&nbsp;PRIORITY_JUNK;&nbsp;--$pri)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;my&nbsp;$queue&nbsp;=&nbsp;$queues->[$pri]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(scalar(@$queue))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;($bucket&nbsp;<&nbsp;1)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;continue&nbsp;later. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$need_more_time&nbsp;=&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last&nbsp;QRUN; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;--$bucket; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;my&nbsp;$entry&nbsp;=&nbsp;shift&nbsp;@$queue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$entry->{code}(@{$entry->{args}}); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}最后，存储桶状态被保存回$ conn数据结构（实际上稍晚于该方法;它首先计算它将在多长时间内完成更多工作）&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Save&nbsp;status. &nbsp;&nbsp;&nbsp;&nbsp;$conn->{fujiko_limit_bucket}&nbsp;=&nbsp;$bucket; &nbsp;&nbsp;&nbsp;&nbsp;$conn->{fujiko_limit_lasttx}&nbsp;=&nbsp;$start_time;如您所见，实际的铲斗处理代码非常小 - 大约四行。其余代码是优先级队列处理。机器人具有优先级队列，例如，与之聊天的人不能阻止它执行其重要的启动/禁令职责。