分布式速率限制算法

Question

我正在制定定价平台,我必须实施分布式速率限制算法.我有k个网关提供x服务.任何网关都可以提供任何服务(通过负载均衡器).客户每秒向服务购买一次呼叫,其呼叫可以通过任何网关路由.那么,有人知道一个好的算法来更新所有网关上的呼叫计数器以限制客户呼叫吗？

关于该算法的两个重要指标是网络开销以及接受呼叫数量与速率限制之间的偏差.

谢谢!

编辑 我只想知道是否有"众所周知"的算法.

Answer 1

我已经根据这篇文章（archive.org）实现了一个解决方案。我认为该算法称为“漏桶”，但效果很好。它并不完美，因为它允许一次性使用整个配额，但总的来说，使用 Node.js 和 Redis 速度非常快。接受的请求和速率之间的差异可能非常大，并且取决于样本窗口和存储桶大小之间的比率。