Sentinel のコールドスタート電流制限アルゴリズム

[[336019]]

コールド スタート アルゴリズムは、トークン バケット アルゴリズムに基づいて実装されます。

トークン バケット アルゴリズムの原理は、一定のレートでトークンをトークン バケットに入れて、リクエストを受信したときにトークン バケットからトークンを申請することです。トークンを取得したリクエストのみが承認されます。トークン バケットがいっぱいになると、余分なトークンは破棄されます。トークン バケットが空になると、要求はトークンを取得できず、拒否されます。

たとえば、トークン バケット アルゴリズムを使用してインターフェイスの最大 QPS を 200 に制限する場合は、5 ミリ秒ごとにトークンを生成してトークン バケットに入れる必要がありますが、トークンを生成してトークン バケットに入れる速度は変わりません。

コールド スタート アルゴリズムは、トークン バケットのトークン生成率、つまり各トークンの生成の時間間隔を制御するために使用されます。

コールド スタートの継続時間が 10 秒、初期状態がコールド スタート状態、現在の制限しきい値が 200QPS であると仮定します。通常の状況では、トークン生成レートは 5 ミリ秒/トークンである必要があります。コールド スタート フェーズでは、レートは最小値から 5 ミリ秒/トークンに増加します。最小レートは、コールド スタート係数とコールド スタート サイクルの継続時間に関連します。

Sentinel は Guava とは実装が異なります。Sentinel はパフォーマンスを考慮して各リクエスト間の時間間隔を制御せず、1 秒あたりに通過できるリクエストの数のみを制御します。

コールド スタート アルゴリズムを理解するには、次の図を使用します。

軸：

• 横軸のstoredPermitsはバケット内のトークンの数を表します。
• 縦軸はトークンを取得するために必要な時間、つまりリクエストが通過する時間間隔を表します。

stableInterval: 安定したトークン生成の時間間隔。現在の制限しきい値 QPS が 200 であると仮定すると、stableInterval の値は 5 ミリ秒になります。

coldInterval: コールド スタート トークン生成の最大時間間隔。これは、安定したトークン生成の時間間隔にコールド スタート係数 (stableInterval * coldFactor) を掛けたものに等しくなります。Sentinel の coldFactor のデフォルト値は 3 です。

warmupPeriod: ウォームアップ時間、つまりコールド スタート期間。上図の台形領域に相当します。Sentinel のデフォルト値は 10 秒です。

thresholdPermits: コールド スタートから通常までのトークン バケット内のトークン数のしきい値。トークン バケット内のトークン数がこの値を超えると、コールド スタート フェーズが開始されます。

coldFactor のデフォルトは 3 なので、(coldInterval - stableInterval) は stableInterval の 2 倍となり、thresholdPermits から 0 までの時間は maxPermits から thresholdPermits までの時間の半分となり、コールド スタート期間の半分になります。台形の面積はwarmupPeriodに等しいため、長方形の面積は台形の面積の半分となり、長方形の面積はwarmupPeriod / 2となります。

長方形の面積の公式によると：長さ×幅＝面積

以下が得られます:

しきい値許可 = 0.5 * ウォームアップ期間 / 安定間隔

maxPermits: バケットに保存できるトークンの最大数。

台形の面積の公式によると：（上端の最低値＋下端の最低値）×高さ／２

以下が得られます:

 warmupPeriod = (安定間隔 + コールド間隔) * (最大許可数 - しきい値許可数) / 2

ロールアウトする：

 maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval)

傾き: 線の傾き、つまりトークンが生成される速度。

傾きの計算式 (y2-y1) / (x2-x1) によれば、次のようになります。

傾き = (coldInterval - stableInterval) / (maxPermits - thresholdPermits)

Sentinel は 1 秒に 1 回トークンを生成し、新しく生成されたトークンをトークン バケットに入れて、このトークン生成の時刻を記録します。次のトークン生成を実行すると、現在の時刻と最後のトークン生成の間の時間間隔と、各トークンの生成間隔に基づいて、この生成に必要なトークンの数が計算されます。

サービスが初めて起動された場合、またはインターフェイスが長時間アクセスされていない場合、現在の時刻はトークンが最後に生成された時刻からかなり離れています。そのため、最初のトークン生成では maxPermits 個のトークンが生成され、トークン バケットが直接満たされます。トークン バケットがいっぱいなので、次の 10 秒間はコールド スタート フェーズになります。

コールド スタート フェーズでのトークン生成間隔は通常の消費速度よりも遅いため、時間が経つにつれて、バケット内の残りのトークンの数は thresholdPermits に近づき、トークン生成間隔も coldInterval から stableInterval に減少します。バケット内の残りのトークンの数が thresholdPermits 未満になると、コールド スタートが終了し、システムは安定状態になります。トークンを生成する時間間隔は stableInterval で、1 秒あたりに生成されるトークンの数は QPS に等しくなります。

Sentinel は、リクエストが渡されたときにトークン バケット内のトークンの数を減らしません。代わりに、次の 1 秒間に新しいトークンを生成するときに、前の 1 秒間に渡されたリクエストの数と同じ数のトークンをバケットから減算します。これは、Sentinel が正式に自動トークン ドロップと呼んでいるものです。

Sentinel は、各リクエストが通過するときにトークン バケットからトークンを取得しません。では、Sentinel はどのようにして QPS を制御するのでしょうか。別の図を見てみましょう。

x1: 現在のトークン バケット内で、thresholdPermits を超えるトークンの数。

y1: y1 に stableInterval を加えた値が現在のトークン生成時間間隔に等しくなります。

傾きと x1 に基づいて、y1 を計算できます。

 y1 = 傾き * x1

y1 に stableInterval を加えた値が現在のトークン生成率です。

トークンを生成する現在の時間間隔（秒単位）は次のとおりです。

傾き * (保存トークン - しきい値許可) + 安定間隔

理由: stableInterval = 1.0 (1秒) / 現在の制限しきい値 (カウント)

したがって、上記の式 = 傾き * (storedTokens - thresholdPermits) + 1.0 / count

最後に、現在のタイムスタンプの QPS しきい値は次のように計算されます。

 1.0 / 傾き * (保存トークン - しきい値許可) + 1.0 /カウント 

参考文献:

[1] Guava RateLimiter分析：

https://blog.wangqi.love/articles/Java/Guava%20RateLimiter%E5%88%86%E6%9E%90.html

この記事はWeChatの公開アカウント「Java Art」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合はJava Art公式アカウントまでご連絡ください。