目录

1. 概述
2. 常见的负载均衡类型
3. 常用的负载均衡算法
   1. 轮询法
   2. 加权轮询法
   3. 平滑加权轮询
   4. 随机法
   5. 加权随机法
   6. 源地址哈希法
   7. 最小连接数法
   8. 加权最小连接数
   9. 最短响应时间 LRT
   10. 一致性哈希
       1. 算法原理
       2. 节点宕机
       3. 扩容
       4. 引入虚拟节点
       5. 算法总结
4. 负载均衡实现
   1. 经典负载均衡
   2. HTTP 重定向负载均衡
   3. DNS 负载均衡
   4. 反向代理负载均衡
   5. IP 负载均衡
   6. 数据链路层负载均衡
5. 高可用系统
   1. 第一层：客户端层到反向代理层
   2. 第二层：反向代理层到站点层
   3. 第三层：站点层到服务层
   4. 第四层：访问数据层
      1. 按照 range 水平切分
      2. 按照 id 哈希水平切分
   5. 总结
6. 附录

¶概述

❓什么是负载均衡？

✨ 负载均衡具有以下特点，使用带有负载均衡的多个服务器组件，取代单一的组件，可以通过冗余提高可靠性（负载均衡服务通常是由专用软件和硬件来完成）

负载均衡技术通过将大量作业合理地分摊到多个操作单元上进行执行，用于解决互联网架构中的高并发和高可用问题。

通过负载均衡技术，最终希望系统能够达到：高性能（高并发，快速响应）、高可靠（集群高可靠、故障切换、故障恢复和扩容）、高可用（达到 99%，99.999%的可用性）、可伸缩(节点下线和扩容)以及可防护的作用

可用性(Availability) = 平均故障时间/(平均故障时间+平均修复时间)

简而言之，负载均衡就是将请求均匀分摊在多个操作单元上执行，负载均衡的关键在于两个问题：选择那台服务器和如何将请求转发到这台服务器

¶常见的负载均衡类型

按照最终负载均衡工作的方式可以将负载均衡分为两大类：服务端负载均衡以及客户端负载均衡，下文主要关注点在于：服务端负载均衡技术

📖 按照负载均衡的实现方式，可以将负载均衡分为 软件负载均衡 和 硬件负载均衡，前者的代表是LVS，后者则是均衡服务器（比如F5），其中硬件负载均衡并没有太多的要求，并且一般性能较高；反观软件负载均衡，一般要求软件所在的机器性能较高才能取得较好的效果。常见的负载均衡架构如下

按照服务端负载均衡技术在网络协议栈的工作方式，可以分为链路层负载均衡技术（LVS）、网络层负载均衡技术（LVS、路由）、传输层负载均衡技术（LVS、HAPROXY）以及应用层负载均衡技术（NGINX、HAPROXY）

¶常用的负载均衡算法

🎯本小节将主要介绍常用的负载均衡算法；通用的结构（自定义的服务地址以及服务的权重）如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class IpMap {
public static HashMap<String, Integer> serverWeight = new HashMap<>();
/_ 模拟假数据，内部服务的 IP 地址及对应的权重 _/
static {
serverWeight.put("192.168.1.100", 1);
serverWeight.put("192.168.1.101", 1);
// 权重为 4
serverWeight.put("192.168.1.102", 4);
serverWeight.put("192.168.1.103", 4);
serverWeight.put("192.168.1.104", 4);
// 权重为 3
serverWeight.put("192.168.1.105", 3);
serverWeight.put("192.168.1.106", 3);
// 权重为 2
serverWeight.put("192.168.1.107", 2);
serverWeight.put("192.168.1.108", 2);
serverWeight.put("192.168.1.109", 2);
serverWeight.put("192.168.1.110", 2);
}
}

¶轮询法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class RoundRobin {
private static Integer pos = 0;
public static String getServer() {
// 重建一个 Map，避免服务器的上下线导致的并发问题
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverWeight.size());
serverMap.putAll(IpMap.serverWeight);
// 取得 Ip 地址 List
Set<String> keySet = serverMap.keySet();
ArrayList<String> keyList = new ArrayList<>(keySet);
String server;
synchronized (pos) {
if (pos > keySet.size()) {
pos = 0;
}
server = keyList.get(pos);
pos++;
}
return server;
}
}

真实场景中 serverWeightMap 中的地址列表是动态的，随时可能有机器上线、下线或者宕机，因此为了避免出现并发问题，方法内部新建局部变量 serverMap，将 serverMap 中的内容拷贝到线程本地，以避免被多个线程修改

这样可能会引入新的问题：复制以后 serverWeightMap 的修改无法反映给 serverMap（当前线程对动态列表权重不敏感）；也就是说这一轮选择服务器的过程中，新增服务器或者下线服务器，负载均衡算法将无法获知；新增服务器影响不大，如果有服务器下线或者宕机，那么可能会访问到不存在的地址。因此，服务调用端需要有相应的容错处理，比如重新发起一次 server 选择并调用

对于当前轮询的位置变量 pos，为了保证并发安全性，需要在操作时对其加锁（瞬时并发量巨大，可能造成 RR 算法失效），使得同一时刻只能有一个线程可以修改 pos 的值，否则当 pos 变量被并发修改，则无法保证服务器选择的顺序性，甚至有可能导致 keyList 数组越界

¶加权轮询法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class WeightRoundRobin {
private static Integer pos = 0;
public static String getServer() {
// 重建一个 Map，避免服务器的上下线导致的并发问题
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverWeight.size());
serverMap.putAll(IpMap.serverWeight);
// 取得 Ip 地址 List
Set<String> keySet = serverMap.keySet();
ArrayList<String> serverList = new ArrayList<>();
for (String key : keySet) {
Integer weight = serverMap.get(key);
for (int i = 0; i < weight; i++) {
serverList.add(key);
}
}
String server;
synchronized (pos) {
server = serverList.get(pos);
pos = (pos + 1) % serverList.size();
}
return server;
}
}

✨根据权重的大小，将地址重复地增加到服务器地址列表中，权重越大，该服务器每轮所获得的请求数量越多

¶平滑加权轮询

¶随机法

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Random {
public static String getServer() {
// 重建一个 Map，避免服务器的上下线导致的并发问题
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverWeight.size());
serverMap.putAll(IpMap.serverWeight);
// 取得 Ip 地址 List
Set<String> keySet = serverMap.keySet();
ArrayList<String> keyList = new ArrayList<>(keySet);
java.util.Random random = new java.util.Random();
int randomPos = random.nextInt(keyList.size());
return keyList.get(randomPos);
}
}

整体代码思路和轮询法一致，先重建 serverMap，再获取到 server 列表。在选取 server 的时候，通过 Random.nextInt() 方法取 0~keyList.size() 区间的一个随机值，随后从服务器列表中随机获取到一台服务器地址进行返回。请求越大，随机算法的效果越接近于轮询算法的效果

¶加权随机法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class WeightRandom {
public static String getServer() {
// 重建一个 Map，避免服务器的上下线导致的并发问题
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverWeight.size());
serverMap.putAll(IpMap.serverWeight);
// 取得 Ip 地址 List
Set<String> keySet = serverMap.keySet();
ArrayList<String> serverList = new ArrayList<>();
for (String key : keySet) {
Integer weight = serverMap.get(key);
for (int i = 0; i < weight; i++) {
serverList.add(key);
}
}
Random random = new Random();
int randomPosition = random.nextInt(serverList.size());
return serverList.get(randomPosition);
}
}

¶源地址哈希法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class SourceHash {
public static String getServer() {
// 重建一个 Map，避免服务器的上下线导致的并发问题
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverWeight);
// 取得 Ip 地址 List
Set<String> keySet = serverMap.keySet();
ArrayList<String> keyList = new ArrayList<>(keySet);
// 在 Web 应用中可通过 HttpServlet 的 getRemoteIp 方法获取
String remoteIp = "127.0.0.1";
int hashCode = remoteIp.hashCode();
int serverListSize = keyList.size();
int serverPos = hashCode % serverListSize;
return keyList.get(serverPos);
}
}

¶最小连接数法

前述所有的负载均衡均是从调用者角度看待最终的结果，从调用者而言访问的服务器不同，做到了服务器的均衡访问；但是，从后端服务器角度看待整个系统可能请求分配是不均衡的，某时刻一个服务器可能还是不可避免的接收到海量的请求，甚至服务器中的服务已经 OOM 了，还会有请求被分配到此服务器，造成请求堆积

最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将请求合理地分流到每一台服务器

¶加权最小连接数

¶最短响应时间 LRT

RT(Response Time)是衡量服务器负载的一个非常重要的指标。对于响应很慢的服务器，说明其负载一般很高了，应该降低它的 QPS。

¶一致性哈希

一致性哈希算法(Consistent Hashing)在 1997 年由麻省理工学院提出的一种分布式哈希表（DHT）实现算法，通过一致性哈希能够将同样的请求尽量落到同一台机器上，并且保证服务器动态变化时，需要更改的操作最少

❓上面的例子通过源地址哈希就可以解决，为什么还需要一致性哈希算法？

¶算法原理

⛵具体的算法原理如下：

1. 存在这样一个哈希环，一个长度为 32 位的哈希环，环上存在一个$2^32$个哈希桶，通过哈希函数能够将不同的请求映射到哈希环上的某个桶中，一个哈希环如下：

   

2. 每一个服务节点都通过哈希函数映射到换上的某个桶中，称为 Node。每个 Node 管理从其当前桶节点开始到下一个存在服务的桶节点之前的所有空节点，如下图所示

   

3. 当实际请求进来时，仍然将请求通过哈希函数映射到某一个桶上，再按照顺时针的规则，请求沿着哈希环找到最近的节点，对应的管理节点就是其需要真实访问的服务地址。具体细节如下图，请求 Job_1 按照规则就分配到 Node_1 上，请求 Job_k、Job_k+1 分配到 Node_n 上面

   

¶节点宕机

如果存在节点宕机，能够通过修改少部分的节点做到哈希信息的维持，不需要重新将节点再哈希一遍。如下图，假设后端节点 Node_1 宕机，按照规则，请求 Job_1 被分配到 Node_k 上，但是 Job_k、Job_k+1、Job_i 不受影响，即仅仅影响宕机节点上的请求

¶扩容

按照规则，仅仅请求 Job_k 被重新分配到 Node_i 上去了，其它请求 Job_1、Job_k+1、Job_i 都不受影响，即仅仅影响分流的很少部分请求

¶引入虚拟节点

为了保证均匀性，将给每个物理节点虚拟出一定数量的虚拟节点，分散到哈希环上，需要尽可能地随机分散开。虚拟节点承载的请求实际是指向真实的物理节点。出现物理机节点宕机时，虚拟节点上的请求按照规则转移至下一个节点，避免雪崩效应。当物理节点较少时，虚拟节点数需要更高来确保更好的一致性表现

¶算法总结

¶负载均衡实现

负载均衡算法是负载均衡器进行负载均衡的核心，但是系统中到底如何部署这些负载均衡器尼？接下来将详细介绍多种不同的负载均衡方案，以保证系统能够达到负载均衡效果

¶经典负载均衡

在高并发请求下，通过负载均衡服务器将请求均衡分发给不同的应用服务器

¶HTTP 重定向负载均衡

重定向服务器仅仅做一件事情：在响应头中写入重定向地址，利用路由算法，改写请求的目标 IP 地址，并把 IP 地址写入到响应的重定向 Head 中，随后把请求发送到用户端。用户端解析重定向响应，把请求重新发送给 Web 应用服务器的目标服务器

✨特点：

¶DNS 负载均衡

通过 DNS 进行负载均衡，用户一般都是通过域名访问后台服务，所以就需要进行域名解析（将一个域名解析为 IP 地址）。DNS 负载均衡方案的想法在于：通过 DNS 解析域名时，对同一个域名，解析出不同的地址，来实现负载均衡

在生产环境中大型互联网应用中，使用两级负载均衡避免出现上述问题：

• 一级负载均衡：DNS 负载均衡，通过 DNS 解析出不同负载均衡服务器的 IP 地址
• 二级负载均衡：负载均衡器完成请求分配，每台负载均衡服务器后面连接若干台应用服务器，多台负载均衡服务器构成负载均衡集群，整个负载均衡器集群负责二级负载均衡，将请求真正导向到特定的服务器集群
  

¶反向代理负载均衡

反向代理服务器向后分发请求时，可以实现将不同用户请求分发到不同应用服务器，从而达到负载均衡效果。在生产环境中，适用于规模比较小的应用服务器集群，几台到十几台小规模应用服务器集群；大规模应用服务器集群，不使用反向代理服务器实现负载均衡（由于服务器集群庞大，此时使用反向代理效率低，性能低）
❓为什么反向代理效率低?

🎶效率低的主要原因在于：应用层协议转换，可以通过更底层的网络协议进行负载均衡，使数据包不到达应用层，可能在网络层就将数据包进行转发，这就是下面要说的负载均衡方案

¶IP 负载均衡

反向代理负载均衡在应用层封包拆包代价巨大，所以 IP 负载均衡的想法就是：TCP/IP 数据包比较小，修改 IP 地址后，直接转发，不需要应用层协议转换、转发效率快、性能压力比反向代理小很多。

😣这种方式存在响应瓶颈，高并发响应的数据包通过负载均衡服务器，由于负载均衡服务器自身的网络带宽限制，最终网卡可能成为瓶颈，造成响应数据内容太大，处理不过来，造成消息堆积
❓为什么会造成响应内容太大？

🎶也存在能够解决此问题的方法，将数据包的拆分放在更底层进行，尽量减少负载均衡服务器的压力

¶数据链路层负载均衡

IP 负载均衡的缺点在于：所有后端服务器的响应统一交由前端负载均衡服务器 ^[1] 进行封包处理，使得前端负载均衡器成为整个系统的瓶颈，这种瓶颈最终可以通过数据链路层负载均衡方案进行解决

在数据链路层负载均衡方案中，负载均衡服务器不再修改 IP 地址，直接在数据链路层修改数据包中的 MAC 地址，应用服务器集群使用虚拟 IP。当应用服务器集群完成处理后，不再将响应发送给负载均衡服务器，而是直接发送到源地址。这是由于负载均衡服务器没有修改过 IP 地址，数据包源地址仍然为源地址（以上的模式又称为三角请求）

¶高可用系统

通过上述介绍，已经知道了负载均衡模块的组成，那么在一个大型分布式系统中，到底如何部署负载均衡模块，以保证最终分布式系统是满足负载均衡特性的？

接下来将对每一层的负载均衡方案进行介绍

¶第一层：客户端层到反向代理层

¶第二层：反向代理层到站点层

🎶虽然站点层可以存储 session，但是不建议这么做，站点层无状态是分布式架构设计的基本原则之一，如果站点层存储 session 将会造成非常多的麻烦，由于不是本文的重心，所以不在这里阐述。因此 session 最好放到数据层存储

¶第三层：站点层到服务层

¶第四层：访问数据层

业内常见的水平切分方式有这么几种：

¶按照 range 水平切分

👍这样进行水平切分的好处是：

• 规则简单，service 只需判断一下 uid 范围就能路由到对应的存储服务
• 数据均衡性较好
• 比较容易扩展，可以随时加一个 uid[2kw,3kw] 的数据服务
  😣这样做也存在一些弊端，请求的负载不一定均衡，一般来说，新注册的用户会比老用户更活跃，大 range 的服务请求压力会更大

¶按照 id 哈希水平切分

👍这样做的好处是：

• 规则简单，service 只需对 uid 进行 hash 能路由到对应的存储服务
• 数据均衡性较好
• 请求均匀性较好
  😣同样存在一些弊端：通过哈希之后就不容易进行扩展，hash 方法改变时候，可能需要进行数据迁移
  

¶总结

👴如果是比较小的网站（日 pv < 1000 万），用 nginx 就完全可以了，如果机器也少，可以用 dns 轮询。Lvs 所耗费的机器比较多，对于大型网站或者重要的服务，要多多考虑利用 Lvs。如果为了应对亿级别的 PV ，DNS 端也应配置多个 LVS 集群的地址，保证 LVS 的高可用。简单的负载均衡架构如下：

¶附录

几种简单的负载均衡算法及其 Java 代码实现
关于负载均衡的一切
5.5 负载均衡架构
讲讲亿级 PV 的负载均衡架构
吃透负载均衡
Consistent hashing
常用负载均衡策略分析
加权平滑轮询算法