引言

Nacos在Client選擇節點時提供了一種基于權重的隨機算法，通過源碼分析掌握其實現原理，方便實戰中加以運用。

一、內容提要

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

節點列表

假設注冊了5個節點，每個節點的權重如下。

組織遞增數組

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

隨機算法

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

二、源碼分析

隨機權重負載均衡算法是在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 已訂閱「從緩存獲取注冊節點列表」，默認subscribe為true。

注解@2 從 「從服務器獲取注冊節點列表」

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 非健康節點不會被選中，組裝Pair的列表，包含健康節點的權重和Host信息

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

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; 
        } 
 
        // 值如果為非數字值 
        if (Double.isNaN(weight)) { 
            weight = 1.0D; 
        } 
 
        // 累加權重總和 
        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; 
        } 
        // 每個節點權重的占比 
        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 所有健康節點權重求和originWeightSum

注解@4.2 計算每個健康節點權重占比exactWeights數組

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

以一個例子來表示這個過程，假設有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 

步驟一 計算節點權重求和

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

步驟二 計算每個節點權重占比

• exactWeights[0] = 0.2272
• exactWeights[1] = 0.2272
• exactWeights[2] = 0.2272
• exactWeights[3] = 0.1818
• exactWeights[4] = 0.1363

步驟三 組織遞增數組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 產生0到1區間的隨機數

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

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

注解@5.4 命中直接返回選中節點

小結： 一種基于權重的隨機算法的實現過程，扒開看也不復雜。

本文轉載自微信公眾號「瓜農老梁」，可以通過以下二維碼關注。轉載本文請聯系瓜農老梁公眾號。