NGINXと「2つの選択肢の力」負荷分散アルゴリズム

Owen Garrettプロダクトマネジメント担当シニアディレクター

新しいユースケースでは、新たな負荷分散アルゴリズムが必要になる場合があります。そこで、NGINX Plus R16とNGINX Open Source 1.15.1に、分散型ロードバランサーに特に適した新しい手法として、「2つの選択肢の力」アルゴリズムを実装しました。

新しい負荷分散アルゴリズムが必要な理由

従来の負荷分散方式（最小接続数など）は、負荷分散対象ノードの状態を完全に把握できる単一のアクティブなロードバランサーを運用する場合に、非常に効果的です。「2つの選択肢の力」アプローチは、単一のロードバランサーではそれほど効果的ではありませんが、複数の独立したロードバランサーへスケールアウトする際に発生し得る、望ましくない「群集行動」を巧みに回避します。

このシナリオは、高パフォーマンス環境でスケールアウトする場合に限らず、複数のプロキシがそれぞれ同じサービスインスタンス群へのトラフィックを負荷分散するコンテナ環境でも見られます。

このシナリオの一般的な例として、KubernetesでNGINX Ingress Controllerを使用し、Kubernetesノードごとに1つの負荷分散インスタンスを配置する場合があります。

このアルゴリズムは、Michael Mitzenmacherが1996年の博士論文『ランダム化ロードバランシングにおける2つの選択肢の力』で初めて提唱したことから、文献では「power of two choices」と呼ばれています。NGINXおよびNGINX Plusでは、Randomロードバランシングアルゴリズムの一種として実装されているため、「Random with Two Choices」とも呼ばれます。

「Power of Two Choices」の仕組み

まずは、よくあるかもしれない状況から考えてみましょう。長時間の国際線を降りたばかりで、ほかの400人の旅行者とともに、混雑した到着ロビーへ足を踏み入れたところです。

多くの空港では、到着ロビーに案内係を配置しています。案内係の役割は、各旅行者を入国審査カウンターごとに設けられた複数の列のいずれかへ誘導することです。この案内係をロードバランサーに例えると、次のようになります。

• 皆さんとほかの旅行者は、リクエストに相当し、それぞれができるだけ早く処理されることを望んでいます。
• 入国審査カウンターは（バックエンド）サーバーに相当し、それぞれが滞留しているリクエストを処理します。
• 案内係は、リクエストごとに最適なサーバーを選択することで、効率を最大限に高めます。
• ガイドが最適なサーバーを選択するために使用できる方法は、負荷分散アルゴリズムに対応しています。

到着ロビーのような分散型負荷分散のシナリオで、考えられるいくつかのアルゴリズムがどの程度うまく機能するかを見てみましょう。

ラウンドロビン負荷分散

ラウンドロビンは、単純な負荷分散方式です。この方式では、案内係が各列を順番に選択します。最初の旅行者を列Aに、次の旅行者を列Bに案内し、以降も同様に振り分けます。旅行者を最後の列に案内すると、列Aから同じ手順を繰り返します。ラウンドロビンは、NGINXで使用されるデフォルトの負荷分散アルゴリズムです。

この方法は、いずれかの列で遅れが生じるまでは問題なく機能します。たとえば、旅行者の1人が書類を紛失していたり、入国審査官に不審を抱かれたりする場合があります。

列が進まなくなっても、案内係はその列に旅行者を振り分け続けます。待ち行列はどんどん長くなり、待ちきれない旅行者の不満は募るばかりです！

最小接続数ロードバランシング

もっと優れた方法があります。案内係が各列を監視し、旅行者が到着するたびに、最も短い列へ誘導します。この方法は、NGINXのLeast Connections負荷分散方式に相当します。この方式では、新しいリクエストを、未処理（キュー待ち）のリクエストが最も少ないサーバーに割り当てます。

最小接続数ロードバランシングは、処理にかかる時間が異なるトラベラーにも非常に効果的に対応します。キューの長さを均等に保ち、滞留しているキューにリクエストがさらに追加されるのを防ぎます。

最短時間ロードバランシング

これまで見てきたように、乗客によって手続きにかかる時間は異なり、列によっても処理の速さに差があります。たとえば、ある入国審査官はコンピューターの不具合により旅行者の手続きに時間がかかるかもしれません。また、別の審査官は細部まで厳密に確認し、旅行者に詳しく質問することがあります。一方、経験豊富な審査官であれば、旅行者の手続きをより迅速に進められる可能性があります。

各入国審査ブースの上にカウンターを設置し、たとえば直近10分間に何人の旅行者を処理したかを表示するとしたらどうでしょうか。案内係は、列の長さと処理速度に基づいて、旅行者を適切な列へ誘導できます。これは負荷をより効果的に分散する方法であり、NGINX PlusのLeast Time負荷分散アルゴリズムは、まさにこの仕組みを採用しています。

このアルゴリズムは、NGINX Plusの「Extended Status」メトリクスで収集される追加データを利用するため、NGINX Plus固有のものです。各サーバーへのレイテンシーが予測不能に変動する可能性があり、キューの長さだけでは遅延を推定できないクラウド環境や仮想環境で特に効果を発揮します。

複数のガイドを使用すると、すべてが破綻する

ここまでは、到着ロビーの待ち行列と応答時間をすべて把握している案内係（つまり、ロードバランサー）が1人いる状況を見てきました。この案内係は、把握している情報に基づいて、旅行者一人ひとりに最適な選択をしようとします。

ここで、複数の案内係がそれぞれ独立して旅行者を誘導する場合を考えてみましょう。各案内係は、待ち行列の長さと待ち時間を個別に把握しており、自分が各待ち行列に誘導した旅行者だけを考慮します。

このシナリオでは、すべての案内係が、ある待ち行列が一時的に短く、流れも速いことに気づき、全員がその待ち行列に旅行者を誘導するという望ましくない動作が起こりがちです。シミュレーションによると、この「群集行動」によって旅行者の振り分けに偏りが生じ、不公平になります。同様に、複数の独立したロードバランサーを使用すると、どの「最適選択」アルゴリズムを使用しても、一部のアップストリームサーバーに過剰な負荷がかかる可能性があります。

「Power of Two Choices」負荷分散アルゴリズム

その解決策となるのが、「2つの選択肢の力」と呼ばれる負荷分散アルゴリズムです。不完全なデータに基づいて絶対的に最善の選択肢を求めるのではなく、このアルゴリズムでは2つのキューをランダムに選び、そのうち良い方を選択することで、より悪い選択肢を回避します。

「2つの選択肢の力」は、効率的に実装できます。毎回すべてのキューを比較して最適なものを選ぶ必要はなく、2つだけを比較すれば済みます。また、直感に反するかもしれませんが、規模が大きくなるほど、最適な選択肢を選ぶアルゴリズムよりも効果的に機能します。最も状態の悪いキューを避け、ある程度ランダムにトラフィックを分散するというシンプルな方法で、望ましくない群集行動を回避します。

NGINXおよびNGINX Plusでの「Power of Two Choices」の使用

NGINXとNGINX Plusでは、「Power of Two Choices」負荷分散方式はRandomアルゴリズムの一種として実装されているため、Random with Two Choicesと呼びます。

NGINX Open Sourceでは、Random with Two Choicesは、ランダムに選択した2台のサーバーのうち、現在のアクティブ接続数が少ない方を選択します。これは、Least Connectionsアルゴリズムと同じ選択基準です。（これはNGINX Plusでもデフォルトのアルゴリズムであり、least_connパラメーターを追加して明示的に設定することもできます。）

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two; 
}

NGINX Plusは、least_timeパラメーターもサポートしています。このパラメーターでは、Least Timeアルゴリズムと同じ選択基準が使用されます。このアルゴリズムと同様に、さらに次のいずれを考慮するかを選択します。

• The time to receive the レスポンスヘッダーの受信時間（least_time=header）
• 次のスニペットに示すように、レスポンス全体を受信するまでの時間（least_time=last_byte）です。Least Time基準は、各アップストリームサーバーへのレイテンシーが変動する可能性がある場合に最適です。

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two least_time=last_byte; # use header or last_byte
}

まとめ

NGINXとNGINX Plusは、さまざまな負荷分散方式をサポートしています。本記事では、決定論的な「Hash」方式と「IP Hash」方式については取り上げていません。

Least Connections方式（NGINX PlusではLeast Time方式も含む）は、各ノードに割り当てられたワークロードと過去のパフォーマンスをロードバランサーが完全に把握している場合、負荷を非常に効果的に分散できます。一方、複数のロードバランサーがリクエストを割り当て、それぞれがワークロードとパフォーマンスを部分的にしか把握していない場合、効果は低下します。

「Power of two choices」は偏りのあるランダムアルゴリズムを使用し、各ロードバランサーが不完全または遅延した情報しか把握できない場合でも、負荷分散に有効であることが実証されています。また、リクエストごとに最適な判断を下そうとする他のアルゴリズムで見られる「群集行動」を回避します。

非常に高いパフォーマンスが求められる環境や、分散ロードバランシングのシナリオでは、「power of two choices」をNGINXに実装したRandom with Two Choicesの使用をご検討ください。Kubernetesで複数のIngressコントローラーを使用する場合が、適切なユースケースです。

著者について

Owen Garrettプロダクトマネジメント担当シニアディレクター

Owen Garrettのその他のブログ記事