python - 什么是好的速率限制算法？

Question

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

Answer 1

这里是 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;

此解决方案中没有数据结构、计时器等，它运行良好 :) 看到这一点，“津贴”最多以每秒 5/8 个单位的速度增长，即每八秒最多五个单位。转发的每条消息都会扣除一个单位，因此每 8 秒发送的消息不能超过 5 条。

注意 rate 应该是一个整数，即没有非零小数部分，否则算法将无法正常工作(实际速率不会是 rate/per )。例如。 速率=0.5； per=1.0; 不起作用，因为 allowance 永远不会增长到 1.0。但是 rate=1.0; per=2.0; 工作正常。