通用信元速率算法比漏桶算法的优势

Question

我正在寻找一种将传入请求限制到REST HTTP的速率算法。我看过“漏桶”和“通用细胞速率算法:虚拟调度”

根据我的理解，漏桶有以下限制：

1. 如果队列/桶是空的，并且请求出现在时钟滴答之前(当我们实际处理请求时)，那么请求必须等待时间，直到时钟滴答作响。
2. 网络域变长分组

我已经读过这个博客，它实现了“通用细胞速率算法:虚拟调度”。

有人能解释一下吗？

1. GCRA如何解决#1中提到的漏桶的局限性？
2. 在我的用例中，如果我将时钟刻度设置为低(可能每毫秒签入一次)，那么漏桶的问题难道不应该减轻吗？

Answer 1

漏桶算法有两个变体：计量器和队列。表一在这里更相关，所以让我们来关注它。

其思想是，水桶被分配一个滴水率(或者是跨桶均匀的，或者是基于某一层)。进来的工作有一些与之相关的“量”。它既可以装进水桶，也可以放不下。如果没有，它就会被丢弃。如果符合，它是经过处理(至少在仪表版本)。

谁负责滴水桶？你提到的博客声称，这通常是通过一个后台过程来完成的，这个过程在水桶周围循环并滴水。它提到了一个缺点，即如果它可以处理桶的速度很低(在其脱机的极端情况下)，作业可能会被丢弃，这不是因为没有足够的空卷属于桶，而是因为滴水过程没有更新它。这基本上就是你的第一点；我看不出你的第2点有什么问题(虽然你可能读过一本描述，其中一个版本的漏桶被限制在统一的卷中，但算法的固有特性并不需要这样)。

这就是GCRA进来的原因。如果你想一想，一个单独的滴水过程是没有必要的。如果您跟踪每个桶、当前状态和一个作业，您可以计算下一次任何给定的任务大小都会有足够的空卷。因此，当一份工作到来时，它只是检查它是在这段时间之前还是之后。如果它以前出现过，它就会被丢弃。如果它出现在之后，它将被允许通过，时间--直到下一个--工作将被更新。

关于你的问题(相关问题)：

1. 因为使用GCRA，您不依赖于单独的进程滴水，您不会遇到问题，它死了，或只是无法跟上。这就引出了下一个问题:特别是，
2. 如果你以非常高的频率运行单独的进程，那么，只要滴水过程保持正常，事情就会好起来。然而，由于频率较高，滴水过程有可能无法跟上。

但请注意，这里没有免费午餐。不管你有什么处理能力，都需要有人检查一下空卷，然后更新点滴。YMMV对于某些设置和实现，很容易想象一个单独的滴漏过程(假设有人很好地设计了系统，并且它不会离线)，会给整个系统提供更低的延迟、更高的吞吐量，或者两者兼而有之。其他设置和实现可能有相反的情况。