共计 15999 个字符，预计需要花费 40 分钟才能阅读完成。
一、负载平衡简介
1.1. 大型网站面临的挑战
大型网站都要面对宏大的用户量，高并发，海量数据等挑战。为了晋升零碎整体的性能，能够采纳垂直扩大和程度扩大两种形式。
垂直扩大 ：在网站倒退晚期，能够从单机的角度通过减少硬件解决能力，比方 CPU 解决能力，内存容量，磁盘等方面，实现服务器解决能力的晋升。然而，单机是有性能瓶颈的，一旦涉及瓶颈，再想晋升，付出的老本和代价会极高。这显然不能满足大型分布式系统（网站）所有应答的大流量，高并发，海量数据等挑战。
程度扩大 ：通过集群来分担大型网站的流量。集群中的应用服务器（节点）通常被设计成无状态，用户能够申请任何一个节点，这些节点独特分担拜访压力。程度扩大有两个要点：
- 利用集群：将同一利用部署到多台机器上，组成解决集群，接管负载平衡设施散发的申请，进行解决，并返回相应数据。
- 负载平衡：将用户拜访申请，通过某种算法，散发到集群中的节点。
1.2. 什么是负载平衡
负载平衡（Load Balance，简称 LB）是高并发、高可用零碎必不可少的要害组件，指标是 尽力将网络流量均匀散发到多个服务器上，以进步零碎整体的响应速度和可用性。
负载平衡的次要作用如下：
高并发 ：负载平衡通过算法调整负载，尽力平均的调配利用集群中各节点的工作量，以此进步利用集群的并发解决能力（吞吐量）。
伸缩性 ：增加或缩小服务器数量，而后由负载平衡进行散发管制。这使得利用集群具备伸缩性。
高可用 ：负载均衡器能够监控候选服务器，当服务器不可用时，主动跳过，将申请分发给可用的服务器。这使得利用集群具备高可用的个性。
平安防护 ：有些负载平衡软件或硬件提供了安全性性能，如：黑白名单解决、防火墙，防 DDos 攻打等。
二、负载平衡的分类
反对负载平衡的技术很多，咱们能够通过不同维度去进行分类。
2.1 载体维度分类
从反对负载平衡的载体来看，能够将负载平衡分为两类： 硬件负载平衡、软件负载平衡
2.1.1 硬件负载平衡
硬件负载平衡，个别是在定制处理器上运行的独立负载平衡服务器，价格昂贵，土豪专属。硬件负载平衡的主流产品有:F5 和 A10。
硬件负载平衡的 长处：
- 功能强大：反对全局负载平衡并提供较全面的、简单的负载平衡算法。
- 性能强悍：硬件负载平衡因为是在专用处理器上运行，因而吞吐量大，可反对单机百万以上的并发。
- 安全性高：往往具备防火墙，防 DDos 攻打等平安性能。
硬件负载平衡的 毛病：
- 老本低廉：购买和保护硬件负载平衡的老本都很高。
- 扩展性差：当访问量突增时，超过限度不能动静扩容。
2.1.2 软件负载平衡
软件负载平衡，利用最宽泛，无论大公司还是小公司都会应用。
软件负载平衡从软件层面实现负载平衡，个别能够在任何规范物理设施上运行。
软件负载平衡的 主流产品 有：Nginx、HAProxy、LVS。
- LVS 能够作为四层负载均衡器。其负载平衡的性能要优于 Nginx。
- HAProxy 能够作为 HTTP 和 TCP 负载均衡器。
- Nginx、HAProxy 能够作为四层或七层负载均衡器。
软件负载平衡的 长处：
- 扩展性好：适应动态变化，能够通过增加软件负载平衡实例，动静扩大到超出初始容量的能力。
- 老本低廉：软件负载平衡能够在任何规范物理设施上运行，升高了购买和运维的老本。
软件负载平衡的 毛病：
- 性能略差：相比于硬件负载平衡，软件负载平衡的性能要略低一些。
2.2 网络通信分类
软件负载平衡从通信层面来看，又能够分为四层和七层负载平衡。
1) 七层负载平衡 ：就是能够依据拜访用户的 HTTP 申请头、URL 信息将申请转发到特定的主机。
- DNS 重定向
- HTTP 重定向
- 反向代理
2) 四层负载平衡 ：基于 IP 地址和端口进行申请的转发。
- 批改 IP 地址
- 批改 MAC 地址
2.2.1 DNS 负载平衡
DNS 负载平衡个别用于互联网公司，简单的业务零碎不适宜应用。大型网站个别应用 DNS 负载平衡作为 第一级负载平衡伎俩，而后在外部应用其它形式做第二级负载平衡。DNS 负载平衡属于七层负载平衡。
DNS 即 域名解析服务，是 OSI 第七层网络协议。DNS 被设计为一个树形构造的分布式应用，自上而下顺次为：根域名服务器，一级域名服务器，二级域名服务器，…，本地域名服务器。显然，如果所有数据都存储在根域名服务器，那么 DNS 查问的负载和开销会十分宏大。
因而，DNS 查问绝对于 DNS 层级构造，是一个逆向的递归流程，DNS 客户端顺次申请本地 DNS 服务器，上一级 DNS 服务器，上上一级 DNS 服务器，…，根 DNS 服务器（又叫权威 DNS 服务器），一旦命中，立刻返回。为了缩小查问次数，每一级 DNS 服务器都会设置 DNS 查问缓存。
DNS 负载平衡的工作原理就是：基于 DNS 查问缓存，依照负载状况返回不同服务器的 IP 地址。
DNS 重定向的 长处：
应用简略：负载平衡工作，交给 DNS 服务器解决，省掉了负载平衡服务器保护的麻烦
进步性能：能够反对基于地址的域名解析，解析成间隔用户最近的服务器地址（相似 CDN 的原理），能够放慢访问速度，改善性能；
DNS 重定向的 毛病：
可用性差：DNS 解析是多级解析，新增 / 批改 DNS 后，解析工夫较长；解析过程中，用户拜访网站将失败；
扩展性低：DNS 负载平衡的控制权在域名商那里，无奈对其做更多的改善和扩大；
维护性差：也不能反映服务器的以后运行状态；反对的算法少；不能辨别服务器的差别（不能依据零碎与服务的状态来判断负载）。
2.2.2 HTTP 负载平衡
HTTP 负载平衡是基于 HTTP 重定向实现的。HTTP 负载平衡属于七层负载平衡。
HTTP 重定向原理是：依据用户的 HTTP 申请计算出一个实在的服务器地址，将该服务器地址写入 HTTP 重定向响应中，返回给浏览器，由浏览器从新进行拜访。
HTTP 重定向的长处：计划简略。
HTTP 重定向的 毛病：
性能较差：每次拜访须要两次申请服务器，减少了拜访的提早。
升高搜寻排名：应用重定向后，搜索引擎会视为 SEO 舞弊。
如果负载均衡器宕机，就无法访问该站点。
因为其毛病比拟显著，所以这种负载平衡策略理论利用较少。
2.2.3 反向代理负载平衡
反向代理（Reverse Proxy）形式是指以 代理服务器 来承受网络申请，而后 将申请转发给内网中的服务器，并将从内网中的服务器上失去的后果返回给网络申请的客户端。反向代理负载平衡属于七层负载平衡。
反向代理服务的主流产品：Nginx、Apache。
正向代理与反向代理有什么区别？
正向代理：产生在 客户端，是由用户被动发动的。翻墙软件就是典型的正向代理，客户端通过被动拜访代理服务器，让代理服务器取得须要的外网数据，而后转发回客户端。
反向代理：产生在 服务端，用户不晓得代理的存在。
反向代理是如何实现负载平衡的呢？以 Nginx 为例，如下所示：
首先，在代理服务器上设定好负载平衡规定。而后，当收到客户端申请，反向代理服务器拦挡指定的域名或 IP 申请，依据负载平衡算法，将申请散发到候选服务器上。其次，如果某台候选服务器宕机，反向代理服务器会有容错解决，比方散发申请失败 3 次以上，将申请散发到其余候选服务器上。
反向代理的 长处：
- 多种负载平衡算法：反对多种负载平衡算法，以应答不同的场景需要。
- 能够监控服务器：基于 HTTP 协定，能够监控转发服务器的状态，如：零碎负载、响应工夫、是否可用、连接数、流量等，从而依据这些数据调整负载平衡的策略。
反向代理的 毛病：
- 额定的转发开销：反向代理的转发操作自身是有性能开销的，可能会包含创立连贯，期待连贯响应，剖析响应后果等操作。
- 减少零碎复杂度：反向代理罕用于做分布式应用的程度扩大，但反向代理服务存在以下问题，为了解决以下问题会给零碎整体减少额定的复杂度和运维老本：
- 反向代理服务如果本身宕机，就无法访问站点，所以须要有 高可用 计划，常见的计划有：主备模式（一主一备）、双主模式（互为主备）。
- 反向代理服务本身也存在性能瓶颈，随着须要转发的申请量一直攀升，须要有 可扩大 计划。
2.2.4 IP 负载平衡
IP 负载平衡是在网络层通过批改申请目标地址进行负载平衡。
如上图所示，IP 平衡解决流程大抵为：
客户端申请 192.168.137.10，由负载平衡服务器接管到报文。
负载平衡服务器依据算法选出一个服务节点 192.168.0.1，而后将报文申请地址改为该节点的 IP。
实在服务节点收到申请报文，解决后，返回响应数据到负载平衡服务器。
负载平衡服务器将响应数据的源地址改负载平衡服务器地址，返回给客户端。
IP 负载平衡在内核过程实现数据散发，较反向代理负载平衡有更好的从解决性能。然而，因为所有申请响应都要通过负载平衡服务器，集群的吞吐量受制于负载平衡服务器的带宽。
2.2.5 数据链路层负载平衡
数据链路层负载平衡是指在通信协议的数据链路层批改 mac 地址进行负载平衡。
在 Linux 平台上最好的链路层负载平衡开源产品是 LVS (Linux Virtual Server)。LVS 是基于 Linux 内核中 netfilter 框架实现的负载平衡零碎。netfilter 是内核态的 Linux 防火墙机制，能够在数据包流经过程中，依据规定设置若干个关卡（hook 函数）来执行相干的操作。
LVS 的工作流程大抵如下：
当用户拜访 www.sina.com.cn 时，用户数据通过层层网络，最初通过交换机进入 LVS 服务器网卡，并进入内核网络层。
进入 PREROUTING 后通过路由查找，确定拜访的目标 VIP 是本机 IP 地址，所以数据包进入到 INPUT 链上
IPVS 是工作在 INPUT 链上，会依据拜访的 vip+port 判断申请是否 IPVS 服务，如果是则调用注册的 IPVS HOOK 函数，进行 IPVS 相干主流程，强行批改数据包的相干数据，并将数据包发往 POSTROUTING 链上。
POSTROUTING 上收到数据包后，依据指标 IP 地址（后端服务器），通过路由选路，将数据包最终发往后端的服务器上。
开源 LVS 版本有 3 种工作模式，每种模式工作原理截然不同，说各种模式都有本人的优缺点，别离适宜不同的利用场景，不过最终实质的性能都是能实现平衡的流量调度和良好的扩展性。次要包含三种模式：DR 模式、NAT 模式、Tunnel 模式。
三、负载平衡算法
负载均衡器的实现能够分为两个局部：
依据负载平衡算法在候选服务器列表选出一个服务器;
将申请数据发送到该服务器上。
负载平衡算法是负载平衡服务外围中的外围。负载平衡产品多种多样，然而各种负载平衡算法原理是共性的。负载平衡算法有很多种，别离实用于不同的利用场景，本文仅介绍最为常见的负载平衡算法的个性及原理： 轮询、随机、最小沉闷数、源地址哈希、一致性哈希 。
注 ：负载平衡算法的实现，举荐浏览 Dubbo 官网负载平衡算法阐明，源码解说十分具体，十分值得借鉴。
3.1 随机
3.1.1 随机算法
随机（Random） 算法将申请随机散发到候选服务器。
随机算法 适宜服务器硬件雷同的场景。学习过概率论的都晓得，调用量较小的时候，可能负载并不平均，调用量越大，负载越平衡。
【示例】随机算法实现示例
负载平衡接口
public interface LoadBalance<N extends Node> {N select(List<N> nodes, String ip);
}
负载平衡抽象类
public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> {
@Override
public N select(List<N> nodes, String ip) {if (CollectionUtil.isEmpty(nodes)) {return null;}
// 如果 nodes 列表中仅有一个 node，间接返回即可，无需进行负载平衡
if (nodes.size() == 1) {return nodes.get(0);
}
return doSelect(nodes, ip);
}
protected abstract N doSelect(List<N> nodes, String ip);
}
服务器节点类
public class Node implements Comparable<Node> {
protected String url;
protected Integer weight;
protected Integer active;
// ...
}
随机算法实现
public class RandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = new Random();
@Override
protected N doSelect(List<N> nodes, String ip) {
// 在列表中随机选取一个节点
int index = random.nextInt(nodes.size());
return nodes.get(index);
}
}
3.1.2 加权随机算法
加权随机（Weighted Random）算法在随机算法的根底上，依照概率调整权重，进行负载调配。
【示例】加权随机算法实现示例
public class WeightRandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = ThreadLocalRandom.current();
@Override
protected N doSelect(List<N> nodes, String ip) {
int length = nodes.size();
AtomicInteger totalWeight = new AtomicInteger(0);
for (N node : nodes) {Integer weight = node.getWeight();
totalWeight.getAndAdd(weight);
}
if (totalWeight.get() > 0) {int offset = random.nextInt(totalWeight.get());
for (N node : nodes) {
// 让随机值 offset 减去权重值
offset -= node.getWeight();
if (offset < 0) {
// 返回相应的 Node
return node;
}
}
}
// 间接随机返回一个
return nodes.get(random.nextInt(length));
}
}
3.2 轮询
3.2.1 轮询算法
轮询（Round Robin） 算法的策略是：将申请顺次散发到候选服务器。
如下图所示，负载均衡器收到来自客户端的 6 个申请，(1, 3, 5) 的申请会被发送到服务器 1，(2, 4, 6) 的申请会被发送到服务器 2。
该算法适宜场景：各服务器解决能力相近，且每个事务工作量差别不大。如果存在较大差别，那么解决较慢的服务器就可能会积压申请，最终无奈承当过大的负载。
【示例】轮询算法示例
轮询负载平衡算法实现
public class RoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final AtomicInteger position = new AtomicInteger(0);
@Override
protected N doSelect(List<N> nodes, String ip) {int length = nodes.size();
// 如果地位值曾经等于节点数，重置为 0
position.compareAndSet(length, 0);
N node = nodes.get(position.get());
position.getAndIncrement();
return node;
}
}
3.2.2 加权轮询算法
加权轮询（Weighted Round Robbin） 算法在轮询算法的根底上，减少了权重属性来调节转发服务器的申请数目。性能高、处理速度快的节点应该设置更高的权重，使得散发时优先将申请散发到权重较高的节点上。
如下图所示，服务器 A 设置权重为 5，服务器 B 设置权重为 1，负载均衡器收到来自客户端的 6 个申请，那么 (1, 2, 3, 4, 5) 申请会被发送到服务器 A，(6) 申请会被发送到服务器 B。
【示例】加权轮询算法实现示例
以下实现基于 Dubbo 加权轮询算法做了一些简化。
public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
/**
* 60 秒
*/
private static final int RECYCLE_PERIOD = 60000;
/**
* Node hashcode 到 WeightedRoundRobin 的映射关系
*/
private ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>();
/**
* 原子更新锁
*/
private AtomicBoolean updateLock = new AtomicBoolean();
@Override
protected N doSelect(List<N> nodes, String ip) {
int totalWeight = 0;
long maxCurrent = Long.MIN_VALUE;
// 获取以后工夫
long now = System.currentTimeMillis();
N selectedNode = null;
WeightedRoundRobin selectedWRR = null;
// 上面这个循环次要做了这样几件事件：// 1. 遍历 Node 列表，检测以后 Node 是否有相应的 WeightedRoundRobin，没有则创立
// 2. 检测 Node 权重是否产生了变动，若变动了，则更新 WeightedRoundRobin 的 weight 字段
// 3. 让 current 字段加上本身权重，等价于 current += weight
// 4. 设置 lastUpdate 字段，即 lastUpdate = now
// 5. 寻找具备最大 current 的 Node，以及 Node 对应的 WeightedRoundRobin，// 暂存起来，留作后用
// 6. 计算权重总和
for (N node : nodes) {int hashCode = node.hashCode();
WeightedRoundRobin weightedRoundRobin = weightMap.get(hashCode);
int weight = node.getWeight();
if (weight < 0) {weight = 0;}
// 检测以后 Node 是否有对应的 WeightedRoundRobin，没有则创立
if (weightedRoundRobin == null) {weightedRoundRobin = new WeightedRoundRobin();
// 设置 Node 权重
weightedRoundRobin.setWeight(weight);
// 存储 url 惟一标识 identifyString 到 weightedRoundRobin 的映射关系
weightMap.putIfAbsent(hashCode, weightedRoundRobin);
weightedRoundRobin = weightMap.get(hashCode);
}
// Node 权重不等于 WeightedRoundRobin 中保留的权重，阐明权重变动了，此时进行更新
if (weight != weightedRoundRobin.getWeight()) {weightedRoundRobin.setWeight(weight);
}
// 让 current 加上本身权重，等价于 current += weight
long current = weightedRoundRobin.increaseCurrent();
// 设置 lastUpdate，示意近期更新过
weightedRoundRobin.setLastUpdate(now);
// 找出最大的 current
if (current > maxCurrent) {
maxCurrent = current;
// 将具备最大 current 权重的 Node 赋值给 selectedNode
selectedNode = node;
// 将 Node 对应的 weightedRoundRobin 赋值给 selectedWRR，留作后用
selectedWRR = weightedRoundRobin;
}
// 计算权重总和
totalWeight += weight;
}
// 对 weightMap 进行查看，过滤掉长时间未被更新的节点。// 该节点可能挂了，nodes 中不蕴含该节点，所以该节点的 lastUpdate 长时间无奈被更新。// 若未更新时长超过阈值后，就会被移除掉，默认阈值为 60 秒。if (!updateLock.get() && nodes.size() != weightMap.size()) {if (updateLock.compareAndSet(false, true)) {
try {
// 遍历批改，即移除过期记录
weightMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
} finally {updateLock.set(false);
}
}
}
if (selectedNode != null) {
// 让 current 减去权重总和，等价于 current -= totalWeight
selectedWRR.decreaseCurrent(totalWeight);
// 返回具备最大 current 的 Node
return selectedNode;
}
// should not happen here
return nodes.get(0);
}
protected static class WeightedRoundRobin {
// 服务提供者权重
private int weight;
// 以后权重
private AtomicLong current = new AtomicLong(0);
// 最初一次更新工夫
private long lastUpdate;
public long increaseCurrent() {
// current = current + weight；return current.addAndGet(weight);
}
public long decreaseCurrent(int total) {
// current = current - total;
return current.addAndGet(-1 * total);
}
public int getWeight() {return weight;}
public void setWeight(int weight) {
this.weight = weight;
// 初始状况下，current = 0
current.set(0);
}
public AtomicLong getCurrent() {return current;}
public void setCurrent(AtomicLong current) {this.current = current;}
public long getLastUpdate() {return lastUpdate;}
public void setLastUpdate(long lastUpdate) {this.lastUpdate = lastUpdate;}
}
}
3.3 最小沉闷数
最小沉闷数 （Least Active）算法 将申请散发到连接数 / 申请数起码的候选服务器（目前解决申请起码的服务器）。
- 特点：依据候选服务器以后的申请连接数，动态分配。
- 场景：实用于对系统负载较为敏感或申请连贯时长相差较大的场景。
因为每个申请的连贯时长不一样，如果采纳简略的轮循或随机算法，都可能呈现某些服务器以后连接数过大，而另一些服务器的连贯过小的状况，这就造成了负载并非真正平衡。尽管，轮询或算法都能够通过加权重属性的形式进行负载调整，但加权形式难以应答动态变化。
例如下图中，(1, 3, 5) 申请会被发送到服务器 1，然而 (1, 3) 很快就断开连接，此时只有 (5) 申请连贯服务器 1；(2, 4, 6) 申请被发送到服务器 2，只有 (2) 的连贯断开。该零碎持续运行时，服务器 2 会承当过大的负载。
最小沉闷数算法会记录以后时刻，每个候选节点正在解决的连接数，而后抉择连接数最小的节点。该策略可能动静、实时地反馈服务器的当前状况，较为正当地将负责调配平均，实用于对以后零碎负载较为敏感的场景。
例如下图中，服务器 1 以后连接数最小，那么新到来的申请 6 就会被发送到服务器 1 上。
加权最小沉闷数 （Weighted Least Connection）在最小沉闷数的根底上，依据服务器的性能为每台服务器调配权重，再依据权重计算出每台服务器能解决的连接数。
最小沉闷数算法实现要点：沉闷调用数越小，表明该服务节点解决能力越高，单位工夫内可解决更多的申请，应优先将申请分发给该服务。在具体实现中，每个服务节点对应一个沉闷数 active。初始状况下，所有服务提供者沉闷数均为 0。每收到一个申请，沉闷数加 1，实现申请后则将沉闷数减 1。在服务运行一段时间后，性能好的服务提供者解决申请的速度更快，因而沉闷数降落的也越快，此时这样的服务提供者可能优先获取到新的服务申请、这就是最小沉闷数负载平衡算法的根本思维。
【示例】最小沉闷数算法实现
以下实现基于 Dubbo 最小沉闷数负载平衡算法做了些许改变。
public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final Random random = new Random();
@Override
protected N doSelect(List<N> nodes, String ip) {int length = nodes.size();
// 最小的沉闷数
int leastActive = -1;
// 具备雷同“最小沉闷数”的服务者提供者（以下用 Node 代称）数量
int leastCount = 0;
// leastIndexs 用于记录具备雷同“最小沉闷数”的 Node 在 nodes 列表中的下标信息
int[] leastIndexs = new int[length];
int totalWeight = 0;
// 第一个最小沉闷数的 Node 权重值，用于与其余具备雷同最小沉闷数的 Node 的权重进行比照，// 以检测是否“所有具备雷同最小沉闷数的 Node 的权重”均相等
int firstWeight = 0;
boolean sameWeight = true;
// 遍历 nodes 列表
for (int i = 0; i < length; i++) {N node = nodes.get(i);
// 发现更小的沉闷数，从新开始
if (leastActive == -1 || node.getActive() < leastActive) {
// 应用以后沉闷数更新最小沉闷数 leastActive
leastActive = node.getActive();
// 更新 leastCount 为 1
leastCount = 1;
// 记录以后下标值到 leastIndexs 中
leastIndexs[0] = i;
totalWeight = node.getWeight();
firstWeight = node.getWeight();
sameWeight = true;
// 以后 Node 的沉闷数 node.getActive() 与最小沉闷数 leastActive 雷同} else if (node.getActive() == leastActive) {
// 在 leastIndexs 中记录下以后 Node 在 nodes 汇合中的下标
leastIndexs[leastCount++] = i;
// 累加权重
totalWeight += node.getWeight();
// 检测以后 Node 的权重与 firstWeight 是否相等，// 不相等则将 sameWeight 置为 false
if (sameWeight && i > 0
&& node.getWeight() != firstWeight) {sameWeight = false;}
}
}
// 当只有一个 Node 具备最小沉闷数，此时间接返回该 Node 即可
if (leastCount == 1) {return nodes.get(leastIndexs[0]);
}
// 有多个 Node 具备雷同的最小沉闷数，但它们之间的权重不同
if (!sameWeight && totalWeight > 0) {// 随机生成一个 [0, totalWeight) 之间的数字
int offsetWeight = random.nextInt(totalWeight);
// 循环让随机数减去具备最小沉闷数的 Node 的权重值，// 当 offset 小于等于 0 时，返回相应的 Node
for (int i = 0; i < leastCount; i++) {int leastIndex = leastIndexs[i];
// 获取权重值，并让随机数减去权重值
offsetWeight -= nodes.get(leastIndex).getWeight();
if (offsetWeight <= 0) {return nodes.get(leastIndex);
}
}
}
// 如果权重雷同或权重为 0 时，随机返回一个 Node
return nodes.get(leastIndexs[random.nextInt(leastCount)]);
}
}
3.4 源地址哈希
源地址哈希 （IP Hash）算法 依据申请源 IP，通过哈希计算失去一个数值，用该数值在候选服务器列表的进行取模运算，失去的后果便是选中的服务器。
能够保障同一 IP 的客户端的申请会转发到同一台服务器上，用来实现会话粘滞（Sticky Session）。
特点：保障特定用户总是申请到雷同的服务器，若服务器宕机，会话会失落。
【示例】源地址哈希算法实现示例
public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
@Override
protected N doSelect(List<N> nodes, String ip) {if (StrUtil.isBlank(ip)) {ip = "127.0.0.1";}
int length = nodes.size();
int index = hash(ip) % length;
return nodes.get(index);
}
public int hash(String text) {return HashUtil.fnvHash(text);
}
}
3.5 一致性哈希
一致性哈希（Consistent Hash）算法的指标是：雷同的申请尽可能落到同一个服务器上。
一致性哈希 能够很好的解决 稳定性问题，能够将所有的 存储节点 排列在 首尾相接 的 Hash 环上，每个 key 在计算 Hash 后会 顺时针 找到 临接 的 存储节点 寄存。而当有节点 退出 或 退出 时，仅影响该节点在 Hash 环上顺时针相邻的后续节点。
1）雷同的申请是指：个别在应用一致性哈希时，须要指定一个 key 用于 hash 计算，可能是：
用户 ID
申请方 IP
申请服务名称，参数列表形成的串
2）尽可能是指：服务器可能产生高低线，多数服务器的变动不应该影响大多数的申请。
当某台候选服务器宕机时，本来发往该服务器的申请，会基于虚构节点，平摊到其它候选服务器，不会引起激烈变动。
长处 ：退出 和 删除 节点只影响 哈希环 中 顺时针方向 的 相邻的节点，对其余节点无影响。
毛病 ：加减节点 会造成 哈希环 中局部数据 无奈命中。当应用 大量节点 时，节点变动 将大范畴影响 哈希环 中 数据映射，不适宜 大量数据节点 的分布式计划。一般 的 一致性哈希分区 在增减节点时须要 增加一倍 或 减去一半 节点能力保障 数据 和 负载的平衡。
留神 ：因为 一致性哈希分区 的这些毛病，一些分布式系统采纳 虚构槽 对 一致性哈希 进行改良，比方 Dynamo 零碎。
【示例】一致性哈希算法示例
public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
@SuppressWarnings("unchecked")
@Override
protected N doSelect(List<N> nodes, String ip) {
// 分片数，这里设为节点数的 4 倍
Integer replicaNum = nodes.size() * 4;
// 获取 nodes 原始的 hashcode
int identityHashCode = System.identityHashCode(nodes);
// 如果 nodes 是一个新的 List 对象，意味着节点数量产生了变动
// 此时 selector.identityHashCode != identityHashCode 条件成立
ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
if (selector == null || selector.identityHashCode != identityHashCode) {
// 创立新的 ConsistentHashSelector
selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, replicaNum));
selector = (ConsistentHashSelector<N>) selectors.get(ip);
}
// 调用 ConsistentHashSelector 的 select 办法抉择 Node
return selector.select(ip);
}
/**
* 一致性哈希选择器
*/
private static final class ConsistentHashSelector<N extends Node> {
/**
* 存储虚构节点
*/
private final TreeMap<Long, N> virtualNodes;
private final int identityHashCode;
/**
* 结构器
*
* @param nodes 节点列表
* @param identityHashCode hashcode
* @param replicaNum 分片数
*/
ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {this.virtualNodes = new TreeMap<>();
this.identityHashCode = identityHashCode;
// 获取虚构节点数，默认为 100
if (replicaNum == null) {replicaNum = 100;}
for (N node : nodes) {for (int i = 0; i < replicaNum / 4; i++) {
// 对 url 进行 md5 运算，失去一个长度为 16 的字节数组
byte[] digest = md5(node.getUrl());
// 对 digest 局部字节进行 4 次 hash 运算，失去四个不同的 long 型正整数
for (int j = 0; j < 4; j++) {
// h = 0 时，取 digest 中下标为 0 ~ 3 的 4 个字节进行位运算
// h = 1 时，取 digest 中下标为 4 ~ 7 的 4 个字节进行位运算
// h = 2, h = 3 时过程同上
long m = hash(digest, j);
// 将 hash 到 node 的映射关系存储到 virtualNodes 中，// virtualNodes 须要提供高效的查问操作，因而选用 TreeMap 作为存储构造
virtualNodes.put(m, node);
}
}
}
}
public N select(String key) {
// 对参数 key 进行 md5 运算
byte[] digest = md5(key);
// 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 办法，// 寻找适合的 Node
return selectForKey(hash(digest, 0));
}
private N selectForKey(long hash) {
// 查找第一个大于或等于以后 hash 的节点
Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
// 如果 hash 大于 Node 在哈希环上最大的地位，此时 entry = null，// 须要将 TreeMap 的头节点赋值给 entry
if (entry == null) {entry = virtualNodes.firstEntry();
}
// 返回 Node
return entry.getValue();}
}
/**
* 计算 hash 值
*/
public static long hash(byte[] digest, int number) {return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
/**
* 计算 MD5 值
*/
public static byte[] md5(String value) {
MessageDigest md5;
try {md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {throw new IllegalStateException(e.getMessage(), e);
}
md5.reset();
byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
md5.update(bytes);
return md5.digest();}
}
以上示例基于 Dubbo 的一致性哈希负载平衡算法做了一些简化。
四、参考资料
1. Comparing Load Balancing Algorithms
2.《大型网站技术架构：外围原理与案例剖析》
3. 大型网站架构系列：负载平衡详解（1）
4. 什么是负载平衡
5. What Is Load Balancing
6. Dubbo 官网负载平衡算法阐明
7. 负载平衡算法及伎俩
8. 利用 dns 解析来实现网站的负载平衡
作者：vivo 互联网团队 -Zhang Peng
