Nacos之随机权重负载均衡算法

引言

Nacos在Client选择节点时提供了一种基于权重的随机算法，通过源码分析掌握其实现原理，方便实战中加以运用。

一、内容提要

下面以图示的方式贯穿下随机权重负载均衡算法的流程：

节点列表

假设注册了5个节点，每个节点的权重如下。

组织递增数组

目的在于形成weights数组，该数组元素取值[0~1]范围，元素逐个递增，计算过程如下图示。另外注意非健康节点或者权重小于等于0的不会被选择。

随机算法

通过生成[0~1]范围的随机数，通过二分法查找递增数组weights[]接近的index，再从注册节点列表中返回节点。

二、源码分析

随机权重负载均衡算法是在NacosNamingService#selectOneHealthyInstance提供，一起走查下。

1. @Override 
2. public Instance selectOneHealthyInstance(String serviceName, String groupName, boolean subscribe) 
3.   throws NacosException { 
4.   return selectOneHealthyInstance(serviceName, groupName, new ArrayList<String>(), subscribe); 
5. } 

1. @Override 
2. public Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters, 
3.                                          boolean subscribe) throws NacosException { 
4.   String clusterString = StringUtils.join(clusters, ","); 
5.   // 注解@1 
6.   if (subscribe) { 
7.     ServiceInfo serviceInfo = serviceInfoHolder.getServiceInfo(serviceName, groupName, clusterString); 
8.     if (null == serviceInfo) { 
9.       serviceInfo = clientProxy.subscribe(serviceName, groupName, clusterString); 
10.     } 
11.     return Balancer.RandomByWeight.selectHost(serviceInfo); 
12.   } else { 
13.     // 注解@2 
14.     ServiceInfo serviceInfo = clientProxy 
15.       .queryInstancesOfService(serviceName, groupName, clusterString, 0, false); 
16.     return Balancer.RandomByWeight.selectHost(serviceInfo); 
17.   } 
18. } 

注解@1 已订阅「从缓存获取注册节点列表」，默认subscribe为true。

注解@2 从 「从服务器获取注册节点列表」

1. protected static Instance getHostByRandomWeight(List<Instance> hosts) { 
2.   NAMING_LOGGER.debug("entry randomWithWeight"); 
3.   if (hosts == null || hosts.size() == 0) { 
4.     NAMING_LOGGER.debug("hosts == null || hosts.size() == 0"); 
5.     return null; 
6.   } 
7.   NAMING_LOGGER.debug("new Chooser"); 
8.   List<Pair<Instance>> hostsWithWeight = new ArrayList<Pair<Instance>>(); 
9.   for (Instance host : hosts) { 
10.     if (host.isHealthy()) {  // 注解@3 
11.       hostsWithWeight.add(new Pair<Instance>(host, host.getWeight())); 
12.     } 
13.   } 
14.   NAMING_LOGGER.debug("for (Host host : hosts)"); 
15.   Chooser<String, Instance> vipChooser = new Chooser<String, Instance>("www.taobao.com"); 
16.   // 注解@4 
17.   vipChooser.refresh(hostsWithWeight); 
18.   NAMING_LOGGER.debug("vipChooser.refresh"); 
19.   // 注解@5 
20.   return vipChooser.randomWithWeight(); 
21. } 

注解@3 非健康节点不会被选中，组装Pair的列表，包含健康节点的权重和Host信息

注解@4 刷新需要的数据，具体包括三部分：所有健康节点权重求和、计算每个健康节点权重占比、组织递增数组。

1. public void refresh() { 
2.     Double originWeightSum = (double) 0; 
3.     // 注解@4.1 
4.     for (Pair<T> item : itemsWithWeight) { 
5.  
6.         double weight = item.weight(); 
7.         // ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest 
8.         // weight小于等于 0的将会剔除 
9.         if (weight <= 0) { 
10.             continue; 
11.         } 
12.  
13.         items.add(item.item()); 
14.  
15.         // 值如果无穷大 
16.         if (Double.isInfinite(weight)) { 
17.             weight = 10000.0D; 
18.         } 
19.  
20.         // 值如果为非数字值 
21.         if (Double.isNaN(weight)) { 
22.             weight = 1.0D; 
23.         } 
24.  
25.         // 累加权重总和 
26.         originWeightSum += weight; 
27.     } 
28.  
29.     // 注解@4.2 
30.     double[] exactWeights = new double[items.size()]; 
31.     int index = 0; 
32.     for (Pair<T> item : itemsWithWeight) { 
33.         double singleWeight = item.weight(); 
34.         //ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest 
35.         if (singleWeight <= 0) { 
36.             continue; 
37.         } 
38.         // 每个节点权重的占比 
39.         exactWeights[index++] = singleWeight / originWeightSum; 
40.     } 
41.  
42.     // 注解@4.3 
43.     weights = new double[items.size()]; 
44.     double randomRange = 0D; 
45.     for (int i = 0; i < index; i++) { 
46.         weights[i] = randomRange + exactWeights[i]; 
47.         randomRange += exactWeights[i]; 
48.     } 
49.    
50.     double doublePrecisionDelta = 0.0001; 
51.  
52.     if (index == 0 || (Math.abs(weights[index - 1] - 1) < doublePrecisionDelta)) { 
53.         return; 
54.     } 
55.     throw new IllegalStateException( 
56.             "Cumulative Weight caculate wrong , the sum of probabilities does not equals 1."); 
57. } 

注解@4.1 所有健康节点权重求和originWeightSum

注解@4.2 计算每个健康节点权重占比exactWeights数组

注解@4.3 组织递增数组weights，每个元素值为数组前面元素之和

以一个例子来表示这个过程，假设有5个节点：

1. 1.2.3.4 100 
2. 1.2.3.5 100 
3. 1.2.3.6 100 
4. 1.2.3.7 80 
5. 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 随机选取一个，逻辑如下：

1. public T randomWithWeight() { 
2.     Ref<T> ref = this.ref; 
3.     // 注解@5.1 
4.     double random = ThreadLocalRandom.current().nextDouble(0, 1); 
5.     // 注解@5.2 
6.     int index = Arrays.binarySearch(ref.weights, random); 
7.     // 注解@5.3 
8.     if (index < 0) { 
9.         index = -index - 1; 
10.     } else { 
11.         // 注解@5.4 
12.         return ref.items.get(index); 
13.     } 
14.  
15.     // 返回选中的元素 
16.     if (index >= 0 && index < ref.weights.length) { 
17.         if (random < ref.weights[index]) { 
18.             return ref.items.get(index); 
19.         } 
20.     } 
21.  
22.     /* This should never happen, but it ensures we will return a correct 
23.      * object in case there is some floating point inequality problem 
24.      * wrt the cumulative probabilities. */ 
25.     return ref.items.get(ref.items.size() - 1); 
26. } 

注解@5.1 产生0到1区间的随机数

注解@5.2 二分法查找数组中接近的值

注解@5.3 没有命中返回插入数组理想索引值

注解@5.4 命中直接返回选中节点

小结： 一种基于权重的随机算法的实现过程，扒开看也不复杂。作者小姐姐养的狗 。转载本文请联系小姐姐味道公众号。

原文链接：https://mp.weixin.qq.com/s/aq2Uymvv9EnnfgI8DJKd6Q