负载均衡

## 概述

1. 在分布式系统中，负载均衡（Load Balancing）是**一种将任务分派到多个服务端进程的方法**，例如，将一个 HTTP 请求派发到实际的 Web 服务器中执行的过程就涉及到负载均衡的实现，一个 HTTP 请求到达 Web 服务器，这中间设计多个过程，也存在多种不同负载均衡的方法，下图是负载均衡的原理图，图中**客户端的请求经过负载均衡器**（Load Balancer）**的分发**，**被指定的服务器进程进行处理**。![](https://notebook.ricear.com/media/202108/2021-08-13_1129130.3451463128892627.png)
2. 实现负载均衡主要有两个目的：
   1. 第一个目的是**将任务的处理负载均摊到不同的进程**，**减少单一进程的负载**，**达到处理能力水平扩容的目的**。
   2. 第二个目的是**提高容错能力**，在线上正式环境中，机器宕机或者进程异常导致服务不可用是畅游的现象，在实现负载均衡的系统中，多个服务器进程提供同样的服务，一个进程不可用的情况下，任务会被负载均衡器派发到其他可用的进程，已达到高可用的目的，**在多台不同的服务器中部署相同的服务进程**，**通过负载均衡对外提供服务**，**这组进程也被称为集群**（Cluster）。

## 实现策略

常见的负载均衡实现策略有以下几种：

1. **均匀派发**（Even Task Distribution Schema）。
2. **加权派发**（Weighted Task Distribution Schema）。
3. **粘滞会话**（Sticky Session Schema）。
4. **均匀任务队列派发**（Even Size Task Queue Distribution Schema）。
5. **单一队列**（Autonomous Queue Schema）。

### 均匀派发

1. 均匀派发是指**任务会被均匀地派发到所有的服务器进程**，在**实现时可以使用随机派发或者轮流派发**（Round Robin）**的方法**，他**是实现负载均衡最简单的策略**。
2. 均匀派发策略**假设集群内所有进程具有相同的处理能力**，**且任务处理用时相同**，但实际上，**由于进程部署环境的不同**，**且处理能力一般不同**，**任务处理时间也不尽相同**，因此**均匀派发的策略并不能很好地将任务负载均摊到各个进程中**。![](https://notebook.ricear.com/media/202108/2021-08-13_1146010.7831356227262808.png)

### 加权派发

1. 加权派发策略在派发任务时，会**赋予服务器进程一个权值**，即**不同的进程会接受不同数量的任务**，**具体数量为权值确定**，例如，三个进程的处理任务的能力比率为 3:3:2，那么可以赋予这三个进程 3:3:2 的权值，即每 8 个任务中，3 个派发给第一个进程，3 个派发给第二个进程，2 个派发给第三个进程。
2. 加权派发策略**考虑了进程处理能力的不同**，因此**更接近实际的应用**，但是，加权派发策略**也没有考虑任务处理的要求**。![](https://notebook.ricear.com/media/202108/2021-08-13_1151530.0821075316999722.png)

### 粘滞会话

1. 前两种负载均衡策略**没有考虑任务之间的依赖关系**，在实际中，**后面的任务处理通常会依赖于前面的任务**，例如，对于同一个登录用户的请求，用户购买的请求用户登录的请求，如果用户的登录信息保存在进程 1 中，购买请求被分派到进程 2 或者进程 3 上，那么购买请求将不能正确处理，这种**请求间的依赖关系也被称为粘滞会话**，**负载均衡需要考虑粘滞会话的情况**。
2. 粘滞会话的派发策略要求**属于同一个会话的任务将会被分派到同一个进程中**，虽然这**可以正确处理任务**，但是却**带来任务派发不均匀的问题**，因为**一些会话可能包含更多的任务**，**一些会话包含更少的任务**。
3. 粘滞会话的另一种处理策略是**使用数据库或者缓存**，**将所有会话数据存储到数据库或者缓存中**，**集群内所有进程都可以通过访问数据库或者缓存来获取会话数据**，**进程内存都不保存会话数据**，这样负载均衡器便可以前面介绍的策略来派发任务。![](https://notebook.ricear.com/media/202108/2021-08-13_1424140.08890672795157328.png)

### 均匀任务队列派发

1. 均匀任务队列派发策略和加权派发策略类似，**都考虑了进程的处理能力**，不过其实现方式不同，在均匀队列派发策略下，**负载均衡器为每个进程都创建一个大小相等的任务队列**，**这些任务队列包含了对应进程需要处理的任务**：
   1. **任务处理快的进程**，其**队列也会减少得快**，这样**负载均衡器会派发更多的任务给这个进程**。
   2. **任务处理慢的进程**，其**队列也会减少得慢**，这样**负载均衡器会派发更少的任务给这个进程**。
2. 因此，**通过这些任务队列**，**负载均衡器在派发任务时将进程处理任务的能力因素考虑了进去**。![](https://notebook.ricear.com/media/202108/2021-08-13_1432270.7616708670176362.png)

### 单一队列

1. 与上面的均匀队列策略一样，单一队列策略也使用了队列来实现负载均衡，不同的是，**单一队列策略只使用了一个队列**。
2. 单一队列策略中，实际上并**没有负载均衡器的存在**，**所有的服务器进程从队列中取出任务执行**，**如果某个进程出现宕机的情况**，那么**其他进程仍然可以继续执行任务**。
3. 这样一来，**任务队列并不需要知道服务进程的情况**，**只需要服务进程知道自己的任务队列**，**并不断执行任务即可**。
4. 单一队列策略实际上也**考虑到进程的处理能力**，**进程任务处理得越快**，其**从队列取出任务的速度也越快**。![](https://notebook.ricear.com/media/202108/2021-08-13_1439080.09166370320907324.png)

## 实现方法

常见的负载均衡实现方法包括**HTTP 重定向**、**DNS 负载均衡**、**反向代理**、**IP 负载均衡**、**数据链路层负载均衡**五种。

### HTTP 重定向

#### 含义

1. HTTP 重定向服务器是一台普通的 Web 服务器，**用户的请求先到达重定向服务器**，**这台服务器会挑选一台后端服务器的地址**（例如使用[轮询](#2-1-均匀派发)的方式），并**将该地址写入 HTTP 重定向响应结果中**（以响应状态码 302 返回）**返回给用户**，**用户将根据这个新地址重新发送请求到选中的服务器上**，**选中的服务器会处理用户请求**，**并将结果返回给用户**。
2. **通过重定向服务器的处理**，**用户请求被分配到不同的后端服务器上进行处理**，**实现了负载均衡的目的**。![](https://notebook.ricear.com/media/202108/2021-08-13_1513530.17919384110888048.png)

#### 优缺点

##### 优点

1. HTTP 重定向负载均衡的方法**实现上比较简单**。

##### 缺点

1. **增加了用户的时延**，因为**访问请求需要进行两次往返**。
2. **重定向服务器没有将后端服务器的负载差异考虑进去**，**有些后端服务器可能在相当繁忙时仍然接收较多的请求**。
3. **重定向服务器的并发处理能力制约着整个系统的并发处理能力**。
4. **如果重定向服务器出现故障**，**站点就会瘫痪**。
   > **由于存在这些缺点**，**HTTP 重定向通常都会与其他一种或多种负载均衡技术结合使用**。

### DNS 负载均衡

#### 含义

1. DNS 负载均衡的实现原理是**在 DNS 服务器中为同一个主机名配置多个 IP 地址**，**在应答 DNS 查询时**，**DNS 服务器对于每个查询将以 DNS 记录的 IP 地址按顺序返回不同的解析结果**，**将客户端的访问引导到不同的机器上去**，**使得不同客户端访问不同的服务器**，**从而达到负载均衡的目的**。![](https://notebook.ricear.com/media/202108/2021-08-13_1530470.21303848406548787.png)

#### 优缺点

##### 优点

1. 由于**DNS 系统本身是一个分布式系统**，相对来说他**不存在性能和吞吐能力的限制**，故**使用 DNS 来做负载均衡并不需要担心负载均衡服务器的处理能力**。
2. **可以根据用户 IP 进行智能解析**，**DNS 服务器可以在所有可用的 A 记录中寻找离用户最近的一台服务器为用户提供服务**。

##### 缺点

1. **DNS 服务器并不知道后端服务器的情况**，**如果后端服务器宕机**，**而用户的请求继续分配到这个服务器**，**会导致无法响应用户的请求**。
2. **DNS 服务器依然没有将后端服务器的负载差异考虑进去**。
3. **DNS 服务器存在缓存**，**当需要更新请求的分配时**，**新增一个 IP 或者删除一个 IP 并不能立即生效**。

### 反向代理

#### 含义

1. 反向代理服务器的工作主要是**转发 HTTP 请求**，因此他**工作在 HTTP 层**，**也就是[OSI 七层结构](https://notebook.ricear.com/project-26/doc-314)中的应用层**（第七层），所以**基于反向代理的负载均衡也称为七层负载均衡**。
2. **反向代理服务器处于后端服务器的前面**，由于**需要直接接受用户的请求**，因此**反向代理服务器需要一个外网 IP**，而**后端服务器并不直接对外提供访问**，因此**后端服务器并不需要外网 IP**，**反向代理服务器通过内网 IP 与后端服务器进行通信**。
3. 具体的示例如下：
   1. 如下图所示，浏览器的请求到达反向代理服务器 ，反向代理服务器收到请求后，根据负载均衡算法计算得到一台真实的后端服务器地址 `10.0.0.1`，并将请求转发到这台后端服务器。
   2. `10.0.0.1` 处理请求后，将响应返回给反向代理服务器，再由反向代理服务器将该响应返回给用户。![](https://notebook.ricear.com/media/202108/2021-08-13_1557290.16610122430105267.png)
4. 常见的反向代理服务器有**Ngnix**、**Apache**、**Haproxy**。

#### 优缺点

##### 优点

1. **部署比较简单**，**使用常见的反向代理服务器软件即可部署反向代理服务器**。
2. **调度策略丰富**，例如，**可以为不同的后端机器设置不同的分配权重**，**这样处理能力高的机器可以分配到较多的任务**，**达到能者多劳的目的**。
3. **反向代理服务器可以让用户在一次会话周期内的所有请求始终分配到一台特定的后端服务器**（[粘贴会话](#2-3-粘滞会话)）。

##### 缺点

1. 由于**反向代理工作在 HTTP 层**，**所有请求都经过反向代理服务器的处理**，**后端服务器的响应结果也必须经过反向代理服务器传送给用户**，故这种负载均衡方式**要求反向代理的并发处理能力较高**。

### IP 负载均衡

#### 含义

1. **前面几种负载均衡的方法都是工作在 HTTP 层**，实际上，**在数据链路层**（第二层）、**网络层**（第三层）、**传输层**（第四层）**都可以实现不同机制的负载均衡**。
2. 与 HTTP 层机制不同，**这些负载均衡调度的工作必须由 Linux 内核来完成**，即**网络数据包在从内核缓冲区进入用户进程空间前**，**已完成转发的工作**。
3. 下图为**在网络层通过修改请求目的地址进行负载均衡**：
   1. **用户请求到达负载均衡服务器 `114.113.200.84`**，**负载均衡服务器在操作系统内核获取网路数据包**，**根据负载均衡算法计算得到一台真实的后端服务器 `10.0.0.1`**，**然后将数据包的目的地址改为 `10.0.0.1`**，**不需要用户进程处理**。
   2. **后端服务器 `10.0.0.1` 处理完成后**，**响应数据包返回到负载均衡服务器**，**负载均衡服务器再将数据包源地址修改为自身的 IP 地址**（`114.113.200.84`）**发送给用户**。![](https://notebook.ricear.com/media/202108/2021-08-13_1616080.6124761973221439.png)

#### 优缺点

##### 优点

1. **IP 负载均衡在内核进程完成数据分发**，**处理性能得到了很大的提高**。

##### 缺点

1. 由于**所有请求和响应都要经过负载均衡服务器**，**系统的最大吞吐量仍然受到负载均衡服务器网卡带宽的限制**，**对于提供下载服务或者视频服务等需要传输大量数据的站点**，**IP 负载均衡的方式是难以满足需求的**。

### 数据链路层负载均衡

#### 含义

1. 数据链路层的负载均衡**通过修改 MAC 地址来实现负载均衡的目的**。
2. 数据链路层是 OSI 网络模型的第二层，由于**数据链路层负载均衡的方法走的是 MAC 层的协议**，因此**需要负载均衡服务器和后端服务器处在同一个二层**（同一个广播域）**之中**。
3. **负载均衡数据分发过程中不修改 IP 地址**，**只修改 MAC 地址**，**通过配置后端服务器与负载均衡服务器具有相同的 IP 地址**，**从而达到不修改数据包的源 IP 地址和目的 IP 地址就可以达到数据分发的目的**。
4. 由于**后端服务器的 IP 和数据请求目的 IP 一致**，**不需要通过负载均衡服务器进行地址转换**，**可以将响应数据包直接返回给用户浏览器**，**避免负载均衡服务器网卡带宽成为瓶颈**。
5. 具体的示例如下：
   1. 用户请求到达负载均衡服务器 `114.113.200.84`，负载均衡服务器将请求数据的目的 MAC 地址改为 `00.0c.29.d2`，并不修改数据包目的 IP 地址。
   2. 由于后端服务器与负载均衡服务器有相同的 IP 地址，因此数据可以正常传输到 `00.0c.29.d2` 对应的服务器，该服务器处理完成后将响应数据直接返回给用户，不需要经过负载均衡服务器。![](https://notebook.ricear.com/media/202108/2021-08-13_1645200.0991937385665469.png)
6. 在 Linux 平台上最好的数据链路层负载均衡的开源产品是**LVS**（Linux Virtual Server），LVS 有三种运行模式，分别为**NAT 模式**、**TUN 模式**、**DR 模式**，**DR 模式正是运行在数据链路层**，**通过修改数据帧的 MAC 地址来实现负载均衡的**。

#### 优缺点

##### 优点

1. **数据链路层负载均衡工作在 Linux 内核进程**，**性能很高**。
2. **服务器的响应不需要再次经过负载均衡服务器**，**解决了负载均衡服务器网卡流量瓶颈的问题**。

##### 缺点

1. **可配置性较高**，**并不支持复杂的调度策略**。

## 常用算法

负载均衡的常用算法包括**轮询法**（Round Robin）、**最小连接数法**（Least Connections）、**随机法**（Random）、**源地址哈希法**（Source Hashing）。

### 轮询法

轮询法主要有三种，分别为 **简单轮询法**、**加权轮询法** 和 **平滑加权轮询法**。

#### 简单轮询法

1. 简单轮询法是轮询算法中最简单的一种，但是由于他 **不支持配置负载**，所以 **应用较少**。
2. 简单轮询法是指**负载均衡服务器将客户端请求按顺序轮流分配到后端服务器上**，**以达到负载均衡的目的**。
3. 具体示例如下：
   1. 假设现在有 6 个客户端请求，2 台后端服务器。
   2. 当第一个请求到达负载均衡服务器时，负载均衡服务器会将这个请求分派到后端服务器 1。
   3. 当第二个请求到达时，负载均衡服务器会将这个请求分派到后端服务器 2。
   4. 当第三个请求到达时，由于只有两台服务器，因此请求 3 会被分派到后端服务器 1，以此类推。![这里写图片描述](https://notebook.ricear.com/media/202108/2021-08-13_1702110.9675721142565203.png)

4. 在实际应用中，同一服务会部署到 **不同的硬件环境**，会出现 **性能不同** 的情况，若直接使用简单轮询法，给每个服务实例相同的负载，必然会出现 **资源浪费** 的情况。为了避免这种情况，提出了下面的 **加权轮询法**。

#### 加权轮询法

1. 加权轮询法引入了 **权值**，改进了简单轮询法，可以 **根据硬件性能配置实例负载的权重**，从而达到资源的合理利用。
2. 具体的示例如下：
   1. 假设有 6 个客户端请求，2 台后端服务器，后端服务器 1 被赋予权值 5，后端服务器 2 被赋予权值 1。
   2. 这样一来，客户端请求 1、2、3、4、5 都被分派到服务器 1 处理，客户端请求 6 被分派到服务器 2 处理。
   3. 接下来，请求 7、8、9、10、11 被分派到服务器 1，请求 12 被分派到服务器 2，以此类推。![这里写图片描述](https://notebook.ricear.com/media/202108/2021-08-13_1709250.26193282927954187.png)

3. 加权轮询法虽然通过配合实例权重，解决了简单轮询的资源利用问题，但是还存在一个明显的缺陷。

> 服务实例 $S = \{ a, b, c \}$，权重 $W = \{ 5, 1, 1 \}$，使用加权轮询调度生成的实例序列为 $\{ a, a, a, a, a, b, c \}$，那么就会存在连续 5 个请求都被调度到实例 $a$，而实际中，这种不均匀的负载是不被允许的，因为连续请求会突然加重实例 $a$ 的负载，可能会导致严重的事故。

4. 为了解决加权轮询调度不均匀的缺陷，提出了下面的 **平滑加权轮询法**。

#### 平滑加权轮询法

> 所谓平滑就是 **调度不会集中压在同一台权重比较高的机器上**，这样对所有机器都更加公平。比如，对于服务实例 $S = \{ a, b, c \}$，权重 $W = \{ 5, 1, 1 \}$，产生 $\{ a, a, b, a, c, a, a\}$ 的调度序列就比 $\{ a, a, a, a, a, b, c \}$  更加平滑。

平滑加权轮询法的原理其实很简单，步骤如下：

1. 每个节点，用他们的 **当前值加上他们自己的权重**。
2. **选择当前值最大的节点为选中节点**，并 **把他的当前值减去所有节点的权重总和**。

> 例如 $\{ a:5, b:1, c:1 \}$ 三个节点，一开始我们初始化三个节点的当前值为 $\{ 0, 0, 0 \}$，选择过程如下表：
>
> | 轮数 | 选择前的当前权重  | 选择节点 | 选择后的当前权重  |
> | ---- | ----------------- | -------- | ----------------- |
> | 1    | $\{ 5, 1, 1 \}$   | $a$      | $\{ -2, 1, 1 \}$  |
> | 2    | $\{ 3, 2, 2 \}$   | $a$      | $\{ -4, 2, 2 \}$  |
> | 3    | $\{ 1, 3, 3 \}$   | $b$      | $\{ 1, -4, 3 \}$  |
> | 4    | $\{ 6, -3, 4 \}$  | $a$      | $\{ -1, -3, 4 \}$ |
> | 5    | $\{ 4, -2, 5 \}$  | $c$      | $\{ 4, -2, -2 \}$ |
> | 6    | $\{ 9, -1, -1 \}$ | $a$      | $\{ 2, -1, -1 \}$ |
> | 7    | $\{ 7, 0, 0 \}$   | $a$      | $\{ 0, 0, 0 \}$   |
>
> 我们可以发现，$a$、$b$、$c$ 选择的次数符合 5:1:1，而且权重大的不会被连续选择，七轮选择后，当前值又回到 $\{ 0, 0, 0 \}$，以上操作可以一直循环，同时符合平滑和基于权重。

### 最小连接数法

1. **即使后端服务器的性能和负载一样**，**不同客户端请求复杂度不一样导致处理时间也不一样**，**最小连接数法根据后端服务器当前的连接数情况**，**动态地选取其中积压连接数最小的一台服务器来处理当前的请求**，**尽可能的提高后端服务器的利用效率**，**合理地将请求分流到每一台服务器**。
2. 具体的示例如下：
   1. 考虑**一个客户端请求的处理逻辑较复杂**，**需要服务器的处理时间较长**，由于**客户端需要等待服务器的响应**，故**需要保持与服务器的连接**，**这样一来**，**客户端就需要与服务器保持较长时间的连接**。
   2. 假设客户端请求 1、2、3、4、5 已被分派给服务器 1 和服务器 2。
   3. 此时，服务器上的请求 1、3 已处理完毕，与客户端的连接已断开，而请求 2、4、5 还在服务器上处理，即服务器还保持与这些请求的客户端的连接。
   4. 如果再把请求分派到服务器 2，则会导致服务器的请求更多，服务器 2 的负载更高，如果考虑服务器的连接数，当前服务器 1 的连接数为 1，服务器 2 的连接数为 2，将请求分派到服务器 1，则负载相对均衡。![这里写图片描述](https://notebook.ricear.com/media/202108/2021-08-13_1723150.02914465661909571.png)

### 随机法

1. 随机法也很简单，就是**随机选择一台后端服务器进行请求的处理**，由于**每次服务器被挑中的概率都一样**，**客户端的请求可以被均匀地分派到所有的后端服务器上**。

### 源地址哈希法

1. 源地址哈希的思想是**根据获取客户端的 IP 地址**，**进行哈希函数计算得到的一个数值**，**用该数值对服务器列表的大小进行取模运算**，**得到的结果便是客户端要访问服务器的序号**。
2. **采用源地址哈希法进行负载均衡**，**同一 IP 地址的客户端**，**当后端服务器列表不变时**，**他每次都会映射到同一台服务器进行访问**。
3. **如果后端服务器是一缓存系统**，**当后端服务器增加或减少时**，**采用简单的哈希取模的方法**，**会使得命中率大大降低**，这个问题**可以采用[一致性哈希](https://notebook.ricear.com/project-37/doc-762)的方法来解决**。

## 参考文献

1. [负载均衡（Load Balancing）学习笔记(一)](https://leehao.me/%E8%B4%9F%E8%BD%BD%E5%9D%87%E8%A1%A1%EF%BC%88Load-Balancing%EF%BC%89%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-%E4%B8%80)。
2. [负载均衡（Load Balancing）学习笔记(二)](https://leehao.me/%E8%B4%9F%E8%BD%BD%E5%9D%87%E8%A1%A1%EF%BC%88Load-Balancing%EF%BC%89%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-%E4%BA%8C)。
3. [负载均衡（Load Balancing）学习笔记三——负载均衡算法](https://leehao.me/%E8%B4%9F%E8%BD%BD%E5%9D%87%E8%A1%A1%EF%BC%88Load-Balancing%EF%BC%89%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E4%B8%89%E2%80%94%E2%80%94%E8%B4%9F%E8%BD%BD%E5%9D%87%E8%A1%A1%E7%AE%97%E6%B3%95)。
4. [负载均衡算法 — 轮询](https://www.fanhaobai.com/2018/11/load-balance-round-robin.html)。
5. [nginx平滑的基于权重轮询算法分析](https://tenfy.cn/2018/11/12/smooth-weighted-round-robin)。