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

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

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

最小接続などの従来の負荷分散方法は、負荷分散されたノードの状態を完全に把握できる単一のアクティブ ロード バランサーを操作する場合に非常に有効に機能します。 「2 つの選択肢の力」アプローチは、単一のロード バランサーではそれほど効果的ではありませんが、複数の独立したロード バランサーにスケール アウトするときに発生する可能性のある、悪いケースの「群衆行動」を巧みに回避します。

このシナリオは、高パフォーマンス環境でスケールアウトするときにのみ見られるものではなく、複数のプロキシがそれぞれ同じサービス インスタンス セットにトラフィックを負荷分散するコンテナー化された環境でも見られます。

このシナリオの一般的なインスタンスは、Kubernetes ノードごとに 1 つのロード バランシング インスタンスを備えたNGINX Ingress Controller for Kubernetes を使用する場合に発生します。

このアルゴリズムは、Michael Mitzenmacher の 1996 年の論文「ランダム化負荷分散における 2 つの選択の力」で初めて説明されたため、文献では「2 つの選択の力」と呼ばれています。 NGINX および NGINX Plus では、ランダム ロード バランシング アルゴリズムのバリエーションとして実装されているため、ランダム 2 つの選択肢とも呼ばれます。

「2つの選択の力」はどのように機能しますか?

まずは、よくある状況から始めましょう。 あなたは長い国際飛行を終えて着陸し、他の 400 人の旅行者とともに混雑した到着ロビーに足を踏み入れました。

多くの空港では到着ロビーにガイドを配置しています。 彼らの仕事は、各入国審査デスクごとに用意された複数の列の 1 つに各旅行者を誘導することです。 ガイドをロードバランサーとして考えると、次のようになります。

• あなたと他の旅行者はリクエストであり、それぞれができるだけ早く処理されることを望んでいます。
• 入国審査デスクは（バックエンド）サーバーであり、それぞれがバックログのリクエストを処理します。
• ガイドは、各リクエストに最適なサーバーを選択することで効率を最大化します。
• 最適なサーバーを選択するためのガイドで使用できる方法は、負荷分散アルゴリズムに対応しています。

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

ラウンドロビン負荷分散

ラウンドロビンは負荷分散に対する単純なアプローチです。 このアプローチでは、ガイドが各キューを順番に選択します。最初の旅行者はキュー A に誘導され、次の旅行者はキュー B に誘導されます。 トラベラーが最後のキューに誘導されると、キュー A からプロセスが繰り返されます。ラウンドロビンは、 NGINX が使用するデフォルトの負荷分散アルゴリズムです。

このアプローチは、キューの 1 つに遅延が発生するまでは適切に機能します。 旅行者の 1 人が書類を紛失したか、入国審査官に疑いを抱かせた可能性があります。

列は動きを止めますが、ガイドは旅行者をその列に割り当て続けます。 バックログはどんどん長くなります – これではせっかちな旅行者たちは幸せになれません!

最小接続負荷分散

もっと良いアプローチがあります。 ガイドは各列を監視し、旅行者が到着するたびに、その旅行者を最も短い列に送ります。 この方法は、NGINX のLeast Connectionsロード バランシング メソッドに似ており、各新しいリクエストを、未処理 (キューに入れられた) リクエストが最も少ないサーバーに割り当てます。

最小接続負荷分散は、処理に異なる時間を要する旅行者に非常に効果的に対処します。 キューの長さのバランスを取り、停止したキューにさらにリクエストが追加されないようにします。

最小時間負荷分散

乗客によって処理にかかる時間が異なり、また、列によっては他の列よりも処理が速かったり遅かったりすることがわかりました。 たとえば、ある入国審査官はコンピューターに問題があり、旅行者の手続きが遅くなる場合があります。また、別の審査官は細かいことにこだわり、旅行者に非常に厳しく質問する場合があります。 他の職員は非常に経験豊富で、旅行者をより迅速に処理できるかもしれません。

各入国審査ブースの上に、例えば過去 10 分間に何人の旅行者が処理されたかを示すカウンターがあったらどうでしょうか? 次に、ガイドは列の長さと処理の速さに基づいて旅行者を適切な列に誘導できます。 これは負荷を分散するより効果的な方法であり、NGINX Plus のLeast Time負荷分散アルゴリズムが行うことです。

このアルゴリズムは、NGINX Plus の拡張ステータスメトリックで収集された追加データに依存するため、NGINX Plus に固有のものです。 これは、各サーバーへの待ち時間が予測できないクラウド環境や仮想環境で特に効果的であり、キューの長さだけでは遅延を推定するのに十分ではありません。

複数のガイドがあるとすべてが崩壊する

これまで、到着ホールの待ち行列と応答時間を完全に把握できるガイド (つまり、ロード バランサー) が 1 つありました。 そのガイドは、自分が知っている情報に基づいて各旅行者にとって最善の選択をしようとします。

ここで、複数のガイドがいて、それぞれが独立して旅行者を案内するとしたら何が起こるか考えてみましょう。 ガイドはキューの長さとキューの待ち時間を個別に表示します。ガイドが考慮するのは、各キューに送る旅行者のみです。

このシナリオでは、すべてのガイドが 1 つのキューが一時的に短くて速いことに気づき、全員が旅行者をそのキューに送るという望ましくない動作が発生しやすくなります。 シミュレーションでは、この「群集行動」によって旅行者が不均衡かつ不公平な形で分配されることが示されています。 同様に、どの「最適な選択」アルゴリズムを使用しても、複数の独立したロード バランサによって一部の上流サーバーに過負荷がかかる可能性があります。

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

解決策は、「2 つの選択肢の力」負荷分散アルゴリズムにあります。 不完全なデータを使用して絶対的に最良の選択を行う代わりに、「2 つの選択肢の力」を使用すると、2 つのキューをランダムに選択し、2 つのうちより良いオプションを選択して、より悪い選択を回避します。

「2つの選択肢の力」は実装に効率的です。 毎回最適なオプションを選択するためにすべてのキューを比較する必要はありません。代わりに、2 つのキューを比較するだけで済みます。 そして、直感に反するかもしれませんが、これは、最適選択アルゴリズムよりも大規模に機能する傾向があります。 最悪のキューを回避し、ある程度ランダムにトラフィックを分散するという単純なアプローチにより、望ましくない群集行動を回避します。

NGINX と NGINX Plus で「2 つの選択肢の力」を使用する

NGINX および NGINX Plus では、「2 つの選択肢の累乗」負荷分散方式がランダム アルゴリズムのバリエーションとして実装されているため、これを「2 つの選択肢を持つランダム」と呼びます。

NGINX オープンソースでは、Random with Two Choices は、現在アクティブな接続が少ないサーバーに基づいて、ランダムに選択された 2 つのサーバーのいずれかを選択します。 これは、最小接続アルゴリズムで使用される選択基準と同じです。 (これは NGINX Plus のデフォルトのアルゴリズムでもあり、 least_connパラメータを追加することで明示的に設定できます。)

アップストリーム サービス 1 { ゾーン サービス 1 64k; サーバー 192.168.1.11; サーバー 192.168.1.12; サーバー 192.168.1.13;ランダム 2 ; }

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

• レスポンスヘッダーを受信するまでの時間 ( least_time=header )
• 次のスニペットのように、完全な応答を受信するまでの時間 ( least_time=last_byte )。 最小時間基準は、各アップストリーム サーバーへの待ち時間が変化する可能性がある状況に最適です。

アップストリーム service1 { ゾーン service1 64k; サーバー 192.168.1.11; サーバー 192.168.1.12; サーバー 192.168.1.13;ランダム 2 least_time=last_byte ; # ヘッダーまたは last_byte を使用 }

結論

NGINX と NGINX Plus はさまざまな負荷分散方式をサポートしていますが、この記事では決定論的ハッシュ方式とIP ハッシュ方式については考慮していません。

最小接続（NGINX Plus の場合は最小時間）方式は、ロードバランサーが各ノードに割り当てられたワークロードとその過去のパフォーマンスを完全に把握している場合、負荷分散に非常に効果的です。 複数のロード バランサがリクエストを割り当てており、それぞれのロード バランサがワークロードとパフォーマンスを不完全に把握している場合、効果は低くなります。

「2 つの選択肢のパワー」は、偏りのあるランダム アルゴリズムを使用し、各ロード バランサーのビューが不完全または遅延している場合に負荷を分散するのに効果的であることが実証されています。 これは、すべてのリクエストに対して最善の決定を下そうとする他のアルゴリズムが示す「群衆行動」を回避します。

非常に高性能な環境や分散型負荷分散シナリオ向けに、NGINX の「2 つの選択肢の力」の実装である Random with Two Choices を検討してください。 Kubernetes 上で複数のIngress コントローラーを使用する場合、適切なユースケースが発生します。