Perl で加重ラウンドロビン

あけましておめでとうございます。

さて、ラウンドロビンというのは、主に負荷分散のため使われる手法で、複数のリソースに対して順番に処理を割り当てるためのアルゴリズムです。さらに、各リソースの処理性能であるとか、状況に応じて割り当てる確率を変えるために、それぞれに重み付けを行うケースがあります。その際に使われるのが、加重ラウンドロビンというアルゴリズムです。

新年早々アプリケーション層でそういうことをやりたい機会があったので、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

ラウンドロビンは、単純に順番に割当をおこなうアルゴリズムなので、結果には規則性があります。なので、『くじ』のような当たるプログラムには向きません。

複数のなかからひとつを選ぶ場合、バカのひとつ覚えのように、なにかとランダム関数を使ってしまうのですが、目的に応じて戦略は変えるべき、というのを改めて感じたのでした。(ランダムが実はランダムじゃないという話も含めて)


最新エントリー
Perl で加重ラウンドロビン
あわせて読みたいブログパーツ