RateLimiterソース分析
7919 ワード
キャッシュ、制限流と降格はシステムの三本の剣です。ちょうどプロジェクトの中で毎朝データをエクスポートする時、注文インターフェースの周波数を調整するのが高すぎるため、注文システムはユーザー側の使用に影響を与えると心配しています。呼び出しの制限速度に対して、ちょうど使います。
一般的な制限ストリームアルゴリズムは、リーキーバケツアルゴリズムとトークンバケットアルゴリズムの2つがある。
バケツもれアルゴリズム
リーキーバケツアルゴリズム:要求はまず「バケツ」に入り、その後、要求を一定のレートで処理する。要求のスピードが速すぎると、バケツが溢れてしまいます。説明によれば、リーキーバケツアルゴリズムは、要求処理の速度を強制的に制限することができる。あなたが要請したのがもっと早くても遅くても、私はこのスピードで処理します。
しかし、多くの場合、平均処理速度を制限することが要求される以外に、ある程度の突発状況を許可することが求められます。これでは、ドラム缶アルゴリズムが不適切となり、トークンバケットアルゴリズムがより適切となる。
トークンバケットアルゴリズム
トークンバケットアルゴリズムの原理は、システムが一定のレートでバケットに一定の数のトークンを落とし、要求はトークンを取得してからでないと処理できない。バケットにトークンがない場合はサービスを拒否することができます。
GuavaのRatelimiterは、トークンバケットアルゴリズムを実装し、ある程度のバースト要求をサポートすることができる。
続いて、ソースで解析します。
トークンバケットのアルゴリズム記述を初めて見た時、本当にスレッドがX秒ごとにカウンタのようなところに数字を加えていると思いました。
guavaの限流アルゴリズムには2つのモードがあり、一つは安定速度であり、もう一つはトークンを生成する速度が安定速度を維持するまで徐々に向上することである。2つのモード原理は似ていますが、具体的にどれぐらい待つかの時間計算に違いがあります。以下は、特に安定速度のパターンを指します。
まず、そのacquireの方法を見てみましょう。
1.limiter作成時に入ってきたパラメータに基づいて、これらの数のトークンを生成するにはどれぐらいの時間がかかりますか?
2.スレッドをmicroTowaitにブロックさせるのはこんなに長い時間(単位:マイクロ秒)です。
3.また戻ってどれぐらい渋滞しましたか?単位:秒
具体的にはどのように計算すればどれぐらいかかりますか?reerveの方法を見てみましょう。
この方法の意味は、現在の時間が前のラウンドに設定された次の取得時間よりも大きい場合(前に取得した場合、例えば前回直接10個を取得した場合、その前輪に設定されているnextFreeTicketMirosは前のラウンドの時間+5 sです。後で述べる)、この中間理論でどれぐらいのトークンが生成できるかを計算します。例えば、この中で1秒間隔で、そしてstable IntervalMicrosoft=5000(安定した発生速度の場合)であれば、この中間で2つのトークンを生成することができる。それに加えて、元に記憶されていたstordPermits個は、maxPermitsより大きいなら、最大でもmaxPermitsだけです。maxPermitsより小さいと、stordPermits=元にあった+この中間生成の数量です。また、次回取得時に差し引く時間、つまり現在時間を記録します。
続いてreerveEarliest Availableの方法を見ます。
二行目が設定されたら。3行目は、次に取得するときに減算する時間をリターン値とします。
この2つはどういう意味ですか?
この2つはRateLimiterがある程度の突発的な要求をすることができる原因です。requiredPermits=10を仮定して、私達の貯蓄することができるstoredPermits=2、そんなにfreshPermits=8、つまり8つ多く取りました。6行目はこの多く取った8つを計算するのにどれぐらいの時間がかかりますか?3秒かかります。この3秒を、私たちの前に割り当てられた「次の取得時に減算する時間」に加えます。
例えば、05秒に10個を一度に取得した場合、7行目はnext Free TicketMicrosoft=13 Sに対応するシステムのミリ秒数を意味します。そしてstordPermitsは-8です。1秒が過ぎたら、次の請求でacquire(1)を呼び出します。reyncメソッドはnowMirosのためです。
ですから、何よりもnext Free TicketMicrosoftは、今回取得したときにトークンの生成を開始することができる時間を記録しています。例えば、現在は05 Sですが、next FreeTicketMicrosoft=10なら、トークンの生成を10 Sにして開始するという意味です。前のものはこんなに多く取りましたか?今回は多く取りましたか?それともただのトークンを持っていますか?待つ時間は全部こんなに多いです。今回も多く取ったら、今度はもっと長く待ちます。
以上は本稿のRateLimiterの常用方法とソース分析の全部の内容についてです。興味のある友達はOpenfireクラスタのソースコードの分析についてを参照してください。 、 Spring Spring MVCの起動完了後のソースコード解析 、 Javaは本機のポートがソースコードを占用されているかどうかを確認します。などです。皆さん、私達のウェブサイトに対する支持に感謝します。
一般的な制限ストリームアルゴリズムは、リーキーバケツアルゴリズムとトークンバケットアルゴリズムの2つがある。
バケツもれアルゴリズム
リーキーバケツアルゴリズム:要求はまず「バケツ」に入り、その後、要求を一定のレートで処理する。要求のスピードが速すぎると、バケツが溢れてしまいます。説明によれば、リーキーバケツアルゴリズムは、要求処理の速度を強制的に制限することができる。あなたが要請したのがもっと早くても遅くても、私はこのスピードで処理します。
しかし、多くの場合、平均処理速度を制限することが要求される以外に、ある程度の突発状況を許可することが求められます。これでは、ドラム缶アルゴリズムが不適切となり、トークンバケットアルゴリズムがより適切となる。
トークンバケットアルゴリズム
トークンバケットアルゴリズムの原理は、システムが一定のレートでバケットに一定の数のトークンを落とし、要求はトークンを取得してからでないと処理できない。バケットにトークンがない場合はサービスを拒否することができます。
GuavaのRatelimiterは、トークンバケットアルゴリズムを実装し、ある程度のバースト要求をサポートすることができる。
private static RateLimiter one=RateLimiter.create(2);// 2
private static RateLimiter two=RateLimiter.create(2);// 2
private RateLimitUtil(){};
public static void acquire(RateLimiter r,int num){
double time =r.acquire(num);
System.out.println("wait time="+time);
}
public static void main(String[] args) throws InterruptedException {
acquire(one,1);
acquire(one,1);
acquire(one,1);
System.out.println("-----");
acquire(two,10);
acquire(two,1);
}
出力結果:
wait time=0.0
wait time=0.499163
wait time=0.489308
-----
wait time=0.0
wait time=4.497819
2つの要求の速度でトークンを生成することが見える。oneにとっては、2回目と3回目のリクエストの場合、待ち時間を合わせて1秒ぐらいです。twoにとっては、初めてトークンを10個取得した後、1つの要求を2回目に取得すると、ほぼ5 S(10/2=5)を待つ。Guavaは、後に要求される待ち時間を制限することにより、ある程度の突発要求をサポートすることができる。続いて、ソースで解析します。
トークンバケットのアルゴリズム記述を初めて見た時、本当にスレッドがX秒ごとにカウンタのようなところに数字を加えていると思いました。
guavaの限流アルゴリズムには2つのモードがあり、一つは安定速度であり、もう一つはトークンを生成する速度が安定速度を維持するまで徐々に向上することである。2つのモード原理は似ていますが、具体的にどれぐらい待つかの時間計算に違いがあります。以下は、特に安定速度のパターンを指します。
まず、そのacquireの方法を見てみましょう。
public double acquire(int permits) {
long microsToWait = reserve(permits);//
stopwatch.sleepMicrosUninterruptibly(microsToWait);// microTowait
return 1.0 * microsToWait / SECONDS.toMicros(1L);//
}
主に3ステップに分けます 1.limiter作成時に入ってきたパラメータに基づいて、これらの数のトークンを生成するにはどれぐらいの時間がかかりますか?
2.スレッドをmicroTowaitにブロックさせるのはこんなに長い時間(単位:マイクロ秒)です。
3.また戻ってどれぐらい渋滞しましたか?単位:秒
具体的にはどのように計算すればどれぐらいかかりますか?reerveの方法を見てみましょう。
final long reserve(int permits) {
checkPermits(permits);//
synchronized (mutex()) {
return reserveAndGetWaitLength(permits, stopwatch.readMicros());
}
}
↓
↓
↓
final long reserveAndGetWaitLength(int permits, long nowMicros) {
long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
return max(momentAvailable - nowMicros, 0);
}
↓
↓
↓
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
resync(nowMicros);//here
long returnValue = nextFreeTicketMicros;
double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
double freshPermits = requiredPermits - storedPermitsToSpend;
long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
+ (long) (freshPermits * stableIntervalMicros);
this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
this.storedPermits -= storedPermitsToSpend;
return returnValue;
}
最終的に呼び出されたのは、reerveEarliest Availableの方法です。まず、reyncの方法を見てください。
private void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
if (nowMicros > nextFreeTicketMicros) {
storedPermits = min(maxPermits,
storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
nextFreeTicketMicros = nowMicros;
}
}
nextFree TicketMicrosoftとは、次の取得時に差し引く時間という意味です。初めてaccquire()を呼び出す場合、nowMicrosoft-next Free TicketMirosは初期化(初期化時にnextFree TicketMirosに一度値を与え、具体的にはRateLimiterのコンストラクタを見ることができます)から最初の要求までの間に発生する時間です。 この方法の意味は、現在の時間が前のラウンドに設定された次の取得時間よりも大きい場合(前に取得した場合、例えば前回直接10個を取得した場合、その前輪に設定されているnextFreeTicketMirosは前のラウンドの時間+5 sです。後で述べる)、この中間理論でどれぐらいのトークンが生成できるかを計算します。例えば、この中で1秒間隔で、そしてstable IntervalMicrosoft=5000(安定した発生速度の場合)であれば、この中間で2つのトークンを生成することができる。それに加えて、元に記憶されていたstordPermits個は、maxPermitsより大きいなら、最大でもmaxPermitsだけです。maxPermitsより小さいと、stordPermits=元にあった+この中間生成の数量です。また、次回取得時に差し引く時間、つまり現在時間を記録します。
続いてreerveEarliest Availableの方法を見ます。
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) { //1
resync(nowMicros); //2
long returnValue = nextFreeTicketMicros;//3
double storedPermitsToSpend = min(requiredPermits, this.storedPermits);//4
double freshPermits = requiredPermits - storedPermitsToSpend;//5
long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
+ (long) (freshPermits * stableIntervalMicros);//6
this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;//7
this.storedPermits -= storedPermitsToSpend;//8
return returnValue;//9
}
私たち一行で見に来ました。 二行目が設定されたら。3行目は、次に取得するときに減算する時間をリターン値とします。
この2つはどういう意味ですか?
この2つはRateLimiterがある程度の突発的な要求をすることができる原因です。requiredPermits=10を仮定して、私達の貯蓄することができるstoredPermits=2、そんなにfreshPermits=8、つまり8つ多く取りました。6行目はこの多く取った8つを計算するのにどれぐらいの時間がかかりますか?3秒かかります。この3秒を、私たちの前に割り当てられた「次の取得時に減算する時間」に加えます。
例えば、05秒に10個を一度に取得した場合、7行目はnext Free TicketMicrosoft=13 Sに対応するシステムのミリ秒数を意味します。そしてstordPermitsは-8です。1秒が過ぎたら、次の請求でacquire(1)を呼び出します。reyncメソッドはnowMirosのためです。
final long reserveAndGetWaitLength(int permits, long nowMicros) {
long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
return max(momentAvailable - nowMicros, 0);//
}
つまり、reerveAndGetWaitLengthはmax(13-6,0)、つまり7に戻ります。この方法の戻り値はまた、sleepスレッドのためのもので、つまり最初に見たものです。
public double acquire(int permits) {
long microsToWait = reserve(permits);
stopwatch.sleepMicrosUninterruptibly(microsToWait);
return 1.0 * microsToWait / SECONDS.toMicros(1L);
}
まとめてみると、一番大切なのはnowMicrosoft、next Free TicketMicrosoftの2つの値です。nextFree TicketMicrosoftは、最初のコンストラクタの実行時に、コンストラクタの実行時間に一度の価値を与えます。accquire()を初めて呼び出した場合、reyncは実行され、accquire()にnextFree Ticketmirosを現在の時間に設定します。しかしながら、要求されたトークンの数と現在記憶されているトークンの数とは、reerveEarliest Availableで比較されることに留意されたい。要求されたトークン数が大きいと、これらの余分なトークンを生成するために必要な時間が計算され、nextFree TicketMicrosoftに追加され、次回のaccquire()の呼び出し時にnext Free TicketMicrosと当時のnowMicrosoftによって減らされることが保証されます。流量の急激な増加にも対応できます。 ですから、何よりもnext Free TicketMicrosoftは、今回取得したときにトークンの生成を開始することができる時間を記録しています。例えば、現在は05 Sですが、next FreeTicketMicrosoft=10なら、トークンの生成を10 Sにして開始するという意味です。前のものはこんなに多く取りましたか?今回は多く取りましたか?それともただのトークンを持っていますか?待つ時間は全部こんなに多いです。今回も多く取ったら、今度はもっと長く待ちます。
private static RateLimiter too=RateLimiter.create(2);// 2
private RateLimitUtil(){};
public static void acquire(RateLimiter r,int num){
double time =r.acquire(num);
System.out.println("wait time="+time);
}
public static void main(String[] args) throws InterruptedException {
acquire(too,1);
acquire(too,10);// 0.5 10
acquire(too,10);// 5 10
acquire(too,1);// 1 , 5
}
締め括りをつける以上は本稿のRateLimiterの常用方法とソース分析の全部の内容についてです。興味のある友達はOpenfireクラスタのソースコードの分析についてを参照してください。 、 Spring Spring MVCの起動完了後のソースコード解析 、 Javaは本機のポートがソースコードを占用されているかどうかを確認します。などです。皆さん、私達のウェブサイトに対する支持に感謝します。