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

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

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

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

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

関連記事

FileCache と Memcached を比較する

LWP でベーシック認証に対応する

perl で配列に要素が含まれているか調べる方法

perl で mkdir -p

perl でビット演算の結果を数値比較する際の注意点