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

Question

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

Answer 1

这是最简单的算法，如果您只想在消息到达太快时就丢弃它们（而不是对其进行排队，这很有意义，因为队列可能会任意大）：

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个单位的速度增长，即每八秒最多五个单位。转发的每封邮件都会扣除一个单位，因此每八秒钟发送的邮件不能超过五个。

请注意，该值rate应为整数，即不包含非零的小数部分，否则该算法将无法正常工作（实际费率将不是rate/per）。例如，rate=0.5; per=1.0;它无法正常工作，因为allowance它将永远不会增长到1.0。但是rate=1.0; per=2.0;效果很好。