このシステム、どんだけ待たせるんだよ!~そんな時の待ち行列

このエントリーをはてなブックマークに追加
こんにちわ。朝と昼の寒暖の激しさに着るものを毎日迷う開発エンジニアのsugimotoです。
今回はパフォーマンス関連でちょっと調べた待ち行列について書いてみます。


〇動機

弊社サービスのShanonMarketingPlatformは、レスポンスタイム向上のために、リクエスト時に行っていた処理の一部を、リクエストとは切り離して非同期で実行するようにしています。

そのためにGearmanを使用しており、切り離した処理はGearmanのワーカーとして実行しています。

最近、そのワーカーで処理が詰まることが多くなってきたことと、今後更に非同期化を進めていった時のキャパシティプランニングにも役立てたいと思い、待ち行列について勉強してみました。

待ち行列の詳しい説明についてはWebで調べてもらった方が遥かに良いので、ここでは必要な説明のみ軽くします。


〇用語
λ・・・単位時間当たりの平均到着数
μ・・・1窓口での単位時間当たりの平均処理数
L・・・系内にいる人(タスク)の平均数
Lq・・・サービスを待っている人(タスク)の平均数
W・・・系の中の平均滞在時間
Wq・・・到着してからサービスを受けるまでの時間(待ち時間)

〇ケンドールの記号
A/B/C(N)で表記される待ち行列モデルの表現方法です。
A・・・到着分布
B・・・処理分布
C・・・窓口数
N・・・系内数
情報処理試験とかにあるM/M/1はM/M/1(∞)のことです。
到着・処理分布のMは指数分布を表し、処理レーン数は1です。
M/M/1(1)は電話のように窓口が塞がっていたら切れてしまうものです。N=1は処理中のもののみということです。

M/M/1(∞)モデル
まずは情報処理試験とかで出てくるモデルです。



レジ待ちとかこれに該当します。
公式は以下の通り。



ここまで書いてなんですが、今回の話にはM/M/1(∞)は関係ないんです。ワーカーの数(窓口数)が1ということはないので。。。


M/M/S(∞)モデル


待ち行列が1個で窓口が複数あるタイプです。Webサーバとか今回のワーカーのようなものがこれに当たります。
公式は以下の通り。




だそうです。



〇ワーカーの数を求める
ここまでで準備は終わりです。
今回の場合だと知りたいのは「ワーカー数(窓口数)をいくつにすべきか?」です。
到着分布と処理分布は指数分布とします。
系内数は∞とします。Gearmanのキューはメモリ上にあり、メモリは有限ですが相当多くのタスクを入れられるので∞として問題ないと思います。


λ、μは分かるのでM/M/S(∞)の公式からSを求めたいのですが、この公式をSの方程式として解くのは難しいので、Sに値をいくつかあてはめ、その中で最適なものを選択するようにします。

ということでプログラムを書いてみました。
慣れ親しんだPerlスクリプトです。



#!/usr/bin/perl

use strict;
use warnings;

use Text::SimpleTable;

my $LABMDA = 200000;
my $MU = 7200;
my $S;
my $RHO;

my $SECOND_PER_HOUR = 3600;
my $ROUNDOFF_THRESHOLD = 1000000;

main();
exit(0);

sub main {
    $S = int($LABMDA / $MU) + 1;
    $RHO = $LABMDA / ($MU * $S);
    
    my @result;
    for (my $i = $S; $i < $S + 20; $i++) {
        my $P0 = 1 / (_A($i) + _B($i));
        my $Lq = $RHO * _power($S * $RHO, $S) / (_factorial($S) * _power(1 - $RHO, 2)) * $P0;
        my $L = $Lq + $S * $RHO;
        my $Wq = $Lq / $LABMDA * 3600;
        my $W = $Wq + 1 / $MU * 3600;
        push(@result, [$i, $Lq, $L, $Wq, $W]);
    }
    
    _format(\@result);
}

sub _A {
    my($a) = @_;
    
    my $result = 0;
    for (my $i = 0; $i < $a; $i++) {
        $result += _power($a * $RHO, $i)/_factorial($i);
    }
    
    return $result;
}

sub _B {
    my($a) = @_;
    
    my $result = _power($a * $RHO, $a) / (_factorial($a) * (1 - $RHO));
    
    return $result;
}

sub _power {
    my($a, $b) = @_;
    
    return $a ** $b;
}

sub _factorial {
    my($a) = @_;
    
    my $result = 1;
    while ($a > 0) {
        $result *= $a;
        $a--;
    }
    
    return $result;
}

sub _format {
    my($array) = @_;
    
    my $t = Text::SimpleTable->new([4, "S"], [10, "Lq"], [10, "L"], [10, "Wq(s)"], [10, "W(s)"]);
    foreach my $row (@{$array}) {
        $t->row($row->[0], _round_off($row->[1]), _round_off($row->[2]), _round_off($row->[3]), _round_off($row->[4]));
    }
    
    print($t->draw());
}

sub _round_off {
    my($number) = @_;
    
    return int($number * $ROUNDOFF_THRESHOLD + 0.5)/$ROUNDOFF_THRESHOLD;
}

今回使用する値は以下の通りです。
・1時間当たりのタスク数λ=200000
・1時間当たりの1ワーカーの処理数μ=7200

結果は以下の通りです。





キューの中の待ちを1タスク以下にするのならワーカーは33個以上であればいいことになります(Lqの値より)。


ただ、これはあくまで平均の待ち数を1以下にするために必要なワーカー数であって、常に1以下に保っていたいのならもう少しワーカーを多めにする必要があると思います。
今回は単純にM/M/S(∞)の公式に当てはめて求めていますが、もう少し見直すところはあります。
今後は以下の点についてもう少し調べて検証してみたいと思ってます。
・到着分布は指数分布で良いとして、処理分布をアーラン分布にしてみる
・行列長や待ち時間の平均だけでなく分散も利用してワーカーの数を決める
次回のブログで検証結果をご報告できれば。。。

※当然のことながらワーカーの数は今回のことだけで決まるわけではなく、負荷やリソースの利用状況等の情報を使って決めますのであしからず。

次の記事
« Prev Post
前の記事
Next Post »
Related Posts Plugin for WordPress, Blogger...