【Dubbo】Cluster 层 LoadBalance

爱被打了一巴掌 2023-01-19 15:49 3阅读 0赞

主要内容

*  LoadBalance 的实现原理

讲解 LoadBalance 及实现原理

# 负载均衡的实现 #

在整个集群容错流程中 ， 首先经过 Directory 获取所有 Invoker 列表 ， 然后经过 Router 根据路由规则过滤 Invoker, 最后幸存下来的 Invoker 还需要经过负载均衡这一关 ， 选出最终要调用的 Invoker

## 1 包装后的负载均衡 ##

2 节介绍了 7 种容错策略 ， 发现在很多容错策略中都会使用负载均衡方法 ， 并且所有的容错策略中的负载均衡都使用了抽象父类 Abstractclusterinvoker 中定义的 `Invoker<T> select` 方法 ， 而并不是直接使用 LoadBalance 方法 。 因为抽象父类在LoadBalance 的基础上又封装了一些新的特性 ：

*  (1) 粘滞连接 。 Dubbo 中有一种特性叫粘滞连接 ， 以下内容摘自官方文档 ：粘滞连接用于有状态服务 ， 尽可能让客户端总是向同一提供者发起调用 ， 除非该提供者 “ 挂了 ” ， 再连接另一台 。粘滞连接将自动开启延迟连接 ， 以减少长连接数 。<dubbo:protocol name= “dubbo” sticky=“true” />
 *  (2) 可用检测 。 Dubbo 调用的 URL 中 ， 如果含有 cluster.availablecheck=false, 则不会检测远程服务是否可用 ， 直接调用 。 如果不设置 ， 则默认会开启检查 ， 对所有的服务都做是否可用的检查 ， 如果不可用 ， 则再次做负载均衡 。
 *  (3) 避免重复调用 。 对于已经调用过的远程服务 ， 避免重复选择 ， 每次都使用同一个节点 。这种特性主要是为了避免并发场景下 ， 某个节点瞬间被大量请求 。整个逻辑过程大致可以分为 4 步 ：
    
     *  (1) 检查 URL 中是否有配置粘滞连接 ， 如果有则使用粘滞连接的 Invoker 。 如果没有配置粘滞连接 ， 或者重复调用检测不通过 、 可用检测不通过 ， 则进入第 2 步 。
     *  (2) 通过 ExtensionLoader 获取负载均衡的具体实现 ， 并通过负载均衡做节点的选择 。 对选择出来的节点做重复调用 、 可用性检测 ， 通过则直接返回 ， 否则进入第 3 步 。
     *  (3) 进行节点的重新选择 。 如果需要做可用性检测 ， 则会遍历 Directory 中得到的所有节点 ， 过滤不可用和已经调用过的节点 ， 在剩余的节点中重新做负载均衡 ； 如果不需要做可用性检测 ， 那么也会遍历 Directory 中得到的所有节点 ， 但只过滤已经调用过的 ， 在剩余的节点中重新做负载均衡 。 这里存在一种情况 ， 就是在过滤不可用或已经调用过的节点时 ， 节点全部被过滤 ， 没有剩下任何节点 ， 此时进入第 4 步 。
     *  (4) 遍历所有已经调用过的节点 ， 选出所有可用的节点 ， 再通过负载均衡选出一个节点并返回 。 如果还找不到可调用的节点 ， 则返回 null 。从上述逻辑中 ， 我们可以得知 ， 框架会优先处理粘滞连接 。 否则会根据可用性检测或重复调用检测过滤一些节点 ， 并在剩余的节点中做负载均衡 。 如果可用性检测或重复调用检测把节点都过滤了 ， 则兜底的策略是 ： 在己经调用过的节点中通过负载均衡选择出一个可用的节点 。以上就是封装过的负载均衡的实现 ， 下面讲解原始的 LoadBalance 是如何实现的

## 2 负载均衡的总体结构 ##

Dubbo 现在内置了 4 种负载均衡算法 ， 用户也可以自行扩展 ， 因为 LoadBalance 接口上有@SPI 注解

*负载均衡接口*  
![在这里插入图片描述][20210508201636804.png]  
从代码中我们可以知道默认的负载均衡实现就是 RandomLoadBalance, 即随机负载均衡 。由于 select 方法上有 @Adaptive (“loadbalance”) 注解 ， 因此我们在 URL 中可以通过loadbalance=xxx 来动态指定 select 时的负载均衡算法 。 下面我们来看一下官方文档中对所有负载均衡算法的说明 ， 如表所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]  
4 种负载均衡算法都继承自同一个抽象类 ， 使用的也是模板模式 ， 抽象父类中己经把通用的逻辑完成 ， 留了一个抽象的 doSelect 方法给子类实现 。 负载均衡的接口关系如图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]  
抽象父类 AbstractLoadBalance 有两个权重相关的方法 ： calculateWarmupWeight 和 getWeight。 getWeight 方法就是获取当前 Invoker 的权重 ， calculateWarmupWeight 是计算具体的权重 。 getWeight 方法中会调用 calculateWarmupWeight

*计算权重*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]  
calculateWarmupWeight 的计算逻辑比较简单 ， 由于框架考虑了服务刚启动的时候需要有一个预热的过程 ， 如果一启动就给予 100% 的流量 ， 则可能会让服务崩溃 ， 因此实现了calculateWarmupWeight 方法用于计算预热时候的权重 ， 计算逻辑是 ： ( 启动至今时间 / 给予的预热总时间) \* 权重 。 例如 ： 假设我们设置 A 服务的权重是 5, 让它预热 10 分钟 ， 则第一分钟的时候 ， 它的权重变为 (1/10) X5 = 0.5, 0.5/5 = 0.1, 也就是只承担 10% 的流量 ； 10 分钟后 ， 权重就变为 (10/10) X5 = 5, 也就是权重变为设置的 100%, 承担了所有的流量 。

抽象父类的 select 方法是进行具体负载均衡逻辑的地方 ， 这里只是做了一些判断并调用需要子类实现的 doSelect 方法 ， 因此不再赘述 。 下面直接看一下不同子类实现 doSelect 的方式 。

## 3 Random 负载均衡 ##

Random 负载均衡是按照权重设置随机概率做负载均衡的 。 这种负载均衡算法并不能精确地平均请求 ， 但是随着请求数量的增加 ， 最终结果是大致平均的 。 它的负载计算步骤如下 ：

*  (1) 计算总权重并判断每个 Invoker 的权重是否一样 。 遍历整个 Invoker 列表 ， 求和总权重 。 在遍历过程中 ， 会对比每个 Invoker 的权重 ， 判断所有 Invoker 的权重是否相同 。
 *  (2) 如果权重相同 ， 则说明每个 Invoker 的概率都一样 ， 因此直接用 nextlnt 随机选一个Invoker 返回即可 。
 *  (3) 如果权重不同 ， 则首先得到偏移值 ， 然后根据偏移值找到对应的 Invoker

*随机负载均衡源码*  
![在这里插入图片描述][20210508201827226.png]  
看源码可能还没理解原理 ， 下面做一个场景假设 ： 假设有 4 个 Invoker, 它们的权重分别是 1 、 2 、 3 、 4, 则总权重是 1 +2+3+4=10 。 说明每个 Invoker 分别有 1/10 、 2/10 、 3/10 、 4/10 的概率会被选中 。 然后 nextlnt(10) 会返回 0 〜 10 之间的一个整数 ， 假设为 5 。 如果进行累减,则减到 3 后会小于 0, 此时会落入 3 的区间 ， 即选择 3 号 Invoker, 如图所示  
![在这里插入图片描述][20210508201850997.png]

## 4 RoundRobin 负载均衡 ##

权重 ， 轮询负载均衡会根据设置的权重来判断轮询的比例 。 普通轮询负载均衡的好处是每个节点获得的请求会很均匀 ， 如果某些节点的负载能力明显较弱 ， 则这个节点会堆积比较多的请求 。 因此普通的轮询还不能满足需求 ， 还需要能根据节点权重进行干预 。 权重轮询又分为普通权重轮询和平滑权重轮询 。 普通权重轮询会造成某个节点会突然被频繁选中 ， 这样很容易突然让一个节点流量暴增 。 Nginx 中有一种叫平滑轮询的算法 ( smooth weighted round-robinbalancing), 这种算法在轮询时会穿插选择其他节点 ， 让整个服务器选择的过程比较均匀 ， 不会“ 逮住 ” 一个节点一直调用 oDubbo 框架中最新的 RoundRobin 代码已经改为平滑权重轮询算法 。

我们先来看一下 Dubbo 中 RoundRobin 负载均衡的工作步骤 ， 如下 ：

*  (1) 初始化权重缓存 Map 。 以每个 Invoker 的 URL 为 key, 对象 WeightedRoundRobin 为 value 生成一个 ConcurrentMap, 并把这个 Map 保存到全局的 methodWeightMap 中 ： ConcurrentMap<String, ConcurrentMap<String , WeightedRoundRobin>> methodWeightMap 。 methodWeightMap 的 key 是每个接口 + 方法名 。 这一步只会生成这个缓存 Map, 但里面是空的 ， 第 2 步才会生成每个 Invoker 对应的键值 。
    
    WeightedRoundRobin 封装了每个 Invoker 的权重 ， 对象中保存了三个属性  
    ![在这里插入图片描述][20210508201924528.png]
 *  (2) 遍历所有 Invoker 。 首先 ， 在遍历的过程中把每个 Invoker 的数据填充到第 1 步生成的权重缓存 Map 中 。 其次 ， 获取每个 Invoker 的预热权重 ， 新版的框架 RoundRobin 也支持预热 ，通过和 Random 负载均衡中相同的方式获得预热阶段的权重 。 如果预热权重和 Invoker 设置的权重不相等 ， 则说明还在预热阶段 ， 此时会以预热权重为准 。 然后 ， 进行平滑轮询 。 每个 Invoker会把权重加到自己的 current 属性上 ， 并更新当前 Invoker 的 lastUpdate 。 同时累加每个 Invoker的权重到 totalweighto 最终 ， 遍历完后 ， 选出所有 Invoker 中 current 最大的作为最终要调用的节点 。
 *  (3) 清除已经没有使用的缓存节点 。 由于所有的 Invoker 的权重都会被封装成一个weightedRoundRobin 对象 ， 因此如果可调用的 Invoker 列表数量和缓存 weightedRoundRobin 对象的 Map 大小不相等 ， 则说明缓存 Map 中有无用数据 （ 有些 Invoker 己经不在了 ， 但 Map 中还有缓存 ） 。
    
    为什么不相等就说明有老数据呢 ？ 如果 Invoker 列表比缓存 Map 大 ， 则说明有没被缓存的Invoker, 此时缓存 Map 会新增数据 。 因此缓存 Map 永远大于等于 Invoker 列表 。
    
    清除老旧数据时 ， 各线程会先用 CAS 抢占锁 （ 抢到锁的线程才做清除操作 ， 抢不到的线程就直接跳过 ， 保证只有一个线程在做清除操作 ） ， 然后复制原有的 Map 到一个新的 Map 中 ， 根据 lastupdate 清除新 Map 中的过期数据 （ 默认 60 秒算过期 ） ， 最后把 Map 从旧的 Map 引用修改到新的 Map 上面 。 这是一种 CopyOnWrite 的修改方式 。
 *  （4） 返回 Invoker 。 注意 ， 返回之前会把当前 Invoker 的 current 减去总权重 。 这是平滑权重轮询中重要的一步 。

看了这个逻辑 ， 很多读者可能也没明白整个轮询过程 ， 因为穿插了框架逻辑 。 因此这里把算法逻辑提取出来 ：

*  （1） 每次请求做负载均衡时 ， 会遍历所有可调用的节点 （ Invoker 列表 ） 。 对于每个 Invoker,让它的 current = current + weight 。 属性含义见 weightedRoundRobin 对象 。 同时累加每个Invoker 的 weight 到 totalWeight, 即 totalweight = totalweight + weight
 *  （2） 遍历完所有 Invoker 后 ， current 值最大的节点就是本次要选择的节点 。 最后 ， 把该节点的 current 值减去 totalWeight, 即 current = current - totalweight

假设有 3 个 Invoker ： A 、 B 、 C, 它们的权重分别为 1 、 6 、 9, 初始 current 都是 0, 则平滑权重轮询过程如表所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]  
从这 16 次的负载均衡来看 ， 我们可以清楚地得知 ， A 刚好被调用了 1 次 ， B 刚好被调用了6 次 ， C 刚好被调用了 9 次 。 符合权重轮询的策略 ， 因为它们的权重比是 1 ： 6 ： 9 0 此外 ， C 并没有被频繁地一直调用 ， 其中会穿插 B 和 A 的调用 。 至于平滑权重轮询的数学原理 ， 就不在讨论的范围内了 ， 感兴趣的读者可以去进一步了解 。

## 5 LeastActive 负载均衡 ##

LeastActive 负载均衡称为最少活跃调用数负载均衡 ， 即框架会记下每个 Invoker 的活跃数 ，每次只从活跃数最少的 Invoker 里选一个节点 。 这个负载均衡算法需要配合 ActiveLimitFilter过滤器来计算每个接口方法的活跃数 。 最少活跃负载均衡可以看作 Random 负载均衡的 “ 加强版 ” ， 因为最后根据权重做负载均衡的时候 ， 使用的算法和 Random 的一样 。 我们现在配合一些代码来看一下具体的运行逻辑 ， 不重要的代码直接使用省略

*LeastActive 负载均衡源码*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4]  
从代码清单中我们可以得知其逻辑 ： 遍历所有 Invoker, 不断寻找最小的活跃数( leastActive ), 如果有多个 Invoker 的活跃数都等于 least Active, 则把它们保存到同一个集合中 ，最后在这个 Invoker 集合中再通过随机的方式选出一个 Invoker.

那最少活跃的计数又是如何知道的呢 ？在 ActiveLimitFilter 中 ， 只要进来一个请求 ， 该方法的调用的计数就会原子性 +1 。 整个Invoker 调用过程会包在 try-catch-finally 中 ， 无论调用结束或出现异常 ， finally 中都会把计数原子 -1 。 该原子计数就是最少活跃数 。

## 6 一致性 Hash 负载均衡 ##

一致性 Hash 负载均衡可以让参数相同的请求每次都路由到相同的机器上 。 这种负载均衡的方式可以让请求相对平均 ， 相比直接使用 Hash 而言 ， 当某些节点下线时 ， 请求会平摊到其他服务提供者 ， 不会引起剧烈变动 。 普通一致性 Hash 的简单示例如图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 5]  
普通一致性 Hash 会把每个服务节点散列到环形上 ， 然后把请求的客户端散列到环上 ， 顺时针往前找到的第一个节点就是要调用的节点 。 假设客户端落在区域 2, 则顺时针找到的服务 C就是要调用的节点 。 当服务 C 宕机下线 ， 则落在区域 2 部分的客户端会自动迁移到服务 D 上 。这样就避免了全部重新散列的问题 。

普通的一致性 Hash 也有一定的局限性 ， 它的散列不一定均匀 ， 容易造成某些节点压力大 。因此 Dubbo 框架使用了优化过的 Ketama 一致性 Hash 。 这种算法会为每个真实节点再创建多个虚拟节点 ， 让节点在环形上的分布更加均匀 ， 后续的调用也会随之更加均匀 下面我们来看下一致性 Hash 的实现原理

*— 致性 Hash 负载均衡源码*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 6]

整个逻辑的核心在 ConsistentHashSelector 中 ， 因此我们继续来看 ConsistentHashSelector 是如何初始化的 。 ConsistentHashSelector 初始化的时候会对节点进行散列 ， 散列的环形是使用一个 TreeMap 实现的 ， 所有的真实 、 虚拟节点都会放入 TreeMap。 把节点的 IP+ 递增数字做 “ MD5 ” ，以此作为节点标识 ， 再对标识做 “ Hash ” 得到 TreeMap 的 key, 最后把可以调用的节点作为TreeMap 的 value

*一致性 Hash 散列源码*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 7]  
TreeMap 实现一致性 Hash ： 在客户端调用时候 ， 只要对请求的参数也做 “ MD5 ” 即可 。 虽然此时得到的 MD5 值不一定能对应到 TreeMap 中的一个 key, 因为每次的请求参数不同 。 但是由于 TreeMap 是有序的树形结构 ， 所以我们可以调用 TreeMap 的 ceilingEntry 方法 ， 用于返回一个至少大于或等于当前给定 key 的 Entry, 从而达到顺时针往前找的效果 。 如果找不到 ， 则使用 firstEntry 返回第一个节点 。

# 小结 #

负载均衡接口的实现原理 ， 介绍了三种不同路由规则的实现方式和四种不同负载均衡策略的实现方式 。

[20210508201636804.png]: /images/20221021/dcbc7c6f8a354eb9938e8e1d29358478.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221021/8ad78a013fe0493389a4ce10e5b3a2a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221021/25b535413b2a4cb88dacd671435930ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]: /images/20221021/9b9da13b2b024bdc99f5f874be21a9be.png
[20210508201827226.png]: /images/20221021/b4724c7989594567a3c421fa667a3450.png
[20210508201850997.png]: /images/20221021/9ebf75e2555c41e1a8bf7b8476d04523.png
[20210508201924528.png]: /images/20221021/98256fe572f341f1af7ba505e685d65d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]: /images/20221021/367cab8b7bff4537ae7ed486e67a9697.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4]: /images/20221021/8a885e614fb54beea3bb01ae0296195b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 5]: /images/20221021/1b2a2ac4bd8a4ffca417bfeb8eef8f82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 6]: /images/20221021/15cc0167f6a44036ba70333b356459be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 7]: /images/20221021/4e06d8f4133044e794dbe047468e41a3.png