什么是好的速率限制算法?

问题:

我可以使用一些伪代码,或更好的Python。我试图为Python IRC机器人实现速率限制队列,并且部分工作,但是如果有人触发的消息少于限制(例如,速率限制是每8秒5个消息,并且该人仅触发4)并且下一个触发器超过8秒(例如,16秒后),机器人发送消息,但队列已满,并且机器人等待8秒,即使不需要,因为8秒钟的时间已经过去。

回答:

这里simplest algorithm,如果你想只是在消息到达时太快(而不是排队他们,这是有道理的,因为队列可能会任意变大):

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; [/code] 在这个解决方案中没有数据结构,计时器等,它的工作很干净:)为了看到这个,“容限”最多以每秒5/8个单位增长,即每八秒最多五个单位。每个转发的消息都会扣除一个单位,所以每八秒钟不能发送五条以上的消息。 注意,rate应该是一个整数,即没有非零小数部分,否则算法将无法正常工作(实际速率不会是rate/per)。例如。 rate=0.5; per=1.0;不起作用,因为allowance永远不会增长到1.0。但rate=1.0; per=2.0;工作正常。

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: What’s a good rate limiting algorithm?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

31 + = 34