技术分享| 浅谈负载均衡算法实现

在真正讲解算法之前，我们需要知道什么是负载均衡。在软件架构设计中，我们的应用一般会跑在一个服务器上，而随着流量增加，单服务器所承载的压力也会不断增大，这时候我们通常会选择增加单服务器配置来提高请求吞吐效率，但这会带来两个问题。一是单服务器的配置不可能无限提升，单应用的优化也不能无限提升，一定会存在一个瓶颈。二是提升单服务器配置所带来的成本会越来越高。这时候，纵向的扩容所带来的局限就凸显出来，我们需要通过横向扩容来解决该场景也就是搭建集群，而问题就在于我们如何把现有的流量均匀地分配在集群中的各个服务器上，负载均衡由此而生。

在负载均衡的实现中，也有几种不同的实现，可以根据实际场景使用不同的算法来达到想要的效果。本文会列举一下几种常用的算法并讲解其实现原理：

• 随机

• 轮询

• 平滑加权轮询算法

• 一致性Hash算法

• 其他

随机算法

顾名思义，完全随缘的一种算法，从生产的角度上来讲不会去使用一个纯随机的方式去分配流量。这个方式还存在一个缺陷，在于随机算法需要提供的几台服务器的配置大致相同，这样才能够保证随机选择一定程度上是“公平”的。那如果提供服务器的配置有所不同，例如有些服务器配置高一些，那么我们就需要引入权重的概念来标志服务器的处理能力，然后去左右我们随机后的一个分配结果，下面我们来提供一段伪代码来讲解：

服务器名称及权重
A:5
B:3
C:2


把所有的权重放入数组中 [5, 3, 2]
根据权重的总和，生成一个10以内的随机数(5+3+2)
random=7


随机算法中我们希望在10次请求中，50%概率分配给A机器，30%概率分配给B机器，20%概率分配给C机器，那么我们可以通过三台机器的权重生成一个递增的权重轴，并确保每次随机出来的值一定在权重总和之内
0-----5---8--10
      A   B  C


第一次判断:
通过比对发现random值7大于数组内的第一个值，所以我们断定这个点无法落位在A服务器上，我们就利用数组中后两位值重新生成权重轴，并将random值改为本身和数组第一位权重的差值，这样就可以继续向后寻找
random>5; random=random-5; random=2;
0---3--5
    B  C
    
第二次判断：
发现计算后的random为2，小于数组第二位元素的值3，由此可得出该请求应落位于B服务器
random<3; retur

轮询算法的逻辑相对来说也比较简单，在没有权重的情况下，假如我们有三台服务器且对应编号为 ABC ，那么如果有五个请求，我们就会按照顺序平均分配至三台服务器中，结果为 ABCAB 。若加入权重因素的影响，那么我们同样可以使用随机算法中的伪代码去实现。我们只需要将变量 random 换成一个请求的递增序列即可，这样我们就可以使用递增序列的id去寻找对应在坐标轴上的位置，当然，请求序列的数值在一定时间后一定会大于轴上权重总和的最大值，这样我们就无法使该点落位，这时候只要对该序列的值对总权重取余即可，按照上述伪代码改造后的结果，我们会得到的结果为 AAAAABBBCC 。

在实现了刚才的轮询算法之后，大家应该就已经发现了问题，采用递增序列的random变量后，会在A服务器的权重完全消耗完毕才会把流量分配给下个服务器，这样的分配方式会导致A服务器的瞬时压力非常大，所以我们需要让我们的静态权重变成动态模式，让我们整个分配的结果从AAAAABBBCC变为ABCAABACBA，这也是 Nginx 中所使用的默认算法模式。

1. 首先我们进入第一轮的选举，我们先准备一个等于服务器长度的 currentWeight 数组，在第一列的位置 currentWeight 就等于当前 weight 值加上静态的 weight 所得出的结果，因为一开始我们默认为0，所以第一行第一列的值等于我们初始准备的权重；

2. 我们在计算后的权重中找出权重最高的一个做为我们选定的服务器，也就是 max(currentWeight) 列的值；

3. 在选举完成后，我们选举完成的元素需要减去静态权重的总和值，也就从(5-10)变成了 -5；

4. 完成上述逻辑后返回 max(currentWeight) 列所对应的服务器 hostname ，即服务器 A ；

5. 进入第二轮的选举后，上一行经过计算的 max(currentWeight) -= sum(weight) 列的每个元素需要加上自身初始的权重值，然而再进入第二轮的选举，循环往复。

可以看到，经过十轮之后我们的 currentWeight 会重新回到一个初始值状态进行新一轮的轮回，这也就达到了流量在时间范围内的动态分配，不会让权重大的服务器在较短时间承受流量冲击。

在介绍一致性 Hash 算法之前，我们可以先了解一下什么是 Hash 以及我们为什么推荐使用 Hash 算法。

Hash 函数：一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射 pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

碰撞（冲突）：如果两个关键字通过 Hash 函数得到的值是一样的，就是碰撞或冲突。

Hash 表（散列表）：根据散列函数和冲突处理将一组关键字分配在连续的地址空间内，并以散列值记录在表中的存储位置，这种表成为散列表。

从上面的引用我们可以得出以下几点结论：

• 任意输入通过 Hash 函数（例如 hash(key) ）计算后会得到一个唯一值，并且把计算后的映射关系存储在散列表中。

• 散列函数的输入和输出不是唯一对应关系，如果计算结果相同，输入值有可能是不同的，这就是Hash碰撞。

在负载均衡场景下，我们希望理想中的散列函数达到的效果是 key1 != key2 则 hash(key1) != hash(key2) 。然而在真实情况下，想要找到一个不同的key对应的散列值都不一样的散列函数几乎是不可能的，即使是我们耳熟能详的MD5或者是SHA-1算法都无法实现，也就是说，再好的散列函数都无法避免散列冲突。这是为什么呢？其实结论非常简单，我们刚才提到所有的映射关系都会存储到一个大小有限的散列表中，那么既然“坑”是有限的，终究无法避免两个结果被计入一个相同的坑。那么如何去解决Hash碰撞问题呢，通用的做法有线性探测法、二次探测法、双重散列法、链表法等，这里就不展开说明，有兴趣的同学可以自行搜索了解其原理。

在上文提到的算法中，我们会发现使用平滑加权轮询算法后，从算法层面上看我们的分配机制已经非常平衡了，但是无论是轮询还是随机算法都存在着一个问题。web 服务中不是所有的请求都是无状态的模式，通常一个请求都会在服务器中有一个 session 的记录，在往期的文章（ Web 身份验证：JWT vs Session）中有介绍，这种场景我们可以使用 JWT(Json Web Token) 的技术架构或使用 Redis 存储所有会话信息让服务器之间访问并共享来解决。换言之，我们希望我们的负载均衡算法能使携带唯一值的相同请求命中之前的缓存保持其有状态连接的特性。

在使用了Hash算法后，我们得到了一个固定长度的唯一值，我们把这个计算后的值和服务器的总数进行取模 hash(key) % node_count = num 便可以定位到任一一台服务器并且在key值不变的情况下永远命中这一台服务器，但该方案会有一个弊端，如果我们改变了服务器的总数，那么所有的计算结果都将会偏移。

我们在云趣科技 QueryX 数据库安全管控平台上采用了 Hash 一致性算法，我们在与数据库建立一个通道之后该用户的请求同样能够命中相同服务器继续使用该通道，并且在动态扩缩容时只会影响到一部分的计算结果。

简单地说，一致性Hash算法将整个 Hash 值空间组织成一个虚拟的圆环，如假设某空间 Hash 函数H的值空间是0-2^32-1（即Hash值是一个32位无符号整形），整个 Hash 空间如下：

这时候，我们可以通过一个Hash函数去处理我们的服务器的名称后得到一个 Hash 值，并把计算后的值分布在我们生成好的 Hash 环上。

在分布好我们的服务器之后，只要我们之后的请求有一个唯一的 uuid ，就可以对每个请求的 id 值进行 Hash ，然后分布在环上，并通过顺时针方向去寻找最近的一个server节点，由于这是一个环，所以一定能寻找到一个对应的节点。且在 uuid 不变的情况下， Hash 的计算一定是一个幂等的操作，那么下一次携有相同 uuid 的请求再次发起时，仍旧能使用该方法命中之前选择的节点，效果如下：

Hash 环的好处就在于，我们可以动态地扩容或缩容节点，当然，发生此动作时会影响到部分请求的节点选择。例如在 Server2 节点被移除后，原先落在它上面的请求会被转移到 Server3 节点上，扩容时也有类似的效果。

【再加一个图】

当然，Hash 后的结果我们在业务上没办法精准预测，我们上面两张图对于 server 及请求的分配从环上看较为平均，但实际上可能不是如此。

从上图可以看出，节点名称的 Hash 结果可能并不是以我们希望的结果均匀地分散在圆环上的，更大概率会出现上图散落不均的情况，在这种情况下 Server2 节点就会接收到大量的流量，而其他两个节点接收到流量的概率会大大降低。这时候，我们需要再引入一个概念：虚拟节点。既然服务器的节点太少， Hash 的结果在 Hash 环上可能会分布地不均匀，那我们就变相地增多节点数量（增加一个虚拟节点和真实节点名称的映射关系，虚拟节点等同于根据真实节点的克隆体，指向的是同一个 IP 地址），只要数量增加，那么整体的分布就会趋于平均，效果如下：

上面介绍的算法有些是针对有状态请求的场景，有些是针对节点权重不同所实现的，那在真实的场景下上面的算法更多的是处于一个理想状态下的流量分配，如果通过业务层面，我们需要考虑更多的因素：例如节点本身的负载（需要依赖各节点的实时监控数据来分配流量）、服务器本身的连接数（请求本身的存活时间及执行业务逻辑会有所不同，那么可能会造成单节点请求堆积现象，需要通过连接数缓存判断动态管理）、节点应用程序负载等其他场景。

在负载均衡的场景下没有银弹，若需要根据考虑更多的因素（如节点负载、权重、网络、IO，应用的负载、连接数，连接本身的业务特性等）就需要增加负载均衡节点本身的判断逻辑以及信息采集，这时候就需要在绝对的流量平衡和性能消耗上找一个平衡点，本质上还需要根据具体场景来选择适合的算法或组合来解决实际的业务问题。

作者：钟灵

简介：云趣科技全栈工程师

出品：云趣科技