分散レート制限アルゴリズム

Question

私は、分散レート制限アルゴリズムを実装する必要がある価格設定プラットフォームに取り組んでいます。私はkゲートウェイを提供しており、xのサービスを提供しています。ゲートウェイは、（ロードバランサを介して）任意のサービスを提供できます。顧客はサービスに1秒間に多数の通話を購入し、その通話は任意のゲートウェイ経由でルーティングできます。だから、顧客の通話を制限するために、すべてのゲートウェイでコールカウンターを更新するための良いアルゴリズムを知っている人がいますか？

このアルゴリズムに関する2つの重要な指標は、ネットワークオーバーヘッドと受け入れられたコール数とレート制限の間の偏差です。

ありがとうございます！

「よく知られている」アルゴリズムがあるかどうかを知りたいだけです。

Answer 1

私はこのarticle（archive.org）に基づいて解決策を実装しました。私はアルゴリズムがLeaky Bucketと呼ばれると思うが、それは正常に動作します。クォータ全体をバーストで使用できるので完璧ではありませんが、全体的にnode.jsとRedisでは非常に高速です。受け入れられたリクエストとレートの差はかなり大きく、サンプルウィンドウとバケットサイズの比に依存します。