2009年11月アーカイブ

Request Counting は、lbmethod=byrequests とすると有効になる。このスケジューリングアルゴリズムを左右するパラメータは、lbfactor と lbstatus の２つ。

設定パラメータ lbfactor は、ワーカーに割り当てる仕事量を意味する(クオータ)。lbfactor は正規化されるので、Worker[A].lbfactor = 4, Worker[B].lbfactor = 2 とした場合、2:1 の比率で仕事が割り振られる事になる。ドキュメントによれば、割り振られる順序に影響する様で、[Worker[A], Worker[A], Worker[A], Worker[A], Worker[B], Worker[B]] という順序にはならず、[Worker[A], Worker[A], Worker[B]] という順序になるとの事。正規かによって、A=4, B=2 は A=2, B=1 と全く同じになるという事らしい。

スケジューリング処理の内部パラメータ lbstatus は、ワーカーにどの程度の優先度で仕事を割り当てなければならないかを意味する。

ここで言うワーカーはロードバランサのメンバを意味し、通常はリクエストを割り振られるリモートホストの事。

スケジューリングは以下の様にして行われる。

for each worker in workers
    worker lbstatus += worker lbfactor
    total factor    += worker lbfactor
    if worker lbstatus > candidate lbstatus
        candidate = worker

candidate lbstatus -= total factor

まず、各ワーカーの優先度(lbstatus)を調整し、仕事を割り当てるべきワーカーとして優先度(lbstatus)が最も高いものを選ぶ。最後に、選ばれたワーカーの優先度(lbstatus)からクオータ(lbfactor)の総量を差し引く事で、優先度(lbstatus)の比率を調整する。これを繰り返す事で、設定されているクオータ(lbfactor)に従った割り振りを実現している。

A,B,C,D という４つのワーカーが存在し、それぞれ lbfactor=25 と設定されているとする。以下はそれらの初期状態を示している。

#(0)
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus   0   0   0   0

最初のスケジューリングによって、以下の様にパラメータが変動する。

#(1)
           v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -75  25  25  25

lbstatus の総量は変わらず、優先度の調整がされている事がわかる。以降のスケジューリングによる変遷を以下に示す。

#(2)
               v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -50 -50  50  50
#(3)
                   v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -25 -25 -25  75
#(4)
                       v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus   0   0   0   0

25:25:25:25 = 1:1:1:1 と正規化された挙動になっている事がわかる。つまり、[A,B,C,D,...] という順序の繰り返しでワーカーが選択される。

途中で、C が無効になった場合は、以下の様に変遷する。

#(2)
               v
worker     A   B   C   D
lbfactor  25  25   0  25
lbstatus -50 -50   0  50
#(3)
                       v
worker     A   B   C   D
lbfactor  25  25   0  25
lbstatus -25 -25   0 -25
#(4)
           v
worker     A   B   C   D
lbfactor  25  25   0  25
lbstatus -75   0   0   0
#(5)
               v
worker     A   B   C   D
lbfactor  25  25   0  25
lbstatus -50 -50   0  25
#(6)
                       v
worker     A   B   C   D
lbfactor  25  25   0  25
lbstatus -25 -25   0 -25

さらに C が復旧した場合は、以下の様に変遷する。

#(7)
                       v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -25 -25   0 -25
#(8)
           v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus-100   0   0   0
#(9)
               v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -75 -75  25  25
#(10)
                   v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -50 -50 -50  50
#(11)
                       v
worker     A   B   C   D
lbfactor  25  25  25  25
lbstatus -25 -25 -25 -25

ドキュメントの例では、優先度(lbstatus)の総量が変化していないので、何かしらの調整が入っているのかもしれないが、調整がなかったとしても、ワーカー間での比率は変わらないはず。よくわからないので、ソース(2.2.14)を感じ取る(処理は大雑把に関数名でわかった気になる)。

まず、各ワーカーは init_balancer_members 関数で初期化される。初期化処理の順序は、ワーカー配列の並びに従い、ワーカー配列への追加順序は、設定の記述順序に従う。初期化の中で、ワーカーの lbstatus と lbfactor に、設定パラメータの lbfactor (デフォルト 1)が代入されている。

この時点で、先述の lbstatus 遷移の例は間違っている気がする。初期時点で、lbfactor の値がセットされている様子。

proxy_balancer_pre_request 関数内で、find_best_worker 関数が呼ばれ、その中で設定値 lbmethod に応じた関数を利用して、仕事を割り当てるべきワーカーを選択する。Request Counting (lbmethod=byrequests) では、find_best_byrequests 関数が呼ばれる。

選択を行う前の候補ワーカーは、ワーカー配列の先頭。先述の選択時のワーカー走査は、初期か処理同様にワーカー配列の並び順序に従う。

ワーカーが有効かどうかは、PROXY_WORKER_IS_USABLE で判断される様子。この戻り値が偽である場合に呼ばれるのが ap_proxy_retry_worker 関数。この関数の中では、lbstatus の調整を行っている様な様子は見られない。mod_proxy_balancer.c や proxy/ 内のソースから lbstatus を探しても、無効ワーカーに関する特別な調整は見当たらなかった。感じ取った範囲では、特別な調整はしていないのではないかと思う。

調整がなかったとしても、先述の例による手計算では、比率的に問題にならないはずなので、これ以上は調べない。

Weighted Traffic Counnting は、lbmethod=bytraffic とすると有効になる。基本的には Request Counting と同様だが、以下の点が異なる。

lbfactor は、どれだけのバイト数のトラフィック量を、そのワーカーに処理させたいかを意味する。この値も正規化される。リクエスト数を単純に数えるのではなく、どれだけの転送量を処理したかを数える。

ドキュメントには、上記程度の内容しか書かれていない。心もとないので、ソースを感じ取る。ワーカー選択の関数だけ、確認する事にする。

使われる関数は、find_best_bytraffic 関数。

各ワーカーを走査し、それぞれについて、ワーカーが処理した転送量と読み込んだ量を lbfactor で割り、その和をトラフィック量とする。そして、トラフィック量が最も最小のワーカーが選択される。

先述のドキュメント内にあった疑似コードに従うと、以下の様に書ける(はず)。

for each worker in workers
    worker traffic = (worker transferred + worker read) / worker lbfactor
    if worker traffic < current minimum traffic
        candidate = worker
        current minimum traffic = worker traffic

トラフィック量をそのワーカーの lbfactor で割る事で、概ね公平にリクエストを分散させている。

mod_proxy_balancer のスケジューリングアルゴリズムをまじめに知っておこうと思ったきっかけは、期待通りに振り分けられていないのではないかという話を聞いたから。

「ある程度の時間で見ると、公平に振り分けられているが、ある瞬間で見ると偏りが見られる事がある。何事か。」という事があったらしい。

ここまでの調査を元に考えると、Request Counting (byrequests) を採用していれば、そのような問題は起こらないのではないかと思う。一方で、Weighted Traffic Counnting (bytraffic) を採用していると、トラフィック量次第なので、偏る事は十分考えられる。

改めてつついてみると、どうやら bytraffic を採用している雰囲気が…。