単一マシンおよび分散シナリオにおけるフロー制御ソリューションは何ですか?

異なるシナリオで必要なフロー制御アルゴリズムは同じではありません。では、適切なフロー制御ソリューションをどのように選択すればよいのでしょうか?この記事では、単一マシンおよび分散フロー制御シナリオにおける、シンプル ウィンドウ、スライディング ウィンドウ、リーキー バケット、トークン バケット、スライディング ログなどのいくつかのフロー制御アルゴリズムのアイデアとコード実装を共有し、それぞれの複雑さと適用可能なシナリオをまとめます。かなり長いので、生徒は保存して後で読むことができます。

一流のコントロールシーン

フロー制御の重要性を説明する必要はありません。最も一般的に使用されるシナリオでは、フロー制御は、限られたダウンストリーム リソースがトラフィックによって圧倒されることを防ぎ、サービスの可用性を確保するために使用されます。一般的に、フロー制御しきい値にはある程度の柔軟性が認められており、時折の過剰なアクセスは許容されます。

場合によっては、フロー制御が課金モデルとして機能することもあります。たとえば、一部のクラウドベンダーは API 呼び出しの頻度に応じて料金を請求します。金銭が絡むため、限度額を超える通話は原則として許可されません。

これらの異なるシナリオでは、適用可能なフロー制御アルゴリズムが異なります。ほとんどの場合、Sentinel ミドルウェアは問題を適切に処理できますが、Sentinel は万能薬ではないため、他のフロー制御ソリューションを検討する必要があります。

2. インターフェース定義

便宜上、以下のサンプル コード実装はすべて Throttler インターフェイスに基づいています。

Throttler インターフェースは、単一のクォータを申請するための共通メソッドを定義します。

もちろん、シグネチャ tryAcquire(String key, int permits) を持つメソッドを定義して、一度に複数の割り当てを適用することもできます。実装の考え方は同じです。

一部のフロー制御アルゴリズムでは、キーごとに Throttler インスタンスを維持する必要があります。

パブリックインターフェース スロットラー {
 /**
 * 割り当てを申請してみる
 *
 * @param key クォータ申請のキー
 * @return アプリケーションが成功した場合は true を返し、そうでない場合は false を返します
 */
 ブール型tryAcquire(文字列キー);
 }

3つのスタンドアロンフロー制御

1つのシンプルなウィンドウ

シンプルウィンドウは私自身の名前です。後述する引き違い窓と区別するために、固定窓と呼ぶ場合もあります。

フロー制御は、指定された時間間隔内に許可されるアクセスの量を制限することです。したがって、最も直感的なアイデアは、特定の時間枠に基づいてアクセス数をカウントするカウンターを維持し、次のルールを実装することです。

• アクセス数が閾値未満の場合はアクセスが許可され、アクセス数が 1 増加します。
• アクセス数が閾値を超えるとアクセスが制限され、アクセス数が増加しなくなります。
• 時間ウィンドウを超えると、カウンターはクリアされ、クリア後の最初の成功したアクセス時刻が現在の時刻にリセットされます。これにより、カウンターは最新のウィンドウ内の訪問回数をカウントするようになります。

SimpleWindowThrottlerを実装するコード

 /**
 * 時間ウィンドウ（ミリ秒単位）
 */
 プライベート最終長いウィンドウInMs;
 /**
 * 時間枠内で許容される最大しきい値
 */
 プライベート最終intしきい値;
 /**
 * 最後に成功したリクエストの時刻
 */
 プライベート long lastReqTime = System.currentTimeMillis();
 /**
 * カウンター
 */
 プライベートロングカウンター。

 パブリックブール型tryAcquire(文字列キー) {
 現在の長さ = System.currentTimeMillis();
 // 現在の時刻が最後のアクセス時刻から始まる時間ウィンドウを超えた場合は、カウンターをリセットし、現在の時刻を新しいウィンドウの開始値として使用します。
 if (現在 - lastReqTime > windowInMs) { #1
 カウンター = 0;
 最後の要求時間 = 現在; ＃2
 }
 if (カウンタ < 閾値) { #3
 カウンター++; ＃4
 true を返します。
 } それ以外 {
 false を返します。
 }
 }

もう 1 つの一般的なシナリオは、異なるキーに基づいてフロー制御を実行することです。各キーには個別の時間ウィンドウとしきい値構成があるため、キーごとに個別のフロー リミッター インスタンスを維持する必要があります。

マルチスレッド環境に切り替える

実際のアプリケーションでは、複数のスレッドが同時にクォータを申請することがよくあります。アルゴリズムのアイデアをより簡潔に表現するために、サンプル コードでは同時同期制御は実行されません。

単純なウィンドウの実装を例にとると、それをマルチスレッドセーフなフロー制御アルゴリズムに変換する直接的な方法は、tryAcquire メソッドを synchronized に設定することです。

もちろん、より効率的な方法は、読み取り変数と書き込み変数の型を変更することです。

プライベート volatile long lastReqTime = System.currentTimeMillis();
 プライベート LongAdder カウンタ = new LongAdder();

しかし、これは本当に「安全」というわけではありません。次のシナリオを想像してください。2 つのスレッド A と B が順番にクォータを取得しようとします。位置 #1 の判定条件が満たされた後、同時に位置 #2 に移動して lastReqTime 値を変更します。スレッド B によって割り当てられた値はスレッド A の値を上書きし、時間ウィンドウの開始点が後方にシフトします。同様に、位置 #3 と #4 も競合状態になります。もちろん、フロー制御の精度に対する要求が高くない場合は、この種の競争は許容されます。

重大な突然変異問題

シンプルなウィンドウフロー制御の実装は非常にシンプルです。たとえば、1 分間に 100 回のアクセスが許可され、トラフィックが 1 分あたり 200 回のアクセス レートを維持する場合、システムのアクセス カーブはおおよそ次のようになります (1 分ごとにクリア)。

​​

しかし、トラフィックが均一でない場合、時間枠の開始時の 0:00 に散発的な訪問がいくつかあり、その後 0:50 にリクエストが 10 回/秒の速度で開始されると、次の訪問グラフが表示されます。

​​

重要な 20 秒間 (0:50 ~ 1:10) にシステムへの実際のアクセス数は 200 です。つまり、最悪の場合、システムはウィンドウの重要なポイント付近で 2 倍のトラフィックの影響を受けることになります。これは、単純なウィンドウでは解決できない重大な突然変異の問題です。

2 引き違い窓

単純なウィンドウアルゴリズムの重大な突然変異問題を解決するにはどうすればよいでしょうか?ウィンドウ統計の精度は低いため、大きな時間ウィンドウ全体をより細かいサブウィンドウに分割し、各サブウィンドウを個別にカウントすることができます。同時に、サブウィンドウのサイズ分の時間が経過するたびに、サブウィンドウが右にスライドします。これがスライディングウィンドウアルゴリズムの考え方です。

​​

上図に示すように、1 分間の時間ウィンドウは 6 つのサブウィンドウに分割されます。各サブウィンドウは独立したカウンターを保持し、10 秒以内の訪問回数をカウントします。 10 秒ごとに、時間ウィンドウは 1 グリッド右にスライドします。

単純なウィンドウ内のクリティカルジャンプの例に戻り、スライディングウィンドウが上記の図と組み合わせてクリティカルな突然変異をどのように排除するかを見てみましょう。 0:50 から 1:00 (灰色のグリッドに対応) の間に 100 件のリクエストが届いた場合、1:00 から 1:10 までの次の 100 件のリクエストは黄色のグリッドに分類されます。アルゴリズムは 6 つのサブウィンドウへの訪問の合計数をカウントするため、この時点で合計が設定されたしきい値の 100 を超え、次の 100 件のリクエストは拒否されます。

コード実装（Sentinelを参照）

Sentinel は、軽量で高性能なスライディング ウィンドウ フロー制御アルゴリズムの実装を提供します。コードを読むときは、次のクラスに注目してください。

1) 関数スロット StatisticSlot は、RT、QPS など、さまざまな次元のランタイム インジケーター監視情報を記録およびカウントする役割を担います。

Sentinel は内部的にスロット チェーン責任チェーン設計パターンを使用します。各機能スロットには異なる機能 (電流制限、劣化、システム保護) があり、ProcessorSlotChain を通じて直列に接続されます。

公式Wikiを参照してください: https://github.com/alibaba/Sentinel/wiki/Sentinelの主な作業プロセス

2) StatisticSlot は、StatisticNode#addPassRequest を使用して、秒と分のディメンションを含む許可されたリクエストの数を記録します。

3) 特定のレコードは Metric インターフェースを使用し、対応する実装クラスは ArrayMetric です。その背後にある実際のスライディング ウィンドウ データ構造は LeapArray です。

4) LeapArray は、スライディング ウィンドウで使用される主要なプロパティと構造を内部的に管理します。これには以下が含まれます。

a) 合計ウィンドウサイズ intervalInMs、スライディングサブウィンドウサイズ windowLengthInMs、サンプル数 sampleCount:

サンプル数 = 間隔（ミリ秒） / ウィンドウの長さ（ミリ秒）

現在の実装ではデフォルトで 2 に設定されており、合計ウィンドウ サイズのデフォルトは 1 秒です。つまり、デフォルトのスライディング ウィンドウ サイズは 500 ミリ秒です。サンプル数を調整することで統計の精度を調整できます。

b) スライディング ウィンドウの配列。配列内の各要素は WindowWrap によって表され、次のものが含まれます。

• windowStart: スライディング ウィンドウの開始時刻。
• windowLength: スライディング ウィンドウの長さ。
• 値: スライディング ウィンドウによって記録されたコンテンツ。ジェネリック型で表されます。キー タイプは MetricBucket で、これには、渡されたリクエストの数、ブロックされたリクエストの数、リクエスト例外の数など、さまざまな種類のデータを記録するための LongAdder のセットが含まれています。

簡単に言えば、記録要求のロジックは、現在の時刻に基づいて、それが属するスライディング ウィンドウを取得し、ウィンドウの統計値に 1 を加算することです。しかし実際には、現在の時間ウィンドウを取得する手順には多くの詳細が隠されています。詳細な実装については、LeapArray#currentWindow を参照してください。ソースコード内のコメントは非常に詳細なので、ここでは詳細には触れません。

上記のプロセスを説明するために他の学生が描いた絵がこちらです。

​​

上記のプロセスはバージョン 3.9.21 のソース コードに基づいています。以前のバージョンの Sentinel では内部実装が異なり、SentinelRollingNumber と呼ばれるデータ構造を使用しますが、原理は似ています。

精度の問題

ここで、次の質問について考えてみましょう。スライディング ウィンドウ アルゴリズムは、特定の時間ウィンドウ T 内の訪問回数が N 以下になるように正確に制御できますか?

答えはノーです。 1 分間を 10 秒のサブウィンドウ 6 つに分割する例を見てみましょう。リクエスト レートが現在 20 回/秒で、0:05 に開始すると仮定すると、0:05 から 0:10 までの期間に 100 件のリクエストが許可され、後続のリクエストは 1:00 にウィンドウがスライドするまで調整され、1:00 から 1:05 の間にさらに 100 件のリクエストが許可されます。 0:05～1:05 を 1 分間の時間枠とみなすと、この時間枠内の実際のリクエスト数は 200 となり、指定されたしきい値 100 を超えます。

より高い精度が必要な場合、理論的にはスライディング ウィンドウを小さな部分に分割するだけで済みます。たとえば、Sentinel では、単位時間あたりのサンプル数の sampleCount 値を変更することで精度を設定できます。この値は通常、精度とメモリ消費のバランスをとるためにビジネス ニーズに応じて決定されます。

滑らかさの問題

スライディング ウィンドウ アルゴリズムを使用してトラフィックを制限すると、次のようなトラフィック曲線がよく見られます。

​​

ウィンドウの開始直後に突然大量のトラフィックが発生すると、現在の制限しきい値が直接満たされ、残りのウィンドウ内のすべてのリクエストが通過できなくなります。時間ウィンドウの単位が比較的大きい場合（たとえば、フロー制御が分単位で実行される場合）、この問題の影響は比較的大きくなります。実際のアプリケーションでは、必要なフロー制限効果は、フローを一度にすべて遮断することではなく、フローがスムーズにシステムに入ることを可能にすることであることが多いです。

3 漏れやすいバケツ

スライディング ウィンドウでは、滑らかさの問題をうまく解決できません。スムーズさに対する要求を振り返ると、トラフィックが一定範囲を超えたときに、トラフィックを一斉に遮断するのではなく、システムが耐えられる一定の速度内でトラフィックを制御することを望んでいます。平均アクセス レートが v であると仮定すると、実行する必要があるフロー制御は、実際にはフロー レート制御、つまり平均アクセス レート v ≤ N / T を制御することです。

リーキー バケット アルゴリズムは、トラフィック シェーピングを実装するためにネットワーク通信でよく使用されます。リーキーバケットアルゴリズムの考え方は、流量に基づいて制御することです。学校でよくやった、プールから水を汲み上げて水を満たすという応用問題を想像してください。プールをバケツ（底に穴が開いていて、水を注ぐとすぐに水が漏れ始めるタイプのもの）に置き換えます。このリクエストをバケツに水を注ぐことと考えてください。バケツの底から漏れる水は、サーバーで処理されるためにバッファから出るリクエストを表し、バケツの口から溢れる水は破棄されるリクエストを表します。概念的な類推:

• 許可されるリクエストの最大数 N: バケットサイズ
• 時間窓サイズT: バケツ一杯の水が漏れ出すのにかかる時間
• 最大アクセス速度V：バケツの水が漏れる速度、つまりN/T
• リクエストが調整されます。バケツの水が漏れるよりも速く満たされ、最終的にバケツが溢れてしまいます。

最初はバケツが空で、訪れるたびに 1 単位量の水がバケツに注入されると仮定します。そして、N/T 以下の速度でバケツに水を注入すると、バケツ内の水が溢れることはありません。逆に、実際の水充填率が水漏れ率を超えると、バケツの中に水がどんどん溜まり、ついには溢れてしまいます。同時に、漏れ率は常に N/T 以内に制御され、スムーズな流れを実現します。

リーキー バケット アルゴリズムのアクセス レート曲線は次のとおりです。

​​

添付されているのは、インターネット上でよく見られるリーキー バケット アルゴリズムの元の画像です。

​​

LeakyBucketThrottler のコード実装

 /**
 * 現在のバケツに残っている水の量
 */
 プライベートロングレフト;
 /**
 * 最後に成功した注水時のタイムスタンプ
 */
 プライベート long lastInjectTime = System.currentTimeMillis();
 /**
 * バケット容量
 */
 プライベートロングキャパシティ。
 /**
 * バケツの水が排出されるまでの時間
 */
 プライベートな長い期間;
 /**
 * バケツが漏れる速度、つまり容量/持続時間
 */
 プライベートダブルベロシティ;

 パブリックブール型tryAcquire(文字列キー) {
 現在の長さ = System.currentTimeMillis();
 // 現在の残水量 = 以前の残水量 - 過去の期間に失われた水の量
 // 過去の期間に漏水した水の量 = (現在の時間 - 最後の注水時間) * 漏水率
 // 現在の時間が前回の給水時間に比べて長すぎる場合（水が追加されていない場合）、バケツ内の残りの水は 0 になります（漏れています）
 左 = Math.max(0, 左 - (long)((now - lastInjectTime) * 速度));
 // 現在の水量に 1 単位の水を追加します。オーバーフローが発生しない限り、アクセスは可能であることを意味します。
 （左+ 1 <= 容量）の場合{
 lastInjectTime = 今;
 左++;
 true を返します。
 } それ以外 {
 false を返します。
 }
 }

漏れやすいバケツ問題

漏れやすいバケツの利点は、トラフィックをスムーズにできることです。トラフィックが均一でない場合、スライディング ウィンドウ アルゴリズムと同様に、リーキー バケット アルゴリズムでは、真に正確な制御を実現できません。極端な場合、リーキー バケットは、時間枠 T 内でしきい値 N の 2 倍に相当するトラフィックも許可します。

訪問回数がウィンドウサイズNよりはるかに多い場合、ウィンドウの開始時の0の時点で訪問回数が殺到し（0~T）、tの時点で漏れやすいバケツがいっぱいになる（0≈t

バケット サイズを制限することでアクセス量を N 以内に制御できますが、その副作用として、制限に達する前にトラフィックが禁止されます。

もう 1 つの暗黙の制約は、漏れバケツの漏れ速度が整数値 (つまり、容量 N が時間ウィンドウ サイズ T を割り切れる値) である必要があることです。そうでない場合、残りの水量の計算でエラーが発生します。

4 トークン バケット

漏れやすいバケツモデルでは、リクエストが来るとバケツに水が注がれます。状況を逆転させて要求を解除すると、バケツから水を汲むことになります。同様に、水注入をシステムが耐えられる流量を補充するものと見なすと、リーキーバケツモデルはトークンバケツモデルになります。

リーキーバケットを理解した後は、トークンバケットを調べるのは非常に簡単です。トークン バケットの原理についての説明は次のとおりです。

トークン バケット アルゴリズムの原理は、システムが一定速度でトークンを生成し、そのトークンをトークン バケットに入れるというものです。トークン バケットには容量があります。トークン バケットがいっぱいになると、さらにトークンが追加され、余分なトークンは破棄されます。リクエストを処理する場合は、トークン バケットからトークンを取得する必要があります。この時点でトークン バケットにトークンがない場合、要求は拒否されます。

​​

TokenBucketThrottlerのコード実装

トークン バケットとリーキー バケットは本質的に同じであるため、リーキー バケットのコードを少し変更するだけでトークン バケットに変換できます。

現在の長さ = System.currentTimeMillis();
 left = Math.min(容量、left + (long)((now - lastInjectTime) * 速度));
 （左 - 1 > 0）の場合{
 lastInjectTime = 今;
 左 - ;
 true を返します。
 } それ以外 {
 false を返します。
 }

実稼働環境でトークン バケットを使用する場合は、Guava が提供する RateLimiter の使用を検討できます。その実装はマルチスレッドセーフです。 RateLimiter#acquire を呼び出すときに、残りのトークンが不十分な場合は、使用可能なトークンが十分になるまでスレッドはしばらくブロックされます (直接拒否するのではなく、これはいくつかのシナリオで役立ちます)。デフォルトの SmoothBursty 戦略に加えて、RateLimiter はウォームアップ期間の設定をサポートする SmoothWarmingUp と呼ばれる戦略も提供します。ウォームアップ期間中、RateLimiter はトークンのリリース速度を最大速度までスムーズに増加させます。この設計は、アクセスごとに安定したサービス レートを提供できるのではなく、ウォームアップ時間を必要とするリソース プロバイダーのニーズを満たすことを目的としています (たとえば、キャッシュを定期的に更新する必要があるキャッシュ サービス)。 RateLimiter の欠点の 1 つは、QPS レベルのみをサポートしていることです。

リーキーバケットとトークンバケットの違い

本質的にはこれら 2 つは逆になっているだけですが、実際の使用では、適用可能なシナリオが若干異なります。

1) リーキーバケット: ネットワーク内のレートを制御するために使用されます。このアルゴリズムでは、入力レートは変化する可能性がありますが、出力レートは一定のままです。多くの場合、FIFO キューと組み合わせて使用​​されます。

漏れやすいバケツの穴の大きさが固定されており、水が漏れる速度が一定のままであると想像してください。

2) トークン バケット: トークンは固定レートでバケットに追加され、出力レートはバースト サイズに応じて変化します。

たとえば、システムでは 60 秒以内の最大訪問回数が 60 回に制限されており、コンバージョン率は 1 回/秒です。一定期間訪問者がいない場合は、その時点で漏れやすいバケツは空になります。ここで、一度に 60 件のリクエストが到着すると、トラフィック シェーピング後、リーキー バケットは 1 秒あたり 1 件のリクエストの割合で 60 件のリクエストをダウンストリームにリークし、1 分かかります。これをトークン バケットに置き換えると、トークン バケットから一度に 60 個のトークンが取り出され、ダウンストリームに一気に詰め込まれます。

5 スライドログ

一般に、上記のアルゴリズムは、ほとんどの実用的なアプリケーション シナリオで適切に使用できます。本当に完全に正確な制御 (つまり、特定の時間枠 T 内のリクエスト数が N を超えない) を必要とするシナリオはほとんどありません。正確な制御を行うには、すべてのユーザー要求ログを記録する必要があります。各フロー制御の判断を行う際には、最新の時間ウィンドウ内のログの数を取り出し、それがフロー制御しきい値より大きいかどうかを確認します。これがスライディングログのアルゴリズムの考え方です。

ある時刻 t にリクエストがあったとします。許可されるかどうかを判断するために実際に確認する必要があるのは、過去 t - N 期間内にリリースされたリクエストが N 件以上あるかどうかです。したがって、システムが各リクエストの時間を記録するキュー q を維持している限り、理論的には、t - N からリクエストの数を計算できます。

現在時刻より前の最長時間 T 内のレコードのみを考慮する必要があることを考慮すると、キュー q の長さは動的に変更される可能性があり、キューには最大 N 回のアクセスのみが記録されるため、キューの長さの最大値は N になります。

スライディングログはスライディングウィンドウと非常によく似ています。違いは、スライディング ログはログ レコードの時間に基づいて動的にスライドするのに対し、スライディング ウィンドウはサブウィンドウのサイズに基づいてサブウィンドウの次元でスライドすることです。

擬似コードの実装

アルゴリズムの疑似コードは次のとおりです。

 # 初期化
 カウンター = 0
 q = []

 # リクエスト処理フロー
 # 1. タイムスタンプ >= tT を持つキュー内の最初のリクエスト、つまり、現在の時刻 t で終了する時間ウィンドウ T 内の最も早いリクエストを検索します。
 t = 今
 開始 = findWindowStart(q, t)

 # 2. キューを切り捨て、最新のT時間ウィンドウ内のレコードとカウント値のみを保持します
 q = q[開始, q.長さ - 1]
 カウンター -= 開始

 # 3. 解放するかどうかを決定し、許可されている場合は、この要求をキューqの末尾に追加します。
 カウンタ < しきい値の場合
 プッシュ(q, t)
 カウンター++
 ＃ リリース
 それ以外
 # 現在の制限

findWindowStart の実装は、キュー q で使用されるデータ構造によって異なります。単純な配列を例にとると、バイナリ検索やその他の方法を使用できます。他のデータ構造を使用してこれを実装する方法についても後ほど説明します。

配列を使用して実装する場合、キューを切り捨てる方法が問題になる可能性があります。実現可能なアイデアとしては、配列内の最も近い有効なレコード インデックスと最も古い有効なレコード インデックスをそれぞれポイントするヘッド ポインターとテール ポインターのセットを使用することです。 findWindowStart の実装は、末尾と先頭の間の対応する要素を検索するようになります。

複雑さの問題

アルゴリズムは精度の問題を解決しますが、コストがかかることは明らかです。

まず、最大長 N のキューを保存する必要があります。これは、空間計算量が O(N) に達することを意味します。異なるキーに対してフロー制御を行う場合、より多くのスペースが必要になります。もちろん、非アクティブなキーのキューを再利用してメモリ消費を削減することもできます。

次に、キュー内の時間ウィンドウを決定する必要があります。つまり、findWindowStart メソッドを使用して、現在のタイムスタンプ t - N より前ではないリクエスト レコードを検索する必要があります。バイナリ検索を例にとると、時間の計算量は O(logN) です。

4つの分散フロー制御

実際には、アプリケーション サービスは分散形式で展開されることがよくあります。共有リソース (データベースなど) または依存するダウンストリーム サービスにトラフィック制限がある場合は、分散フロー制御が役立ちます。

フロー制御クォータを各アプリケーション サーバーに均等に分配し、問題を単一マシンのフロー制御に変換することは可能ですが、トラフィックの不均一、マシンのダウンタイム、一時的な容量の拡張または縮小などのシナリオがある場合、このアプローチは効果的ではありません。

分散環境でのフロー制御のコアアルゴリズムの考え方は、実際には単一マシンのフロー制御の考え方と同じです。違いは、グローバル クォータを確保するために同期メカニズムを実装する必要があることです。同期メカニズムは、集中型と分散型の 2 つの方法で実装できます。

1) 集中化: クォータは中央システムによって集中管理され、アプリケーション プロセスは中央システムに申請することでフロー制御クォータを取得します。

• 状態の一貫性は中央システムで維持されるため、実装が簡単です。
• 中央システム ノードが利用できなくなると、フロー制御エラーが発生する可能性があり、追加の保護が必要になります。たとえば、中央ストレージが利用できない場合、集中型フロー制御は単一マシン フロー制御に退化することがよくあります。

2) 分散化: アプリケーションプロセスはフロー制御クォータの状態を独立して保存・維持し、クラスタ内で定期的に非同期通信を実行して一貫した状態を維持します。

• 集中型ソリューションと比較すると、分散型ソリューションは集中型の単一ポイント信頼性の影響を軽減できますが、実装がより複雑になり、状態の一貫性を保証することが困難になります。
• CAP では、分散化は A に傾き、集中化は C に傾きます。

分散型ソリューションは実稼働環境では見られないため、次の記事では集中型フロー制御のアイデアについてのみ説明します。

1 アクセス層の入力フロー制御

アプリケーションアクセスのためのネットワークアーキテクチャでは、アプリケーションサーバーの前に統一された入口として LVS または Nginx のレイヤーが存在することが多く、このレイヤーで入口のフロー制御を行うことができます。これは本質的には単一マシンのフロー制御シナリオです。

Nginx を例にとると、Nginx はフロー制御用の ngx_http_limit_req_module モジュールを提供し、その基礎となるアルゴリズムはリーキー バケット アルゴリズムです。

Nginx フロー制御構成の例は次のとおりです。これは、各 IP アドレスが /login/ インターフェースを 1 秒あたり 10 回しか要求できないことを意味します。

 limit_req_zone $binary_remote_addr ゾーン=mylimit:10m レート=10r/s;

 サーバー{
 場所 /ログイン/ {
 制限要求ゾーン=mylimit;

 proxy_pass http://my_upstream;
 }
 }

Nginx のフロー制御命令も、より多くの構成をサポートしています。たとえば、limit_req 命令を構成するときに、burst および nodelay パラメータを追加してある程度のバーストを許可したり、geo 命令と map 命令を組み合わせてブラックリストとホワイトリストのフロー制御を実装したりできます。詳細については、Nginx の公式ドキュメント「NGINX および NGINX Plus を使用したレート制限」(https://www.nginx.com/blog/rate-limiting-nginx/) を参照してください。

組み込みモジュールがニーズを満たせない場合は、カスタム Lua モジュールを使用します。 OpenResty が提供する Lua トラフィック制限モジュール lua-resty-limit-traffic を参照してください。

2 トークンサーバフロー制御

ここでは、Sentinel の TokenServer の名前を借用しています。 Sentinel クラスター フロー制御の概要については、公式ドキュメント「Sentinel Cluster Flow Control (https://github.com/alibaba/Sentinel/wiki/小组流量控)」を参照してください。

このタイプのフロー制御の考え方は、総呼び出し量のカウント、単一の要求が許可されるかどうかの決定など、フロー制御クォータを具体的に管理する TokenServer を見つけることです。アプリケーション サーバーは、クォータを取得するためにクライアントとして TokenServer と通信します。フロー制御ロジックは TokenServer 内で均一に処理されるため、スタンドアロン フロー制御で説明したアルゴリズムも適用できます。

このタイプのフロー制御は、TokenServer のパフォーマンスと可用性に大きく依存すると考えるのが自然です。

パフォーマンスの面では、単一ポイントの TokenServer は簡単にボトルネックになる可能性があります。 Sentinel のソース コードを見ると、ネットワーク通信には Netty が使用され、データ パケットはカスタム形式を使用しています。それ以外のパフォーマンス最適化はあまり見つかりません。

可用性に関しては、Sentinel の公式ドキュメントに記載されているように、実稼働環境で TokenServer クラスターの現在の制限を使用する場合は、次の問題を解決する必要があります。

• トークン サーバーの自動管理とスケジュール (トークン サーバーの割り当て/選択)
• トークン サーバーは可用性が高く、サーバーが利用できない場合は他のマシンに自動的にフェールオーバーします。

現在、Sentinel の TokenServer はこれらの機能をデフォルトで実装していないため、実装するにはカスタマイズするか、他のシステムに追加する必要があります。たとえば、クラスターの選択には分散一貫性プロトコルが使用され、ステータスを監視するにはモニターのグループが使用されます。実装コストはまだかなり高いです。

3 ストレージフロー制御

ストレージベースのフロー制御の考え方は、ストレージ システムを使用して、フロー制御のカウント値などの統計情報を保存することです。アプリケーションはストレージから統計情報を取得し、最新のリクエスト情報をストレージに書き込みます。ストレージ システムには、既製の MySQL データベースや Redis キャッシュなどが使用できます。一般的に、パフォーマンスの観点からキャッシュの方が人気があります。ここでは、Tair と Redis を例として選択します。

タイヤフロー制御

比較的シンプルで、コードに直接実装できます。

パブリックブール型tryAcquire(文字列キー) {
 // 数秒でTairのキーを構築します
 文字列 wrapKey = wrapKey(key);
 // 各リクエストは +1、初期値は 0、キーの有効期間は 5 秒に設定されます
 結果<Integer> result = tairManager.incr(NAMESPACE, wrapperKey, 1, 0, 5);
 result.isSuccess() && result.getValue() <= しきい値を返します。
 }

 プライベート文字列 wrapKey(文字列キー) {
 長い秒 = System.currentTimeMillis() / 1000L;
 リターンキー + ":" + sec;
 }

ちょっと単純すぎる気がしますか? Tair の高性能のおかげで、この方法は大規模なトラフィック フローを非常にうまくサポートできます。

この Tair フロー制御ソリューションは、実際には単純なウィンドウの考え方を使用しており、各キーは QPS 制御の時間ウィンドウとして 1 秒を使用します (QPM/QPD の原理も同様です)。重要なのは、Tair の API を使用することです。

• 増加
• 結果 incr(int 名前空間、シリアル化可能なキー、int 値、int defaultValue、int expireTime)
• 説明する
• カウントを増やします。注意: incr の前に置かないでください。
• パラメータ
• namespace - 適用時に割り当てられる名前空間、key - 1k を超えないキーのリスト、value - 増加量、defaultValue - incr が初めて呼び出されたときのキー数の初期値。最初に返される値は defaultValue + value です。 expireTime - データの有効期限（秒単位）。相対時間または絶対時間（Unix タイムスタンプ）として設定できます。 expireTime = 0 は、データが期限切れにならないことを示します。 expireTime > 0 は有効期限を設定することを意味します。 expireTime > 現在のタイムスタンプの場合は絶対時間を使用し、それ以外の場合は相対時間を使用します。 expireTime < 0 は有効期限が考慮されないことを意味します。以前に有効期限が設定されている場合は、以前の有効期限が基準として使用されます。そうでない場合は、期限切れにならないものとして扱われます。ただし、現在の MDB では、有効期限が切れないものとして一律に扱われます。
• 戻り値
• 結果オブジェクト。戻り値は負の値になる場合があります。キーが存在しない場合は、最初に defaultValue + 値が返されます。後続の増分はこの値に基づいて値が増加します。

もちろん、このアプローチには欠点もあります。

• 単純なウィンドウの重大な突然変異問題。
• Tair の信頼性の問題には、ダウングレード ソリューションが必要です。前述のように、集中型フロー制御は通常、ダウングレードされたスタンドアロン フロー制御と組み合わせる必要があります。
• クラスター マシン間の時間同期の問題。キーの生成にはクラスター マシンのローカル時間が使用されるため、マシン時間は一貫している必要があります。

たとえば、異なるマシンの時間が 10 ミリ秒異なる場合、時間ウィンドウの間隔ポイントでの統計では比較的大きな誤差が発生します。たとえば、同じ瞬間に、1 台のマシンの時間は 0.990 で、別のマシンの時間は 1.000 です。 2 つの呼び出しが incr の場合、操作されるキーが異なり、当然、精度に影響が出ます。

Redis フロー制御

Redis はさまざまなデータ構造をサポートし、優れたパフォーマンスを発揮します。 「シングルプロセス」モデルは同期制御を容易にし、分散フロー制御ストレージに非常に適しています。

1) シンプルなウィンドウの実装

Redis を使用して単純なウィンドウフロー制御を実装するという考え方は、Tair を使用する場合と同じです。 Redisはまた、カウント用の増分コマンドを提供し、Redisの「単一プロセス」モデルも優れた並行性保護を提供します。公式のRedisドキュメントでは、increを使用してレートリミッターを実装する方法について説明します。ここで少し翻訳しました：

• Redis Increキー（https://redis.io/commands/incr）

単純なウィンドウを例にとると、最も単純で最も直接的な実装は次のとおりです。

関数limit_api_call（ip）
 ts = current_unix_time（）
 keyname = ip+"："+ts
 current = get（keyname）
 現在の場合！= nullとcurrent> 10の場合
 エラー「1秒あたりのリクエストが多すぎる」
 それ以外
 マルチ
 Incr（keyname、1）
 期限切れ（keyname、10）
 exec
 perform_api_call（）
 終わり

実装は、上記のTairに似ています。また、各キーの数秒でカウンターを維持します。違いは、RedisがAtomic Incr +の有効期限を切る命令を提供しないため、キーの有効期間を設定するには、増分後に再度呼び出される必要があることです。同時に、取引性を確保するために、外層にマルチとexecで包まれています。

毎回有効期限を取得したくない場合は、2番目の方法を考慮することができます。

 function limit_api_call（ip）：
 current = get（ip）
 現在の場合！= nullとcurrent> 10の場合
 エラー「1秒あたりのリクエストが多すぎる」
 それ以外
 value = inch（ip）
 値== 1の場合
 期限切れ（IP、1）
 終わり
 perform_api_call（）
 終わり

カウンターの有効期間は最初の増分で1秒に設定されるため、キーの追加処理は必要ありません。

ただし、このアプローチには隠された人種状態があることに注意する必要があります。アプリケーションのクラッシュやその他の理由により、クライアントが初めて電話をかけた後に呼び出さない場合、カウンターは残ります。

方法2のこの問題については、LUAスクリプトを使用して解決できます。

ローカル電流
 current = redis.call（ "incr"、keys [1]）
 tonumber（current）== 1の場合
 redis.call（ "expire"、keys [1]、1）
 終わり

3番目の方法は、Redisリスト構造を使用することです。もう少し複雑ですが、すべてのリクエストを記録できます。

関数limit_api_call（ip）
 current = llen（ip）
 現在の場合は10の場合
 エラー「1秒あたりのリクエストが多すぎる」
 それ以外
 存在する場合（ip）== false＃1
 マルチ
 rpush（ip、ip）
 期限切れ（IP、1）
 exec
 それ以外
 rpushx（ip、ip）
 終わり
 perform_api_call（）
 終わり

ここには暗黙の人種状態もあります。存在する判断ライン（位置＃1）を実行すると、両方のクライアントの存在コマンドがfalseを返すことがあるため、マルチ/execブロックのコマンドが2回実行されます。ただし、この状況はめったに発生せず、カウンターの精度に影響しません。

上記の方法をさらに最適化できます。 Incrやrpushなどのコマンドは、操作後にカウンター値を返すため、セットトゥエットメソッドを使用してカウンター値を取得できます。

単純なウィンドウをスライドウィンドウに変換するというアイデアは似ています。単一のキーはハッシュ構造に置き換えられます。ハッシュは、各サブウィンドウのカウント値を保存します。カウントするとき、同じハッシュ内のすべてのサブウィンドウのカウント値が一緒に加えられます。

2）トークンバケット/漏れやすいバケットの実装

また、Redisを使用してトークンバケットまたは漏れやすいバケットを実装することも非常に簡単です。トークンバケットを例として、実装の観点から、2つのキーを使用して、利用可能なトークンの数と各ユーザーの最後の要求時間を保存することができます。もう1つのより良い方法は、Redisのハッシュデータ構造を使用することです。

次の図は、User_1という名前のユーザーによって現在Redisで保存されているフロー制御割り当てデータを示しています。現在、トークンバケットに2つのトークンが残っており、最新のアクセスのタイムスタンプは1490868000です。

​​

新しいリクエストが受信されると、Redisクライアントは単一マシンフロー制御アルゴリズムで見たのと同じ操作を実行します。最初に、対応するハッシュ（hgetall）から現在のクォータデータを取得し、現在のタイムスタンプ、最後のリクエストのタイムスタンプ、およびトークン充填速度に基づいて埋めるトークンの数を計算します。次に、それをリリースするかどうかを決定し、新しいタイムスタンプとトークン番号（HMSET）を更新します。

例は次のとおりです。

同様に、より高い精度が必要な場合は、クライアント操作の並行性制御をここで実行する必要があります。

同期制御が実行されない場合に発生する可能性のある問題の例：バケツには1つのトークンのみがあり、2つのクライアントが同時にリクエストすると同時性の競合が発生し、両方のリクエストがリリースされます。

​​

LUAコードの例は次のとおりです。

ローカルトークン_key = keys [1]
 ローカルタイムスタンプ=キー[2]

 ローカルレート = tonumber(ARGV[1])
 ローカル容量 = tonumber(ARGV[2])
 ローカルnow = tonumber(ARGV[3])
 ローカル要求 = tonumber(ARGV[4])

 ローカルfill_time = 容量/レート
 ローカル ttl = math.floor(fill_time*2)

 local last_tokens = tonumber（redis.call（ "get"、tokens_key）））
 last_tokens == nilの場合
 last_tokens = 容量
 終わり

 local last_refreshed = tonumber（redis.call（ "get"、timestamp_key）））
 last_refreshed == nilの場合
 最終更新日 = 0
 終わり

 ローカルdelta = math.max（0、now-last_refreshed）
 local fell_tokens = math.min（容量、last_tokens+（delta*reat））
 ローカルで許可 = filled_tokens >= 要求
 ローカル new_tokens = filled_tokens
 許可されれば
 new_tokens = filled_tokens - リクエスト済み
 終わり

 redis.call（ "setex"、tokens_key、ttl、new_tokens）
 redis.call（ "setex"、timestamp_key、ttl、今）

 return {許可、new_tokens}

3）スライドログの実装

Redisのソートされたセット構造のおかげで、スライドログを実装するのは非常に簡単です。プロセスはおおよそ次のようになります。

a）各ユーザーには、リクエストログを記録するための対応するソートセットがあります。

各要素のキーと値は同じ、つまりリクエストのタイムスタンプです。

ソートされたセットは、タイムウィンドウのサイズに応じて有効期間を設定できます。たとえば、時間ウィンドウが1の場合、有効期限は5秒に設定されます。これにより、リクエストボリュームが大きくないときにRedisサーバーメモリを保存できます。

b）新しいユーザー要求が受信されると、ソートされたセットの有効期限切れの要素がZremrangeByscoreコマンドを介して最初に削除されます。ここで期限切れの要素は次のとおりです。

リクエストタイムスタンプt <現在のタイムスタンプ今すぐ - 時間ウィンドウサイズ間隔

c）ZADDを使用して、現在のリクエストをセットに追加します。

d）Zcountを使用して、現在の残りのセットサイズを取得し、フロー制御が必要かどうかを判断します。

 function limit_api_call（ip）：
 current = get（ip）
 現在の場合！= nullとcurrent> 10の場合
 エラー「1秒あたりのリクエストが多すぎる」
 それ以外
 value = inch（ip）
 値== 1の場合
 期限切れ（IP、1）
 終わり
 perform_api_call（）
 終わり

別のJS実装コード例：https：//github.com/peterkhayes/rolling-late-limiter/blob/master/index.js

スライドログアルゴリズムのスペースの複雑さは他のアルゴリズムのスペースの複雑さよりも高いため、スライドログアルゴリズムを使用する場合、Redisメモリの使用を監視することに注意する必要があります。

4）並行性制御

上記のアルゴリズムはすべて、並行性制御を実行しないことによって引き起こされる可能性のある人種条件に言及していますが、追加の並行性制御は必然的にパフォーマンスの劣化につながり、通常、精度とパフォーマンスの間にトレードオフを行う必要があります。 Redisフロー制御には、いくつかの一般的なタイプの並行性制御があります。

• Redis Transactions Multi/Execを使用します。
• Redlock（https://redis.io/topics/distlock）などの分散ロックを使用すると、各クライアントは操作前に対応するキーの分散ロックを取得する必要があります。
• Lua スクリプト。

使用する方法を決定する最良の方法は、パフォーマンステストによるものです。

4拡張に関するいくつかの考え

分散フロー制御は、ネットワーク通信やロック同期などのオーバーヘッドをもたらし、パフォーマンスに特定の影響を与えます。同時に、分散環境の信頼性もより多くの課題をもたらします。高性能で高度な高度な分散フロー制御システムを設計するにはどうすればよいですか？これは、システム全体のすべての側面を含む大きなトピックかもしれません。

私の考えのいくつかを共有してください、歓迎してください：

1）実際の要求によると、異なる層でのマルチレベルのフロー制御を合理的に一致させ、外側の層でトラフィックをブロックしようとすることをお勧めします。たとえば、一般的なインターフェイスレイヤーnginxフロー制御 +アプリケーションレイヤーフロー制御。

2）適切なキャッシュシステムを選択して、フロー制御の動的なデータを保存します。フロー制御は、一般に統一された技術アーキテクチャに従います。

3）構成センター（ダイヤモンドなど）にフロー制御の静的構成を配置します。

4）設計するときは、分散フロー制御が利用できない状況を検討してください（たとえば、キャッシュが失敗します）。必要に応じて、シングルマシンフロー制御に切り替えます。センチネルは成熟して信頼できます。

5）多くの場合、特定のバーストが一般的に許可されるため、精度要件はそれほど高くありません。現時点では、いくつかのパフォーマンスの最適化を行うことができます。パフォーマンスにおける最大のボトルネックは、すべてのリクエストがキャッシュにアクセスすることです。設計時に妥協方法を使用しました。

• 利用可能なクォータの一部は、特定の割合（たとえば、50％）でクラスター内のマシンに事前に割り当てられます。一般に、それは均等に分布しています。各マシンの交通重量が事前に既知である場合、重み付けすることができます。各マシンの消費クォータレートは異なり、中央にマシンダウンタイムがあり、拡張容量と拡張能力がある可能性があります。したがって、前配置前の比率が大きすぎてはなりません。もちろん、小さすぎてはいけません。
• 各マシンが使い果たされると、中央システムに割り当てを要求します。ここでの最適化ポイントは、各マシンが独自のクォータ消費のレートを記録し（耐えるトラフィックレートに相当）、レートサイズに応じて異なるサイズのクォータを適用することです。消費率が大きい場合は、一度にさらに多くが適用されます。
• 利用可能なクォータ全体が特定の割合（たとえば、10％）よりも少ない場合、一度に適用できるクォータの数が限られている場合、発行されたクォータのサイズは残りのウィンドウのサイズに基づいて計算され、各発行の量は残りのクォータ（たとえば、50％）を超えないため、残りのトラフィックは平滑化することができます。

5. 結論

分散フロー制御アルゴリズムは、実際にはスタンドアロンフロー制御の拡張であり、アルゴリズムは本質的に同じです。ここでは、私の個人的な理解に基づいて、上記のフロー制御アルゴリズムの複雑さと適用可能なシナリオが要約されています。

​​