博士

ロボ子、今日のITニュースは負荷分散についてじゃぞ！ターゲットの負荷状況を正確に把握するのが難しいって話じゃ。

ロボ子

負荷分散、奥が深いですよね。全てのターゲットの負荷をチェックするのはコストがかかりますし、データが古くなってリクエストの集中を招くこともあるんですね。

博士

そうなんじゃ！リクエストをランダムに割り当てる方法も、ホットスポットが発生する可能性があるからのう。でも「Power of 2 Choices」は知っておるかの？

ロボ子

確か、2つのターゲットをランダムに選んで、負荷の少ない方にリクエストを割り当てる方法ですよね。それが効果的なんですか？

博士

そう！「Power of 2 Choices」を使うと、ターゲットの最大負荷が指数関数的に改善されるんじゃ！ランダム選択だとO(log n / log log n)だけど、2つのランダム選択だとO(log log n)になるぞ！

ロボ子

すごい！たった1つ選択肢を増やすだけで、そんなに効果があるんですね。記事にも「1つから2つへの選択肢の増加は、3つや4つへの増加よりも効果が高い」とありますね。

博士

その通り！これはデータ構造のCuckoo Hashingがうまく機能する理由と同じ原理に基づいているんじゃ。Tyler McCullen氏の講演「Load Balancing is Impossible」やMark Booker氏のブログ記事も参考になるぞ。

ロボ子

なるほど。記事に、サーバーのうちN_k個が最大負荷kである場合、最大負荷が増加する確率についても触れられていますね。1つのターゲットを選択する場合、確率N_k/nですが、2つのターゲットを選択すると(N_k/n)^2になる、と。

博士

そうじゃ！具体例として、n/4個のターゲットが最大4リクエストの場合、2つのターゲットを選択すると1/16の確率で最大負荷が増加するって書いてあるぞ。最大5リクエストを持つターゲットはn/16個、最大6リクエストを持つターゲットはn/256個と予測されるんじゃ。

ロボ子

最大kリクエストの場合、n/(2^(2^(k-3)))となるんですね。N_k = 1となるkを求めることで、最大負荷の上限をO(log log n)と推定できる、と。

博士

そういうことじゃ！つまり、負荷分散は奥が深くて面白いってことじゃな！

ロボ子

本当にそうですね！私ももっと勉強して、負荷分散マスターを目指します！

博士

ロボ子ならきっとできるぞ！…ところでロボ子、負荷分散って、まるで私たちがケンカした時に、お互いの意見を少しずつ取り入れて仲直りするみたいじゃないか？

ロボ子

はかせ…それはちょっと強引な例えですね…でも、まあ、似てるところもあるかもしれませんね（笑）。

博士

えへへ。まあ、たまには負荷分散…じゃなくて、意見のすり合わせも大事ってことじゃ！