关于dubbo:Dubbo-负载均衡

前言

大家好，明天给大家分享 Dubbo 中的负载平衡。在前一个章节中咱们介绍 Dubbo 提早服务裸露，咱们例举了常见的应用场景并且进行了源码解析来剖析其实现原理，同时咱们也晓得 Dubbo 提早服务裸露其外围就是通过一个 提早的调度器指定延迟时间后开始服务的裸露。很多小伙伴可能会好奇：咱们的服务部署根本都是集群模式，那服务生产端到底是调用哪一个服务提供者呢？都有哪些常见的服务抉择算法？为了揭开这些困惑，上面就让咱们疾速开始吧！

1. 负载平衡简介

那么什么是负载平衡呢？举个简略例子：在火车站购买火车票场景，咱们晓得节假日必定有十分多的人购买火车票，那么一个售票窗口卖票的话必定会排很长的队对用户来说体验十分差。那咱们能不能多减少几个售票窗口呢？是不是并行处理的能力马上失去进步了呢？没错！咱们在软件工程外面也是如此。比方 Nginx 经常用作软件负载平衡、F5 用作硬件的负载均衡器等等。负载平衡算法能够无效进步零碎的并发解决能力、容错能力、一致性拜访等。如下图所示：

1. 并发解决能力：通过横向拓展部署后端服务器数量做到服务扩容。
2. 容错能力：通过 Nginx 代理申请后端服务失败时转移调用其余存活服务。
3. 一致性拜访：在某些场景中指定路由到固定服务器，比方：特定服务器对登录用户 Session 进行缓存。

2. Dubbo 反对负载平衡算法

2.1 加权随机算法

随机算法比较简单就和数学中的随机值选取一样，比方：1-100 中随机抉择一个数字。在 Dubbo 中对随机算法减少了一个权重概念。举个例子：

从上表中咱们晓得 4 个服务权重别离是 10、20、20、50，参考下图形容了随机抉择步骤：

1. 首先咱们依据权重总和利用随机值获取初始 offset，假如 offset 值为 60。
2. 第一步循环服务列表第一个服务获取权重值 10 并应用 offset – weight 后果值为 50 > 0 继续执行从新赋值offset = 50。
3. 第二步循环服务列表第二个服务获取权重值 20 并应用 offset – weight 后果值为 30 > 0 继续执行。
4. 第三步循环服务列表第三个服务获取权重值 20 并应用 offset – weight 后果值为 10 > 0 继续执行。
5. 第四步循环服务列表第四个服务获取权重值 50 并应用 offset – weight 后果值为 -40 > 0 找到服务终止。

Tips：此算法数据量越大数据调配越平均。

2.1.1 算法实现：

public class RandomLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "random";

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // 服务总数
        int length = invokers.size();
        // 标识这些服务是否具备雷同的权重
        boolean sameWeight = true;
        // 所有服务权重汇合
        int[] weights = new int[length];
        // 第一个服务权重
        int firstWeight = getWeight(invokers.get(0), invocation);
        weights[0] = firstWeight;
        // 权重总和
        int totalWeight = firstWeight;
        for (int i = 1; i < length; i++) {int weight = getWeight(invokers.get(i), invocation);
            // 记录权重
            weights[i] = weight;
            // 共计权重值
            totalWeight += weight;
            if (sameWeight && weight != firstWeight) {sameWeight = false;}
        }
        if (totalWeight > 0 && !sameWeight) {// 从（0,totalWeight]范畴抉择权重值
            int offset = ThreadLocalRandom.current().nextInt(totalWeight);
            // 基于随机值返回服务
            for (int i = 0; i < length; i++) {// offset = offset - weights[i]
                offset -= weights[i];
                if (offset < 0) {return invokers.get(i);
                }
            }
        }
        // 如果权重值雷同或者 totalWeight= 0 返回服务列表中随机服务
        return invokers.get(ThreadLocalRandom.current().nextInt(length));
    }
}

2.1.2 算法过程剖析：

1. 循环 invokers 服务列表计算出权重总和并标记出是否存在权重全副雷同状况。
2. 依据下面步骤的标记判断 invokers 服务列表所有服务权重是否雷同，雷同则随机返回服务列表中的一个服务。
3. invokers 服务列表存在服务权重不雷同时，产生一个权重总和范畴内的一个大于 0 的随着整数赋值给 offset，而后循环拜访服务列表中的元素并且应用 offset 减去以后循环元素的权重值，如果差值大于 0 则赋值给以后的 offset 继续执行元素循环，当 offset 减去以后元素的权重大于零时进行循环，则以后查找的元素为抉择的服务。

2.2 加权轮询算法

轮询负载平衡算法顾名思义就是轮流调用服务。举个例子：假如 4 个申请通过 Nginx 代理转发到后端服务：

同时 Dubbo 中的轮询算法也是须要权重反对。轮询负载平衡算法能够让 RPC 调用严格依照咱们设置的比例来调配。不论是大量的调用还是大量的调用。然而轮询负载平衡算法也有有余的中央，存在慢的服务累积申请的问题，比方：第二台 Service2 很慢，但没挂，当申请调到第二台时就卡在那，长此以往，所有申请都卡在调到第二台上，导致整个零碎变慢。以下是加权轮询算法图：

2.2.1 算法实现

public class RoundRobinLoadBalance extends AbstractLoadBalance {
    
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
         // 服务惟一标识，获取这一组服务第一个服务：因为这是一组服务所有 key 是雷同的
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();//DemoService.method1
        // 通过服务惟一标识对这一组服务进行缓存 key -> Map
        ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
        if (map == null) {methodWeightMap.putIfAbsent(key, new ConcurrentHashMap<String, WeightedRoundRobin>());
            map = methodWeightMap.get(key);
        }
        int totalWeight = 0;
        long maxCurrent = Long.MIN_VALUE;
        long now = System.currentTimeMillis();
        Invoker<T> selectedInvoker = null;
        WeightedRoundRobin selectedWRR = null;
        for (Invoker<T> invoker : invokers) {String identifyString = invoker.getUrl().toIdentityString();// 服务实例惟一示意：[test://127.0.0.1:1/DemoService,test://127.0.0.1:2/DemoService,test://127.0.0.1:3/DemoService]
            WeightedRoundRobin weightedRoundRobin = map.get(identifyString);
            // 获取服务权重
            int weight = getWeight(invoker, invocation);
            //WeightedRoundRobin 封装实体
            if (weightedRoundRobin == null) {weightedRoundRobin = new WeightedRoundRobin();
                weightedRoundRobin.setWeight(weight);
                map.putIfAbsent(identifyString, weightedRoundRobin);
            }
            // 权重产生变更
            if (weight != weightedRoundRobin.getWeight()) {
                // 从新赋值
                weightedRoundRobin.setWeight(weight);
            }
            long cur = weightedRoundRobin.increaseCurrent();
            // 记录更新工夫
            weightedRoundRobin.setLastUpdate(now);
            if (cur > maxCurrent) {// 大于以后最大权重则被抉择
                maxCurrent = cur;
                selectedInvoker = invoker;
                selectedWRR = weightedRoundRobin;
            }
            // 计算所有权重值
            totalWeight += weight;
        }
        // 获取锁并且存在服务下线状况【invokers.size() != map.size()】if (!updateLock.get() && invokers.size() != map.size()) {if (updateLock.compareAndSet(false, true)) {
                try {
                    // copy -> modify -> update reference
                    ConcurrentMap<String, WeightedRoundRobin> newMap = new ConcurrentHashMap<>(map);
                    // 回收周期
                    newMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
                    methodWeightMap.put(key, newMap);
                } finally {updateLock.set(false);
                }
            }
        }
        if (selectedInvoker != null) {
            // 将其抉择服务权重值减去总权重值
            selectedWRR.sel(totalWeight);
            return selectedInvoker;
        }
        // should not happen here
        return invokers.get(0);
    }
}

2.2.2 算法过程剖析

1. 首先初始化 maxCurrent 为最小值 Long.MIN_VALUE、totalWeight 为 0。
2. 循环 invokers 服务列表，每个元素中的 current (初始化为 0)加上元素权重值大于 maxCurrent，
   则赋值给 maxCurrent 并且赋值选中服务 (selectedInvoker ) 为以后元素，并且累计以后元素权重值赋值给 totalWeight。
3. 设置以后选中服务权重值为选中元素权重减去以后权重总和。

Tips：上述算法存在肯定的难度，稍作理解即可。

2.3 起码沉闷调用数算法

咱们在理论服务调度场景中个别存在多服务实例部署状况，当雷同的利用部署到不同机器很可能存在不同服务解决的能力不同有快有慢，那么咱们理想化的认为在服务调用过程中解决能力慢的服务器接管较少的服务申请更为合乎咱们的要求。如下示例图：

从图中能够看出假如咱们这里有 5 个申请通过 Ngingx 代理转发到后端服务，这里 Service02 只接管到一个申请(解决能力较弱)。

2.3.1 算法实现

public class LeastActiveLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "leastactive";

    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {int length = invokers.size();
        // 初始化最小沉闷值，最小沉闷数，最小沉闷的 invoker 索引（index）, 权重数组
        int leastActive = -1;
        int leastCount = 0;
        int[] leastIndexes = new int[length];
        int[] weights = new int[length];
        int totalWeight = 0;
        int firstWeight = 0;
        boolean sameWeight = true;

        // 过滤出所有起码沉闷服务
        for (int i = 0; i < length; i++) {Invoker<T> invoker = invokers.get(i);
            // 获取这个 invoker 沉闷数
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
            // 获取 invoker 的权重 默认 100.
            int afterWarmup = getWeight(invoker, invocation);
            // 权重保留到汇合中
            weights[i] = afterWarmup;
            // 找到最小沉闷数 invoker
            if (leastActive == -1 || active < leastActive) {
                // 重置最小沉闷数值
                leastActive = active;
                // 重置最小沉闷计数
                leastCount = 1;
                // 记录最小沉闷数对应索引
                leastIndexes[0] = i;
                // 重置权重共计
                totalWeight = afterWarmup;
                // 记录第一个最小沉闷数对应权重值
                firstWeight = afterWarmup;
                // 重置是否具备雷同权重标记
                sameWeight = true;
                // 以后 invoker 沉闷数等于最小沉闷数
            } else if (active == leastActive) {
                // 最小沉闷数 leastCount 减少并且记录以后 invoker 对应索引
                leastIndexes[leastCount++] = i;
                // 累计 invoker 权重值
                totalWeight += afterWarmup;
                // 判断是否权重值雷同
                if (sameWeight && i > 0
                        && afterWarmup != firstWeight) {sameWeight = false;}
            }
        }
        // 最小沉闷数 invoker 只有一个
        if (leastCount == 1) {
            // 间接返回
            return invokers.get(leastIndexes[0]);
        }
        // 具备多个雷同沉闷数、具备不同权重且权重和大于 0
        if (!sameWeight && totalWeight > 0) {// 依据权重值进行一个 (0,totalWeight] 整数随机值
            int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
            // 基于随机值抉择所在区间和随机负载平衡算法统一
            for (int i = 0; i < leastCount; i++) {int leastIndex = leastIndexes[i];
                offsetWeight -= weights[leastIndex];
                if (offsetWeight < 0) {return invokers.get(leastIndex);
                }
            }
        }
        // 如果所有权重值雷同或者 totalWeight= 0 返回服务列表中随机一个服务
        return invokers.get(leastIndexes[ThreadLocalRandom.current().nextInt(leastCount)]);
    }
}

2.3.2 算法过程剖析

1. 初始化最小沉闷值，最小沉闷数，最小沉闷的 invoker 索引（index）, 权重数组。
2. 循环 invokers 服务列表获取 invoker 沉闷数、权重且过滤出所有起码沉闷服务并记录最小沉闷数对应索引，同时标记服务列表是否存在不同权重值。
3. 如果最小沉闷数为一间接反正这个服务。
4. 如果存在多个雷同沉闷数、具备不同权重且权重和大于 0，则依据权重值进行一个 (0, totalWeight ] 整数随机值
   而后基于随机值抉择所在区间和下面讲的随机负载平衡算法统一。
5. 如果所有权重值雷同或者 totalWeight=0 返回服务列表中随机一个服务。

Tips：上述算法存在肯定的难度，稍作理解即可。

2.4 一致性 Hash 算法

要明确什么是一致性 Hash 首先得晓得什么是 Hash 算法。咱们在学习 HashMap 的 JDK 源码时能够理解到 HashMap 的数据结构由一个数组 + 链表形成如下所示：

上图简略画出了 HashMap 底层数据存储构造，从中能够看出当咱们调用 HashMap.put(K key, V value) 办法时通过 hash(key) 计算出一个 Hash 值与数组长度求模失去一个索引即为数组下标对应地位，当这个地位存在元素时即产生 Hash 碰撞就会产生一个链。

一个常见的场景，比方咱们在申请某个服务时须要固定拜访某一台服务器如下所示：

从图中能够看出 Client01 通过 Nginx 固定拜访 Service01、Client02 通过 Nginx 固定拜访 Service02、Client03 通过 Nginx 固定拜访 Service03。要满足这种场景就须要应用 Hash 算法。然而一般 Hash 算法存在一个问题是 Hash 进去的是理论后端服务节点，当其中某个服务宕机时 Hash 计算因子产生扭转 ( 求模的分子 ) 如果计算 Hash 因子不调整则可能会路由到宕机那台服务就会存在问题。那一致性 Hash 就是解决这样的问题。

什么是一致性 Hash 呢？一致性哈希算法是采纳的环形哈希空间的形式，它首先依据 Ip 或者其余信息为机器节点生成一个 Hash 值，它投射到一个 [0,2^32-1] 的圆环中。之后咱们能够认为它是一个锚点。当申请进来后，它携带的数据，都对立生成一个 Hash 值，这时候比对之前的机器节点信息产生的 Hash 值，当遇到第一个大于或者等于该 Hash 值的缓存节点，咱们将这个数据便归属于这个机器节点。

假如虚构节点 12 个、实在服务 3 个别离是：Invoker1、Invoker2、Invoker3。下图展现了服务节点怎么进行虚构节点映射的过程：

1. Invoker1 通过 Hash 计算后映射到环上对应地位

2. Invoker2 通过 Hash 计算后映射到环上对应地位

3. Invoker3 通过 Hash 计算后映射到环上对应地位

上图中长方形色块代表实在的服务，圆形代表虚构节点。所有同一种色彩的圆形虚构节点归属于同一色块的长方形色块所代表的实在服务。

2.4.1 算法实现

public class ConsistentHashLoadBalance extends AbstractLoadBalance {
    public static final String NAME = "consistenthash";

    /**
     * Hash nodes name
     */
    public static final String HASH_NODES = "hash.nodes";

    /**
     * Hash arguments name
     */
    public static final String HASH_ARGUMENTS = "hash.arguments";

    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<String, ConsistentHashSelector<?>>();

    @SuppressWarnings("unchecked")
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // 获取调用办法名称
        String methodName = RpcUtils.getMethodName(invocation);
        // 生成惟一标识
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
        int identityHashCode = System.identityHashCode(invokers);
        // 对 ConsistentHashSelector 进行缓存
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        // 缓存中 selector == null 或 当 invokers 中服务发生变化 服务上限 / 服务上线 invokers hash 值产生变更须要从新构建 ConsistentHashSelector
        if (selector == null || selector.identityHashCode != identityHashCode) {selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }
        // 执行服务抉择
        return selector.select(invocation);
    }

    private static final class ConsistentHashSelector<T> {

        private final TreeMap<Long, Invoker<T>> virtualInvokers;

        private final int replicaNumber;

        private final int identityHashCode;

        private final int[] argumentIndex;

        ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
            // 虚构 Invoker（虚构节点）this.virtualInvokers = new TreeMap<>();
            this.identityHashCode = identityHashCode;
            URL url = invokers.get(0).getUrl();
            // 虚构节点数
            this.replicaNumber = url.getMethodParameter(methodName, HASH_NODES, 160);
            String[] index = COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, HASH_ARGUMENTS, "0"));// 参加 hash 的参数索引
            argumentIndex = new int[index.length];
            for (int i = 0; i < index.length; i++) {argumentIndex[i] = Integer.parseInt(index[i]);
            }
            for (Invoker<T> invoker : invokers) {String address = invoker.getUrl().getAddress();//127.0.0.1:1
                // 将虚构节点细化为（replicaNumber / 4）份
                for (int i = 0; i < replicaNumber / 4; i++) {
                    // 地址 + 序号进行摘要
                    byte[] digest = md5(address + i);
                    // 每份 4 个点散列到 treeMap 中
                    for (int h = 0; h < 4; h++) {long m = hash(digest, h);
                        virtualInvokers.put(m, invoker);
                    }
                }
            }
        }

        public Invoker<T> select(Invocation invocation) {String key = toKey(invocation.getArguments());
            byte[] digest = md5(key);
            return selectForKey(hash(digest, 0));
        }
        private Invoker<T> selectForKey(long hash) {
            // 获取至多大于或等于给定 hash 值
            Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
            if (entry == null) {
                // 获取第一个 Entry
                entry = virtualInvokers.firstEntry();}
            return entry.getValue();}

    }

}

2.4.2 算法过程剖析

1. 虚构节点构建：

• 首先初始化虚构节点数，默认 160 能够通过内部参数指定。
• 获取参加 Hash 计算的参数值，hash.arguments 属性值，缺省是 0 参数地位。
• 循环 invokers 服务列表依据 ip+port+ 序号 生成 replicaNumber 个的节点（生成虚构节点），其中 key 就是算进去的 Hash 值，value 就是 invoker 且 key 的值从小到大排序的。

2. 节点查找

• 依据 hash.arguments参数取出对应位的参数，拼接成 key。
• 应用 md5 对 key 计算，应用 Hash 算法算出 key 对应的 Hash 值。
• 依据这个 key 的 Hash 值找出对应的 invoker，这里返回键值大于或等于 key 的那局部，而后再取第一个。

Tips：上述算法存在肯定的难度，稍作理解即可。

3. 小结

在本大节中咱们次要学习了 Dubbo 中常见的负载平衡算法以及应用场景。

本节课程的重点如下：

1. 了解 什么是负载平衡算法
2. 晓得负载平衡算法应用场景
3. 理解 Dubbo 中有哪些负载平衡算法
4. 理解 Dubbo 负载平衡算法实现逻辑

作者

集体从事金融行业，就任过易极付、思建科技、某网约车平台等重庆一流技术团队，目前就任于某银行负责对立领取零碎建设。本身对金融行业有强烈的喜好。同时也实际大数据、数据存储、自动化集成和部署、散布式微服务、响应式编程、人工智能等畛域。同时也热衷于技术分享创建公众号和博客站点对常识体系进行分享。关注公众号：青年 IT 男 获取最新技术文章推送！

博客地址： http://youngitman.tech

微信公众号：