この記事ではSentinelと一般的なフロー制御アルゴリズムを紹介します。

この記事ではSentinelと一般的なフロー制御アルゴリズムを紹介します。

[[401361]]

この記事では主に、カウンター アルゴリズム、リーキー バケット アルゴリズム、トークン バケット アルゴリズムなど、いくつかの一般的な電流制限アルゴリズムについて説明します。次に、Sentinel 1.8.0 についての私の理解に基づいて、Sentinel がソース コード内でフロー制御の判断にこれらのアルゴリズムをどのように使用するかについて説明します。

逆電流制限アルゴリズム

カウンターを直接使用して、1 秒あたりに受信できるリクエストの数を制限できます。たとえば、qps が 1000 に設定されている場合、実装のアイデアは、最初に到着したリクエストからタイミングを開始することです。次の 1 秒間に、到着するリクエストごとにカウントが 1 ずつ増加します。累積数が 1000 に達すると、後続のすべてのリクエストは拒否されます。 1 秒が経過したら、カウントを 0 に戻し、再びカウントを開始します。

利点: シンプルな実装

デメリット: 1 秒のうち最初の 0.5 秒で 1,000 件のリクエストを受信した場合、次の 0.5 秒ではリクエストを拒否することしかできません。この現象を「スパート現象」と呼びます。

実装コードの例:

  1. パブリッククラスCounter{
  2. パブリックlong timeStamp = getNowTime();
  3. 公共 要求カウント = 0;
  4.  public final int limit = 100; // 時間枠内のリクエストの最大数
  5. public final long interval = 1000; // 時間ウィンドウ ms 
  6.  
  7. パブリックブール制限（）{
  8.         長い今 = getNowTime();
  9.         if (現在 <タイムスタンプ+ 間隔) {
  10.             // 時間枠内
  11.             要求カウント++;
  12.             // 現在の時間枠内で制御されるリクエストの最大数を超えているかどうかを判定します
  13. reqCount <= limitを返します。
  14.         }それ以外{
  15. タイムスタンプ= 現在;
  16.             // タイムアウト後にリセット
  17.             要求数 = 1;
  18. 戻る 真実;
  19.         }
  20.     } 
  21.  
  22. パブリックlong getNowTime() {
  23.  System.currentTimeMillis()を返します。
  24.     }
  25.  }

スライディングタイムウィンドウアルゴリズム

スライディング ウィンドウ、ローリング ウィンドウとも呼ばれます。カウンター アルゴリズムの欠点を解決するために、スライディング ウィンドウ アルゴリズムを導入しました。次の図は、スライディング ウィンドウ アルゴリズムを非常にわかりやすく説明しています。

上の図では、赤い四角形全体が時間枠を表しています。この例では、時間枠は 1 分です。次に、時間ウィンドウを分割します。たとえば、図では、スライディング ウィンドウを 6 つのグリッドに分割し、各グリッドは 10 秒を表します。 10 秒ごとに、時間ウィンドウは 1 グリッド右にスライドします。各グリッドには独立したカウンターがあります。例えば、0:35 秒にリクエストが到着すると、0:30 ～ 0:39 に対応するカウンターが 1 増加します。

では、スライディング ウィンドウはどのようにしてこの重大な問題を解決するのでしょうか。上の図からわかるように、0:59 に到着する 100 件のリクエストは灰色のグリッドに分類され、1:00 に到着するリクエストはオレンジ色のグリッドに分類されます。時間が 1:00 になると、ウィンドウは 1 グリッド右に移動します。すると、時間ウィンドウ内のリクエストの合計数は 200 となり、制限の 100 を超えます。したがって、現在の制限がトリガーされたことが検出されます。

ここで、カウンター アルゴリズムをもう一度確認してみましょう。カウンター アルゴリズムは、実際にはスライディング ウィンドウ アルゴリズムであることがわかります。時間ウィンドウをさらに分割しないので、グリッドは 1 つだけになります。

スライディング ウィンドウを分割するグリッドの数が増えるほど、スライディング ウィンドウのスクロールがスムーズになり、電流制限の統計がより正確になることがわかります。

実装コードの例:

  1. パブリッククラスSlideWindow { 
  2.  
  3.     /** キュー ID とキューのマッピング関係。キューは各パスのタイムスタンプを保存するため、プログラム内に複数の電流制限キューが存在する可能性があります */
  4.     プライベート volatile静的Map<String, List<Long>> MAP = new ConcurrentHashMap<>(); 
  5.  
  6.     プライベートスライドウィンドウ() {} 
  7.  
  8. 公共 静的void main(String[] args)はInterruptedExceptionをスローします{
  9.         （真）の間{
  10.             // 10秒間に2回のパスのみ許可されます
  11.             システム.out .println(LocalTime.now().toString() + SlideWindow.isGo( "ListId" , 2, 10000L));
  12.             // 0～10 秒間スリープ
  13.             スレッドをスリープ状態にします(1000 * 新しい Random().nextInt(10));
  14.         }
  15.     } 
  16.  
  17.     /**
  18.      * スライディングタイムウィンドウ電流制限アルゴリズム
  19.      * 指定された時間枠と指定された回数内でアクセスを許可するかどうか
  20.      *
  21.      * @param listId キューID
  22.      * @param count回数制限
  23.      * @param timeWindow 時間ウィンドウのサイズ
  24.      * @return通過を許可するかどうか
  25.      */
  26. 公共 静的同期ブール値 isGo(String listId, int   count 、長い時間ウィンドウ) {
  27.         // 現在の時刻を取得する
  28.         長いnowTime = System.currentTimeMillis();
  29.         //キューIDに応じて、対応する現在の制限キューを取り出し、存在しない場合は作成します
  30.         リスト<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
  31.         // キューがいっぱいでない場合は、キューを通過させ、現在のタイムスタンプをキューの先頭に追加します
  32.         if (リスト.size () <カウント) {
  33.             リストに0、現在時刻を追加します。
  34. 戻る 真実;
  35.         } 
  36.  
  37.         // キューがいっぱいの場合（制限に達した場合）、キューに追加された最も古いタイムスタンプを取得します
  38.         Long farTime = list.get( count - 1 );
  39.         // 現在のタイムスタンプから最も古い追加されたタイムスタンプを減算します
  40.         if (nowTime - farTime <= timeWindow) {
  41.             // 結果がtimeWindow以下の場合、timeWindow内で経過した回数がcountより大きいことを意味します 
  42.             // 通過は許可されません
  43. 戻る 間違い;
  44.         }それ以外{
  45.             // 結果がtimeWindowより大きい場合、timeWindow内で経過した回数がcount以下であることを意味します 
  46.             // 通過を許可し、最初に追加されたタイムスタンプを削除し、現在の時刻をキューの先頭に追加します
  47.             リストを削除します(数- 1 );
  48.             リストに0、現在時刻を追加します。
  49. 戻る 真実;
  50.         }
  51.     } 
  52.  
  53.  }

Sentinel では、時間ウィンドウ アルゴリズムは LeapArray 構造を通じて実装されています。そのコア コードは次のとおりです (時間ウィンドウを取得する方法のみがリストされています)。

  1.  /**
  2.      * 現在の時間枠を取得する
  3.      *
  4.      *指定されたタイムスタンプでバケット項目を取得します。
  5.      *
  6.      * @param timeMillisは有効なタイムスタンプです ミリ秒単位
  7.      * @戻る 指定されたタイムスタンプの現在のバケット項目 有効です。時間の場合はnullです 無効です
  8.      */
  9. パブリックWindowWrap<T>現在のウィンドウ(長いtimeMillis) {
  10.   （時間ミリ秒<0）の場合{
  11. 戻る ヌル;
  12.   } 
  13.  
  14.  int idx = calculateTimeIdx(timeMillis);
  15.   //現在のバケットの開始時間を計算します。
  16.   // ウィンドウの開始時間と各グリッドの開始時間を計算します
  17.   長いwindowStart = calculateWindowStart(timeMillis); 
  18.  
  19.   /*
  20.          *指定された時間にバケットアイテムを取得する 配列から。
  21.          *
  22.          * (1) バケットが存在しない場合は、新しいバケットを作成してCASを更新するだけです 円形配列にします。
  23.          * (2) バケットが最新の状態であれば、バケットを返すだけです。
  24.          * (3) バケットは非推奨なので、現在のバケットをリセットし、すべての非推奨のバケットをクリーンアップします。
  25.          */
  26.   （真）の間{
  27.     WindowWrap<T> 古い = array.get(idx);
  28.     // ペインがない場合は作成します
  29.     (古い == null ) の場合 {
  30.       /*
  31.                  * B0 B1 B2ヌルB4
  32.                  * ||_______|_______|_______|_______|_______||___
  33.                  * 200 400 600 800 1000 1200タイムスタンプ 
  34.                  * ^
  35.                  *時間= 888
  36.                  * バケットは空なので、新しく作成して アップデート 
  37.                  *
  38.                  * 古いバケットが存在しない場合は、 {@code windowStart}に新しいバケットを作成します。
  39.                  *試してみて  CAS操作で循環配列を更新します。1つのスレッドのみが
  40.                  * 成功する 他のスレッドがタイムスライスを譲る間に、更新が行われます。
  41.                  */
  42.       WindowWrap<T> ウィンドウ = 新しい WindowWrap<T>(windowLengthInMs、windowStart、newEmptyBucket(timeMillis));
  43.       （array.compareAndSet（idx、 null 、window）の場合）{
  44.         // 正常に更新されました。作成されたバケットを返します。
  45. 返品期間;
  46.       }それ以外{
  47.         // 競合が失敗した場合、スレッドはタイムスライスを放棄して、バケットが使用可能になるまで待機します。
  48.         スレッド.yield();
  49.       }
  50.       // 現在のペインが存在するので、履歴ペインに戻ります
  51.     }そうでない場合 (windowStart == old.windowStart()) {
  52.       /*
  53.                  * B0 B1 B2 B3 B4
  54.                  * ||_______|_______|_______|_______|_______||___
  55.                  * 200 400 600 800 1000 1200タイムスタンプ 
  56.                  * ^
  57.                  *時間= 888
  58.                  * バケット3の開始時刻: 800なので最新です 
  59.                  *
  60.                  *現在の{@code windowStart}が開始タイムスタンプと等しい場合 古いバケツの、
  61.                  * つまり時間 バケット内にあるため、バケットを直接返します。
  62.                  */
  63. 古いものを返す;
  64.       //
  65.     }それ以外の場合 (windowStart > old.windowStart()) {
  66.       /*
  67.                  * （古い）
  68.                  * B0 B1 B2ヌルB4
  69.                  * |_______||_______|_______|_______|_______|_______||___
  70.                  * ... 1200 1400 1600 1800 2000 2200タイムスタンプ 
  71.                  * ^
  72.                  *時間= 1676
  73.                  * バケット 2の開始時間: 400、非推奨、リセットする必要があります
  74.                  *
  75.                  * 開始タイムスタンプが 古いバケットは指定された時間より遅れています。つまり
  76.                  * バケットは非推奨です。バケットをリセットして 現在の{@code windowStart}。
  77.                  * リセットとクリーンアップ操作はアトミックに行うのが難しいことに注意してください。
  78.                  * したがって、バケット更新の正確性を保証するには更新ロックが必要です。
  79.                  *
  80.                  *更新ロックは条件付き（小さな範囲）であり、  いつ 
  81.                  * バケットは非推奨であるため、ほとんどの場合、パフォーマンスの低下にはつながりません。
  82.                  */
  83.       （updateLock.tryLock()）の場合{
  84.         試す {
  85.           //更新ロックを正常に取得しました。次にバケットをリセットします。
  86.           // すべてのペインデータをクリアする
  87. resetWindowTo(old, windowStart)を返します。
  88.         ついに
  89.           更新ロックを解除します。
  90.         }
  91.       }それ以外{
  92.         // 競合が失敗した場合、スレッドはタイムスライスを放棄して、バケットが使用可能になるまで待機します。
  93.         スレッド.yield();
  94.       }
  95.       // 時計が戻された場合は、タイムグリッドを再作成します
  96.     }それ以外の場合 (windowStart < old.windowStart()) {
  97.       //提供された時間のため、ここを通らないでください すでに遅れています。
  98. 新しいWindowWrap<T>(windowLengthInMs、windowStart、newEmptyBucket(timeMillis))を返します。
  99.     }
  100.   }
  101.  }

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

リーキー バケット アルゴリズムは、ネットワークの世界ではトラフィック シェーピングやレート制限でよく使用されるアルゴリズムです。その主な目的は、ネットワークに注入されるデータのレートを制御し、ネットワーク上のバースト トラフィックを平滑化することです。リーキー バケット アルゴリズムは、バースト トラフィックを整形してネットワークに安定したフローを提供するメカニズムを提供します。実行プロセスを次の図に示します。

実装コードの例:

  1. パブリッククラスLeakyBucket{
  2.  public long timeStamp = System.currentTimeMillis(); // 現在の時刻
  3. public long capacity; // バケット容量
  4. public long rate; // 水が漏れる速度
  5. public long water; // 現在の水量（現在の累計リクエスト数） 
  6.  
  7. パブリックブールグラント（）{
  8.     現在の長さ = System.currentTimeMillis();
  9.     // 最初に水漏れを実行し、残りの水量を計算します
  10.     水 = Math.max (0, 水 - (現在 -タイムスタンプ) * 速度); 
  11.  
  12. タイムスタンプ= 現在;
  13.     ((水 + 1) < 容量) の場合 {
  14.       // 水を追加しようとしましたが、まだ水が満杯ではありません
  15.       水 += 1;
  16. 戻る 真実;
  17.     }それ以外{
  18.       // 水が満杯なので、水を追加しないでください
  19. 戻る 間違い;
  20.     }
  21.   }
  22.  }

例:

（１）タンクが満杯でない場合は水を追加します。コードwater +=1を使用して継続的に水を追加します。

（２）漏水：時間差を利用して漏水量を計算します。

（３）残水量：総水量－漏水量

Sentineでは、RateLimiterControllerがリーキーバケットアルゴリズムを実装しています。コアコードは次のとおりです。

  1.  @オーバーライド
  2. パブリックブールcanPass(Node ノード、 int acquireCount、ブール値の優先順位) {
  3.   //カウントを取得すると合格  0以下です。
  4.   取得カウント <= 0 の場合
  5. 戻る 真実;
  6.   }
  7.   // 拒否する場合 カウント  0以下です。
  8.   // それ以外の場合、costTimeは最大になります  longとwaitTimeのオーバーフローは いくつかのケース。
  9.   （カウント<= 0）の場合{
  10. 戻る 間違い;
  11.   } 
  12.  
  13.   現在の時刻が長い = TimeUtil.currentTimeMillis();
  14.   // 2 つのリクエスト間の間隔を計算します。
  15.   // 時間間隔を計算する
  16.   長いコスト時間 = Math.round(1.0 * (acquireCount) / count * 1000); 
  17.  
  18.   // 予想通過時間 このリクエストの。
  19.   // 予想される実行時間
  20.   長い予想時間 = コスト時間 + 最新の通過時間.get(); 
  21.  
  22.   // 現在の時刻 > 予想時刻
  23.   予想時刻 <= 現在の時刻の場合 {
  24.     // ここで競合が発生する可能性がありますが、問題ありません。
  25.     // 通過可能、最終通過時間の設定が可能
  26.     最新の経過時間を設定します(現在の時間) ;
  27. 戻る 真実;
  28.   }それ以外{
  29.     //時間を計算する 待つ。
  30.     // 待ち時間 = 予想時間 - 前回の時間 - 現在時間
  31.     長い待機時間 = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
  32.     // 待機時間 > 最大キュー時間
  33.     待機時間 > 最大キューイング時間ミリ秒の場合 {
  34. 戻る 間違い;
  35.     }それ以外{
  36.       // 最終時間 + 間隔時間
  37.       長い古い時間 = 最新の経過時間.addAndGet(コスト時間);
  38.       試す {
  39.         // 待ち時間
  40.         待機時間 = 古い時間 - TimeUtil.currentTimeMillis();
  41.         // 待機時間 > 最大キュー時間
  42.         待機時間 > 最大キューイング時間ミリ秒の場合 {
  43.           最新の経過時間。addAndGet(-コスト時間);
  44. 戻る 間違い;
  45.         }
  46.         // 競合状態ではwaitTime は 0 未満になる可能性がある
  47.         // 寝て待つ
  48.         待機時間 > 0 の場合
  49.           スレッドをスリープ状態にします。
  50.         }
  51.         // 待機後、解放
  52. 戻る 真実;
  53.       } キャッチ (InterruptedException e) {
  54.       }
  55.     }
  56.   }
  57. 戻る 間違い;
  58.  }

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

トークン バケット アルゴリズムは、ネットワーク トラフィック シェーピングとレート制限で最も一般的に使用されるアルゴリズムです。通常、トークン バケット アルゴリズムは、ネットワークに送信されるデータの量を制御し、データのバーストを送信できるようにするために使用されます。次の図に示すように:

簡単に言えば、一方がリクエスト時にバケット内のトークンを消費し、もう一方が一定の割合でバケットにトークンを入れます。消費されるリクエストが、入力されるレートよりも大きい場合は、待機または拒否などの適切な措置を講じます。

実装コードの例:

  1. パブリッククラスTokenBucket {
  2.  public long timeStamp = System.currentTimeMillis(); // 現在の時刻
  3. public long capacity; // バケット容量
  4. public long rate; //トークン挿入速度
  5. public long tokens; // 現在のトークン数
  6.  
  7. パブリックブールグラント（）{
  8.     現在の長さ = System.currentTimeMillis();
  9.     // 最初にトークンを追加します
  10.     トークン = Math.min (容量、トークン + (現在 -タイムスタンプ) * レート);
  11. タイムスタンプ= 現在;
  12.     （トークン数<1）の場合{
  13.       // トークンが1つ未満の場合は拒否します
  14. 戻る 間違い;
  15.     }それ以外{
  16.       // トークンもあります。トークンを取得します
  17.       トークン -= 1;
  18. 戻る 真実;
  19.     }
  20.   }
  21.  }

Sentinel は、WarmUpController のトークン バケット アルゴリズムを使用します。このアルゴリズムでは、システムを予熱し、予熱時間と水位を設定し、予熱期間中に過剰な要求を直接拒否することができます。

  1. パブリックブールcanPass(Node ノード、 int acquireCount、ブール値の優先順位) {
  2.   長い passQps = (長い) node.passQps(); 
  3.  
  4.   長い previousQps = (long) node.previousPassQps();
  5.   syncToken(前のQps); 
  6.  
  7.   // 傾斜の計算を開始する
  8.   // 警告ラインに入ったら、QPS の調整を開始します
  9.   長いrestToken = 格納されたTokens.get();
  10.   （restToken >= 警告トークン）の場合{
  11.     long aboveToken = restToken - warningToken;
  12.     // 消費率は警告より速いが、
  13.     //現在の間隔 = restToken*slope+1/ count  
  14. ダブル警告Qps = Math.nextUp(1.0 / (aboveToken * 傾き + 1.0 /カウント));
  15.     （passQps + acquireCount <= warningQps）の場合{
  16. 戻る 真実;
  17.     }
  18.   }それ以外{
  19.     （passQps + acquireCount <= count ）の場合{
  20. 戻る 真実;
  21.     }
  22.   } 
  23.  
  24. 戻る 間違い;
  25.  }

電流制限アルゴリズムの概要

カウンターと時間ウィンドウ

タイム ウィンドウ アルゴリズムの本質も、カウンター アルゴリズムを通じて実装されます。

時間ウィンドウ アルゴリズムが分割されるグリッドの数が多いほど、スライディング ウィンドウのスクロールがスムーズになり、現在の制限統計がより正確になりますが、メモリ ストレージの消費量も増加します。

リーキーバケットとトークンバケット

リーキー バケット アルゴリズムとトークン バケット アルゴリズムは、本質的には、大量のトラフィックによるシステムのクラッシュを防ぐためのトラフィック シェーピングまたはレート制限を目的としています。ただし、この 2 つのアルゴリズムの主な違いは、フロー制限の方向が逆であることです。

リーキーバケット: 比較的固定されたトラフィックの流出率を制限します。

トークン バケット: トラフィックの平均流入速度を制限し、ある程度の突発的なトラフィックを許可します。最大速度はバケットの容量とトークンが生成される速度です。

いくつかのシナリオでは、リーキー バケットの漏洩率が比較的固定されているため、リーキー バケット アルゴリズムはネットワーク リソースを効果的に使用できません。そのため、ネットワークの状態が比較的良好で、混雑がない場合でも、リーキー バケットは制限されたままになり、その量を解放できないため、ネットワーク リソースを効果的に活用できません。トークン バケット アルゴリズムは異なります。平均レートを制限しながら、ある程度のバースト トラフィックをサポートします。

参照ドキュメント

https://www.cnblogs.com/linjiqin/p/9707713.html

https://www.cnblogs.com/dijia478/p/13807826.html

<<:  鵬城クラウドブレインは鵬城シリーズの大型モデルの基礎研究をサポート

>>:  注目すべきAIハードウェアスタートアップ3社

ブログ    
ブログ    
ブログ    

推薦する

6つの興味深い画像グレースケール変換アルゴリズム

[楊静卓のブログより引用]序文白黒写真の時代は過ぎ去りましたが、今、昔の写真を見ると、昔に戻ったよう...

AIはあなたの建物をスマートで健康的な建物にします

すぐにスマートで健康的な建物で仕事に戻り、スマートフォンのアプリを使ってハンズフリーでドアを開けるこ...

...

プログラマーが夜遅くにPythonでニューラルネットワークを実行し、中学生のようにデスクランプを消す

[[271670]]一度ベッドに入ったら決して起き上がりたくない人にとって、電気を消すことは寝る前の...

オープンソースの自動車機械ソフトウェアであるOpenpilotがアップデートされ、ナビゲーションに基づいて一般の自動車が自動運転できるようになる

8月1日、 Comma.aiは、2016年に著名なアメリカ人ハッカー、ジョージ・ホッツ氏によって自動...

Twitterはボットアカウントのラベルをテスト中

Twitterは木曜日、自動/ボットアカウントラベルを導入すると発表した。 Twitter社は、ユー...

...

Javaソートアルゴリズムの概要（I）：挿入ソート

挿入ソートの基本的な操作は、ソートされた順序付けられたデータにデータを挿入し、それによって番号が 1...

「自由に眠る」にはヘッドバンドを着けるだけ | Nature サブ出版物

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載...

インテリジェント衛生の開発が加速しており、衛生ロボットは応用の「先駆者」となっている。

環境保護の重要な部分として、都市環境衛生はますます重視されています。衛生産業をうまく発展させ、衛生業...

2021年なのに、出会い系アプリのアルゴリズムはなぜこんなにも悪いのでしょうか?

[[407925]]ビッグデータダイジェスト制作出典: Wiredパンデミックの間、出会い系アプリ...

データサイエンスと機械学習のためのツールと言語の最新情報

[[198310]]第 18 回 KDnuggets ソフトウェア アンケートには、今年もアナリティ...

アンドリュー・ン：機械学習の6つのコアアルゴリズム

この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式...

IoTとAI：輸送管理の変革

私たちが今生きている時代は、これまでで最も技術的に進歩した時代です。これらの新しいテクノロジーの登場...

Nvidia が PC CPU 市場に参入することが明らかになりました。ネットユーザー：Apple M1が市場を開拓したことを羨ましく思う

GPU マニアのNvidiaが、突如としてノート PC の CPU に狙いを定めました。ロイター通信...