本网站(662p.com)打包出售,且带程序代码数据,662p.com域名,程序内核采用TP框架开发,需要联系扣扣:2360248666 /wx:lianweikj
精品域名一口价出售:1y1m.com(350元) ,6b7b.com(400元) , 5k5j.com(380元) , yayj.com(1800元), jiongzhun.com(1000元) , niuzen.com(2800元) , zennei.com(5000元)
需要联系扣扣:2360248666 /wx:lianweikj
Nacos客户端是如何实现实例获取的负载均衡呢?
manongba · 422浏览 · 发布于2021-08-23 +关注

本篇文章追踪Nacos客户端源码,分析了从实例列表中获得其中一个实例的算法,也就是随机权重负载均衡算法。整体业务逻辑比较简单,从ServiceInfo中获得实例列表,一路筛选,选中目标实例,然后根据它们的权重进行二次处理,数据结构封装,最后基于Arrays#binarySearch提供的二分查找法来获得对应的实例。

前面我们讲了Nacos客户端如何获取实例列表,如何进行缓存处理,以及如何订阅实例列表的变更。在获取到一个实例列表之后,你是否想过一个问题:如果实例列表有100个实例,Nacos客户端是如何从中选择一个呢?

这篇文章,就带大家从源码层面分析一下,Nacos客户端采用了如何的算法来从实例列表中获取一个实例进行请求的。也可以称作是Nacos客户端的负载均衡算法。

单个实例获取

NamingService不仅提供了获取实例列表的方法,也提供了获取单个实例的方法,比如:

Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters, boolean subscribe) 
        throws NacosException;

该方法会根据预定义的负载算法,从实例列表中获得一个健康的实例。其他重载的方法功能类似,最终都会调用该方法,我们就以此方法为例来分析一下具体的算法。

具体实现代码:



  1. @Override 
    public Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters, 
            boolean subscribe) throws NacosException { 
        String clusterString = StringUtils.join(clusters, ","); 
        if (subscribe) { 
            // 获取ServiceInfo 
            ServiceInfo serviceInfo = serviceInfoHolder.getServiceInfo(serviceName, groupName, clusterString); 
            if (null == serviceInfo) { 
                serviceInfo = clientProxy.subscribe(serviceName, groupName, clusterString); 
            } 
            // 通过负载均衡算法获得其中一个实例 
            return Balancer.RandomByWeight.selectHost(serviceInfo); 
        } else { 
            // 获取ServiceInfo 
            ServiceInfo serviceInfo = clientProxy 
                    .queryInstancesOfService(serviceName, groupName, clusterString, 0, false); 
            // 通过负载均衡算法获得其中一个实例 
            return Balancer.RandomByWeight.selectHost(serviceInfo); 
        } 
    }


selectOneHealthyInstance方法逻辑很简单,调用我们之前讲到的方法获取ServiceInfo对象,然后作为参数传递给负载均衡算法,由负载均衡算法计算出最终使用哪个实例(Instance)。

算法参数封装

先跟踪一下代码实现,非核心业务逻辑,只简单提一下。

上面的代码可以看出调用的是Balancer内部类RandomByWeight的selectHost方法:


  1. public static Instance selectHost(ServiceInfo dom) { 
        // ServiceInfo中获去实例列表 
        List<Instance> hosts = selectAll(dom); 
        // ... 
        return getHostByRandomWeight(hosts); 
    }


selectHost方法核心逻辑是从ServiceInfo中获取实例列表,然后调用getHostByRandomWeight方法:

protected static Instance getHostByRandomWeight(List<Instance> hosts) { 
    // ... 判断逻辑 
    // 重新组织数据格式 
    List<Pair<Instance>> hostsWithWeight = new ArrayList<Pair<Instance>>(); 
    for (Instance host : hosts) { 
        if (host.isHealthy()) { 
            hostsWithWeight.add(new Pair<Instance>(host, host.getWeight())); 
        } 
    } 
    // 通过Chooser来实现随机权重负载均衡算法 
    Chooser<String, Instance> vipChooser = new Chooser<String, Instance>("www.taobao.com"); 
    vipChooser.refresh(hostsWithWeight); 
    return vipChooser.randomWithWeight(); 
}


getHostByRandomWeight前半部分是将Instance列表及其中的权重数据进行转换,封装成一个Pair,也就是建立成对的关系。在此过程中只使用了健康的节点。

真正的算法实现则是通过Chooser类来实现的,看名字基本上知道实现的策略是基于权重的随机算法。

负载均衡算法实现

所有的负载均衡算法实现均位于Chooser类中,Chooser类的提供了两个方法refresh和randomWithWeight。

refresh方法用于筛选数据、检查数据合法性和建立算法所需数据模型。

randomWithWeight方法基于前面的数据来进行随机算法处理。

先看refresh方法:

public void refresh(List<Pair<T>> itemsWithWeight) { 
    Ref<T> newRef = new Ref<T>(itemsWithWeight); 
    // 准备数据,检查数据 
    newRef.refresh(); 
    // 上面数据刷新之后,这里重新初始化一个GenericPoller 
    newRef.poller = this.ref.poller.refresh(newRef.items); 
    this.ref = newRef; 
}


基本步骤:

  • 创建Ref类,该类为Chooser的内部类;

  • 调用Ref的refresh方法,用于准备数据、检查数据等;

  • 数据筛选完成,调用poller#refresh方法,本质上就是创建一个GenericPoller对象;

  • 成员变量重新赋值;

这里重点看Ref#refresh方法:

/** 
 * 获取参与计算的实例列表、计算递增数组数总和并进行检查 
 */ 
public void refresh() { 
    // 实例权重总和 
    Double originWeightSum = (double) 0; 
     
    // 所有健康权重求和 
    for (Pair<T> item : itemsWithWeight) { 
         
        double weight = item.weight(); 
        //ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest 
        // 权重小于等于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; 
    } 
     
    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; 
    } 
     
    // 初始化递增数组 
    weights = new double[items.size()]; 
    double randomRange = 0D; 
    for (int i = 0; i < index; i++) { 
        // 递增数组第i项值为items前i个值总和 
        weights[i] = randomRange + exactWeights[i]; 
        randomRange += exactWeights[i]; 
    } 
     
    double doublePrecisionDelta = 0.0001; 
    // index遍历完则返回; 
    // 或weights最后一位值与1相比,误差小于0.0001,则返回 
    if (index == 0 || (Math.abs(weights[index - 1] - 1) < doublePrecisionDelta)) { 
        return; 
    } 
    throw new IllegalStateException( 
            "Cumulative Weight calculate wrong , the sum of probabilities does not equals 1."); 
}

    可结合上面代码中的注释来理解,核心步骤包括以下:

    • 遍历itemsWithWeight,计算权重总和数据;非健康节点会被剔除掉;

    • 计算每个节点的权重值在总权重值中的占比,并存储在exactWeights数组当中;

    • 将exactWeights数组当中值进行数据重构,形成一个递增数组weights(每个值都是exactWeights坐标值的总和),后面用于随机算法;

    • 判断是否循环完成或误差在指定范围内(0.0001),符合则返回。

    所有数据准备完成,调用随机算法方法randomWithWeight:

    public T randomWithWeight() { 
        Ref<T> ref = this.ref; 
        // 生成0-1之间的随机数 
        double random = ThreadLocalRandom.current().nextDouble(0, 1); 
        // 采用二分法查找数组中指定值,如果不存在则返回(-(插入点) - 1),插入点即随机数将要插入数组的位置,即第一个大于此键的元素索引。 
        int index = Arrays.binarySearch(ref.weights, random); 
        // 如果没有查询到(返回-1或"-插入点") 
        if (index < 0) { 
            index = -index - 1; 
        } else { 
            // 命中直接返回结果 
            return ref.items.get(index); 
        } 
         
        // 判断坐标未越界 
        if (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); 
    }

     

      该方法的基本操作如下:

      • 生成一个0-1的随机数;

      • 使用Arrays#binarySearch在数组中进行查找,也就是二分查找法。该方法会返回包含key的值,如果没有则会返回”-1“或”-插入点“,插入点即随机数将要插入数组的位置,即第一个大于此键的元素索引。

      • 如果命中则直接返回;如果未命中则对返回值取反减1,获得index值;

      • 判断index值,符合条件,则返回结果;

      至此,关于Nacos客户端实例获取的负载均衡算法代码层面追踪完毕。

      算法实例演示

      下面用一个实例来演示一下,该算法中涉及的数据变化。为了数据美观,这里采用4组数据,每组数据进来确保能被整除;

      节点及权重数据(前面节点,后面权重)如下:

      1 100 
      2 25 
      3 75 
      4 200

        第一步,计算权重综合:

        originWeightSum = 100 + 25 + 75 + 200 = 400

          第二步,计算每个节点权重比:

          exactWeights = {0.25, 0.0625, 0.1875, 0.5}

            第三步,计算递增数组weights:

            weights = {0.25, 0.3125, 0.5, 1}

              第四步,生成0-1的随机数:

              random = 0.3049980013493817

                第五步,调用Arrays#binarySearch从weights中搜索random:

                index = -2

                  关于Arrays#binarySearch(double[] a, double key)方法这里再解释一下,如果传入的key恰好在数组中,比如1,则返回的index为3;如果key为上面的random值,则先找到插入点,取反,减一。

                  插入点即第一个大于此key的元素索引,那么上面第一个大于0.3049980013493817的值为0.3125,那么插入点值为1;

                  于是按照公式计算Arrays#binarySearch返回的index为:

                  index = - ( 1 ) - 1 = -2

                    第六步,也就是没有恰好命中的情况:

                    index = -( -2 ) - 1 = 1


                      然后判断index是否越界,很明显 1 < 4,未越界,则返回坐标为1的值。

                      算法的核心

                      上面演示了算法,但这个算法真的能够做到按权重负载吗?我们来分析一下这个问题。

                      这个问题的重点不在random值,这个值基本上是随机的,那么怎么保证权重大的节点获得的机会更多呢?

                      这里先把递增数组weights用另外一个形式来表示:

                      上面的算法可以看出,weights与exactWeights为size相同的数组,对于同一坐标(index),weights的值是exactWeights包含当前坐标及前面所有坐标值的和。

                      如果把weights理解成一条线,对应节点的值是线上的一个个点,体现在图中便是(图2到图5)有色(灰色+橘黄色)部分。

                      而Arrays#binarySearch算法的插入点获取的是第一个大于key(也就是random)的坐标,也就是说每个节点享有的随机范围不同,它们的范围由当前点和前一个点的区间决定,而这个区间正好是权重比值。

                      权重比值大的节点,占有的区间就比较多,比如节点1占了1/4,节点4占了1/2。这样,如果随机数是均匀分布的,那么占有范围比较大的节点更容易获得青睐。也就达到了按照权重获得被调用的机会了。

                      小结

                      本篇文章追踪Nacos客户端源码,分析了从实例列表中获得其中一个实例的算法,也就是随机权重负载均衡算法。整体业务逻辑比较简单,从ServiceInfo中获得实例列表,一路筛选,选中目标实例,然后根据它们的权重进行二次处理,数据结构封装,最后基于Arrays#binarySearch提供的二分查找法来获得对应的实例。

                      而我们需要注意和学习的重点便是权重获取算法的思想及具体实现,最终达到能够在实践中进行运用。


                      相关推荐

                      将Fedora 29升级到Fedora 30

                      吴振华 · 697浏览 · 2019-05-14 22:00:02
                      使用Nginx反向代理到go-fastdfs

                      iamitnan · 719浏览 · 2019-05-23 13:42:00
                      利用VLC搭建组播流服务器

                      追忆似水年华 · 2684浏览 · 2019-06-14 11:27:06
                      用Bash脚本监控Linux上的内存使用情况

                      吴振华 · 962浏览 · 2019-06-24 11:27:02
                      加载中

                      0评论

                      评论
                      分类专栏
                      小鸟云服务器
                      扫码进入手机网页