[toc]
1 简介
Dubbo提供了4种负载均衡机制：
- 权重随机算法：
RandomLoadBalance - 最少活跃调用数算法：
LeastActiveLoadBalance - 一致性哈希算法：
ConsistentHashLoadBalance - 加权轮询算法：
RoundRobinLoadBalance
Dubbo的负载均衡算法均实现自LoadBalance接口，其类图结构如下：
1.1 自适应默认算法
Dubbo的负载均衡算法利用Dubbo的自适应机制，默认的实现为RandomLoadBalance（即：权重随机算法），接口如下：
1// 默认为RandomLoadBalance算法 2@SPI(RandomLoadBalance.NAME) 3public interface LoadBalance { 4 // 该方法为自适应方法 5 @Adaptive("loadbalance") 6 <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException; 7}
1.2 抽象基类
1.2.1 选择Invoker
抽象基类针对select()方法判断invokers集合的数量，如果集合中只有一个Invoker，则无需使用算法，直接返回即可：
1@Override 2public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) { 3 if (invokers == null || invokers.isEmpty()) 4 return null; 5 // 如果只有一个元素，无需负载均衡算法 6 if (invokers.size() == 1) 7 return invokers.get(0); 8 // 负载均衡算法：该方法为抽象方法，由子类实现 9 return doSelect(invokers, url, invocation); 10}
1.2.2 计算权重
抽象基类除了对select()方法进行了重写，还封装了服务提供者的权重计算逻辑。Dubbo的权重计算，考虑到服务预热（服务器启动后，以低功率方式运行一段时间，当服务器运行效率逐渐达到最佳状态）：
若当前的服务器运行时长
小于服务预热时间，对服务器降权，让服务器的权重降低。
1protected int getWeight(Invoker<?> invoker, Invocation invocation) { 2 // 从URL中获取服务器Invoker的权重信息 3 int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT); 4 if (weight > 0) { 5 // 获取服务器Invoker的启动时间戳 6 long timestamp = invoker.getUrl().getParameter(Constants.REMOTE_TIMESTAMP_KEY, 0L); 7 if (timestamp > 0L) { 8 int uptime = (int) (System.currentTimeMillis() - timestamp); 9 // 获取服务器Invoker的预热时长（默认10分钟） 10 int warmup = invoker.getUrl().getParameter(Constants.WARMUP_KEY, Constants.DEFAULT_WARMUP); 11 if (uptime > 0 && uptime < warmup) { 12 weight = calculateWarmupWeight(uptime, warmup, weight); 13 } 14 } 15 } 16 return weight; 17} 18// (uptime / warmup) * weight，即：(启动时长 / 预热时长) * 原权重值 19static int calculateWarmupWeight(int uptime, int warmup, int weight) { 20 int ww = (int) ((float) uptime / ((float) warmup / (float) weight)); 21 return ww < 1 ? 1 : (ww > weight ? weight : ww); 22}
2 负载均衡算法实现
2.1 加权随机算法
该算法思想简单：假如有服务器：
- A，权重weight=2
- B，权重weight=3
- C，权重weight=5
这些服务器totalWeight = AWeight + BWeight + CWeight = 10。这样生成10以内的随机数
- [0, 2)：属于服务器A
- [2, 5)：属于服务器B
- [5, 10)：属于服务器C
加权随机算法由RandomLoadBalance，其核心源码实现如下:
1private final Random random = new Random(); 2 3@Override 4protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { 5 int length = invokers.size(); 6 // 总权重值 7 int totalWeight = 0; 8 // 是否所有的Invoker服务器的权重值都相等，若都相等，则在Invoker列表中随机选中一个即可 9 boolean sameWeight = true; 10 for (int i = 0; i < length; i++) { 11 int weight = getWeight(invokers.get(i), invocation); 12 totalWeight += weight; // Sum 13 if (sameWeight && i > 0 && weight != getWeight(invokers.get(i - 1), invocation)) { 14 sameWeight = false; 15 } 16 } 17 // 生成totalWeight以内的随机数offset，然后该offset挨个减Invoker的权重，一旦小于0，就选中当前的Invoker 18 if (totalWeight > 0 && !sameWeight) { 19 int offset = random.nextInt(totalWeight); 20 for (int i = 0; i < length; i++) { 21 offset -= getWeight(invokers.get(i), invocation); 22 if (offset < 0) { 23 return invokers.get(i); 24 } 25 } 26 } 27 return invokers.get(random.nextInt(length)); 28}
2.2 最小活跃数算法
活跃调用数越小，表明该Provider的效率越高，单位时间内可以处理更多的请求。此时如果有新的请求，应该将请求优先分配给该Provider。Dubbo中，每个Provider都会保持一个active，表示该Provider的活跃数：
没收到一个请求，active的值加1，请求处理完成后，active的值减1。
Dubbo使用LeastActiveLoadBalance实现最小活跃数算法，LeastActiveLoadBalance引入了权重，若多个Provider的活跃数相同
则权重较高的
Provider被选中的几率更大
若权重相同，则随机选取一个Provider
该算法的核心思想：
-
循环遍历所有Invoker，找出活跃数最小的所有Invoker
-
如果有多个Invoker具有多个相同的最小活跃数，此时需要记录这些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)]); }
2.3 一致性哈希
该算法起初用于缓存系统的负载均衡，算法过程如下：
① 根据IP或其他信息为缓存节点生成一个hash值，将该hash值映射到[0, 2^32-1]的圆环中。
② 当查询或写入缓存时，为缓存的key生成一个hash值，查找第一个大于等于该hash值的缓存节点，以应用该缓存
③ 若当前节点挂了，则依然可以计算得到一个新的缓存节点
Dubbo通过引入虚拟节点，让所有的Invoker在圆环上分散开，避免数据倾斜（由于节点不够分散，导致大量请求落在同一个节点，而其他节点只会接受到少量请求）。Dubbo对一个Invoker默认使用160个虚拟节点：
如：Invoker1-1, invoker1-2, invoker1-3... invoker1-160
Dubbo使用ConsistentHashLoadBalance来实现一致性哈希算法，其内部定义ConsistentHashSelector内部类完成节点选择。Dubbo中使用方法的入参数值进行哈希，来选择落点到哪一个Invoker上。
1public class ConsistentHashLoadBalance extends AbstractLoadBalance { 2 // key：group+version+methodName，即调用方法的完整名称 3 // value：ConsistentHashSelector，利用该类完成节点选择 4 private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>(); 5 6 @Override 7 protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { 8 // 获取调用方法名 9 String methodName = RpcUtils.getMethodName(invocation); 10 String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName; 11 12 // 获取invokers的hashcode 13 int identityHashCode = System.identityHashCode(invokers); 14 ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key); 15 // 如果 invokers 是一个新的 List 对象，意味着服务提供者数量发生了变化 16 // 此时 selector.identityHashCode != identityHashCode 条件成立 17 if (selector == null || selector.identityHashCode != identityHashCode) { 18 // 创建新的 ConsistentHashSelector 19 selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode)); 20 selector = (ConsistentHashSelector<T>) selectors.get(key); 21 } 22 23 // 利用选择器，选择节点 24 return selector.select(invocation); 25 } 26 private static final class ConsistentHashSelector<T> {...} 27}
ConsistentHashLoadBalance#doSelect()方法主要是做前置工作，每个方法的一致性哈希选择具体由ConsistentHashSelector来实现：
1private static final class ConsistentHashSelector<T> { 2 // 使用TreeMap存储Invoker虚拟节点，保证查询效率 3 private final TreeMap<Long, Invoker<T>> virtualInvokers; 4 // 虚拟节点数量 5 private final int replicaNumber; 6 // invokers的hashCode值 7 private final int identityHashCode; 8 // 参数索引数组 9 private final int[] argumentIndex; 10 11 ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) { 12 this.virtualInvokers = new TreeMap<Long, Invoker<T>>(); 13 this.identityHashCode = identityHashCode; 14 URL url = invokers.get(0).getUrl(); 15 this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160); 16 // 获取参与 hash 计算的参数下标值，默认对方法的第一个参数进行 hash 运算 17 String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0")); 18 argumentIndex = new int[index.length]; 19 for (int i = 0; i < index.length; i++) { 20 argumentIndex[i] = Integer.parseInt(index[i]); 21 } 22 // 如下方法创建虚拟节点，每个invoker生成replicaNumber个虚拟结点， 23 for (Invoker<T> invoker : invokers) { 24 String address = invoker.getUrl().getAddress(); 25 for (int i = 0; i < replicaNumber / 4; i++) { 26 byte[] digest = md5(address + i); // digest是一个长度为16的数组 27 // 对 digest 部分字节进行4次 hash 运算，得到四个不同的 long 型正整数 28 for (int h = 0; h < 4; h++) { 29 // 根据h的值，对digest进行位运算。h=0，则0~3字节位运算；h=1，则4~7字节位运算。 30 long m = hash(digest, h); 31 virtualInvokers.put(m, invoker); 32 } 33 } 34 } 35 } 36}
选择节点，使用TreeMap#tailMap方法，可以获取到TreeMap中大于Key的子Map，子Map中第一个Entry即为选择的Invoker。因为TreeMap不是环形结构，因此如果没有取到任何值，则认为是第一个Key的值。如下： 
1public Invoker<T> select(Invocation invocation) { 2 // 根据argumentIndex，决定方法的哪几个参数值作为Key 3 String key = toKey(invocation.getArguments()); 4 byte[] digest = md5(key); 5 return selectForKey(hash(digest, 0)); 6} 7private Invoker<T> selectForKey(long hash) { 8 /* 9 TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>(); 10 tree_map.put(10, "Geeks"); 11 tree_map.put(15, "4"); 12 tree_map.put(20, "Geeks"); 13 tree_map.put(25, "Welcomes"); 14 tree_map.put(30, "You"); 15 System.out.println("The tailMap is " + tree_map.tailMap(15)); 16 // The tailMap is {15=4, 20=Geeks, 25=Welcomes, 30=You} 17 */ 18 Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry(); 19 if (entry == null) { 20 entry = virtualInvokers.firstEntry(); 21 } 22 return entry.getValue(); 23} 24 25private String toKey(Object[] args) { 26 StringBuilder buf = new StringBuilder(); 27 for (int i : argumentIndex) { 28 if (i >= 0 && i < args.length) { 29 buf.append(args[i]); 30 } 31 } 32 return buf.toString(); 33} 34
2.4 加权轮询算法
待补充