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

概要

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

[[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. 最速の応答時間

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