分散フロー制御アルゴリズムを5分で理解する

フロー制御は、複雑なシステムでは必ず考慮しなければならない問題です。この記事では、さまざまなフロー制御アルゴリズムを紹介して比較し、システム要件とアーキテクチャに基づいて適切なソリューションを選択できるようにします。オリジナル: 分散レート制限アルゴリズム [1]

分散レート制限システムを設計するときに必要なツールとアルゴリズムは何ですか?

ジョシュア・ホーネ @Unsplash

Criteo は世界最大級の広告テクノロジー企業です。広告市場が発展し続ける中、Criteo は過去数年にわたり API の改善に注力し、プログラム可能なインターフェースを通じて顧客が必要なサービスに簡単にアクセスできるようにしてきました。

新しい API を使用するクライアントが増えるにつれて、すべてのクライアントがリソースに平等にアクセスできるようにし、頻繁な (悪意のある、または誤った) 呼び出しから API を保護するために、何らかのフロー制御を実装する必要があることが明らかになります。

フロー制御は単純に見えます。特定のクライアントが 1 分あたり X 回の呼び出しのみを実行できるようにします。単一のサーバーインスタンスにフロー制御を実装するのは非常に簡単で、それを実装するための関連ライブラリを見つけるのも簡単です。しかし問題は、当社の API が 6 つのデータセンター (ヨーロッパ、北米、アジア) でホストされており、それぞれに複数のインスタンスがあるため、何らかの分散フロー制御システムが必要になることです。

フロー制御は、呼び出し回数に関係するだけでなく、現在の制限ステータスをクライアントと同期する必要もあります (専用のヘッダーとステータスコードを使用するなど)。ただし、この記事では主にフロー制御に使用されるアルゴリズムとシステムに焦点を当てます。

負荷分散の使用

独自のシステムの開発を試みる前に、既存のインフラストラクチャが必要な機能を提供できるかどうかを確認することが重要です。

では、データセンター内のすべてのインスタンスの前にデプロイされ、トラフィックの検査とルーティングをすでに担当しているものは何でしょうか?ロードバランサー。ほとんどのロードバランサは、フロー制御機能またはフロー制御を実装するために使用できる抽象化を提供します。たとえば、HAProxy にはフロー制御を設定するために使用できる既存のスティックテーブルがあります。 [2] は、インスタンス間で状態を同期することができ、非常にうまく機能します。

残念ながら、ロードバランサーは必要な機能の一部 (動的制限、トークンイントロスペクションなど) をサポートしていないため、これらの特定の要件を自分で実装する必要があります。

基本計画

スティッキーセッション

負荷分散について言えば、特定のクライアントが均等に負荷をかけられず、常に単一のインスタンスと対話する場合、分散フロー制御システムは必要ありません。ほとんどのクライアントは、最も近いデータセンターにアクセスします (geo-DNS 経由)。ロードバランサーで「スティッキネス」が有効になっている場合、クライアントは常に同じインスタンスにアクセスする必要があります。その場合、単純な「ローカル」レート制限を使用できます。

これは理論的には機能しますが、実際には機能しません。 Criteo のシステムが受ける負荷は一定ではありません。たとえば、ブラックフライデー/サイバーウィークは 1 年で最も重要な期間です。この期間中、チームは警戒を怠らず、顧客からの需要の高まりに対応するためにインフラストラクチャを拡張する準備を整えていました。しかし、セッションのスティッキー性とスケーラビリティはうまく連携しません (すべてのクライアントが古いインスタンスに固執している場合、新しいインスタンスを作成する意味は何でしょうか?)

よりスマートなセッションスティッキー性 (スケーリング時にトークンを再割り当てする) を使用すると役立ちますが、スケーリングするたびに、クライアントが前のインスタンスで実行した呼び出しの数を知らずに、別のインスタンスに切り替える可能性があることを意味します。本質的には、これにより、スケールするたびにフロー制御に一貫性がなくなり、システムに負荷がかかるたびにクライアントがより多くの呼び出しを行う可能性が高くなります。

チャッティサーバー

クライアントが任意のインスタンスにアクセスできる場合、「呼び出し回数」をインスタンス間で共有する必要があることを意味します。 1 つの方法は、各インスタンスが他のすべてのインスタンスを呼び出して、特定のクライアントの現在のカウントを要求し、それを合計することです。別のアプローチでは、逆のことが行われ、各サーバーが他のサーバーに「カウント更新」をブロードキャストします。

これにより、主に 2 つの問題が発生します。

インスタンスの数が増えるほど、必要な呼び出しの数も増えます。
各インスタンスは他のインスタンスのアドレスを認識する必要があり、サービスがスケールアップまたはスケールダウンされるたびにアドレスを更新する必要があります。

このソリューションは可能ですが (基本的にはポイントツーポイントリングであり、多くのシステムですでに実装されています)、コストがかかります。

カフカ

各インスタンスが他のインスタンスと通信しないようにしたい場合は、Kafka を使用してすべてのインスタンスのカウンターを同期できます。

たとえば、インスタンスが呼び出されると、対応するトピックにイベントがプッシュされます。イベントはスライディングウィンドウで集約され (Kafka Streams はこれをうまく実行します)、各クライアントの最後の 1 分間の最新のカウントが別のトピックに公開されます。各インスタンスは、このトピックを通じてすべてのクライアントの共有カウントを取得します。

問題は、Kafka が本質的に非同期であり、通常はレイテンシが最小限であるものの、API 負荷が増加するとレイテンシが増加する可能性があることです。インスタンスが古いカウンターを使用している場合、本来ブロックされるはずの呼び出しが失われる可能性があります。

これらのソリューションにはすべて共通点が 1 つあります。それは、すべてが正常に動作しているときは非常にうまく機能しますが、負荷が大きくなるとパフォーマンスが低下することです。当社のシステムのほとんどはこのように設計されており、通常は問題はありませんが、フロー制御は一般的なコンポーネントではなく、その目的はシステムの残りの部分をこの重い負荷から保護することです。

フロー制御システムの目的は、システムの負荷が高いときにも適切に動作することであり、最良の 99% のケースではなく最悪の 1% のケースに対応するように構築されています。

分散アルゴリズム

集中型の同期ストレージシステムと、各クライアントの現在のレートを計算するアルゴリズムが必要です。メモリキャッシュ (Memcached や Redis など) は理想的なシステムですが、すべてのフロー制御アルゴリズムをキャッシュシステムに実装できるわけではありません。どのようなアルゴリズムがあるのか見てみましょう。

簡単にするために、「1 分あたり 100 回の呼び出し」のフロー制御を実現することを考えてみましょう。

利用可能なツールを確認します。

納屋の画像 @Unsplash

イベントログ経由のスライディングウィンドウ

特定のクライアントが過去 1 分間に何回呼び出しを行ったかを知りたい場合は、各クライアントのタイムスタンプのリストをキャッシュに保存できます。呼び出されるたびに、対応するタイムスタンプがリストに追加されます。次に、リスト内の各項目をループし、1 分以上経過した古い項目を破棄して、新しい項目を計算します。

:+1: 利点:

非常に正確
単純

:-1: デメリット:

強力なトランザクションサポートが必要です (同じリストを更新する必要がある同じクライアントの 2 つのインスタンスの処理)。
制限と呼び出し回数に応じて、保存されるオブジェクト (リスト) のサイズがかなり大きくなる可能性があります。
パフォーマンスは不安定です (呼び出しが増えると、処理するタイムスタンプも増えます)。

固定ウィンドウ

ほとんどの分散キャッシュシステムには、特定の高性能な「カウンター」抽象化 (文字列キーに添付された自動的に増分される整数値) があります。

による" {クライアントID} 「」でキー設定された各クライアントのカウンターを維持するのは非常に簡単ですが、これではカウンターが作成されてからクライアントが行った呼び出しの数のみがカウントされ、最後の 1 分間に行われた呼び出しの数はカウントされません。 {クライアントID}_{yyyyMMddHHmm} " をキーとして使用することで、クライアントのカウンターを 1 分ごとに維持できます (つまり、1 分の固定ウィンドウ)。現在の時刻に対応するカウンターを調べると、この 1 分間にクライアントが実行した通話の数がわかります。この値が上限を超えると、通話をブロックできます。

これは「最後の瞬間」と同じではないことに注意してください。午前 7 時 10 分 23 秒に通話があった場合、固定ウィンドウカウンターには午前 7 時 10 分 00 秒から午前 7 時 10 分 23 秒までの通話数が表示されます。しかし、私たちが本当に知りたいのは、午前 7:09:23 から 7:10:23 までの間の通話数です。

ある意味では、固定ウィンドウアルゴリズムは、経過する各分の前に何回の呼び出しがあったかを「忘れる」ため、クライアントは理論的には 07:09:59 に 100 回の呼び出しを実行し、その後 07:10:00 にさらに 100 回の呼び出しを実行できます。

:+1: 利点:

非常に高速（単一のアトミック増分 + 読み取り操作）
非常に基本的なトランザクションサポートのみが必要です（アトミックカウンター）
安定したパフォーマンス
単純

:-1: デメリット:

不正確（通話回数は最大2回まで許可されます）

トークンバケット

1994 年、両親はあなたをゲームセンターに送り、友達とスーパーストリートファイター 2 をプレイさせました。彼らは 5 ドル硬貨の入ったバケツを渡し、通りの向かいにあるバーに行くと、1 時間ごとに誰かがやって来て、バケツに 5 ドル硬貨を投げ入れます。つまり、基本的には 1 時間のプレイにつき 5 ドルに制限されます (ストリートファイターが上手ければいいのですが)。

これが「トークンバケット」アルゴリズムの背後にある主な考え方です。単純なカウンターの代わりに、「バケット」が各クライアントキャッシュに保存されます。バケットは、次の 2 つのプロパティで構成されるオブジェクトです。

残りの「トークン」（または残りの呼び出し）の数
最後の通話のタイムスタンプ。

API が呼び出されると、バケットが取得され、現在の呼び出しと最後の呼び出しの間の時間間隔に基づいて新しいトークンがバケットに追加されます。余分なトークンがある場合は、それらが減らされて呼び出しが許可されます。

したがって、ストリートファイターの例とは反対に、毎分バケツを補充するのを手伝ってくれる「親」は存在しません。バケットは、トークンの消費と同じ操作で実質的に補充されます (トークンの数は、最後の呼び出しからの時間間隔に対応します)。最後の通話が 30 秒前だった場合、1 分あたり 100 回の通話の制限は、50 個のトークンがバケットに追加されることを意味します。バケットが古すぎる場合 (最後の呼び出しが 1 分以上前)、トークンカウントは 100 にリセットされます。

実際、初期化時に 100 を超えるトークンを埋めることが可能です (ただし、100 トークン/分の速度)。これは「バースト」機能に似ており、クライアントはフロー制御制限を短時間超過できますが、長時間維持することはできません。

注意: 追加するトークンの数を正しく計算することが重要です。そうしないと、バケットが誤って満たされるリスクがあります。

このアルゴリズムは、確実なパフォーマンスを提供しながら完璧な精度を提供しますが、主な問題はトランザクションが必要になることです (2 つのインスタンスがキャッシュされたオブジェクトを同時に更新することは望ましくありません)。

100 コール/分のトークンバケットのステップバイステップの例

:+1: 利点:

非常に正確
速い
安定したパフォーマンス
初期トークン数を最適化することで、クライアントは「バースト」コールを行うことができる。

:-1: デメリット:

より複雑
強力なトランザクションサポートが必要

漏れやすいバケツ: このアルゴリズムの別のバージョン。このバージョンでは、呼び出しはバケットに蓄積され、一定のレート（レート制限に一致）で処理されます。バケットがオーバーフローすると、呼び出しは拒否されます。これは実装がより複雑ですが、サービス負荷を平準化できます (これが望ましい結果である場合もそうでない場合もあります)。

:trophy:最高のアルゴリズム?

3 つのアルゴリズムを比較すると、トークンバケットがパフォーマンスと精度の間で最も優れた妥協点を提供しているようです。ただし、これが可能なのは、システムが適切なトランザクションサポートを提供している場合のみです。 Redis クラスターがある場合、これは完璧なソリューションです (Lua ベースのアルゴリズムを実装し、それを Redis クラスターで直接実行してパフォーマンスを向上させることもできます)。ただし、Memcached はトランザクションではなく、アトミックカウンターのみをサポートします。

トークンバケットの楽観的並行バージョンはMemcachedに基づいて実装できる。 [3] ただし、これはより複雑であり、負荷が高い場合、楽観的同時実行性のパフォーマンスが低下します。

固定ウィンドウを使用してスライディングウィンドウを近似する

強力なトランザクションサポートがなければ、不正確な固定ウィンドウアルゴリズムを使用するしかないのでしょうか?

そうだと思いますが、まだ改善の余地はあります。固定ウィンドウの主な問題は、時間が経過するごとに、以前に何が起こったかを「忘れてしまう」ことですが、関連情報 (前の 1 分間のカウンター内) には引き続きアクセスできるため、加重平均を計算することで、前の 1 分間の通話数を推定できます。

60年代の固定窓を組み合わせて60年代のスライド窓を近似的にシミュレートします

たとえば、00:01:43 に通話が行われた場合、カウンターを増分して「00:01」の値を取得します。これは現在のカレンダーの分なので、00:01:00 から 00:01:43 までの間の通話数が含まれます (最後の 17 秒はまだ発生していません)。

しかし、私たちが知りたいのは 60 秒のスライディングウィンドウ内の通話数です。つまり、00:00:43 から 00:01:00 までの期間のカウントが欠落していることになります。これを行うには、「00:00」カウンターを読み取り、それを 17/60 の係数で調整して、最後の 17 秒のみに関心があることを示します。

負荷が変化しない場合は、この近似は完璧です。しかし、ほとんどの通話が最初の 1 分間に集中している場合は、過大評価された値が得られます。ほとんどの通話が前の 1 分間の終了後に集中している場合、この数値は過小評価されます。

比較する

精度の違いをより正確に把握するには、両方のアルゴリズムを同じ条件でシミュレートするのが最適です。

次の図は、ランダムなトラフィックが入力されたときに「固定カウンター」アルゴリズムが返す値を示しています。灰色の線は「完璧な」スライディングウィンドウ出力であり、どの時点でもウィンドウは過去 60 秒間の通話数に対応しており、これが私たちの目標です。オレンジ色の破線は、固定ウィンドウアルゴリズムによる同じトラフィックの「カウント」を表します。

最初の 1 分間は出力は同じですが、固定ウィンドウバージョンでは 1 分単位で出力が大きく低下することがすぐにわかります。固定ウィンドウアルゴリズムでは、100 回の呼び出し制限を超えることはほとんどありません。つまり、ブロックする必要がある多くの呼び出しが許可されることになります。

次の図は、同じトラフィックで、同様のスライディングウィンドウを使用した同じシナリオを示しています。ここでも、灰色の線は「完璧な」スライディングウィンドウを表します。オレンジ色の破線は近似アルゴリズムを表します。

1 分あたりのマーク付近での低下は見られなくなり、新しいバージョンのアルゴリズムが完璧なアルゴリズムにかなり近づいていることがわかります。わずかに高くなったり、わずかに低くなったりしますが、全体的には大きな改善が見られます。

収穫逓減

しかし、もっと良い方法はあるのでしょうか?

当社の近似アルゴリズムでは、現在の 60 秒と以前の 60 秒の固定ウィンドウのみを使用します。ただし、複数の小さなサブウィンドウを使用することも可能であり、極端なアプローチとしては、60 個の 1 秒ウィンドウを使用して最後の 1 分間のトラフィックを再構築する方法があります。明らかに、これは各呼び出しごとに 60 個のカウンターを読み取ることを意味し、パフォーマンスコストが大幅に増加します。ただし、任意の固定された時間枠を選択し、それに近似値を当てはめることができます。ウィンドウが小さいほど、必要なカウンターの数が増え、近似値がより正確になります。

5 つの 15 秒のウィンドウを組み合わせると何が起こるか見てみましょう。

予想通り、精度は向上しましたが、まだ完璧ではありません。

私たちは古典的な精度の向上 = パフォーマンスの低下状況下では。絶対的に最善の解決策というものは存在せず、最も適切な解決策を見つけるには、精度とパフォーマンスの要件のバランスを取る必要があります。サービスの過剰使用からの保護のみを重視し、継続的な制御を必要としない場合は、最も単純な固定ウィンドウでも実行可能なソリューションになる可能性があります。