引言

Nacos在Client選擇節(jié)點(diǎn)時(shí)提供了一種基于權(quán)重的隨機(jī)算法，通過源碼分析掌握其實(shí)現(xiàn)原理，方便實(shí)戰(zhàn)中加以運(yùn)用。

一、內(nèi)容提要

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

節(jié)點(diǎn)列表

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

組織遞增數(shù)組

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

隨機(jī)算法

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

二、源碼分析

隨機(jī)權(quán)重負(fù)載均衡算法是在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é)點(diǎn)列表」，默認(rèn)subscribe為true。

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

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é)點(diǎn)不會被選中，組裝Pair的列表，包含健康節(jié)點(diǎn)的權(quán)重和Host信息

注解@4 刷新需要的數(shù)據(jù)，具體包括三部分：所有健康節(jié)點(diǎn)權(quán)重求和、計(jì)算每個(gè)健康節(jié)點(diǎn)權(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; 
        } 
        // 每個(gè)節(jié)點(diǎn)權(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é)點(diǎn)權(quán)重求和originWeightSum

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

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

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

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 

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

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

步驟二 計(jì)算每個(gè)節(jié)點(diǎn)權(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 隨機(jī)選取一個(gè)，邏輯如下：

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ū)間的隨機(jī)數(shù)

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

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

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

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

本文轉(zhuǎn)載自微信公眾號「瓜農(nóng)老梁」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系瓜農(nóng)老梁公眾號。