コールドスタートアルゴリズムは、トークンバケットアルゴリズムに基づいて実装されています。
トークンバケットアルゴリズムの原理は、トークンを一定の割合でトークンバケットに入れ、リクエストを受けたらトークンバケットからトークンを要求し、トークンを獲得したリクエストのみを通過させるというものです。トークン・バケツがいっぱいになると、余ったトークンは捨てられ、トークン・バケツが空になると、トークンを獲得できないリクエストは拒否されます。
例えば、トークン・バケット・アルゴリズムを使ってインターフェイスの最大QPSを200に制限したい場合、トークン・バケットに入れるために5ミリ秒ごとにトークンを生成しなければならず、バケットに入れるためにトークンを生成する速度は変わりません。
コールドスタート・アルゴリズムは、トークン・バケットのトークン生産速度を制御するために使用されます。
コールド・スタートの持続時間が 10 秒、初期状態がコールド・スタート状態、流量制限閾値が 200 QPS とすると、トークンの生成速度は通常時で 5 ms/1回、コールド・スタート段階では最小値から 5 ms/1回まで上昇し、最小値はコールド・スタート・サイクル持続時間に関係するコールド・スタート係数に関係します。
SentinelがGuavaの実装と異なるのは、おそらくパフォーマンス上の理由から、Sentinelは各リクエストの通過の間の時間間隔を制御せず、1秒あたりに通過できるリクエストの数だけを制御するという点です。
コールドスタートのアルゴリズムについては、以下の図を参照してください。
軸：横座標storedPermitsはバケツ内のトークン数を表し、縦座標はトークン取得にかかる時間、つまりリクエスト間の時間間隔を表します；
stableInterval：安定したトークン生成のための時間間隔。フロー制限しきい値QPSが200の場合、stableIntervalの値は5ミリ秒です。
coldInterval: コールドスタートのトークン生成の最大時間間隔。安定したトークン生成の時間間隔にコールドスタート係数を掛けたもので、SentinelのcoldFactorのデフォルトは3です。
warmupPeriod：ウォームアップ時間、つまりコールドスタート期間。上図の台形部分に相当し、Sentinelのデフォルトは10秒。
thresholdPermits: コールドスタートから通常までのトークン・バケット内のトークン数のしきい値。トークン・バケット内のトークン数がこの値を超えると、コールドスタート・フェーズに入ります。
coldFactor のデフォルトは 3 なので、stableInterval の 2 倍の長さとなり、thresholdPermits から 0 までの時間は maxPermits から thresholdPermits までの時間の半分となり、コールドスタート期間の半分となります。台形の面積は warmupPeriod と等しいので、長方形の面積は台形の面積の半分となり、長方形の面積は warmupPeriod / 2 となります。
長方形の面積は、長さ * 幅 = 面積という式で求めることができます：
thresholdPermits = 0.5 * warmupPeriod / stableInterval
maxPermits: バケツに格納できるトークンの最大数。
これは、台形の面積の公式から得られます：*高さ÷2：
warmupPeriod = （stableInterval + coldInterval）* （maxPermits - thresholdPermits）/ 2
打ち上げ：
maxPermits = thresholdPermits + 2 * warmupPeriod / （stableInterval + coldInterval）
傾き：直線の傾き、つまりトークンが生成される速度。
勾配の式： / によると、次のようになります：
slope = (coldInterval - stableInterval) / （maxPermits - thresholdPermits）
Sentinelはトークンを1秒に1回生成し、新しく生成されたトークンをトークン・バケットに入れ、トークンを現在生成した時刻を記録し、次の生成時に、現在の時刻と前回のトークン生成の間の時間間隔、および各トークンの生成の間の時間に基づいて、今回生成する必要があるトークンの数を計算します。
サービスが初めて開始されたときや、長い間インターフェイスにアクセスがなかったときは、現在時刻とトークンが生成された時刻が離れているため、最初のトークン生成でmaxPermitsトークンが生成され、トークン・バケットが直接いっぱいになります。トークン・バケットが満杯になったので、次の10秒はコールド・スタート・フェーズとなります。
コールドスタート段階におけるトークンの生成間隔は、通常の消費速度よりも遅いため、バケツに 残っているトークンの数は時間とともに thresholdPermits に収束し、トークンを生成する時間間隔は coldInterval から stableInterval に減少します。を下回ると、コールドスタートは終了し、システムは定常状態になり、トークンを生成する時間間隔は stableInterval になり、1 秒あたりに生成されるトークンの数は QPS に等しくなります。
Sentinelは、リクエストが通過したときにトークンバケツのトークンの数を減らすのではなく、次の秒に新しいトークンが生成されたときに、前の秒に通過したリクエストの数に等しいトークンの数をバケツから差し引きます。これは、Sentinelが公式にトークンの自動的なドロップと説明しているものです。
Sentinelは各リクエストが通過するたびにトークンバケツからトークンを取り出しません。ではSentinelはどのようにQPSを制御しているのでしょうか、別のグラフを見てください：
- x1: 現在のトークンバケットで thresholdPermits を超えたトークンの数；
- y1: y1 に stableInterval を足したものが、現在のトークン生成間隔に等しくなります；
傾きとx1からy1が計算できます： y1 = 傾き * x1
y1にstableIntervalを足したものが現在のトークン生産率です。
現在の第2プロダクション・トークンの間隔は
slope * (storedTokens - thresholdPermits) + stableInterval
としてstableInterval = 1.0（1(秒) / 現在の限界しきい値
つまり、上の式は slope * (storedTokens - thresholdPermits) + 1.0 / count
最後に、現在のタイムスタンプに対するQPSのしきい値は次のように計算されます：
1.0 / slope * (storedTokens - thresholdPermits) + 1.0 / count
ここで1.0は秒を表します。
