割り当てるサーバが3つ「A, B, C」あって、ユーザが9人(0から8の連番のID)いる場合を考えます。
単純なラウンドロビンだと、何も考えずに「割った余り」を使って割り振ります。この場合、「ユーザIDを3で割ってその余りが0のものをAに、1のものをBに、2のものをCに」と割り振ります。結果として、Aは0,3,6、Bは1,4,7、Cは2,5,8が割り振られます。
これでも問題がない場合は多いでしょう。しかし、各ユーザのもつデータ量にばらつきがありかつデータ量によって負荷が変わる場合には、データの量に着目して振り分ける方法が望ましいでしょう。
下記のデータのケースを考えます。
このときに、ユーザをデータ量の降順でソートし上位から単純に「A, B, C」, 「A, B, C」, 「A, B, C」…の順で割り振ると必ず、Aが最もデータ量が多くCが最も少ない状態になります。
ABC-ABC順
A = 90 + 50 + 20 = 160
B = 80 + 40 + 10 = 130 C = 70 + 30 + 0 = 100 ※サーバ間で最大60の差 これに対し、「A, B, C」, 「C, B, A」, 「A, B, C」…のように振り子のように割り振ると、偏りが小さくなります。
ABC-CBA順
A = 90 + 30 + 20 = 140
B = 80 + 40 + 10 = 130 C = 70 + 50 + 0 = 120 ※サーバ間で最大20の差 直線的なデータの場合このような差しか生まれませんが、データにばらつきが大きいときほど差は拡大します。
単純振り分け
A = 250 + 60 + 2 = 312
B = 180 + 30 + 1 = 211 C = 70 + 5 + 0 = 75 振り子方式
A = 250 + 5 + 2 = 257
B = 180 + 30 + 1 = 211 C = 70 + 60 + 0 = 130 1人の最大値が250なのでまぁこんなもんでしょう。 振り子方式を実現するロジックですが、以下のコードになります。変数aは「0～データ数の2倍」の範囲で変動します。そして(おおむね)「a - データ数」を行い絶対値を取ることで、「4, 3, 2, 1, 1, 2, 3, 4, 4, ...」のような振り子方式の値をとることができます。
// JavaScript
/**
* dataNo - ソート後に付与した番号
* targetNum - 振り分け先の数
*/
function roundRobin(dataNo, targetNum) {
var a = dataNo % (targetNum * 2);
return Math.ceil(Math.abs(a - targetNum + 0.5));
}
for (var i = 0; i < 20; i++) {
alert(roundRobin(i, 4));
}
※0.5を加算している部分とceilしている部分は補正です。「4, 3, 2, 1, 0, 1, 2, 3, 4, 3, ...」のような値になってしまいます。2011/10/07
|
Code Tips >