分布式速率限制算法

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

有关此算法的两个重要指标是网络开销和接受呼叫数量与速率限制之间的偏差。

谢谢！

编辑我只是想知道是否有一个“众所周知”的算法。

来源

2012-11-16 Lambdacrash

你试过什么算法，答案不在你的范围内？ – Woot4Moo

我正在研究这个问题，目前我没有实现任何算法，因为我不知道现有的算法。我们很容易想象一种天真的算法，在每次通话之后发送其计数器以通知其他网关它接收到一个呼叫，然后减少所有其他计数器，但如果速率限制大约为每秒10000个呼叫，则网络开销是可怕的。另一种情况可能是限制<网关的数量，然后在任何呼叫之后暗示柜台广播。 – Lambdacrash

如果您知道分布式速率限制算法，请给我他们的名字：p – Lambdacrash

我已经实施了基于此article（archive.org）的解决方案。我认为该算法被称为Leaky Bucket，但它工作正常。这并不完美，因为它允许整个配额在突发中使用，但总体而言，它对node.js和Redis速度非常快。接受的请求和速率之间的差异可能相当高，并取决于采样窗口和桶大小之间的比率。

来源

2012-11-17 08:30:41 mhvelplund

非常感谢，我会实现这个算法，并检查是否在我的范围内:-) – Lambdacrash

给出的文章链接不再可用。 – lrAndroid

@IrAndroid：修复指向archive.org的链接。 – mhvelplund

分布式速率限制算法

回答

相关问题