バーチャルサーバーのスケジューリングアルゴリズム

このページはLVSで実装されているスケジューリングアルゴリズムについて書かれています。

ラウンドロビンスケジューリング

ラウンドロビンスケジューリングアルゴリズム、この言葉の意味はラウンドロビン方式で異なるサーバーにネットワークコネクションを持つことです。ラウンドロビンスケジューリングアルゴリズはコネクションや応答時間に関係なく平等にすべてのリアルサーバーを処理することです。ラウンドロビンDNSもこのように動作しますが、若干異なります。ラウンドロビンDNSは一つのドメインを異なるIPアドレスに分散させるが、詳細なスケジューリングはホストベースで、DNSのキャッシングは効果のあるアルゴリズムを妨げ、リアルサーバー間の重大なダイナミックロードインバランスを導いてしまう。バーチャルサーバーの詳細なスケジューリングはネットワークコネクションベースで、詳細なスケジューリングが原因でラウンドロビンDNSのほうが優れている。

加重ラウンドロビンスケジューリング

加重ラウンドロビンスケジューリングは異なる処理容量でリアルサーバーを処理することができる。サーバーにはそれぞれ負荷をかけることができ、処理容量を整数であらわす。デフォルトの負荷は1だ。例えば、リアルサーバーA,B,C があり、処理容量がそれぞれ4,3,2 だとする。スケジューリングの結果は A->B->C->A->B->C->A->B->A になる。 加重ラウンドロビンスケジューリングの実装でスケジューリングの結果はバーチャルサーバーが変更した加重にしたがって生成されるだろう。ネットワークコネクションはラウンドロビン方式でスケジューリングされた異なるリアルサーバーにつながる。

加重ラウンドロビンスケジューリングはリアルサーバーのネットワークコネクションをカウントする必要がない。だからスケジューリングのオーバーヘッドはダイナミックスケジューリングアルゴリズムより小さくなり、たくさんのリアルサーバーを持つことができる。しかし、もし接続要求の負荷がとても高くなると、リアルサーバー間でダイナミックロードを導くかもしれない。つまり、ほとんどの長い接続要求はリアルサーバーに直接つながる可能性もあるということだ。

ラウンドロビンスケジューリングは加重ラウンドロビンスケジューリングの特例だ。加重が等しいということである。バーチャルサーバールールを変更後、スケジューリングされた結果を生成するオーバーヘッドは些細なもので、それは実際のスケジューリングでオーバーヘッドにならない。だから、ラウンドロビンスケジューリングを一人で実装する必要はない。

最小コネクションアルゴリズム

最小コネクションスケジューリングアルゴリズムは確立されたコネクションの数が一番小さいサーバーにコネクションを張る。これは一種のダイナミックスケジューリングアルゴリズムである。なぜなら、最小コネクションアルゴリズムはダイナミックにサーバー間の生きているコネクションをカウントする必要があるからだ。 同等なパフォーマンスをもったバーチャルサーバーでは、接続要求の負荷がよく変わる時、最小コネクションスケジューリングは円滑に分配する。なぜなら、すべての長い接続要求はサーバーに分配されつ機会がないからだ。

はじめ見た限りでは、最小コネクションスケジューリングも異なる処理容量のサーバーがある時でさえ、よく動作するように思える。なぜなら、速いサーバーは多くのネットワークコネクションをさばくからだ。だが実際、最小コネクションスケジューリングはTCPのTIME_WAIT状態により高いパフォーマンスを出せない。TCPのTIME_WAITは普通2分で、この2分間の間に忙しいWEBサイトでは何千ものコネクションを得る。例えば、AというサーバーがBというサーバーの2倍のパフォーマンスを持っていたとする。サーバーAは何千もの接続要求を処理し、TCPのTIME_WAIT状態で待っている。しかしサーバーBは何千ものコネクションが終わるのをしこたま待っている。だから最小コネクションスケジューリングは異なる処理容量のサーバー間で負荷をうまく均等にすることができない。

加重最小コネクションスケジューリング

加重最小コネクションスケジューリングは最小コネクションスケジューリングのスーパーセットであなたは性能負荷をリアルサーバーごとにつけることができる。高い負荷が与えられたサーバーはどんな時も割合高いコネクションを受けとるだろう。 バーチャルサーバー管理者はリアルサーバーごとに負荷を設定することができ、ネットワークコネクションは負荷の比率によって現在のコネクション数のパーセンテージがスケジューリングされる。デフォルトの負荷は1である。

加重最小コネクションスケジューリングは次のように動作する

リアルサーバーが n 個あったとして、各サーバーが加重 Wi (i=1,..,n) と コネクション Ci (i=1,..,n) と ALL_CONECTIONS Ci (i=1,..,n) の和 で次のネットワークコネクションがサーバー j にやってきたと仮定すると

(Cj/ALL_CONNECTIONS)/Wj = min { (Ci/ALL_CONNECTIONS)/Wi } (i=1,..,n)

この調査で ALL_CONNECTION は変わらないので、Ci をALL_CONNECTIONによって分割する必要がない。最適化されているからだ。

Cj/Wj = min { Ci/Wi } (i=1,..,n)

加重最小コネクションスケジューリングアルゴリズムは最小コネクションよりも余分な分配が必要だ。サーバーが同じ処理容量の時、スケジューリングのオーバーヘッドを最小化するには最小コネクションスケジューリングと加重最小コネクションスケジューリングアルゴリズムの両方を実装させる。


Last updated: 1998/11/20

Created on: 1998/11/20