负载均衡策略与算法详解

1 负载均衡策略

在分布式架构中,负载均衡策略是非常重要的内容。它不仅能在一定程度上保证整个集群的高可用,而且能够提高系统的吞吐量,降低服务响应时间。每台计算机的系统资源都是有限的,能够承载的任务及处理的请求也是有限的。在分布式系统中一般通过扩容来增加系统整体的承载能力,但是当大量并发的请求发生时,如果请求分配不均匀,就会导致部分机器收到了大量请求,而部分机器非常空闲,这种现象轻则导致吞吐率偏低、响应时间过大,不能让资源的使用达到最优,重则导致接收过载的机器宕机、请求失败,出现服务不可用的现象。所以如何让这些请求较为均匀地分摊到集群内各个服务节点上,就是负载均衡策略所需要做的事情。

负载均衡的本质就是通过合理的算法将请求均匀地分摊到各个服务节点上,它需要根据一定的算法从一大批服务节点中选择一个节点来接收和处理请求。而根据这个服务节点的集合信息是否存放在客户端,可以将负载均衡分为服务端负载均衡客户端负载均衡

1.1 服务端负载均衡

服务端负载均衡是在服务端维护了服务节点集合信息,此处的服务端并不指服务提供者所在的节点,而是一个统一维护服务节点信息的负载均衡器 (Loadbalancer),如下所示:

服务端负载均衡

在服务消费端与服务提供端的中间有一个负载均衡器,当请求到达负载均衡器时,负载均衡器会通过一定的负载均衡算法从服务节点集合中选择一个合适的节点,通过请求转发器将该客户端的请求转发到对应的服务节点上。从上图可以看出,服务端负载均衡可以让客户端和服务端解耦,保证对业务应用没有侵入性,无论负载均衡器如何变化,都不会影响业务代码。服务端负载均衡方案中除了负载均衡算法,最关键的就是网络请求的转发,根据网络请求转发发生的 层级 不同,可以分为二层负载均衡、三层负载均衡、四层负载均衡和七层负载均衡。

  • 二层负载均衡: 集群中不同的服务节点采用相同的 IP 地址,但是机器的 MAC 地址不一样。当负载均衡服务器收到请求之后,通过修改请求报文的目标 MAC 地址的方式将请求转发到目标机器来实现负载均衡。
  • 三层负载均衡:集群中不同的服务节点采用不同的 IP 地址,当负载均衡服务器收到请求之后,选择一个服务节点,通过 IP 地址将请求转发至不同的真实服务器。
  • 四层负载均衡: 传输层包含源 IP 地址、目标 IP 地址,还包含源端口号及目的端口号。四层负载均衡服务器在收到客户端请求后,通过修改请求报文的地址信息(IP 地址 + 端口号)将请求转发到对应的服务节点。
  • 七层负载均衡: 网络请求的转发发生在应用层,应用层有很多不同的协议,比如 HTTP 等,这些应用层协议中包含很多具有特殊意义的字段信息。比如同一个 Web 服务器的负载均衡可以根据七层的 URL、浏览器类别等来决定是否要进行负载均衡。

这四种负载均衡方案中最常见的就是四层负载均衡和七层负载均衡。四层负载均衡与七层负载均衡最大的不同就是四层负载均衡的本质是转发请求,而七层负载均衡是内容的交换和代理,因为七层负载均衡中需要根据特殊字段来选择最终的服务节点,负载均衡器就必须先反向代理最终的服务器来和客户端建立连接,接收客户端发送的真正的应用层内容的报文后才能选择最终的服务节点。

除了依据请求转发的层级进行分类,还可以根据负载均衡器的实现形态进行分类,即分为硬件负载均衡和软件负载均衡。常见的硬件负载均衡方案有 F5、NetScaler、Radware 等设备。常见的软件负载均衡方案有 NginxLVSHAProxy 等。

虽然服务端负载均衡方案能够起到解耦的作用,但这种方案有两个非常严重的缺点:

  • 负载均衡器是整个系统处理性能的瓶颈,负载均衡器的过载或者出现单点问题都会导致响应缓慢或者服务不可用。
  • 请求必须经过负载均衡器转发或者代理,传输效率有所降低。

在微服务架构中,服务之间的依赖关系较为复杂,在一个系统中存在许多服务和服务实例,如果通过服务端负载均衡方案实现负载均衡,则会导致负载均衡器变得尤为重要,系统也增加了不少复杂度,如下图所示:

服务端负载均衡

随着整个调用链路的增加,负载均衡器的影响越来越大,整个请求链路的传输效率由于负载均衡器不断增加而不断降低,所以服务端负载均衡并不适用于微服务架构的系统。

1.2 客户端负载均衡

客户端负载均衡的方案就是把服务列表维护在客户端一侧,由客户端选择某一个服务节点,并且与之通信。

客户端负载均衡无须额外部署负载均衡器,并且也不需要进行请求转发或者代理,客户端可以直接和服务端连接并通信,传输损耗相对较少。没有负载均衡器也就不存在负载均衡器的单点问题。但是客户端负载均衡方案并不能像服务端负载均衡方案样做到对业务应用的无侵入性,并且每一个客户端都与服务节点连接并通信,所以连接数也会相应地增加。

2 负载均衡算法

无论是服务端负载均衡方案还是客户端负载均衡方案,都离不开负载均衡算法。因为无论如何都需要从服务节点的集合中挑选一个合理的节点来处理请求,而算法也直接决定了是否能将流量均匀地分摊到各个服务节点上,以实现资源的最大化利用,以及保障服务节点可用性的目的。下面我们介绍几种常见的负载均衡算法。

2.1 随机算法(加权随机算法)

随机算法最简单的一种算法,服务消费者每次请求选择的服务节点都是随机的。这种算法在使用过程中的随机性太强,非常容易出现集群中某台机器负载过高或者负载过低的情况,导致整个集群的负载不够均衡。而且每台机器的配置和性能很可能不同,所能够承载和处理的请求数量也不一样,所以现实中往往会给每台机器加上权重,将随机算法优化为加权随机算法。

加权随机算法是提供权重能力的随机算法,举个例子:一个服务集群中存在服务节点 A、B、C,它们对应的权重为 7、2、1,权重总和为 10,现在把这些权重值平铺在一维坐标系上,分别出现三个区域,A 区域为 [0,7),B 区域为 [7,9),C 区域为 [9,10),然后产生一个 [10,10) 的随机数,查找该数字落在哪个区间内,该区间所代表的机器就是此次请求选择的服务节点:

1
2
3
4
5
6
7
^
|-------+
|       |--+
|       |  |-+
|   A   | B|C|
+-------|--|-|---->
0       7  9 10

这样做可以保证权重越大的机器被击中的概率就越大,它所承受的请求数量也会越多。加权随机算法相对于普通的随机算法而言,利用权重来减小随机性,让规模和配置不同的机器可以适当调整其权重,使整个集群的负载更加平衡。

2.2 轮询算法

轮询算法可以分为三种,分别是完全轮询算法加权轮询算法平滑加权轮询算法

2.2.1 完全轮询算法

完全轮询算法要求消费者每次请求所选择的服务节点都是以轮询的方式决定的。比如服务提供者有三个服务节点,分别是 A、B、C,服务消费者的第一个请求分配给 A 节点,第二个请求分配给 B 节点,第三个请求分配给 C 节点,第四个请求又分配给 A 服务器。这种完全轮询的算法只适合每台机器性能相近的情况,但是所有机器性能相近是一种非常理想的情况,更多的情况是每台机器的性能都有所差异,这个时候性能差的机器被分到等额的请求,就会出现承受不了并且宕机的情况。

2.2.2 加权轮询算法

加权轮询算法会增加高权重节点的轮询次数。举个例子,服务节点 A、B、C 的权重比为 7:2:1,那么在 10 次请求中,服务节点 A 会收到其中的 7 次请求,服务节点 B 会收到其中的 2 次请求,服务节点 C 则收到其中的 1 次请求。也就是说,每台机器能够收到的请求归结于它的权重。加权轮询的顺序则是 {A A A A A A A B B C}

2.2.3 平滑加权轮询算法

加权轮询算法会导致流量先倾倒式地导向 A 服务节点,而其他服务节点却短暂处于空闲状态,降低了资源的利用率。当流量高峰到达时,也容易直接把高权重的服务节点 A 击垮。所以平滑加权轮询算法在加权轮询算法的基础上新增了平滑处理。

平滑加权轮询算法来源于 Nginx,它通过加权和降权来保证每次请求都被均匀分发。在平滑加权轮询算法中,每个服务节点都有两个权重值,分别是 originalWeightcurrentWeightoriginalWeight 为该节点的原始权重,currentWeight 的初始值为 originalWeight 的大小。下面是平滑加权轮询算法的推演过程:

  1. 请求到来,每个节点都计算一遍 currentWeight += originalWeight
  2. 比较每个节点计算过的 currentWeight 值,并从中选择最大值的节点作为最终节点。
  3. 步骤 2 中选出的最终节点的 currentWeight -= 所有节点的 originalWeight 和

依照上面的逻辑,举例推演执行过程: 假设 A、B、C 三个节点的权重为 7、2、1,下表为计算过程:

执行序号currentWeight
(步骤 1 执行后的结果)
所选服务节点
(执行步骤 2 选择的结果)
选择后的 currentWeight
(执行步骤 3 后的结果)
1{14,4,2}A{4,4,2}
2{11,6,3}A{1,6,3}
3{8,8,4}A{-2,8,4}
4{5,10,5}B{5,0,5}
5{12,2,6}A{2,2,6}
6{9,4,7}A{-1,4,7}
7{6,6,8}C{6,6,-2}
8{13,8,-1}A{3,8,-1}
9{10,10,0}A{0,10,0}
10{7,12,1}B{7,2,1}

由上表可知,最后计算完成后 currentweight 又回到了原来的 7、2、1。这样做得到的 10 次请求的轮询顺序为 {A A A B A A C A A B},不再是 {A A A A A A A B B C} 的顺序。在保证按权重分配的基础上,提高了轮询的平滑性。

2.3 最少活跃数算法

最少活跃数算法是基于最小连接数算法衍生而来的,某个服务节点中活跃的调用数越小,表明该服务提节点处理请求的效率越高,也就表明单位时间内能够处理的请求越多。此时服务消费端的请求应该选择该服务节点作为目标节点。

该算法实现的思路是每个服务节点都有一个活跃数 active 来记录该服务的活跃值,每收到个请求,该 active 就会加 1,每完成一个请求,该 active 就会减 1。在服务运行一段时间后,性能相对较高的服务节点处理请求的速度更快,因此活跃数下降得也越快,此时服务消费者只需要选择 active 最小的那个服务节点作为目标节点,而这个 active 最小的服务节点就能够优先获取新的服务请求。

最少活跃数算法也可以像随机算法和轮询算法一样引入权重,演变成最少活跃数加权算法,在比较活跃数时,如果最小活跃数的服务节点存在多个,则可以利用权重法来进行选择,如果服务节点的权重也一样,则从中随机选择一个服务节点。

2.4 一致性 Hash 负载均衡算法

一致性 Hash 负载均衡算法是一致性 Hash 算法在负载均上的应用。它可以保证相同的请求尽可能落到同一个服务器上,下面我们分析该算法的原理。

  1. 首先利用服务节点的 IP 地址或者其他信息生成该服务节点的唯一 Hash 值,并将这个 Hash 值投射到 [0,2^32] 的圆环上,如图:

    一致性 Hash 负载均衡算法
  2. 当请求到达时,会指定某个值来计算该请求的 Hash 值,这个值可能是请求方 IP 地址、用户 ID 或者其他信息。当请求方的 Hash 值计算完成后,就会顺时针寻找最接近该请求方 Hash 值的服务节点。例如,请求 a 计算后的 Hash 值落在服务节点 A 和服务节点 B 的 Hash 值之间,请求 b 计算后的 Hash 值落在服务节点 B 和服务节点 C 的 Hash 值之间,请求 c 计算后的 Hash 值落在服务节点 C 和服务节点 A 的 Hash 值之间,此时请求 a 将选择 B 节点,请求 b 将选择 C 节点,请求 c 将选择 A 节点,如图:

    一致性 Hash 负载均衡算法
  3. 当有服务下线时,请求归属的节点也会按照顺时针方向往后移动,比如 B 节点“挂了”之后请求 a 会选择节点 C,如图:

    一致性 Hash 负载均衡算法

从上图可以看到,Hash 一致性算法并不能够保证 Hash 算法的平衡性,因为如果一直往顺时针的方向移动,就会导致后续的服务节点接收的请求越来越多,出现数据倾斜现象,最终导致整个集群都被击垮。要解决这个问题就需要引入虚拟节点。虚拟节点是实际节点在 Hash 空间的复制品,即对每一个服务节点计算多个 Hash 值,每个计算结果的位置都会放置一个此服务节点,如下图所示:

一致性 Hash 负载均衡算法

利用虚拟节点,能够在服务节点下线时,保持集群内剩余节点的负载相对均衡。举个例子,原先 [0,2^32] 的圆环被分成了三段,分别是 A~B、B~C 和 C~A,当服务节点 B 下线后,服务节点 C 将接收单位时间内 2/3 的请求,而 A 还是继续接收 C~A 范围内的请求,这部分请求仅仅占用了所有请求的 1/3。引入虚拟节点后,[0,2^32] 的圆环被分成了 3 * n 份,当服务节点 B 下线后,原先服务节点 B 所承受的压力会被服务节点 A 和服务节点 C 分担,避免了完全向服务节点 C 倾斜的现象。


欢迎关注我的公众号,第一时间获取文章更新:

微信公众号

相关内容