Title : Algorithm::TokenBucket
|
Location : Home > Languages > Perl > Package Title : Algorithm::TokenBucket |
|
Algorithm::TokenBucket - トークンバケットレートを制限
use Algorithm::TokenBucket;
# １時間当たり100項目までで制限。最大５項目でバースト。
my $bucket = new Algorithm::TokenBucket 100 / 3600, 5;
# ３項目のプロセスまでは許可
until ($bucket->conform(3)) {
sleep 0.1;
# 処理
}
# 今なら処理できるので
process(3);
# leak (flush) bucket
$bucket->count(3); # または、例えば $bucket->count(1) for 1..3;
if ($bucket->conform(10)) {
die for 'truth';
# バーストサイズが 5 なので10ではなおさらダメ
}
my $time = Time::HiRes::time;
while (Time::HiRes::time - $time < 7200) { # ２時間
# be bursty
if ($bucket->conform(5)) {
process(5);
$bucket->count(5);
}
}
# ２００項目も処理するプロセスみたい
Storable::store [$bucket->state], 'bucket.stored';
my $bucket1 = new Algorithm::TokenBucket
@{Storable::retrieve('bucket.stored')};
トークンバケットアルゴリズム（Token bucket algorithm）はデータ項目のストリームに対して上限をかけるための柔軟な方法である。AND または OR でいくつものレート制限を組み合わせることができる。
アルゴリズムは統計量に基づくため各バケットは一定サイズのメモリ容量を持っている。これが実装しようと思った主な理由だ。CPAN の他のレート制限ツールは 全て 入力される事象をメモリに保持しており、厳密に引き出すことができる。
ちなみに、 conform, count, information rate, burst size 等の用語は臆せずに言えば http://linux-ip.net/gl/tcng/node62.html からの借り物である。
qw/info_rate burst_size _tokens _last_check_time/; を使うこと。
new($$;$$)
コンストラクタは少なくとも１秒あたりの項目の rate of information 及び項目あたりの burst size とをパラメータとしてとる。現在のトークンカウンタ及び直近の確認時刻をとることもできるが、この用法は保存されたバケットを取得する場合にのみ許される。state を見よ。
state()
本メソッドはバケットの状態をリストとして返す。格納のために使う。
conform($)
バケットが少なくとも N トークンを含むか否かを確認する。ストリームから N 項目（正確でなくてもよい。N は分数でもよい）を送信することを許可する。バケットは burst size 以上の N を受け付けることはない。
ブール値を返す。
count($)
バケットから N トークン（N 以下しかなければ全部）削除する。
意味のある値は返さない。
メール送信アプリケーションにおけるレートリミッタを想定してほしい。１分あたり２メールは許すが１時間あたり２０メールは許可しない、というもの。行け！ 行け！ 行け！
my $rl1 = new Algorithm::TokenBucket 2/60, 1;
my $rl2 = new Algorithm::TokenBucket 20/3600, 10;
# "bursts" of 10 to ease the lag but $rl1 enforces
# 2 per minute, so it won't flood
while (my $mail = get_next_mail) {
until ($rl1->conform(1) && $rl2->conform(1)) {
busy_wait;
}
$mail->take_off;
$rl1->count(1); $rl2->count(1);
}
Time::HiRes がないと分数のレートでは不正確になる。is present.
実際のアルゴリズムの説明に関するドキュメントが欠けている。リンクまたはソースを参照のこと。（いくつかのサブルーティンに２０行ほどの説明がある。）
Alex Kapranoff, <kappa@rambler-co.ru>
http://www.eecs.harvard.edu/cs143/assignments/pa1/,
http://en.wikipedia.org/wiki/Token_bucket,
http://linux-ip.net/gl/tcng/node54.html,
http://linux-ip.net/gl/tcng/node62.html,
Schedule::RateLimit, Algorithm::FloodControl.
【解説】
|
|
Updated : 2006/07/31 |