LVS 負荷分散 (LVS の紹介、3 つの動作モード、10 のスケジューリング アルゴリズム)

LVS の紹介

LVS (Linux Virtual Server) は、Zhang Wensong 博士が主導するオープンソースの負荷分散プロジェクトです。現在、LVS は Linux カーネル モジュールに統合されています。このプロジェクトは、Linux カーネルに IP ベースのデータ要求負荷分散スケジューリング ソリューションを実装します。そのアーキテクチャを図 1 に示します。端末インターネット ユーザーが外部から会社の外部負荷分散サーバーにアクセスすると、端末ユーザーの Web 要求が LVS スケジューラに送信されます。スケジューラは、独自の事前設定されたアルゴリズムに基づいて、バックエンドの特定の Web サーバーに要求を送信することを決定します。たとえば、ポーリング アルゴリズムは、外部要求をバックエンドのすべてのサーバーに均等に分散できます。端末ユーザーの LVS スケジューラへのアクセスはバックエンドの実サーバーに転送されますが、実サーバーが同じストレージに接続され、同じサービスを提供している場合、エンド ユーザーはどの実サーバーにアクセスしても同じサービス コンテンツを受け取ります。クラスター全体はユーザーに対して透過的です。最後に、さまざまな LVS 動作モードに応じて、実サーバーはユーザーが必要とするデータをエンドユーザーに送信するさまざまな方法を選択します。LVS 動作モードは、NAT モード、TUN モード、および DR モードに分かれています。

3 つの動作モードの分析。

1. NATに基づくLVSモード負荷分散

NAT (ネットワーク アドレス変換) は、ネットワーク アドレス変換です。その機能は、データ パケット ヘッダーを変更して、企業内にあるプライベート IP アドレスが外部ネットワークにアクセスできるようにし、外部ユーザーが社内にあるプライベート IP ホストにアクセスできるようにすることです。 VS/NAT 動作モードのトポロジを図 2 に示します。LVS ロード スケジューラは、2 つのネットワーク カードを使用して異なる IP アドレスを設定できます。Eth0 は秘密キー IP に設定され、スイッチング デバイスを介して内部ネットワークに接続されます。eth1 デバイスは外部ネットワーク IP であり、外部ネットワークに接続されます。

最初のステップでは、ユーザーはインターネット DNS サーバーを介して会社の負荷分散デバイスの外部ネットワーク アドレスを解決します。実サーバーと比較すると、LVS 外部ネットワーク IP は VIP (仮想 IP アドレス) とも呼ばれます。VIP にアクセスすることで、ユーザーはバックエンドの実サーバー (実サーバー) に接続できますが、これはすべてユーザーにとって透過的です。ユーザーは実サーバーにアクセスしていると考えていますが、アクセスしている VIP が単なるスケジューラーであることは知らず、バックエンドの実サーバーがどこにあり、実サーバーがいくつあるかも知りません。

2 番目のステップでは、ユーザーは 124.126.147.168 に要求を送信します。このとき、LVS は、事前設定されたアルゴリズムに従ってバックエンドの実サーバー (192.168.0.1~192.168.0.3) を選択し、データ要求パケットを実サーバーに転送します。転送する前に、LVS はデータ パケット内の宛先アドレスと宛先ポートを変更します。宛先アドレスと宛先ポートは、選択された実サーバーの IP アドレスと対応するポートに変更されます。

3 番目のステップでは、実サーバーが応答データ パケットを LVS スケジューラに返します。応答データ パケットを受信したスケジューラは、送信元アドレスと送信元ポートを VIP とスケジューラの対応するポートに変更します。変更が完了すると、スケジューラは応答データ パケットをエンド ユーザーに返します。また、LVS スケジューラには接続ハッシュ テーブルがあるため、テーブルには接続要求と転送情報が記録されます。同じ接続の次のデータ パケットがスケジューラに送信されると、ハッシュ テーブルから前の接続レコードを直接見つけることができ、レコード情報に従って同じ実サーバーとポート情報を選択できます。

2. TUNに基づくLVS負荷分散

LVS (NAT) モードのクラスター環境では、すべてのデータ要求パケットと応答パケットを LVS スケジューラによって転送する必要があるため、バックエンド サーバーの数が 10 を超えると、スケジューラがクラスター環境全体のボトルネックになります。データ要求パケットのサイズは、応答パケットのサイズよりもはるかに小さいことが多いことがわかっています。応答データ パケットにはクライアントが必要とする特定のデータが含まれているため、LVS (TUN) の考え方は、要求データと応答データを分離し、スケジューラがデータ要求のみを処理し、実サーバーの応答データ パケットが直接クライアントに返されるようにすることです。 VS/TUN 動作モードのトポロジ構造を図 3 に示します。このうち、IP トンネリングはデータ パケットのカプセル化技術であり、元のデータ パケットをカプセル化し、新しいパケット ヘッダー (新しい送信元アドレスとポート、宛先アドレスとポートを含む) を追加することで、スケジューラの VIP アドレスをターゲットとするデータ パケットのカプセル化を実現し、トンネルを介してバックエンドの実サーバ (Real Server) に転送します。クライアントからスケジューラに送信された元のデータ パケットをカプセル化し、それに基づいて新しいデータ パケット ヘッダーを追加 (ターゲット アドレスをスケジューラによって選択された実サーバの IP アドレスと対応するポートに変更) することにより、LVS (TUN) モードでは実サーバが外部ネットワークに直接接続できることが要求され、実サーバは要求データ パケットを受信した後、クライアント ホストに直接応答します。

3. DRに基づくLVS負荷分散

LVS (TUN) モードでは、LVS スケジューラと実サーバーの間にトンネル接続を作成する必要があるため、サーバーの負荷も増加します。 LVS (TUN) と同様に、DR モードはダイレクト ルーティング モードとも呼ばれます。そのアーキテクチャを図 4 に示します。このモードでは、LVS は引き続き着信データ要求のみを処理し、アルゴリズムに従って適切な実サーバーを選択します。最後に、バックエンドの実サーバーが応答データ パケットをクライアントに送り返す役割を担います。トンネルモードとは異なり、ダイレクトルーティングモード（DRモード）では、スケジューラとバックエンドサーバーが同じLAN内にある必要があり、スケジューラとすべてのバックエンドサーバー間でVIPアドレスを共有する必要があります。これは、最終的な実サーバーがクライアントに応答するときに、ソースIPをVIPアドレスに設定し、ターゲットIPをクライアントIPに設定する必要があるためです。このように、クライアントはスケジューラのVIPアドレスにアクセスし、応答のソースアドレスはVIPアドレス（実サーバー上のVIP）のままです。クライアントはバックエンドサーバーの存在を感じることはありません。複数のコンピュータに同じ VIP アドレスが設定されているため、ダイレクト ルーティング モードでは、スケジューラの VIP アドレスが外部から見えるようにする必要があります。クライアントは、要求データ パケットをスケジューラ ホストに送信する必要があり、すべての実サーバーの VIP アドレスは、非 ARP ネットワーク デバイス上に設定されている必要があります。つまり、ネットワーク デバイスは、自身の MAC アドレスと対応する IP アドレスを外部にブロードキャストしません。実サーバーの VIP は外部からは見えませんが、実サーバーは、ターゲット アドレス VIP からのネットワーク要求を受け入れ、データ パケットに応答するときに、送信元アドレスを VIP アドレスに設定できます。スケジューラは、アルゴリズムに従って実サーバを選択した後、データ メッセージを変更せずに、データ フレームの MAC アドレスを選択した実サーバの MAC アドレスに変更し、スイッチを介してデータ フレームを実サーバに送信します。プロセス全体を通じて、実サーバーの VIP を外部から見えるようにする必要はありません。

LVS 負荷分散スケジューリングアルゴリズム

前回の紹介では、LVS の 3 つの動作モードについて説明しました。実際の環境でどのモードが使用されるかに関係なく、スケジューリング戦略とスケジューリング アルゴリズムのアルゴリズムは LVS のコア技術です。LVS は主に次の 10 個のスケジューリング アルゴリズムをカーネルに実装しています。

1. ポーリングのスケジュール

ラウンドロビン (RR) アルゴリズムは、リクエストを循環的に異なるサーバーにディスパッチします。このアルゴリズムの最大の特徴は、実装が簡単なことです。ポーリング アルゴリズムでは、すべてのサーバーが要求を処理する能力が同じであると想定され、スケジューラはすべての要求を各実サーバーに均等に分散します。

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

加重ラウンドロビン (WRR) アルゴリズムは、主にラウンドロビン アルゴリズムの最適化と補足です。LVS は各サーバーのパフォーマンスを考慮し、各サーバーに重みを追加します。サーバー A の重みが 1 で、サーバー B の重みが 2 の場合、スケジューラはサーバー B にサーバー A の 2 倍の要求をスケジュールします。サーバーの重みが増すほど、処理するリクエストの数も増えます。

3. 最小接続スケジュール

最小接続 (LC) アルゴリズムは、現在の接続数が最も少ないサーバーに新しい接続要求を割り当てます。最小接続スケジューリングは、サーバー上のアクティブな接続の数に基づいてサーバーの状態を推定する動的スケジューリング アルゴリズムです。スケジューラは、各サーバーによって確立された接続の数を記録する必要があります。サーバーにリクエストがスケジュールされると、その接続数は 1 増加します。接続が中断されるかタイムアウトになると、その接続数は 1 減少します。

(クラスタ システム内の実サーバは同様のシステム パフォーマンスを持ち、最小接続スケジューリング アルゴリズムによって負荷をより適切に分散できます。)

4. 加重最小接続スケジューリング

加重最小接続 (WLC) アルゴリズムは最小接続スケジューリングのスーパーセットであり、各サーバーの対応する重みはその処理パフォーマンスを表します。サーバーのデフォルトの重みは 1 です。システム管理者はサーバーの重みを動的に設定できます。重み付け最小接続スケジューリングでは、新しい接続をスケジュールするときに、サーバー上で確立された接続の数をその重みに比例するようにします。スケジューラは、実サーバーの負荷状態を自動的に照会し、重みを動的に調整できます。

5. ローカルベースの最小接続

Locality-Based Least Connections (LBLC) アルゴリズムは、要求メッセージのターゲット IP アドレスに基づく負荷分散アルゴリズムです。キャッシュ クラスタ内のクライアント要求メッセージのターゲット IP アドレスは変化するため、現在は主にキャッシュ クラスタ システムで使用されています。ここでは、どのバックエンド サーバーでも任意のリクエストを処理できると想定しています。アルゴリズムの設計目標は、サーバー負荷が基本的にバランスが取れているときに、同じターゲット IP アドレスを持つリクエストを同じサーバーにスケジュールし、各サーバーのアクセス局所性とキャッシュ ヒット率を向上させて、クラスター システム全体の処理能力を向上させることです。 LBLC スケジューリング アルゴリズムは、まず、要求されたターゲット IP アドレスに基づいて、ターゲット IP アドレスによって最後に使用されたサーバーを検索します。サーバーが使用可能で過負荷になっていない場合は、要求がそのサーバーに送信されます。サーバーが存在しないか、サーバーが過負荷になっていて、ワークロードが半分のサーバーがある場合は、「最小接続」の原則を使用して使用可能なサーバーが選択され、要求がサーバーに送信されます。

6. ローカルベースの最小接続とレプリケーション

Locality-Based Least Connections with Replication (LBLCR) アルゴリズムも、ターゲット IP アドレスの負荷分散を実行します。現在、このアルゴリズムは主にキャッシュ クラスタ システムで使用されています。このアルゴリズムと LBLC アルゴリズムの違いは、このアルゴリズムがターゲット IP アドレスからサーバ グループへのマッピングを維持するのに対し、LBLC アルゴリズムはターゲット IP アドレスからサーバへのマッピングを維持する点です。サーバーは、「最小接続」の原則に従ってサーバー グループから選択されます。サーバーが過負荷になっていない場合は、要求がそのサーバーに送信されます。サーバーが過負荷になっている場合は、「最小接続」の原則に従ってクラスター全体からサーバーが選択され、そのサーバーがサーバー グループに追加され、要求がそのサーバーに送信されます。同時に、サーバー グループが一定期間変更されていない場合は、最もビジーなサーバーがサーバー グループから削除され、レプリケーションの度合いが低減されます。

7. ターゲットアドレスハッシュスケジューリング

宛先ハッシュ (DH) アルゴリズムは、まず要求のターゲット IP アドレスをハッシュ キーとして使用し、静的に割り当てられたハッシュ テーブルから対応するサーバーを検索します。サーバーが使用可能で過負荷でない場合は、要求がサーバーに送信され、そうでない場合は何も返されません。

8. 送信元アドレスハッシュスケジューリング U

ソース ハッシュ (SH) アルゴリズムは、まず要求の送信元 IP アドレスをハッシュ キーとして使用し、静的に割り当てられたハッシュ テーブルから対応するサーバーを検索します。サーバーが使用可能で過負荷でない場合は、要求がサーバーに送信され、そうでない場合は何も返されません。使用するハッシュ関数はターゲット アドレス ハッシュ スケジューリング アルゴリズムと同じであり、アルゴリズム フローは基本的にターゲット アドレス ハッシュ スケジューリング アルゴリズムと同様です。

9. 最短予想遅延

最短予想遅延 (SED) アルゴリズムは、WLC アルゴリズムに基づいています。たとえば、3 つのサーバー ABC の重みはそれぞれ 1、2、3 です。その後、WLC アルゴリズムを使用すると、新しい要求が到着すると、その要求は ABC のいずれかに割り当てられる可能性があります。 SEDアルゴリズムを使用した後、操作が実行されます

A: (1+1)/1=2 B: (1+2)/2=3/2 C: (1+3)/3=4/3 次に、計算結果が最小となるリクエストをサーバーに送信します。

10. 最小キュースケジューリング

Never Queue (NQ) アルゴリズムではキューは必要ありません。実サーバへの接続数が 0 の場合、SED 計算を必要とせず直接割り当てられます。