Nacos ランダムウェイト負荷分散アルゴリズム

導入

Nacos は、クライアントがノードを選択するときに重みベースのランダムアルゴリズムを提供します。ソースコードを分析することで、その実装原理を理解し、実際の戦闘で使用することができます。

1. 要約

次の図は、ランダムウェイト負荷分散アルゴリズムのプロセスを示しています。

ノードリスト

5 つのノードが登録されており、各ノードの重みが次のようになっているとします。

増加する配列の整理

目的は重み配列を形成することです。重み配列の要素は[0〜1]の範囲の値を取り、要素は1つずつ増加します。計算プロセスを下の図に示します。また、不健全なノードや重みが 0 以下のノードは選択されないことに注意してください。

ランダム化アルゴリズム

[0~1]の範囲で乱数を生成し、バイナリサーチを使用して増加する配列weights[]に近いインデックスを見つけ、登録されたノードリストからノードを返します。

2. ソースコード分析

ランダムウェイト負荷分散アルゴリズムは、NacosNamingService#selectOneHealthyInstance で提供されています。一緒に確認してみましょう。

 @オーバーライド
パブリックインスタンス selectOneHealthyInstance(String serviceName, String groupName, boolean subscribe)
  NacosException をスローします {
 selectOneHealthyInstance(serviceName、groupName、新しいArrayList<String>()、subscribe)を返します。
 }

 @オーバーライド
パブリックインスタンス selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters,
                                         ブール型subscribe）はNacosExceptionをスローします{
  文字列 clusterString = StringUtils.join (clusters, ", " );
  // 注釈 @1
  （購読）の場合{
    サービス情報 serviceInfo = serviceInfoHolder.getServiceInfo(サービス名、グループ名、クラスター文字列);
    if ( null == サービス情報 ) {
      serviceInfo = clientProxy.subscribe(サービス名、グループ名、クラスター文字列);
    }
 Balancer.RandomByWeight.selectHost(serviceInfo)を返します。
  }それ以外{
    // 注釈 @2
    サービス情報サービス情報 = clientProxy
      .queryInstancesOfService(サービス名、グループ名、クラスター文字列、0、 false );
 Balancer.RandomByWeight.selectHost(serviceInfo)を返します。
  }
 }

注: @1 は「キャッシュから登録済みノードのリストを取得する」にサブスクライブしており、デフォルトのサブスクライブは true です。

注 @2 「サーバーから登録ノードのリストを取得する」より

保護された静的インスタンス getHostByRandomWeight(List<Instance> ホスト) {
  NAMING_LOGGER.debug( "エントリ randomWithWeight" );
  （ホスト== null || hosts.size () == 0）の場合{
    NAMING_LOGGER.debug( "hosts == null || hosts.size() == 0" );
戻る ヌル;
  }
  NAMING_LOGGER.debug( "新しいセレクター" );
  List<Pair<Instance>> hostsWithWeight = new ArrayList<Pair<Instance>>();
 for (インスタンスホスト: hosts) {
    if (host.isHealthy()) { // 注釈 @3
      hostsWithWeight.add (新しいペア<Instance>(host, host.getWeight()));
    }
  }
  NAMING_LOGGER.debug( "for (ホスト host : hosts)" );
  Chooser<String, Instance> vipChooser = new Chooser<String, Instance>( "www.taobao.com" );
  // 注釈 @4
  vipChooser.refresh(ホストの重みをリフレッシュ)。
  NAMING_LOGGER.debug( "vipChooser.refresh" );
  // 注釈 @5
 vipChooser.randomWithWeight()を返します。
 }

注 @3 不健全なノードは選択されず、健全なノードの重みとホスト情報を含むペアのリストが作成されます。

注 @4 必要なデータを更新します。これには、すべての正常なノードの重みの合計、各正常なノードの重み比の計算、増分配列の整理という 3 つの部分が含まれます。

パブリックボイドリフレッシュ() {
ダブルオリジンウェイト合計 = (ダブル) 0;
    // 注釈@4.1
 (ペア<T>アイテム:アイテムの重量) { 
 
ダブルウェイト = item.weight();
        // 重みがゼロのアイテムは無視します。ChooserTestのtest_randomWithWeight_weight0を参照してください。
        // 0以下の重みは削除されます
        （重み<= 0）の場合{
続く;
        } 
 
        アイテムを追加します(item.item()); 
 
        // 値が無限大の場合
        if ( Double .isInfinite(weight)) {
            重量 = 10000.0D;
        } 
 
        // 値が数値以外の値の場合
        if ( Double .isNaN(重み)) {
            重量 = 1.0D;
        } 
 
        // 重みの合計を累積する
        originWeightSum += 重量;
    } 
 
    // 注釈@4.2
 double [] exactWeights = 新しいdouble [items.size ( )];
整数 インデックス= 0;
 (ペア<T>アイテム:アイテムの重量) {
ダブルシングルウェイト = item.weight();
        // 重みがゼロのアイテムは無視します。ChooserTestのtest_randomWithWeight_weight0を参照してください。
        シングルウェイト <= 0 の場合
続く;
        }
        // 各ノードの重み
        exactWeights[インデックス++] = singleWeight / originWeightSum;
    } 
 
    // 注釈@4.3
    重み = 新しいdouble [items.size ( )];
ダブルランダム範囲 = 0D;
 ( int i = 0; i <インデックス; i++) {
        重み[i] = ランダム範囲 + exactWeights[i];
        ランダム範囲 += exactWeights[i];
    } 
   
ダブルダブル精度デルタ = 0.0001; 
 
    if (インデックス== 0 || (Math.abs (重み[インデックス- 1] - 1) < doublePrecisionDelta)) {
戻る;
    }
    新しいIllegalStateExceptionをスローします(
 「累積重みの計算が間違っています。確率の合計が 1 になりません。」 );
 }

注 @4.1 すべての健全なノードの重みの合計 originWeightSum

注@4.2 各健全ノードの重み比のexactWeights配列を計算する

注@4.3 増加する配列の重みを整理します。各要素の値は配列内の前の要素の合計です。

このプロセスを説明するために例を見てみましょう。5 つのノードがあるとします。

 1.2.3.4 100
 1.2.3.5 100
 1.2.3.6 100
 1.2.3.7 80
 1.2.3.8 60

ステップ1: ノードの重みの合計を計算する

原点重量合計 = 100 + 100 + 100 + 80 + 60 = 440

ステップ2: 各ノードの重みを計算する

正確な重み[0] = 0.2272
正確な重み[1] = 0.2272
正確な重み[2] = 0.2272
正確な重み[3] = 0.1818
正確な重み[4] = 0.1363

ステップ3: 増加する配列の重みを整理する

重み[0] = 0.2272
重み[1] = 0.4544
重み[2] = 0.6816
重み[3] = 0.8634
重み[4] = 1

注 @5 ランダムに 1 つを選択します。ロジックは次のとおりです。

パブリックTランダムウェイト() {
    Ref<T> ref = this.ref;
    // 注釈@5.1
ダブルランダム = ThreadLocalRandom.current(). nextDouble (0, 1);
    // 注釈@5.2
整数 インデックス= Arrays.binarySearch(ref.weights, ランダム);
    // 注釈@5.3
    （インデックス<0）の場合{
インデックス= -インデックス- 1;
    }それ以外{
        // 注釈@5.4
 ref.items.get(インデックス)を返します。
    } 
 
    // 選択された要素を返す
    if (インデックス>= 0 &&インデックス< ref.weights.length) {
        if (random < ref.weights[インデックス]) {
 ref.items.get(インデックス)を返します。
        }
    } 
 
    /* これは決して起こらないはずのことですが、正しい値を返すことを保証します
     * オブジェクト内 ケースがある 浮動小数点の不等式の問題
     * 累積確率に関して。 */
 ref.items.get(ref.items.size ( )-1)を返します。
 }