通用信元率算法相对于漏桶算法的优势
Advantage of Generic Cell Rate Algorithm over Leaky Bucket Algorithm
我正在寻找一种算法来限制对 REST HTTP 服务器的传入请求的速率。我经历了 "Leaky Bucket" & "Generic Cell Rate Algorithm : Virtual Schedulling"
根据我的理解，Leaky Bucket 有以下限制：-
- 如果队列/桶是空的并且请求在时钟滴答之前到达（当我们实际处理请求时）那么请求必须等待时间直到时钟滴答。
- 网络域变长包
我已经完成了实现 "Generic Cell Rate Algorithm : Virtual Schedulling" 的 blog。
能否解释一下：-
- GCRA是如何解决#1中提到的Leaky Bucket的限制的？
- 在我的用例中，如果我将时钟节拍设置为低（可能每纳秒检查一次），漏桶问题是否应该得到缓解？
漏桶算法有两种变体，meter and queue。米一这里比较贴切，重点说说吧。
这个想法是为一个桶分配一个滴水率（跨桶统一，或基于某个层级）。进来的工作有一些与之相关的 "volume" 。它可以放入桶中，也可以不放入桶中。如果不是，则将其丢弃。如果适合，则将其传递以进行处理（至少在仪表版本中）。
谁负责滴水桶？你提到的博客声称这通常是由一个后台进程完成的，它在桶周围循环并滴下它们。它提到了缺点，如果它可以处理桶的速率很低（在它离线的极端情况下），一个工作可能会被丢弃，不是因为没有足够的属于桶的空体积，而是因为滴水进程只是没有更新它。这基本上是您的第 1 点；我没有看到你的第 2 点的问题（尽管你可能已经阅读了关于限制为统一体积的漏桶的无数版本之一的描述，但算法的固有内容不需要这个）。
这就是 GCRA 的用武之地。如果您考虑一下，一个单独的滴水过程并不是真正必要的。如果您跟踪每个存储桶的当前状态并且有作业进入，您可以计算下一次有足够的空卷来满足任何给定的未来作业大小。所以，当一个工作到达时，它只是检查它是在这个时间之前还是之后到达的。如果它之前出现，则将其丢弃。如果它在之后出现，则让它通过，并更新下一个作业之前的时间。
关于您的问题（相关）：
由于使用 GCRA，您不依赖于单独的滴水过程，因此您不会 运行 陷入死机或无法跟上的问题。这就引出了下一点：特别是
如果你运行 separate-process 的频率非常高，那么，只要滴水过程跟上就没问题。但是，如果频率很高，滴水过程可能跟不上。
请注意，天下没有免费的午餐。无论您拥有何种处理能力，都需要有人检查空卷并更新滴灌。 YMMV。对于某些设置和实现，很容易想象一个单独的滴水过程（假设有人对系统进行了很好的设计，并且它不会离线），可以为系统提供整体更低的延迟、更高的吞吐量，或两者兼而有之。其他设置和实现可能相反。
我正在寻找一种算法来限制对 REST HTTP 服务器的传入请求的速率。我经历了 "Leaky Bucket" & "Generic Cell Rate Algorithm : Virtual Schedulling"
根据我的理解，Leaky Bucket 有以下限制：-
- 如果队列/桶是空的并且请求在时钟滴答之前到达（当我们实际处理请求时）那么请求必须等待时间直到时钟滴答。
- 网络域变长包
我已经完成了实现 "Generic Cell Rate Algorithm : Virtual Schedulling" 的 blog。
能否解释一下：-
- GCRA是如何解决#1中提到的Leaky Bucket的限制的？
- 在我的用例中，如果我将时钟节拍设置为低（可能每纳秒检查一次），漏桶问题是否应该得到缓解？
漏桶算法有两种变体，meter and queue。米一这里比较贴切，重点说说吧。
这个想法是为一个桶分配一个滴水率（跨桶统一，或基于某个层级）。进来的工作有一些与之相关的 "volume" 。它可以放入桶中，也可以不放入桶中。如果不是，则将其丢弃。如果适合，则将其传递以进行处理（至少在仪表版本中）。
谁负责滴水桶？你提到的博客声称这通常是由一个后台进程完成的，它在桶周围循环并滴下它们。它提到了缺点，如果它可以处理桶的速率很低（在它离线的极端情况下），一个工作可能会被丢弃，不是因为没有足够的属于桶的空体积，而是因为滴水进程只是没有更新它。这基本上是您的第 1 点；我没有看到你的第 2 点的问题（尽管你可能已经阅读了关于限制为统一体积的漏桶的无数版本之一的描述，但算法的固有内容不需要这个）。
这就是 GCRA 的用武之地。如果您考虑一下，一个单独的滴水过程并不是真正必要的。如果您跟踪每个存储桶的当前状态并且有作业进入，您可以计算下一次有足够的空卷来满足任何给定的未来作业大小。所以，当一个工作到达时，它只是检查它是在这个时间之前还是之后到达的。如果它之前出现，则将其丢弃。如果它在之后出现，则让它通过，并更新下一个作业之前的时间。
关于您的问题（相关）：
由于使用 GCRA，您不依赖于单独的滴水过程，因此您不会 运行 陷入死机或无法跟上的问题。这就引出了下一点：特别是
如果你运行 separate-process 的频率非常高，那么，只要滴水过程跟上就没问题。但是，如果频率很高，滴水过程可能跟不上。
请注意，天下没有免费的午餐。无论您拥有何种处理能力，都需要有人检查空卷并更新滴灌。 YMMV。对于某些设置和实现，很容易想象一个单独的滴水过程（假设有人对系统进行了很好的设计，并且它不会离线），可以为系统提供整体更低的延迟、更高的吞吐量，或两者兼而有之。其他设置和实现可能相反。