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

时间:2021-08-01 01:23:53

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

引言

 

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

一、内容提要

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

节点列表

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

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

组织递增数组

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

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

随机算法

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

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

二、源码分析

随机权重负载均衡算法是在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); 
  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.   } 

注解@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(); 

注解@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."); 

注解@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); 

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

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

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

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

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

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