分散システム設計のための負荷分散アルゴリズム

概要

分散システムの設計では、通常、サービスはクラスターに展開されます。クラスター内の複数のノードが同じサービスを提供するため、サービス要求はクラスター内の任意のノードに分散されて処理されます。クラスタ内のノードにリクエストを適切に分配して処理するには、つまり、クラスタ内の各ノードにリクエストを割り当てられるようにし、ノードに割り当てられたリクエストが多すぎてノードの処理能力を超えないようにするには、特定のルールに基づいてリクエストを分配する必要があります。このルールは負荷分散アルゴリズムとも呼ばれます。以下は、いくつかの一般的な負荷分散アルゴリズムの動作原理の詳細な分析です。

[[270439]]

1. 投票

ポーリング アルゴリズムは、主に、各クラスター ノードの現在の接続数とワークロード、およびノー​​ドのマシン パフォーマンスを考慮せずに、クライアントからロード バランサーに送信された要求をサービス クラスター内のノードに順番に転送します。このアルゴリズムの利点は、実装が簡単で、各クラスター ノードがすべての要求を均等に共有することです。欠点は、クラスター ノードに対応するマシン間でパフォーマンスに差がある場合、パフォーマンスの低いマシン ノードでは要求の処理が遅くなる一方で、パフォーマンスの高いマシン ノードではアイドル状態のシステム リソースが十分に活用されていない可能性があることです。そのため、一般的には、クラスター内のすべてのノードのマシンのパフォーマンスが近い状況で使用されます。

2. ランダム

ランダム アルゴリズムは、主にクラスター内のノードをランダムに選択して、要求を処理します。確率論の知識から、リクエストの数が増えるにつれて、ランダム アルゴリズムは徐々にポーリング アルゴリズムに進化し、クラスター内の各ノードが同様の数のリクエストを処理することがわかります。したがって、利点と欠点はポーリング アルゴリズムと同様です。

3. 加重ラウンドロビン vs 加重ランダム

重み付けアルゴリズムは、主にクラスター内のノードに対応するマシンのパフォーマンスの違いに基づいて、各ノードの重み値を設定します。パフォーマンスの良いマシン ノードには大きな重み値が設定され、パフォーマンスの悪いマシン ノードには小さな重み値が設定されます。その後、ポーリングまたはランダム アルゴリズムに基づいて、リクエストを処理するノードを選択し続けることができますが、重みが大きいノードがより頻繁に選択される可能性があります。実装原理は配列内の要素を選択することに似ており、重み値は対応するマシン ノードが配列内で繰り返し出現する回数です。たとえば、2 つのノード {a, b} があり、ノード a の重み値が 3、ノード b の重み値が 1 であるとします。配列の構成は [a, a, a, b] です。したがって、投票またはランダム選択のいずれの場合でも、a が複数回選択されます。

4. ハッシュと一貫性ハッシュ

ハッシュ アルゴリズムは、主に要求された IP アドレスまたは URL のハッシュ値を計算し、それをクラスター ノードの数で割って、要求を分散するクラスター ノードを決定します。このハッシュ アルゴリズムは実装が簡単で、クラスター ノードの数を変更せずに、同じ IP アドレスを持つ要求を同じマシンに分散して処理できます。ただし、クラスター ノードが変更されると、クラスター内のすべてのノードに影響します。たとえば、マシンのパフォーマンスが低いノードが突然大量のリクエストを受信し、クラスターの全体的な安定性に影響を与える可能性があります。

コンシステント ハッシュ アルゴリズムは、主にコンシステント ハッシュ関数に基づいて実装され、指定されたパラメータを 2 の 32 乗のポイントで構成されるリング スロット内の特定のスロット ポイントにマッピングします。

負荷分散に一貫性のあるハッシュ関数を使用する場合、クラスター内の複数のノードは最初にリング スロット内の対応するスロットにハッシュされます。次に、ロード バランサがリクエストを受信すると、リクエストの IP アドレスまたは URL がコンシステント ハッシュ関数のパラメータとして使用され、リクエストに対応するリング スロット内にスロットが生成されます。リング スロットにある最初のクラスター ノードが時計回りの方向で検出され、要求はこのクラスター ノードに転送されて処理されます。

一貫性ハッシュ アルゴリズムの実装原理から、クラスター ノードの数が変更されていない場合、同じ IP アドレスまたは同じ URL を持つ要求は同じクラスター ノードに転送されて処理されることがわかります。クラスター ノードの数が変更された場合、追加または削除されたノードの時計回り方向にある次のノードにのみ影響するため、クラスターを簡単に拡張および縮小できます。

5. 最小接続数

最小接続負荷分散アルゴリズムは、インテリジェントで動的な負荷分散アルゴリズムです。主に、クラスター内の各ノードの現在の接続数に基づいて、リクエストを転送するノードを決定します。つまり、各リクエストは同時接続数が最も少ないノードに転送されます。

この負荷分散アルゴリズムの利点は、クラスター ノードの負荷状況に応じて要求を動的に分散できることです。つまり、マシン パフォーマンスが良好で、リクエスト処理が高速で、バックログ リクエストが少ないノードには、より多くのリクエストが割り当てられ、その逆も同様です。これにより、クラスターの全体的な安定性が実現され、各ノードにリクエストが適切に分散され、処理できる以上のリクエストを処理することによるノードのクラッシュや応答の遅さが回避されます。

6. 最速の応答時間

最も応答時間が速い負荷分散アルゴリズムは、インテリジェントで動的な負荷分散アルゴリズムでもあります。最小接続数と同様に、クラスター ノードの負荷状況に基づいて各ノードに要求を合理的に分散し、クラスターの全体的な安定性とマシン リソースの再利用を実現します。最小接続数とは異なり、最速応答時間は、要求と応答間の時間遅延に基づいてマシンの負荷を測定します。つまり、リクエストは現在最も速く処理されているノードに分散され、ロード バランサはこのノードから最小の遅延で応答を取得します。応答時間が遅いノードには、割り当てられるリクエストが少なくなります。