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 にアクセスすることで、ユーザーはバックエンドの実サーバー (Real Server) に接続することができ、これらはすべてユーザーにとって透過的になります。ユーザーは実サーバーにアクセスしていると考えていますが、アクセスしている 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) に転送します。 LVS (TUN) モードでは、クライアントからスケジューラに送信された元のデータ パケットをカプセル化し、それに基づいて新しいデータ パケット ヘッダーを追加 (ターゲット アドレスをスケジューラによって選択された実サーバの IP アドレスと対応するポートに変更) することで、実サーバが外部ネットワークに直接接続できることが要求され、実サーバは要求データ パケットを受信した後、クライアント ホストに直接応答します。

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 アルゴリズムの違いは、LBLC アルゴリズムがターゲット IP アドレスからサーバーへのマッピングを維持するのに対し、このアルゴリズムはターゲット 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 計算を必要とせず直接割り当てられます。