algorithm - 分布式限速算法

Question

我正在一个定价平台上工作，我必须实现一个分布式速率限制算法。我有k个提供x服务的网关。任何网关都可以提供任何服务（通过负载均衡器）。客户每秒向服务购买多个呼叫，其呼叫可以通过任何网关路由。那么，是否有人知道一种好的算法来更新所有网关上的呼叫计数器以限制客户呼叫？

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

谢谢！

编辑 我只想知道是否有“知名”算法。

Answer 1

我已经根据这篇文章(archive.org) 实现了一个解决方案。我认为该算法称为Leaky Bucket，但它工作正常。它并不完美，因为它允许一次性使用整个配额，但总体而言，它使用 node.js 和 Redis 非常快。接受的请求和速率之间的差异可能非常大，并且取决于样本窗口和存储桶大小之间的比率。