ロードバランサーのアルゴリズムと原理を探る

負荷分散アルゴリズムの種類を分析した後、動的負荷分散について紹介します。この概念は主にロードバランサの導入を通じて理解されます。重み付けポーリングアルゴリズムに基づいて、負荷分散の動的パフォーマンスを拡張できます。より具体的で詳細な説明については、記事を参照してください。

動的フィードバック負荷分散

クライアントがクラスター リソースにアクセスする場合、送信されたタスクに必要な時間とコンピューティング リソースは、多くの要因によって大きく異なります。たとえば、タスクによって要求されたサービスの種類、現在のネットワーク帯域幅、現在のサーバー リソース使用率などです。負荷の高いタスクの中には、計算集約型のクエリ、データベース アクセス、長い応答データ ストリームを必要とするものがありますが、負荷の軽いタスクでは、多くの場合、小さなファイルの読み取りや非常に単純な計算の実行のみが必要です。

タスク要求の処理時間の違いにより、処理ノードの利用率に偏りが生じる可能性があります。つまり、処理ノードの負荷が不均衡になります。一部のノードがすでに過負荷になっている一方で、他のノードは基本的にアイドル状態になっている状況が発生する可能性があります。同時に、一部のノードはすでにビジー状態であり、要求キューが長く、新しい要求を受信し続けます。一方で、これにより顧客は長時間待たされることになり、クラスター全体のサービス品質が低下します。そのため、ロードバランサーが各ノードの負荷状況をリアルタイムで把握し、負荷の変化に基づいて調整できるメカニズムを採用する必要があります。

具体的なアプローチは、ネガティブフィードバックメカニズムに基づく動的負荷分散アルゴリズムを使用することです。このアルゴリズムは、各ノードのリアルタイム負荷と応答能力を考慮し、一部のノードが過負荷になったときに大量のリクエストを受信しないようにタスク分散の割合を継続的に調整し、単一のクラスターの全体的なスループットを向上させます。

クラスターでは、サーバー監視プロセスはロードバランサー上で実行され、クラスター内の各ノードの負荷情報を監視および収集する役割を担います。また、クライアントプロセスは各ノード上で実行され、定期的に自身の負荷状態をロードバランサーに報告する役割を担います。監視プロセスは、すべてのノードから受信した負荷情報に基づいて同期操作を実行し、重みの割合に応じて割り当てるタスクを再分配します。重みの計算は主に、各ノードの CPU 使用率、使用可能なメモリ、およびディスク I/O 状態に基づいて新しい重みを計算します。新しい重みと現在の重みの差が設定されたしきい値より大きい場合、モニターは新しい重みを使用して、次の負荷情報同期が到着するまでクラスター内のタスクを再分配します。ロードバランサーは、動的な重みを持つ重み付きポーリングアルゴリズムを使用して、受信したネットワークサービス要求をスケジュールできます。

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

加重ラウンドロビン スケジューリング アルゴリズムは、対応する重みを使用してノードの処理パフォーマンスを表します。このアルゴリズムは、重みの順序に従って、ラウンドロビン方式で各ノードにタスク要求を分配します。重みが高いノードは、重みが低いノードよりも多くのタスク要求を処理し、同じ重みのノードは同じ割合の要求を処理します。加重ラウンドロビンの基本原理は、次のように説明できます。

クラスター内にノード集合 N={N0,N1,…,Nn-1} があり、W(Ni) はノード Ni の重みを表し、インジケータ変数 i は前回選択されたサーバーを表し、T(Ni) は現在ノード Ni に割り当てられているタスクの量を表すものとします。

∑T(Ni)は、現在の同期サイクルで処理する必要があるタスクの合計量を表します。

∑W(Ni)はノードの重みの合計を表します。

そして、W(Ni)/∑W(Ni)=T(Ni)/∑T(Ni)

これは、各ノードの重みと全体の重みの比率に応じてタスクが割り当てられることを意味します。

重量計算

クラスタのノードがシステムで初めて使用されるとき、システム管理者はノードのハードウェア構成に応じて各ノードの初期重み DW(Ni) を設定し (通常はノードのハードウェア構成に応じて定義され、ハードウェア構成が高いノードほどデフォルト値が高くなります)、この重みをロード バランサで使用します。その後、ノードの負荷が変化すると、ロード バランサは重みを調整します。

動的重みは、ノードの実行時にノードのさまざまなパラメータから計算されます。実験では、CPU リソース、メモリ リソース、現在のプロセス数、応答時間などの最も重要な項目を計算式の要素として選択しました。各ノードの現在の重みと組み合わせて、新しい重みのサイズを計算できます。動的重みの目的は、ノードの負荷の状態を正しく反映して、将来のノードの負荷の変化を予測することです。各パラメータの重要性は、システム アプリケーションの種類によって異なります。一般的な Web アプリケーション環境では、使用可能なメモリ リソースと応答時間が非常に重要です。ユーザーが主に長いデータベース トランザクションを使用する場合は、CPU 使用率と使用可能なメモリが比較的重要です。システムの動作中にさまざまなアプリケーションで各パラメータの割合を適切に調整できるようにするために、各パラメータに定数係数 Ri を設定して、各負荷パラメータの重要性を示します (∑Ri=1)。したがって、任意のノード Ni の重み式は次のように記述できます。

LOAD(Ni)=R1*Lcpu(Ni)+R2*Lmemory(Ni)+R3*Lio(Ni)+R4*Lprocess(Ni)+R5*Lresponse(Ni)

ここで、Lf(Ni) はノード Ni のパラメータの負荷値を表します。上記の式は、CPU 使用率、メモリ使用量、ディスク I/O アクセス率、プロセスの合計数、および応答時間を表します。

たとえば、Web サーバー クラスターでは、係数 {0.1、0.4、0.1、0.1、0.3} を使用します。ここでは、サーバーのメモリと要求応答時間が他のパラメーターよりも重要であると考えています。現在の係数 Ri がアプリケーションの負荷を適切に反映していない場合、システム管理者は、現在のアプリケーションに近い係数のセットが見つかるまで係数を継続的に変更できます。

また、収集重みの周期値については、非常に短い周期の方が各ノードの負荷をより正確に反映できますが、頻繁な収集（1 秒に 1 回以上など）はロードバランサとノードに負担をかけ、不要なネットワーク負荷も増加する可能性があります。また、コレクターは収集時に負荷計算を実行するため、実験では、ロードバランサによって反映される各ノードの負荷情報に深刻なジッタが見られ、ロードバランサはノードの真の負荷変化の傾向を正確に捉えることができないことがわかりました。したがって、これらの問題を解決するには、一方では、負荷情報の収集周期を適切に調整する必要があり、通常は 5 ～ 10 秒です。他方では、ジッタを回避するために移動平均またはスライディング ウィンドウを使用できます。これにより、ロードバランサによって収集された負荷情報が平均スライディング カーブとして提示され、負のフィードバック メカニズムの調整効果がより高くなります。

ロードバランサーの動的重み収集プログラムは定期的に実行されます。デフォルトの重みが 0 でない場合、ノードの負荷パラメータが照会され、動的重み LOAD(Ni) が計算されます。ノードの初期重みと収集された動的重みを組み合わせて、最終的な重みの結果を計算する次の重み計算式を導入します。

Wi=A*DW(Ni)+B*(LOAD(Ni)-DW(Ni))1/3

式では、動的重みが初期重みと正確に等しく、最終重みが変化しない場合は、システム負荷状態がちょうど理想的な状態に達し、初期重み DW (Ni) に等しいことを意味します。動的重みの計算結果が初期重みよりも高く、最終重みが高くなる場合は、システム負荷が非常に軽いことを意味し、ロードバランサはノードに割り当てるタスクの比率を増やします。動的重みが初期重みよりも低く、最終重みが低くなる場合は、システムが過負荷になり始めていることを意味し、ロードバランサはノードに割り当てるタスクを減らします。実際の使用では、すべてのノードの重みが DW (Ni) よりも小さいことが判明した場合、現在のクラスターが過負荷であり、負荷の一部を処理するためにクラスターに新しいノードを追加する必要があることを意味します。逆に、すべてのノードの重みが DW (Ni) よりもはるかに高い場合は、現在のシステム負荷が比較的軽いことを意味します。

結論

ネットワーク負荷分散は、クラスタージョブスケジューリングシステムの具体的な実装です。処理するジョブ単位は TCP/IP プロトコルのネットワーク接続であるため、ネットワーク接続の集中型基本スケジューリングアルゴリズムを使用できます。クラスター負荷の不均衡の可能性を考慮して、サービスノードの重みを動的に取得し、負のフィードバックメカニズムを使用して、ロードバランサーによるネットワークサービス要求の分散を調整し、操作中のサービスノードのリソースの変化に適応します。実践により、動的バランシングを使用するとクラスターシステムの全体的なスループットが向上することが証明されています。特に、クラスター内の各ノードのパフォーマンスが異なり、クラスターが提供するネットワークサービスプログラムがアクセスするリソースが多様である場合、負のフィードバックメカニズムの効果が特に顕著です。他のタイプのクラスターでも、負のフィードバックメカニズムを使用した動的負荷分散を適切に適用できますが、ロードバランサーが処理するジョブ単位はネットワーク接続とは異なり、特定の負荷アルゴリズムも異なります。