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

也想出现在这里？点击联系我~

引言

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

一、内容提要

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

节点列表

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

组织递增数组

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

随机算法

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

二、源码分析

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

1. @Override
2. publicInstanceselectOneHealthyInstance(StringserviceName,StringgroupName,booleansubscribe)
3. throwsNacosException{
4. returnselectOneHealthyInstance(serviceName,groupName,newArrayList<String>(),subscribe);
5. }

1. @Override
2. publicInstanceselectOneHealthyInstance(StringserviceName,StringgroupName,List<String>clusters,
3. booleansubscribe)throwsNacosException{
4. StringclusterString=StringUtils.join(clusters,",");
5. //注解@1
6. if(subscribe){
7. ServiceInfoserviceInfo=serviceInfoHolder.getServiceInfo(serviceName,groupName,clusterString);
8. if(null==serviceInfo){
9. serviceInfo=clientProxy.subscribe(serviceName,groupName,clusterString);
10. }
11. returnBalancer.RandomByWeight.selectHost(serviceInfo);
12. }else{
13. //注解@2
14. ServiceInfoserviceInfo=clientProxy
15. .queryInstancesOfService(serviceName,groupName,clusterString,0,false);
16. returnBalancer.RandomByWeight.selectHost(serviceInfo);
17. }
18. }

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

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

1. protectedstaticInstancegetHostByRandomWeight(List<Instance>hosts){
2. NAMING_LOGGER.debug("entryrandomWithWeight");
3. if(hosts==null||hosts.size()==0){
4. NAMING_LOGGER.debug("hosts==null||hosts.size()==0");
5. returnnull;
6. }
7. NAMING_LOGGER.debug("newChooser");
8. List<Pair<Instance>>hostsWithWeight=newArrayList<Pair<Instance>>();
9. for(Instancehost:hosts){
10. if(host.isHealthy()){//注解@3
11. hostsWithWeight.add(newPair<Instance>(host,host.getWeight()));
12. }
13. }
14. NAMING_LOGGER.debug("for(Hosthost:hosts)");
15. Chooser<String,Instance>vipChooser=newChooser<String,Instance>("www.taobao.com");
16. //注解@4
17. vipChooser.refresh(hostsWithWeight);
18. NAMING_LOGGER.debug("vipChooser.refresh");
19. //注解@5
20. returnvipChooser.randomWithWeight();
21. }

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

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

1. publicvoidrefresh(){
2. DoubleoriginWeightSum=(double)0;
3. //注解@4.1
4. for(Pair<T>item:itemsWithWeight){
6. doubleweight=item.weight();
7. //ignoreitemwhichweightiszero.seetest_randomWithWeight_weight0inChooserTest
8. //weight小于等于0的将会剔除
9. if(weight<=0){
10. continue;
11. }
13. items.add(item.item());
15. //值如果无穷大
16. if(Double.isInfinite(weight)){
17. weight=10000.0D;
18. }
20. //值如果为非数字值
21. if(Double.isNaN(weight)){
22. weight=1.0D;
23. }
25. //累加权重总和
26. originWeightSum+=weight;
27. }
29. //注解@4.2
30. double[]exactWeights=newdouble[items.size()];
31. intindex=0;
32. for(Pair<T>item:itemsWithWeight){
33. doublesingleWeight=item.weight();
34. //ignoreitemwhichweightiszero.seetest_randomWithWeight_weight0inChooserTest
35. if(singleWeight<=0){
36. continue;
37. }
38. //每个节点权重的占比
39. exactWeights[index++]=singleWeight/originWeightSum;
40. }
42. //注解@4.3
43. weights=newdouble[items.size()];
44. doublerandomRange=0D;
45. for(inti=0;i<index;i++){
46. weights[i]=randomRange+exactWeights[i];
47. randomRange+=exactWeights[i];
48. }
50. doubledoublePrecisionDelta=0.0001;
52. if(index==0||(Math.abs(weights[index-1]-1)<doublePrecisionDelta)){
53. return;
54. }
55. thrownewIllegalStateException(
56. "CumulativeWeightcaculatewrong,thesumofprobabilitiesdoesnotequals1.");
57. }

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

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

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

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

1. 1.2.3.4100
2. 1.2.3.5100
3. 1.2.3.6100
4. 1.2.3.780
5. 1.2.3.860

步骤一 计算节点权重求和

• 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. publicTrandomWithWeight(){
2. Ref<T>ref=this.ref;
3. //注解@5.1
4. doublerandom=ThreadLocalRandom.current().nextDouble(0,1);
5. //注解@5.2
6. intindex=Arrays.binarySearch(ref.weights,random);
7. //注解@5.3
8. if(index<0){
9. index=-index-1;
10. }else{
11. //注解@5.4
12. returnref.items.get(index);
13. }
15. //返回选中的元素
16. if(index>=0&&index<ref.weights.length){
17. if(random<ref.weights[index]){
18. returnref.items.get(index);
19. }
20. }
22. /*Thisshouldneverhappen,butitensureswewillreturnacorrect
23. *objectincasethereissomefloatingpointinequalityproblem
24. *wrtthecumulativeprobabilities.*/
25. returnref.items.get(ref.items.size()-1);
26. }

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

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

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

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

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

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