あけましておめでとうございます。
さて、ラウンドロビンというのは、主に負荷分散のため使われる手法で、複数のリソースに対して順番に処理を割り当てるためのアルゴリズムです。さらに、各リソースの処理性能であるとか、状況に応じて割り当てる確率を変えるために、それぞれに重み付けを行うケースがあります。その際に使われるのが、加重ラウンドロビンというアルゴリズムです。
新年早々アプリケーション層でそういうことをやりたい機会があったので、Perl でラウンドロビンを実装しました。いまいち洗練されてないんですが、メモがてら。
まずは、ラウンドロビン。配列で与えられたリソースのから、利用可能なものを順に引いてきます。
#!/usr/bin/perl
my @DATA = ( { name => 'A', available => 1 }, { name => 'B', available => 1 }, { name => 'C', available => 1 }, { name => 'D', available => 0 }, { name => 'E', available => 1 }, );
our $i = -1; # last time index for (1..10) { my $data = select_data(); if (defined $data) { print sprintf("%d\t%s\n", $_, $data->{name}); } else { print sprintf("%d\tAll datas are unavailable\n", $_); } }
sub select_data {
my $j = $i; do { $j = ($j + 1) % scalar(@DATA); if (${DATA[$j]}->{available}) { $i = $j; return ${DATA[$j]}; } } while ($j != $i); return undef; }
実行結果。
1 A 2 B 3 C 4 E 5 A 6 B 7 C 8 E 9 A 10 B
続いて、加重ラウンドロビン。最大公約数や重みの最大値を毎回計算しているのは、利用可能なリソースが動的に変化することを想定していたためです。実際には、最初に計算して memcached に載せたあとは、リソース状況に変化があった際にメモリを上書きするようにしました。
#!/usr/bin/perl
use Math::BigInt qw(bgcd); use List::Util qw(max);
my @DATA = ( { name => 'A', available => 1, weight => 2 }, { name => 'B', available => 1, weight => 3 }, { name => 'C', available => 1, weight => 4 }, { name => 'D', available => 0, weight => 1 }, { name => 'E', available => 1, weight => 1 }, );
our $i = -1; # last time index our $cw = 0; # current weight
for (1..10) { my $data = select_data(); if (defined $data) { print sprintf("%d\t%s\n", $_, $data->{name}); } else { print sprintf("%d\tAll datas are unavailable\n", $_); } }
sub select_data { my @list = grep { $_->{available} } @DATA; my $gcd = bgcd(map { $_->{weight} } @list); my $max = max(map { $_->{weight} } @list);
while (1) { $i = ($i + 1) % scalar(@list); if ($i == 0) { $cw = $cw - $gcd; if ($cw <= 0) { $cw = $max; return undef if ($cw == 0); } } if ($list[$i]->{weight} >= $cw) { return $list[$i]; } } }
実行結果。
1 C 2 B 3 C 4 A 5 B 6 C 7 A 8 B 9 C 10 E
ラウンドロビンは、単純に順番に割当をおこなうアルゴリズムなので、結果には規則性があります。なので、『くじ』のような当たるプログラムには向きません。
複数のなかからひとつを選ぶ場合、バカのひとつ覚えのように、なにかとランダム関数を使ってしまうのですが、目的に応じて戦略は変えるべき、というのを改めて感じたのでした。（ランダムが実はランダムじゃないという話も含めて）
![お問い合わせ: deftrash[at]gmail.com](http://www.deftrash.com/blog/images/copyright.png){kind=small}