数据结构与算法学习(十七)-负载均衡算法
1、负载均衡算法
1.1、负载均衡介绍
- 负载均衡(Load Balance),指多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的帮忙
- 通过某种负载分担技术,将外部发送来的请求均匀地分配到对称结构中的某一台服务器上,而接收到请求的服务器独立地回应客户的请求。
- 负载均衡能够平均分配客户请求到服务器集合,可以解决大量并发访问服务问题,这种集群技术可以用最少的投资获得接近于大型主机的性能。
负载均衡(Load Balance,简称 LB)是高并发、高可用系统必不可少的关键组件,目标是尽力将网络流量平均分发到多个服务器上,以提高系统整体的响应速度和可用性。
1.2、作用
- 高并发
负载均衡通过算法调整负载,尽力均匀的分配应用集群中各节点的工作量,以此应用集群的并发处理能力(吞吐量)。
- 伸缩性
添加或减少服务器数量,然后由负载均衡进行分发控制。这使得应用集群具备伸缩性。
- 高可用
负载均衡器可以监控候选服务器,当服务器不可用时,自动跳过,将请求分发给可用的服务器。这使得应用集群具备高可用的特性。
- 安全防护
有些负载均衡软件或硬件提供了安全性功能,如:黑白名单处理、防火墙,防 DDos 攻击等。
1.3、分类
从支持负载均衡的载体来看,可以将负载均衡分为两类:硬件负载均衡、软件负载均衡
- 软件负载均衡
软件负载均衡,应用最广泛,软件负载均衡从软件层面实现负载均衡,一般可以在任何标准物理设备上运行。软件负载均衡的特点是 扩展性好 且 成本低廉 ,但效率相比硬件负载均衡来说要差一点。
主流产品有:
- Nginx
- HAProxy
- LVS
- 硬件负载均衡
硬件负载均衡,一般是在定制处理器上运行的独立负载均衡服务器,价格昂贵;
硬件负载均衡功能强大、性能强悍且安全性高,但扩展性差、成本昂贵。
主流产品有:
- F5
- A10
2、负载均衡算法
2.1、随机算法
- 随机(Random) 算法将请求随机分发到候选服务器,随机算法适用于 服务器硬件相同 的场景,一般来说,调用量越大,负载就越均衡
2.2、轮询算法
- 轮询(Round Robin)算法将请求依次分发到候选服务器,该算法适用于各服务器处理能力相近,且每个事务工作量差异不大 的场景。
- 如果各个事务工作量差异大,那么接收大工作量请求的服务器压力可能过大、
- 如果服务器处理能力差异大,那么性能较差的服务器可能积压请求
2.3、加权随机算法
- 在服务器集合中,如果我们希望某台机器被随机到的概率不同(性能越好的服务器被随机到的概率越高),那么我们可以为服务器集合中的每台机器附加一个权重值,让抽取的概率正比于这个权重
举个例子,现在有一个服务器集合 {A,B,C,D} ,我们希望 A 被抽中的概率为 50% ,B 被抽中的概率是 20 % , C 被抽中的概率为 10%,D 被抽中的概率为 20%,那么集合可以变为 : {A:5,B:2,C:1,D:2}
应该如何实现加权随机算法?
- 方法一:扩充集合
扩充服务器集合,使每一项出现的次数与权重正相关,比如说上面的例子我们可以将集合 {A,B,C,D} 扩充为 {A,A,A,A,A,B,B,C,D,D},然后再对扩充后的集合使用随机算法选取即可。
- 优点:选取的时间复杂度为 O (1),且算法实现简单
- 缺点:浪费空间,所占用的空间会随权重的数字增大而变大,比如说集合:{A:500,B:299,C:1,D:200}
- 方法二:使用随机数
先计算权重总和 sum ,然后在 1 到 sum 之间随机选择一个数 R ,遍历整个服务器集合,统计遍历的项的权重之和,如果该和大于等于 R ,那么就停止遍历并选择遇到的项。
以上面的集合为例,比如说随机到的数为6,那么我们遍历服务器集合,并计算权重之和,遍历第一个元素时,权重之和为 5,5 < 6,此时继续遍历,遍历到 B 时,权重之和为 7 ,7 > 6,所以我们本次请求选择 B 进行处理。
同理,如果第二个请求随机到的数为9,那么遍历 ABC 时,权重之和均小于随机到的数 R (9),遍历 D 时,权重之和为 10 ,此时 10 > 9,那么这次请求我们选择 D 进行服务。
- 优点:没有空间浪费,且实现简单
- 缺点:选取时需要遍历集合,时间复杂度为O (n)
2.4、加权轮询算法
- 加权轮询 算法是在轮询算法的基础上,增加了权重属性来调节转发到服务器的请求数目,对于性能好、处理速度快的节点,我们需要对其设置更高的权重,使得分发请求时优先分发到权重较高的节点上。
比如说,现在服务器集合有三个节点,对应的权重信息分别为:{A: 5,B: 3,C:2},那么发送十次请求时,A 节点会被分配 5 次请求,B 节点会被分配 3 次请求,C 节点会被分配 2 次节点。
- 一般的轮询算法的思路可能是:
- 轮询所有节点,找到一个最大的权重节点
- 选中的节点权重 - 1
- 直到权重减到 0 ,此时重新恢复该节点原始权重,继续轮询。
这样的算法实现起来简单,但可能造成权重大的服务器压力过大,而小权重节点服务器一直处于空闲的情况,如果节点集合中的信息换为 {A: 5,B: 1,C:1},那么此时发送七次请求时,请求结果为:{AAAAABC}。
我们可以参考 Nginx 的加权轮询算法,尽可能地让请求分摊到所有节点。
2.5、Nginx 的加权轮询算法
- 概念解释,每个节点有三个权重变量,分别是
- weight
约定权重,即在配置文件或初始化时约定好的每个节点的权重。
- effectiveWeight
有效权重,初始化为weight,如果通讯过程中发现节点异常,那么该值 -1 ,之后再次选取本节点时,调用成功依次则 + 1,上限为 weight
这个变量的作用主要是降低异常节点的权重
- currentWeight
节点当前权重,初始化为0。
- 算法逻辑
- 轮询所有节点,计算当前状态下所有节点的
effectiveWeight
之和totalWeight
currentWeight = currentWeight + effectiveWeight
,选出所有节点中currentWeight
中最大的一个节点作为选中节点- 选中节点的
currentWeight = currentWeight - totalWeight
2.6、最小活跃数
- 最小活跃数算法会将请求分发到连接数/请求数最少的候选服务器(目前处理请求最少的服务器),它能够根据候选服务器当前的请求连接数动态分配请求,适用于对系统负载较为敏感或请求连接时长相差较大的场景。
最小活跃数算法会记录当前时刻,每个候选节点正在处理的连接数,然后选择连接数最小的节点。该策略能够动态、实时地反应服务器的当前状况,较为合理地将负载分配均匀
2.7、加权最小活跃数
加权最小活跃数在最小活跃数的基础上,根据服务器的性能为每台服务器分配权重,再根据权重计算出每台服务器能处理的连接数。
实现思路:基于活跃数 active 实现
活跃调用数越小,表明该服务节点处理能力越高,单位时间内可处理更多的请求,应优先将请求分发给该服务。
在具体实现中,每个服务节点对应一个活跃数 active。初始情况下,所有服务提供者活跃数均为 0。每收到一个请求,活跃数加 1,完成请求后则将活跃数减 1。在服务运行一段时间后,性能好的服务提供者处理请求的速度更快,因此活跃数下降的也越快,此时这样的服务提供者能够优先获取到新的服务请求
2.8、源地址哈希
- 源地址哈希算法根据请求源 IP,通过哈希计算得到一个数值,用该数值在候选服务器列表的进行取模运算,得到的结果便是选中的服务器。
可以保证同一 IP 的客户端的请求会转发到同一台服务器上,用来实现会话粘滞(Sticky Session),保证特定用户总是请求到相同的服务器,若服务器宕机,会话会丢失。
3、服务端负载均衡与客户端负载均衡
3.1、服务端负载均衡
服务端负载均衡是指在服务器上游做服务分发,通常是使用一个组件 / 服务器接收用户发过来的请求,然后通过负载均衡算法,将请求按照不同的策略分发到不同的服务器中;
- Nginx 反向代理负载均衡
使用 Nginx 拦截用户发送的请求,然后通过负载均衡算法,在多个服务器之间选择一个进行访问;即在服务器端再进行负载均衡算法分配
- DNS 域名解析负载均衡
假设我们的域名指向了多个 IP 地址,那么当一个域名请求到达时, DNS 服务器进行域名解析将域名转换 IP 地址时,会在
1 : N
的映射转换中实现负载均衡。DNS 服务器提供了简单的负载均衡算法,但当其中某台服务器出现故障时,通知DNS服务器移除当前故障 IP。
3.2、客户端负载均衡
相比于服务端负载均衡,客户端负载均衡是一个比较小众的概念,客户端负载均衡是指客户端先获取到所有存活的 Service 或者服务提供者的名单,然后在本地根据一些负载均衡算法已经名单来决定要调用哪个 Service ,比如说 Spring Cloud 中的 Ribbon 就是客户端负载均衡的典型代表,在 Spring Cloud 中,Ribbon 通常会与服务注册中心配合使用,此时 Ribbon 会从服务注册中心中获取 Service 列表,然后通过负载均衡算法决定去访问哪台 Service。
3.3、二者差异
服务端负载均衡和客户端负载均衡二者最大的区别在于服务清单所存储的位置。
- 服务端负载均衡中,服务列表由中间服务(Nginx、DNS)单独维护
- 客户端负载均衡中,所有的客户端节点都有一份自己要访问的 Service 列表,这些列表都是从注册中心中获取的。