引言

下面以圖示的方式貫穿下隨機權(quán)重負載均衡算法的流程：

節(jié)點列表

假設(shè)注冊了5個節(jié)點，每個節(jié)點的權(quán)重如下。

組織遞增數(shù)組

目的在于形成weights數(shù)組，該數(shù)組元素取值[0~1]范圍，元素逐個遞增，計算過程如下圖示。另外注意非健康節(jié)點或者權(quán)重小于等于0的不會被選擇。

隨機算法

通過生成[0~1]范圍的隨機數(shù)，通過二分法查找遞增數(shù)組weights[]接近的index，再從注冊節(jié)點列表中返回節(jié)點。

隨機權(quán)重負載均衡算法是在NacosNamingService#selectOneHealthyInstance提供，一起走查下。

@Override
public Instance selectOneHealthyInstance(String serviceName, String groupName, boolean subscribe)
  throws NacosException {
  return selectOneHealthyInstance(serviceName, groupName, new ArrayList<String>(), subscribe);
}

@Override
public Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters,
                                         boolean subscribe) throws NacosException {
  String clusterString = StringUtils.join(clusters, ",");
  // 注解@1
  if (subscribe) {
    ServiceInfo serviceInfo = serviceInfoHolder.getServiceInfo(serviceName, groupName, clusterString);
    if (null == serviceInfo) {
      serviceInfo = clientProxy.subscribe(serviceName, groupName, clusterString);
    }
    return Balancer.RandomByWeight.selectHost(serviceInfo);
  } else {
    // 注解@2
    ServiceInfo serviceInfo = clientProxy
      .queryInstancesOfService(serviceName, groupName, clusterString, 0, false);
    return Balancer.RandomByWeight.selectHost(serviceInfo);
  }
}

注解@1 已訂閱「從緩存獲取注冊節(jié)點列表」，默認subscribe為true。

注解@2 從 「從服務(wù)器獲取注冊節(jié)點列表」

protected static Instance getHostByRandomWeight(List<Instance> hosts) {
  NAMING_LOGGER.debug("entry randomWithWeight");
  if (hosts == null || hosts.size() == 0) {
    NAMING_LOGGER.debug("hosts == null || hosts.size() == 0");
    return null;
  }
  NAMING_LOGGER.debug("new Chooser");
  List<Pair<Instance>> hostsWithWeight = new ArrayList<Pair<Instance>>();
  for (Instance host : hosts) {
    if (host.isHealthy()) {  // 注解@3
      hostsWithWeight.add(new Pair<Instance>(host, host.getWeight()));
    }
  }
  NAMING_LOGGER.debug("for (Host host : hosts)");
  Chooser<String, Instance> vipChooser = new Chooser<String, Instance>("www.taobao.com");
  // 注解@4
  vipChooser.refresh(hostsWithWeight);
  NAMING_LOGGER.debug("vipChooser.refresh");
  // 注解@5
  return vipChooser.randomWithWeight();
}

注解@3 非健康節(jié)點不會被選中，組裝Pair的列表，包含健康節(jié)點的權(quán)重和Host信息

注解@4 刷新需要的數(shù)據(jù)，具體包括三部分：所有健康節(jié)點權(quán)重求和、計算每個健康節(jié)點權(quán)重占比、組織遞增數(shù)組。

public void refresh() {
    Double originWeightSum = (double) 0;
    // 注解@4.1
    for (Pair<T> item : itemsWithWeight) {

        double weight = item.weight();
        // ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest
        // weight小于等于 0的將會剔除
        if (weight <= 0) {
            continue;
        }

        items.add(item.item());

        // 值如果無窮大
        if (Double.isInfinite(weight)) {
            weight = 10000.0D;
        }

        // 值如果為非數(shù)字值
        if (Double.isNaN(weight)) {
            weight = 1.0D;
        }

        // 累加權(quán)重總和
        originWeightSum += weight;
    }

    // 注解@4.2
    double[] exactWeights = new double[items.size()];
    int index = 0;
    for (Pair<T> item : itemsWithWeight) {
        double singleWeight = item.weight();
        //ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest
        if (singleWeight <= 0) {
            continue;
        }
        // 每個節(jié)點權(quán)重的占比
        exactWeights[index++] = singleWeight / originWeightSum;
    }

    // 注解@4.3
    weights = new double[items.size()];
    double randomRange = 0D;
    for (int i = 0; i < index; i++) {
        weights[i] = randomRange + exactWeights[i];
        randomRange += exactWeights[i];
    }
  
    double doublePrecisionDelta = 0.0001;

    if (index == 0 || (Math.abs(weights[index - 1] - 1) < doublePrecisionDelta)) {
        return;
    }
    throw new IllegalStateException(
            "Cumulative Weight caculate wrong , the sum of probabilities does not equals 1.");
}

注解@4.1 所有健康節(jié)點權(quán)重求和originWeightSum

注解@4.2 計算每個健康節(jié)點權(quán)重占比exactWeights數(shù)組

注解@4.3 組織遞增數(shù)組weights，每個元素值為數(shù)組前面元素之和

以一個例子來表示這個過程，假設(shè)有5個節(jié)點：

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

步驟一  計算節(jié)點權(quán)重求和

originWeightSum = 100 + 100 + 100 + 80 + 60 = 440

步驟二 計算每個節(jié)點權(quán)重占比

exactWeights[0] = 0.2272

exactWeights[1] = 0.2272

exactWeights[2] = 0.2272

exactWeights[3] = 0.1818

exactWeights[4] = 0.1363

步驟三 組織遞增數(shù)組weights

weights[0] = 0.2272

weights[1] = 0.4544

weights[2] = 0.6816

weights[3] = 0.8634

weights[4] = 1

注解@5 隨機選取一個，邏輯如下：

public T randomWithWeight() {
    Ref<T> ref = this.ref;
    // 注解@5.1
    double random = ThreadLocalRandom.current().nextDouble(0, 1);
    // 注解@5.2
    int index = Arrays.binarySearch(ref.weights, random);
    // 注解@5.3
    if (index < 0) {
        index = -index - 1;
    } else {
        // 注解@5.4
        return ref.items.get(index);
    }

    // 返回選中的元素
    if (index >= 0 && index < ref.weights.length) {
        if (random < ref.weights[index]) {
            return ref.items.get(index);
        }
    }

    /* This should never happen, but it ensures we will return a correct
     * object in case there is some floating point inequality problem
     * wrt the cumulative probabilities. */
    return ref.items.get(ref.items.size() - 1);
}

注解@5.1 產(chǎn)生0到1區(qū)間的隨機數(shù)

注解@5.2 二分法查找數(shù)組中接近的值

注解@5.3  沒有命中返回插入數(shù)組理想索引值

注解@5.4 命中直接返回選中節(jié)點

小結(jié)： 一種基于權(quán)重的隨機算法的實現(xiàn)過程，扒開看也不復(fù)雜。