6種類の負荷分散アルゴリズムの概要

C言語を学んだ友人やIT関係の人ならアルゴリズムには詳しいと思います。したがって、分野が異なれば、アルゴリズムの単純さも異なります。言語の授業、プログラミングの授業、ネットワークの授業などでは、基本的にアルゴリズムの使用が全体の構造の基礎となります。それでは、負荷分散アルゴリズムの種類を紹介しましょう。どんな種類があるのか​​見てみましょう。

基本的なネットワーク負荷分散アルゴリズム

負荷分散アルゴリズムの設計品質は、負荷分散におけるクラスターのパフォーマンスを直接決定します。アルゴリズムの設計が不十分だと、クラスター内の負荷の不均衡につながります。一般的な負荷分散アルゴリズムの主なタスクは、次のクラスターノードを選択して、新しいサービス要求をそのノードに転送する方法を決定することです。いくつかの単純な負荷分散方法は単独で使用できますが、他の単純な方法や高度な方法と組み合わせて使用​​する必要があるものもあります。優れた負荷分散アルゴリズムは万能ではありません。通常、特定の特殊なアプリケーション環境でのみ最大限の役割を果たします。したがって、負荷分散アルゴリズムを検討するときは、アルゴリズム自体の適用性にも注意を払い、クラスターを展開するときにクラスター自体の特性に基づいて総合的に検討し、さまざまなアルゴリズムとテクノロジを組み合わせる必要があります。

負荷分散アルゴリズム1: ラウンドロビン

ラウンドロビン アルゴリズムは、すべてのスケジューリング アルゴリズムの中で最もシンプルで実装が簡単です。タスク キューでは、キューの各メンバー (ノード) は同じステータスを持ち、ラウンドロビン方式では、このメンバー グループを順番に選択します。負荷分散環境では、バランサーは新しい要求をノード キューの次のノードに順番に送信し、これを継続的に繰り返して実行し、クラスター内の各ノードが同じステータスで順番に選択されます。このアルゴリズムは、DNS ドメイン名ポーリングで広く使用されています。

ラウンドロビン方式のアクティビティは予測可能であり、各ノードが選択される確率は 1/N であるため、ノードの負荷分散を計算するのは簡単です。ラウンドロビン方式は、通常、クラスター内のすべてのノードの処理能力とパフォーマンスが同じである状況に適しています。実際のアプリケーションでは、他の単純な方法と組み合わせて使用​​すると、一般的に効果的です。

負荷分散アルゴリズム 2 ハッシュ方式

ハッシュ方式はHASHとも呼ばれます。シングルショットの不可逆なHASH関数により、ネットワーク要求は一定の規則に従ってクラスターノードに送信されます。ハッシュ方式は、他のタイプのバランシングアルゴリズムがあまり効果的でない場合に特別な力を発揮します。たとえば、前述のUDPセッションの場合、ラウンドロビン方式や接続情報に基づく他のタイプのアルゴリズムでは、セッションの開始マークと終了マークを識別できず、アプリケーションの混乱を引き起こします。

データ パケットの送信元アドレスに基づくハッシュ マッピングにより、この問題はある程度解決できます。同じ送信元アドレスを持つデータ パケットは同じサーバー ノードに送信されるため、高レベル セッションに基づくトランザクションが適切に実行されます。対称的に、宛先アドレスに基づくハッシュ スケジューリング アルゴリズムは、Web キャッシュ クラスターで使用できます。同じターゲット サイトを指すアクセス要求は、ロード バランサーによって同じキャッシュ サービス ノードに送信され、ページ不足によるキャッシュの更新の問題を回避します。

負荷分散アルゴリズム3: 最小接続方式

最小接続方式では、バランサーは現在アクティブな接続をすべて記録し、次の新しいリクエストを接続数が最も少ないノードに送信します。このアルゴリズムは TCP 接続で実行されますが、アプリケーションによって消費されるシステム リソースが大きく異なる場合があり、接続数が実際のアプリケーション負荷を反映できないため、負荷の高い Web サーバーをクラスター ノード サービスとして使用する場合 (Apache サーバーなど)、このアルゴリズムは負荷分散の観点からは無視されます。この悪影響を軽減するために、各ノードの最大接続数を設定できます (しきい値設定によって反映されます)。

負荷分散アルゴリズム 4 最小欠損法

最小損失方式では、バランサーは各ノードへのリクエストを長期間記録し、履歴の中で最も少ないリクエストを処理したノードに次のリクエストを送信します。最小接続方式とは異なり、最小損失は現在の接続数ではなく過去の接続数を記録します。

負荷分散アルゴリズム5: 最速応答方式

バランサは、自身から各クラスタ ノードまでのネットワーク応答時間を記録し、次に到着する接続要求を応答時間が最も短いノードに割り当てます。この方法では、各ノードをアクティブに検出するために、ICMP パケットまたは UDP パケットに基づく専用テクノロジを使用する必要があります。

ほとんどの LAN ベースのクラスターでは、最速応答アルゴリズムはあまりうまく機能しません。これは、LAN 内の ICMP パケットは基本的に 10 ミリ秒以内に応答し、ノード間の差異を反映しないためです。バランス調整が WAN 上で実行される場合、応答時間はユーザーが近くのサーバーを選択するのに依然として意味があります。また、クラスター トポロジが分散しているほど、この方法はより効果的です。この方法は、トポロジ リダイレクトに基づく高度なバランス調整で使用される主な方法です。

負荷分散アルゴリズム6重み付け方式

重み付け方式は、他の方式と組み合わせてのみ使用でき、他の方式を補完するのに適しています。重み付けアルゴリズムは、ノードの優先度または現在の負荷状態 (つまり重み) に基づいて、負荷分散されたマルチ優先度キューを形成します。キューで処理を待機している各接続は同じ処理レベルを持つため、同じキューを以前のラウンドロビン方式または最小接続方式に従ってバランス調整し、優先順位に従ってキューをバランス調整できます。ここで、重みは各ノードの容量に基づく推定値です。