共计 7089 个字符，预计需要花费 18 分钟才能阅读完成。
本文次要解说了一致性哈希算法的原理以及其存在的数据歪斜的问题，而后引出解决数据歪斜问题的办法，最初剖析一致性哈希算法在 Dubbo 中的应用。通过这篇文章，能够理解到一致性哈希算法的原理以及这种算法存在的问题和解决方案。
一、负载平衡
在这里援用 dubbo 官网的一段话——
LoadBalance 中文意思为负载平衡，它的职责是将网络申请，或者其余模式的负载“均摊”到不同的机器上。防止集群中局部服务器压力过大，而另一些服务器比拟闲暇的状况。通过负载平衡，能够让每台服务器获取到适宜本人解决能力的负载。在为高负载服务器分流的同时，还能够防止资源节约，两全其美。负载平衡可分为软件负载平衡和硬件负载平衡。在咱们日常开发中，个别很难接触到硬件负载平衡。但软件负载平衡还是能够接触到的，比方 Nginx。在 Dubbo 中，也有负载平衡的概念和相应的实现。Dubbo 须要对服务消费者的调用申请进行调配，防止多数服务提供者负载过大。服务提供者负载过大，会导致局部申请超时。因而将负载平衡到每个服务提供者上，是十分必要的。Dubbo 提供了 4 种负载平衡实现，别离是基于权重随机算法的 RandomLoadBalance、基于起码沉闷调用数算法的 LeastActiveLoadBalance、基于 hash 一致性的 ConsistentHashLoadBalance，以及基于加权轮询算法的 RoundRobinLoadBalance。这几个负载平衡算法代码不是很长，然而想看懂也不是很容易，须要对这几个算法的原理有肯定理解才行。
二、哈希算法
图 1 无哈希算法申请
如上所示，假如 0,1,2 号服务器都存储的有用户信息，那么当咱们须要获取某用户信息时，因为咱们不晓得该用户信息寄存在哪一台服务器中，所以须要别离查问 0,1,2 号服务器。这样获取数据的效率是极低的。
对于这样的场景，咱们能够引入哈希算法。
图 2 引入哈希算法后的申请
还是下面的场景，但 前提是每一台服务器寄存用户信息时是依据某一种哈希算法寄存的。所以取用户信息的时候，也依照同样的哈希算法取即可。
假如咱们要查问用户号为 100 的用户信息，通过某个哈希算法，比方这里的 userId mod n，即 100 mod 3 后果为 1。所以用户号 100 的这个申请最终会被 1 号服务器接管并解决。
这样就解决了有效查问的问题。
然而这样的计划会带来什么问题呢？
扩容或者缩容时，会导致大量的数据迁徙。起码也会影响 50% 的数据。
图 3 减少一台服务器
为了阐明问题，退出一台服务器 3。服务器的数量 n 就从 3 变成了 4。还是查问用户号为 100 的用户信息时，100 mod 4 后果为 0。这时，申请就被 0 号服务器接管了。
- 当服务器数量为 3 时，用户号为 100 的申请会被 1 号服务器解决。
- 当服务器数量为 4 时，用户号为 100 的申请会被 0 号服务器解决。
所以，当服务器数量减少或者缩小时，肯定会波及到大量数据迁徙的问题。
对于上述哈希算法其长处是简略易用，大多数分库分表规定就采取的这种形式。个别是提前依据数据量，事后估算好分区数。
其毛病是因为扩容或膨胀节点导致节点数量变动时，节点的映射关系须要从新计算，会导致数据进行迁徙。所以 扩容时通常采纳翻倍扩容，防止数据映射全副被打乱，导致全量迁徙的状况，这样只会产生 50% 的数据迁徙。
三、一致性哈希算法
** 一致性 hash 算法由麻省理工学院的 Karger 及其合作者于 1997 年提出的，算法提出之初是用于大规模缓存零碎的负载平衡。** 它的工作过程是这样的，首先依据 ip 或者其余的信息为缓存节点生成一个 hash，并将这个 hash 投射到 [0, 232 – 1] 的圆环上。当有查问或写入申请时，则为缓存项的 key 生成一个 hash 值。而后查找第一个大于或等于该 hash 值的缓存节点，并到这个节点中查问或写入缓存项。如果以后节点挂了，则在下一次查问或写入缓存时，为缓存项查找另一个大于其 hash 值的缓存节点即可。大抵成果如下图所示，每个缓存节点在圆环上占据一个地位。如果缓存项的 key 的 hash 值小于缓存节点 hash 值，则到该缓存节点中存储或读取缓存项。比方上面绿色点对应的缓存项将会被存储到 cache-2 节点中。因为 cache-3 挂了，本来应该存到该节点中的缓存项最终会存储到 cache- 4 节点中。
图 4 一致性哈希算法
在一致性哈希算法中，不论是减少节点，还是宕机节点，受影响的区间仅仅是减少或者宕机服务器在哈希环空间中，逆时针 方向遇到的第一台服务器之间的区间，其它区间不会受到影响。
然而一致性哈希也是存在问题的：
图 5 数据歪斜
当节点很少的时候可能会呈现这样的散布状况，A 服务会承当大部分申请。这种状况就叫做数据歪斜。
那如何解决数据歪斜的问题呢？
退出虚构节点。
首先一个服务器依据须要能够有多个虚构节点。假如一台服务器有 n 个虚构节点。那么哈希计算时，能够应用 IP+ 端口 + 编号 的模式进行哈希值计算。其中的编号就是 0 到 n 的数字。因为 IP+ 端口是一样的，所以这 n 个节点都是指向的同一台机器。
图 6 引入虚构节点
在没有退出虚构节点之前，A 服务器承当了绝大多数的申请。然而假如每个服务器有一个虚构节点（A-1，B-1，C-1），通过哈希计算后落在了如上图所示的地位。那么 A 服务器的承当的申请就在肯定水平上（图中标注了五角星的局部）摊派给了 B -1、C- 1 虚构节点，实际上就是摊派给了 B、C 服务器。
一致性哈希算法中，退出虚构节点，能够解决数据歪斜问题。
四、一致性哈希在 DUBBO 中的利用
图 7 Dubbo 中一致性哈希环
这里雷同色彩的节点均属于同一个服务提供者，比方 Invoker1-1，Invoker1-2，……, Invoker1-160。这样做的目标是通过引入虚构节点，让 Invoker 在圆环上分散开来，防止数据歪斜问题。所谓数据歪斜是指，因为节点不够扩散，导致大量申请落到了同一个节点上，而其余节点只会接管到了大量申请的状况。比方：
图 8 数据歪斜问题
如上，因为 Invoker-1 和 Invoker-2 在圆环上散布不均，导致系统中 75% 的申请都会落到 Invoker-1 上，只有 25% 的申请会落到 Invoker-2 上。解决这个问题方法是引入虚构节点，通过虚构节点平衡各个节点的申请量。
到这里背景常识就遍及完了，接下来开始 剖析源码。咱们先从 ConsistentHashLoadBalance 的 doSelect 办法开始看起，如下：
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors =
new ConcurrentHashMap<String, ConsistentHashSelector<?>>();
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {String methodName = RpcUtils.getMethodName(invocation);
String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
// 获取 invokers 原始的 hashcode
int identityHashCode = System.identityHashCode(invokers);
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
// 如果 invokers 是一个新的 List 对象，意味着服务提供者数量产生了变动，可能新增也可能缩小了。// 此时 selector.identityHashCode != identityHashCode 条件成立
if (selector == null || selector.identityHashCode != identityHashCode) {
// 创立新的 ConsistentHashSelector
selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
selector = (ConsistentHashSelector<T>) selectors.get(key);
}
// 调用 ConsistentHashSelector 的 select 办法抉择 Invoker
return selector.select(invocation);
}
private static final class ConsistentHashSelector<T> {...}
}
如上，doSelect 办法次要做了一些前置工作，比方检测 invokers 列表是不是变动过，以及创立 ConsistentHashSelector。这些工作做完后，接下来开始调用 ConsistentHashSelector 的 select 办法执行负载平衡逻辑。在剖析 select 办法之前，咱们先来看一下一致性 hash 选择器 ConsistentHashSelector 的初始化过程，如下：
private static final class ConsistentHashSelector<T> {
// 应用 TreeMap 存储 Invoker 虚构节点
private final TreeMap<Long, Invoker<T>> virtualInvokers;
private final int replicaNumber;
private final int identityHashCode;
private final int[] argumentIndex;
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
this.identityHashCode = identityHashCode;
URL url = invokers.get(0).getUrl();
// 获取虚构节点数，默认为 160
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
// 获取参加 hash 计算的参数下标值，默认对第一个参数进行 hash 运算
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
argumentIndex = new int[index.length];
for (int i = 0; i < index.length; i++) {argumentIndex[i] = Integer.parseInt(index[i]);
}
for (Invoker<T> invoker : invokers) {String address = invoker.getUrl().getAddress();
for (int i = 0; i < replicaNumber / 4; i++) {
// 对 address + i 进行 md5 运算，失去一个长度为 16 的字节数组
byte[] digest = md5(address + i);
// 对 digest 局部字节进行 4 次 hash 运算，失去四个不同的 long 型正整数
for (int h = 0; h < 4; h++) {
// h = 0 时，取 digest 中下标为 0 ~ 3 的 4 个字节进行位运算
// h = 1 时，取 digest 中下标为 4 ~ 7 的 4 个字节进行位运算
// h = 2, h = 3 时过程同上
long m = hash(digest, h);
// 将 hash 到 invoker 的映射关系存储到 virtualInvokers 中，// virtualInvokers 须要提供高效的查问操作，因而选用 TreeMap 作为存储构造
virtualInvokers.put(m, invoker);
}
}
}
}
}
ConsistentHashSelector 的构造方法执行了一系列的初始化逻辑，比方从配置中获取虚构节点数以及参加 hash 计算的参数下标，默认状况下只应用第一个参数进行 hash。须要特地阐明的是，ConsistentHashLoadBalance 的负载平衡逻辑只受参数值影响，具备雷同参数值的申请将会被调配给同一个服务提供者。ConsistentHashLoadBalance 不 关系权重，因而应用时须要留神一下。
在获取虚构节点数和参数下标配置后，接下来要做的事件是计算虚构节点 hash 值，并将虚构节点存储到 TreeMap 中。到此，ConsistentHashSelector 初始化工作就实现了。接下来，咱们来看看 select 办法的逻辑。
public Invoker<T> select(Invocation invocation) {
// 将参数转为 key
String key = toKey(invocation.getArguments());
// 对参数 key 进行 md5 运算
byte[] digest = md5(key);
// 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 办法，// 寻找适合的 Invoker
return selectForKey(hash(digest, 0));
}
private Invoker<T> selectForKey(long hash) {
// 到 TreeMap 中查找第一个节点值大于或等于以后 hash 的 Invoker
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
// 如果 hash 大于 Invoker 在圆环上最大的地位，此时 entry = null，// 须要将 TreeMap 的头节点赋值给 entry
if (entry == null) {entry = virtualInvokers.firstEntry();
}
// 返回 Invoker
return entry.getValue();}
如上，抉择的过程绝对比较简单了。首先是对参数进行 md5 以及 hash 运算，失去一个 hash 值。而后再拿这个值到 TreeMap 中查找指标 Invoker 即可。
到此对于 ConsistentHashLoadBalance 就剖析完了。
在浏览 ConsistentHashLoadBalance 源码之前，倡议读者先补充背景常识，不然看懂代码逻辑会有很大难度。
五、利用场景
- DNS 负载平衡 最早的负载平衡技术是通过 DNS 来实现的，在 DNS 中为多个地址配置同一个名字，因此查问这个名字的客户机将失去其中一个地址，从而使得不同的客户拜访不同的服务器，达到负载平衡的目标。DNS 负载平衡是一种简略而无效的办法，然而它不能辨别服务器的差别，也不能反映服务器的以后运行状态。
- 代理服务器负载平衡 应用代理服务器，能够将申请转发给外部的服务器，应用这种减速模式显然能够晋升动态网页的访问速度。然而，也能够思考这样一种技术，应用代理服务器将申请平均转发给多台服务器，从而达到负载平衡的目标。
- 地址转换网关负载平衡 反对负载平衡的地址转换网关，能够将一个内部 IP 地址映射为多个外部 IP 地址，对每次 TCP 连贯申请动静应用其中一个外部地址，达到负载平衡的目标。
- 协定外部反对负载平衡 除了这三种负载平衡形式之外，有的协定外部反对与负载平衡相干的性能，例如 HTTP 协定中的重定向能力等，HTTP 运行于 TCP 连贯的最高层。
- NAT 负载平衡NAT（Network Address Translation 网络地址转换）简略地说就是将一个 IP 地址转换为另一个 IP 地址，个别用于未经注册的外部地址与非法的、已获注册的 Internet IP 地址间进行转换。实用于解决 Internet IP 地址缓和、不想让网络内部晓得外部网络结构等的场合下。
- 反向代理负载平衡 一般代理形式是代理外部网络用户拜访 internet 上服务器的连贯申请，客户端必须指定代理服务器，并将原本要间接发送到 internet 上服务器的连贯申请发送给代理服务器解决。反向代理（Reverse Proxy）形式是指以代理服务器来承受 internet 上的连贯申请，而后将申请转发给外部网络上的服务器，并将从服务器上失去的后果返回给 internet 上申请连贯的客户端，此时代理服务器对外就体现为一个服务器。反向代理负载平衡技术是把将来自 internet 上的连贯申请以反向代理的形式动静地转发给外部网络上的多台服务器进行解决，从而达到负载平衡的目标。
- 混合型负载平衡 在有些大型网络，因为多个服务器群内硬件设施、各自的规模、提供的服务等的差别，能够思考给每个服务器群采纳最合适的负载平衡形式，而后又在这多个服务器群间再一次负载平衡或群集起来以一个整体向外界提供服务（即把这多个服务器群当做一个新的服务器群），从而达到最佳的性能。将这种形式称之为混合型负载平衡。此种形式有时也用于单台平衡设施的性能不能满足大量连贯申请的状况下。
作者：京东物流 乔杰
起源：京东云开发者社区
