什么是一个很好的限速算法？ [英] What's a good rate limiting algorithm?

问题描述

我可以利用一些假code，或者更好，巨蟒。我想实现的限速队列Python的IRC机器人，它的部分作品，但如果有人超过极限触发较少的信息（例如，速率限制为每8秒5的消息，而人只会触发4）和下一个触发是在8秒（例如，16个秒后），该机器人发送消息，但排队满和机器人等待8秒，尽管它不是必要的，因为在8秒周期已失效。

I could use some pseudo-code, or better, Python. I am trying to implement a rate-limiting queue for a Python IRC bot, and it partially works, but if someone triggers less messages than the limit (e.g., rate limit is 5 messages per 8 seconds, and the person triggers only 4), and the next trigger is over the 8 seconds (e.g., 16 seconds later), the bot sends the message, but the queue becomes full and the bot waits 8 seconds, even though it's not needed since the 8 second period has lapsed.

推荐答案

下面最简单的算法，如果你只想放弃邮件到达时速度太快了（而不是排队他们来说，这是有道理的，因为队列可能会得到任意大）：

Here the simplest algorithm, if you want just to drop messages when they arrive too quickly (instead of queuing them, which makes sense because the queue might get arbitrarily large):

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单位每秒最多，即最多五个单位每8秒。被转移的每一封邮件扣除一个单位，所以你不能每次每八秒钟后发送五个以上的消息。

There are no datastructures, timers etc. in this solution and it works cleanly :) To see this, 'allowance' grows at speed 5/8 units per seconds at most, i.e. at most five units per eight seconds. Every message that is forwarded deducts one unit, so you can't send more than five messages per every eight seconds.

注意率应该是一个整数，即没有非零小数部分，或者算法将无法正常工作（实际速率不会是率/每）。例如。 率= 0.5;每= 1.0; 不起作用，因为津贴将永远不会增长到1.0。但率= 1.0;每= 2.0; 正常工作

Note that rate should be an integer, i.e. without non-zero decimal part, or the algorithm won't work correctly (actual rate will not be rate/per). E.g. rate=0.5; per=1.0; does not work because allowance will never grow to 1.0. But rate=1.0; per=2.0; works fine.

这篇关于什么是一个很好的限速算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！