面试积累-Dubbo-dubbo的负载均衡的算法

深藏阁楼爱情的钟 2023-07-16 03:44 35阅读 0赞

Dubbo 提供了常见的集群策略实现，并预扩展点予以自行实现。

*  Random LoadBalance: 随机选取提供者策略，有利于动态调整提供者权 重。截面碰撞率高，调用次数越多，分布越均匀；
 *  RoundRobin LoadBalance: 轮循选取提供者策略，平均分布，但是存在请 求累积的问题；
 *  LeastActive LoadBalance: 最少活跃调用策略，解决慢提供者接收更少的 请求；
 *  ConstantHash LoadBalance: 一致性 Hash 策略，使相同参数请求总是发 到同一提供者，一台机器宕机，可以基于虚拟节点，分摊至其他提供者，避 免引起提供者的剧烈变动；

--------------------

> 推荐文章：https://blog.csdn.net/wueryan/article/details/91129212

前面的推荐的文章写的真的很好，有兴趣的可以拜读拜读。  
各种负载均很算法的特点：

# 一、Random LoadBalance（权重随机算法-默认）： #

这个算法很简单，就是生成一个随机值；  
假如我们现在有ABC三台服务器：

*  服务器A：权重weight=1
 *  服务器B：权重weight=2
 *  服务器C：权重weight=7

所以这些服务器totalWeight = AWeight + BWeight + CWeight = 10。这样生成10以内的随机数；

*  \[0, 1)：属于服务器A
 *  \[1, 2)：属于服务器B
 *  \[2, 10)：属于服务器C

private final Random random = new Random();
    
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { 
        int length = invokers.size();
        // 总权重值
        int totalWeight = 0;
        // 是否所有的Invoker服务器的权重值都相等，若都相等，则在Invoker列表中随机选中一个即可
        boolean sameWeight = true;
        for (int i = 0; i < length; i++) { 
            int weight = getWeight(invokers.get(i), invocation);
            totalWeight += weight; // Sum
            if (sameWeight && i > 0 && weight != getWeight(invokers.get(i - 1), invocation)) { 
                sameWeight = false;
            }
        }
        // 生成totalWeight以内的随机数offset，然后该offset挨个减Invoker的权重，一旦小于0，就选中当前的Invoker
        if (totalWeight > 0 && !sameWeight) { 
            int offset = random.nextInt(totalWeight);
            for (int i = 0; i < length; i++) { 
                offset -= getWeight(invokers.get(i), invocation);
                if (offset < 0) { 
                    return invokers.get(i);
                }
            }
        }
        return invokers.get(random.nextInt(length));
    }

--------------------

# 二、RoundRobin LoadBalance（轮询策略）： #

轮询：简单点说就是挨个来呗，但是理论基础就是每台机器的性能一样。  
但是，实际生产过程中个别机器的性能一旦遇到瓶颈了，就容易造成雪崩现象，所以加入了权重理念；

public class RoundRobinLoadBalance extends AbstractLoadBalance { 
    
        public static final String NAME = "roundrobin";
    
        private final ConcurrentMap<String, AtomicPositiveInteger> sequences = 
            new ConcurrentHashMap<String, AtomicPositiveInteger>();
    
        @Override
        protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { 
            // key = 全限定类名 + "." + 方法名，比如 com.xxx.DemoService.sayHello
            String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
            int length = invokers.size();
            // 最大权重
            int maxWeight = 0;
            // 最小权重
            int minWeight = Integer.MAX_VALUE;
            final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
            // 权重总和
            int weightSum = 0;
    
            // 下面这个循环主要用于查找最大和最小权重，计算权重总和等
            for (int i = 0; i < length; i++) { 
                int weight = getWeight(invokers.get(i), invocation);
                // 获取最大和最小权重
                maxWeight = Math.max(maxWeight, weight);
                minWeight = Math.min(minWeight, weight);
                if (weight > 0) { 
                    // 将 weight 封装到 IntegerWrapper 中
                    invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight));
                    // 累加权重
                    weightSum += weight;
                }
            }
    
            // 查找 key 对应的对应 AtomicPositiveInteger 实例，为空则创建。
            // 这里可以把 AtomicPositiveInteger 看成一个黑盒，大家只要知道
            // AtomicPositiveInteger 用于记录服务的调用编号即可。至于细节，
            // 大家如果感兴趣，可以自行分析
            AtomicPositiveInteger sequence = sequences.get(key);
            if (sequence == null) { 
                sequences.putIfAbsent(key, new AtomicPositiveInteger());
                sequence = sequences.get(key);
            }
    
            // 获取当前的调用编号
            int currentSequence = sequence.getAndIncrement();
            // 如果最小权重小于最大权重，表明服务提供者之间的权重是不相等的
            if (maxWeight > 0 && minWeight < maxWeight) { 
                // 使用调用编号对权重总和进行取余操作
                int mod = currentSequence % weightSum;
                // 进行 maxWeight 次遍历
                for (int i = 0; i < maxWeight; i++) { 
                    // 遍历 invokerToWeightMap
                    for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) { 
    					// 获取 Invoker
                        final Invoker<T> k = each.getKey();
                        // 获取权重包装类 IntegerWrapper
                        final IntegerWrapper v = each.getValue();
                        
                        // 如果 mod = 0，且权重大于0，此时返回相应的 Invoker
                        if (mod == 0 && v.getValue() > 0) { 
                            return k;
                        }
                        
                        // mod != 0，且权重大于0，此时对权重和 mod 分别进行自减操作
                        if (v.getValue() > 0) { 
                            v.decrement();
                            mod--;
                        }
                    }
                }
            }
            
            // 服务提供者之间的权重相等，此时通过轮询选择 Invoker
            return invokers.get(currentSequence % length);
        }
    
        // IntegerWrapper 是一个 int 包装类，主要包含了一个自减方法。
        private static final class IntegerWrapper { 
            private int value;
    
            public void decrement() { 
                this.value--;
            }
            
            // 省略部分代码
        }
    }

--------------------

# 三、LeastActive LoadBalance（最少活跃调用数算法）： #

核心思想：

*  每个机器都有一个标记-Invoker，每次调用到该机器Invoker+1，处理完成Invoker-1；
 *  每次请求来的时候，找到活跃最小数的Invoker。
 *  最小活跃的存在多个的时候，Dubbo使用额外的int数组记录这些Invoker在原invokers的索引，通过随即权重的算法决定最终的Invoker；

private final Random random = new Random();
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { 
        int length = invokers.size(); // Number of invokers
        // “最小活跃数”的值
        int leastActive = -1;
        // 具有相同“最小活跃数”的Invoker（即Provider）的数量
        int leastCount = 0;
        // “最小活跃数”的Invoker可能不止一个，因此需要记录所有具有“最小活跃数”的Invoker在invokers列表中的索引位置
        int[] leastIndexs = new int[length];
        // 记录所有“最小活跃数”的Invoker总的权重值
        int totalWeight = 0;
        // 记录第一个“最小活跃数”的Invoker的权重值
        int firstWeight = 0;
        // 所有的“最小活跃数”的Invoker的权重值是否都相等
        boolean sameWeight = true;
        for (int i = 0; i < length; i++) { 
            Invoker<T> invoker = invokers.get(i);
            // 活跃数
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
            // 权重
            int afterWarmup = getWeight(invoker, invocation); 
            if (leastActive == -1 || active < leastActive) { 
                leastActive = active; 
                leastCount = 1; 
                leastIndexs[0] = i; 
                totalWeight = afterWarmup; 
                firstWeight = afterWarmup; 
                sameWeight = true;
            } else if (active == leastActive) {  
                leastIndexs[leastCount++] = i; 
                totalWeight += afterWarmup;
                if (sameWeight && i > 0 && afterWarmup != firstWeight) { 
                    sameWeight = false;
                }
            }
        }
        if (leastCount == 1) { 
            return invokers.get(leastIndexs[0]);
        }
        if (!sameWeight && totalWeight > 0) { 
            int offsetWeight = random.nextInt(totalWeight) + 1;
            for (int i = 0; i < leastCount; i++) { 
                int leastIndex = leastIndexs[i];
                offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
                if (offsetWeight <= 0)
                    return invokers.get(leastIndex);
            }
        }
        return invokers.get(leastIndexs[random.nextInt(leastCount)]);
    }

--------------------

# 四、ConstantHash LoadBalance（哈希一致性策略）： #

算法过程如下：

*  ① 根据IP或其他信息为缓存节点生成一个hash值，将该hash值映射到\[0, 2^32-1\]的圆环中。
 *  ② 当查询或写入缓存时，为缓存的key生成一个hash值，查找第一个大于等于该hash值的缓存节点，以应用该缓存
 *  ③ 若当前节点挂了，则依然可以计算得到一个新的缓存节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70]  
    但是因为，这种算法容易发生数据倾斜；

> 数据倾斜:由于节点不够分散，导致大量请求落到了同一个节点上，而其他节点只会接收到了少量请求的情况

所以，Dubbo引入了虚拟节点的方案；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70]: /images/20230528/8f174182ad2149acae647ada6b958d16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/7d329c5a448d4a23afaa2835c95961ee.png