インタビュー必読: 4 つの典型的な電流制限アルゴリズムの説明

[[402482]]

最近、当社の業務システムは、トークンバケットアルゴリズムに基づいて実装された Guava の RateLimiter 電流制限コンポーネントを導入しました。トークンバケットは非常に古典的な電流制限アルゴリズムです。この記事では、いくつかの古典的な電流制限アルゴリズムについて説明します。

電流制限とは何ですか?

Wikipedia のコンセプトは次のとおりです。

コンピュータネットワークでは、レート制限は、送信されるリクエストのレートを制御するために使用されます。
ネットワークインターフェースコントローラによって受信される。DoS攻撃を防ぐために使用できる。
ウェブスクレイピングを制限する

簡単に訳すと、コンピュータネットワークでは、電流制限はネットワークインターフェイスが要求を送受信する速度を制御することです。これにより、DoS 攻撃を防ぎ、Web クローラーを制限できます。

電流制限、フロー制御とも呼ばれます。これは、システムが高い同時実行性や大量のトラフィック要求に直面した場合、システムの安定性を確保するために、システムへの新しい要求のアクセスを制限することを意味します。現在の制限により、一部のユーザーリクエストが予定より遅れて処理されたり拒否されたりするため、ユーザーエクスペリエンスに影響します。したがって、通常はシステムの安定性とユーザーエクスペリエンスのバランスを取る必要があります。実際の例を見てみましょう。

★人気の観光スポットでは、1日あたりの観光客の入場人数に制限を設けているところもあります。チケットは1日あたり5,000枚など、一定枚数のみ販売されます。メーデーや国慶節の連休中に遅く行くと、その日のチケットが売り切れていて、入場して遊ぶことができない場合があります。たとえ入場できたとしても、行列が長すぎて自分の命が危ぶまれるほどです。 ”

一般的な電流制限アルゴリズム

固定ウィンドウ電流制限アルゴリズム

まず、カウンターを維持し、単位時間をウィンドウとして扱います。カウンターは、このウィンドウで受信されたリクエストの数を記録します。

回数が電流制限しきい値より少ない場合、アクセスが許可され、カウンターが 1 増加します。
回数が現在の制限しきい値を超えると、アクセスは拒否されます。
現在の時間枠が経過すると、カウンターはクリアされます。

単位時間が 1 秒、電流制限しきい値が 3 であると仮定します。 1 秒の単位時間内の各リクエストごとに、カウンターは 1 ずつ増加します。カウンターの累積回数が現在の制限しきい値の 3 を超えると、後続のすべてのリクエストは拒否されます。 1 秒が経過すると、カウンターは 0 にクリアされ、再びカウントを開始します。以下のように表示されます。

疑似コードは次のとおりです。

 /**
  * ウィンドウタイムアルゴリズムを修正
  * @戻る 
  */
 ブール型fixedWindowsTryAcquire() {
     long currentTime = System.currentTimeMillis(); //現在のシステム時刻を取得します
     if (currentTime - lastRequestTime > windowUnit) { // 時間枠内かどうかをチェックする
         counter = 0; // カウンターを0にクリアする
         lastRequestTime = currentTime; //新しい時間ウィンドウを開く
     }
     if (counter < しきい値) { // しきい値未満
         counter++; //カウンタに1を加算
戻る 真実;
     } 
 
戻る 間違い;
 }

しかし、このアルゴリズムには明らかな重大な問題があります。現在の制限しきい値が 5 リクエストで、単位時間ウィンドウが 1 秒であると仮定すると、単位時間の最初の 0.8 ～ 1 秒と 1 ～ 1.2 秒にそれぞれ 5 つの同時リクエストを行うとします。いずれも閾値を超えていないものの、0.8～1.2秒で計算すると同時接続数が10にも達し、単位時間1秒あたり5回以下の閾値の定義を超えてしまいます。

スライディングウィンドウ電流制限アルゴリズム

スライディングウィンドウ電流制限は、固定ウィンドウ臨界値の問題を解決します。単位時間を n 個の小期間に分割し、各小期間におけるインターフェースアクセス数を記録し、時間スライドに基づいて期限切れの小期間を削除します。

スライディングウィンドウアルゴリズムを図で説明すると次のようになります。

単位時間が依然として 1 秒であると仮定すると、スライディングウィンドウアルゴリズムはそれを 5 つの小さな期間に分割します。つまり、スライディングウィンドウ (単位時間) は 5 つの小さなグリッドに分割されます。各グリッドは 0.2 秒を表します。 0.2 秒ごとに、時間ウィンドウは 1 グリッド右にスライドします。そして、それぞれの小周期には独立したカウンターがあり、リクエストが 0.83 秒で到着すると、0.8 ～ 1.0 秒に対応するカウンターが 1 増加します。

スライディングウィンドウが重大な問題をどのように解決するかを見てみましょう。

現在の 1 秒以内の制限しきい値が依然として 5 件のリクエストであり、5 件のリクエストが 0.8 ～ 1.0 秒以内 (たとえば 0.9 秒) に発生し、黄色のグリッドに該当すると仮定します。 1.0 秒後、さらに 5 件のリクエストが届き、紫色のボックスに入ります。固定ウィンドウアルゴリズムであれば制限はありませんが、スライディングウィンドウであれば、小さなサイクルごとに 1 つの小さなグリッドを右に移動します。 1.0秒後、右に1つの小さなグリッドに移動します。現在の単位時間は0.2〜1.2秒です。このエリアのリクエストは5の制限を超えており、現在の制限がトリガーされています。実際、紫色のグリッド内のすべてのリクエストは拒否されています。

ヒント: スライディングウィンドウを分割するグリッド期間が多いほど、スライディングウィンドウのスクロールがスムーズになり、電流制限の統計がより正確になります。

スライディングウィンドウアルゴリズムの疑似コードは次のとおりです。

 /**
    * 単位時間ごとに分割された小さなサイクル（単位時間は1分、10秒は小さなグリッドウィンドウ、合計6つのグリッド）
    */
   プライベートint SUB_CYCLE = 10; 
 
   /**
    * 1分あたりのリクエスト数を制限する
    */
   プライベートintしきい値PerMin = 100; 
 
   /**
    * カウンタ、kは現在のウィンドウの開始時間値（秒）、値は現在のウィンドウのカウントです
    */
   プライベート最終 TreeMap<Long, Integer > counters = new TreeMap<>(); 
 
  /**
    * スライディングウィンドウ時間アルゴリズムの実装
    */
   ブール型スライディングウィンドウトライ取得() {
       long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //現在の時刻の小サイクルウィンドウを取得します
int currentWindowNum = countCurrentWindow(currentWindowTime); //現在のウィンドウのリクエストの総数
 
       //閾値電流制限を超える
       現在のウィンドウ数 >= しきい値あたりの最小値) {
戻る 間違い;
       } 
 
       //カウンター+1
       counters.get(現在のウィンドウ時間)++;
戻る 真実;
   } 
 
  /**
   * 現在のウィンドウ内のリクエストの数をカウントします
   */
   プライベートint countCurrentWindow(long currentWindowTime) {
       //ウィンドウの開始位置を計算する
       long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
整数 カウント= 0; 
 
       //保存されたカウンターを走査する
       イテレータ<Map.Entry<Long, Integer >> iterator = counters.entrySet().iterator();
       (イテレータ.hasNext()) の間 {
           Map.Entry<Long, Integer > entry = iterator.next ( );
           // 無効または期限切れのサブウィンドウカウンタを削除します
           エントリ.getKey() が開始時刻より小さい場合
               イテレータを削除します。
           }それ以外{
               //現在のウィンドウ内のすべてのカウンターの合計を累積します
カウント=カウント+ entry.getValue();
           }
       }
戻る カウント;
   }

スライディングウィンドウアルゴリズムは固定ウィンドウの重大な問題を解決しますが、現在の制限に達すると、要求は直接かつ激しく拒否されます。この方法では、いくつかのリクエストが失われることになり、実際には製品にとってあまり好ましくありません。

リーキーバケットアルゴリズム

リーキーバケットアルゴリズムは、電流制限に直面したときにより柔軟であり、直接的で失礼な拒否はありません。

その原理は非常に単純で、水の注入と漏水のプロセスと考えることができます。漏れやすいバケツには水が任意の速度で流れ込み、水は固定速度で流れ出ます。水がバケツの容量を超えると、あふれて廃棄されます。バケット容量が一定なので、全体のレートが保証されます。

流入する水滴はシステムへのアクセス要求とみなすことができ、流入率は不確実です。
バケットの容量は通常、システムが処理できるリクエストの数を示します。
バケットがいっぱいになると、フロー制限しきい値に達し、ドロップレットは破棄されます (要求は拒否されます)。
流出する液滴は継続的にフィルタリングされ、対応するサービスは一定の速度で要求を処理します。

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

 /**
    * 1秒あたりの処理回数（水出力速度）
    */
   プライベートロングレート; 
 
   /**
    * 現在の残水量
    */
   プライベートロングカレントウォーター; 
 
   /**
    * 最終更新時間
    */
   プライベート長いリフレッシュタイム; 
 
   /**
    * バレル容量
    */
   プライベートロングキャパシティ。 
 
   /**
    * リーキーバケットアルゴリズム
    * @戻る 
    */
   ブール型リーキーバケット制限取得() {
       long currentTime = System.currentTimeMillis(); //現在のシステム時刻を取得します
       long outWater = (currentTime - refreshTime) / 1000 * rate; // 水の流出量 = (現在時刻 - 前回の更新時刻) * 水の流出量
       long currentWater = Math.max (0, currentWater - outWater); // 現在の水量 = バケツ内の以前の水量 - 流出する水量
       refreshTime = currentTime; // 更新時間
 
       // 現在の残水量がバケツの容量より少ない場合は、水を放出するよう要求します
       現在の水量 < 容量の場合 {
           現在の水++;
戻る 真実;
       } 
        
       // 現在の残水量はバケツの容量以上であり、流量が制限されています
戻る 間違い;
   }

通常のトラフィックの間、システムは一定の速度でリクエストを処理します。これが私たちの望む動作です。ただし、トラフィックのバーストが発生した場合、リーキーバケットアルゴリズムは依然として従来の方法でリクエストを処理しますが、これは望ましいことではありません。トラフィックが急増した場合、システムがリクエストをできるだけ早く処理してユーザーエクスペリエンスを向上できることを期待しています。

トークンバケットアルゴリズム

バーストトラフィックが発生した場合は、トークンバケットアルゴリズムを使用してフローを制限できます。

トークンバケットアルゴリズムの原理:

現在の制限に基づいて一定の速度でトークンをトークンバケットに入れるトークン管理者がいます。
トークンの数がいっぱいになり、トークンバケットの容量制限を超えると、トークンは破棄されます。
システムがユーザー要求を受信すると、まずトークンバケットにアクセスしてトークンを要求します。トークンが取得されると、リクエストのビジネスロジックが処理されます。
トークンを取得できない場合、リクエストは直接拒否されます。

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

 /**
  * 1秒あたりのトランザクション数（投入されたトークンの数）
  */
 プライベート long putTokenRate; 
  
 /**
  * 最終更新時間
  */
 プライベート長いリフレッシュタイム; 
 
 /**
  * トークンバケット容量
  */
 プライベートロングキャパシティ。 
  
 /**
  * 現在のバケット内のトークンの数
  */
 プライベートロングcurrentToken = 0L; 
 
 /**
  * リーキーバケットアルゴリズム
  * @戻る 
  */
 ブール型tokenBucketTryAcquire() { 
 
     long currentTime = System.currentTimeMillis(); //現在のシステム時刻を取得します
     long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成されたトークン = (現在時刻 - 最終更新時刻) * トークンの配置レート
     currentToken = Math.min (capacity, generateToken + currentToken); // 現在のトークン数 = バケット内の以前のトークン数 + 投入されたトークン数
     refreshTime = currentTime; // 更新時間
      
     //バケットにはまだトークンが残っているので、リクエストは正常に処理されます
     (現在のトークン > 0) の場合 {
         currentToken --; //トークン数 - 1  
戻る 真実;
     } 
      
戻る 間違い;
 }