一致性哈希算法原理

前言

首先我们学习和了解一个知识时，可能会先下意识搜索一下它的基本概念。所以我先百度了一下。

百度给出的概念，可以说是很明确了：

一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。
在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题 。

正文

根据百度，我们可以知道，所谓一致性Hash算法，是一种特殊的Hash算法。

那么学习的捷径就出来了，我们可以对比学习，先来看看Hash算法，然后再去研究它对于解决动态伸缩问题上的短板究竟是什么。

一、抛砖引玉，简单Hash算法的短板

我们先假设出这样一个场景：

当前有3台机器 node1、node2 、node3，是我们用来存储缓存的。业务数据缓存目前假设有100万个key。
我们的需求是，将这100万个key 尽可能均匀的存储到这3台机器上。

效果图如下：

当我们采取简单Hash算法时，对所有的key值进行hash计算，获取到一个hash值，再取模于3（3台机器，所以取模于3）。

这样就能保证所有算出来的结果一定是 0、1、2 这3个数，从而对应到我们的3台机器，就可以解决以上的问题。如下图所示：

那么问题来了，在分布式场景中，我们的机器会有数量调整的情况。
就好比电商相关的项目，在618、双11等购物狂欢节时，就需要临时增加机器，然后等高峰期过后，又需要减少节点。

这种时候，对机器数量取模，就不好使了。

假设原先有3台机器，存值时使用的是取模于3，在用的时候，有一台挂了，取值时取模于2，如下图：

这种时候，由于node3挂掉，取模模于2，自然会有很多缓存无法命中，也就是失效。

那么大量缓存同时失效，就可以恭喜你了，喜提缓存雪崩，整个缓存系统不可用，这也就是简单Hash算法无法处理的短板，也正是一致性Hash算法所解决的问题之一。

二、一致性Hash算法的基本概念

它的基本概念其实就和我百度出来的相同。可以翻到本文前言，再重新读一遍，理解一下。

本小节内容主要是基于百度出来的基本概念，进行图文讲解。

2.1 一致性Hash算法本质也是取模

一致性Hash算法，本质上也是取模运算，只是与简单Hash算法不同，它是对 2 的 32 次方 取模。
原因如下：

我们都知道IPv4地址，是由 4 段 8位二进制组成的，因为书写方便的问题，将二进制转换为十进制，例如如下地址：

而这个地址的大小范围则是 [0, 2的32次方)，所以取模的值可以固定下来，能够保证每个IP地址有唯一的映射。

2.2 便于理解的抽象，哈希环

上一小节提到，IP地址的范围是 [0, 2的32次方)，如果我们将所有的值抽象成环，正上方为0，以顺时针排列。
将所有的值抽象为圆周上的点，那么可以获得如下的哈希环：

2.3 服务器如何映射到哈希环上

假设现在有3台机器，分别是 nodeA 、nodeB 、nodeC，我们要把他们映射到哈希环中。

首先使用哈希算法对机器的IP地址进行计算，随后再取模，得到 A、B、C 这3个值。随后根据计算结果，映射到哈希环上。

2.4 对象如何映射到哈希环上，并关联到对应的机器

假设有4个对象，需要存起来。

对象计算时的hash函数可以和服务器节点的函数不同，但需要保证计算结果在环的范围内。
计算的结果分别是 H1，H2，H3，H4，将他们先映射到Hash环上。

然后从0开始，顺时针转圈，当对象计算出的结果蓝色H，第一次遇到绿色（机器），就存到该机器上。关联后的结果如下：

H2和H4存到了 B 机器上；H1存到了C机器上，H3存到了A机器上

本质是将原本单个点的Hash映射，转变成了环上的某个片段的映射，也就是百度百科中提到的：

在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。

这一原理的实现，也就在于此。我们接着往下看。

三、一致性Hash算法在增加或减少机器时的骚操作

3.1 服务器数量减少

比如C机器挂了，H1会存到A机器上

3.2 服务器数量增加

比如增加机器D，H2会存到D机器上

四、数据倾斜、机器负载的处理

但凡使用了Hash算法，就可能存在数据倾斜的问题（这里我们不考虑哈希冲突）。上述例子中，为了方便演示，基本使用了比较均衡的散列示例。

这里我们需要考虑两个问题：

• 数据倾斜，也就是Hash散列不均匀，可能给一个机器存储过多的对象数据，而有的机器却一个都不存储；
• 机器负载不均衡，在增加机器时，不能很好的分摊机器负载或只分担很少机器的负载，在现象上看，其实勉强也算是一种数据倾斜的问题；

4.1 数据倾斜的体现

很多对象集中映射到某一台或几台机器，其他机器数据映射很少甚至于没有。
可以看到很多数据都映射到了B机器，而A 、C 机器上映射的数据很少。

4.2 机器负载的体现

在数据倾斜发生时，本身就是机器负载不均衡的一种体现，但本小节提到的，是另一种场景。

在我们增加机器时，新增的机器不能很好的分担其他机器的负载，这也是一个问题。

比如，为了帮忙分担负载，增加了机器D：

但是D映射的位置比较尴尬，没有帮助B 分担到负载。

又或者说另一种情况，A 机器现在也有很多数据存储，我们新增机器D：

D的出现，帮B分担了部分压力，但是对A没有任何影响。

4.3 处理方案，增加虚拟节点

为了处理以上的两个问题，可以引入虚拟节点的概念。
所谓虚拟节点，就是针对每个实际机器，计算多个映射点。

比如：
针对nodeA 计算的虚拟节点有 A#1 、A#2 、A#3 ，实际节点是 A
针对nodeB 计算的虚拟节点有 B#1 、B#2 、B#3，实际节点是 B
针对nodeC 计算的虚拟节点有 C#1 、C#2 、C#3，实际节点是 C

他们分布在哈希环上之后，就如下图所示：

使用虚拟节点时，可以看到当虚拟节点越多，也就越不容易出现数据倾斜。

然后我们再依据虚拟节点对真实节点做一套转换即可。
也就是原先找节点的逻辑基本不变，只是在找到虚拟节点时，一律定位到实际机器上。

比如，我们找到数据H3 在 A#2虚拟节点上，就在此定位到A机器真实的节点A上。

五、Java代码模拟算法

Java 版本使用Java 9
涉及到的类文件有：

5.1 定义哈希算法接口

定义接口，用以实现3种哈希算法

package com.example.demo;import java.util.List;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;/*** 哈希算法接口** @author feng*/
public interface HashAlgorithm {/*** 哈希算法** @param clients 客户端集合* @return 服务端地址和客户端地址列表的映射*/SortedMap<String, List<String>> hash(Set<String> clients);/*** 服务器的编号、地址*/SortedMap<Integer, String> SERVER_ADDRESS_MAP = new TreeMap<>();
}

5.2 简单哈希算法

package com.example.demo;import java.util.*;/*** 简单Hash算法** @author feng*/
public class GeneralHashAlgorithm implements HashAlgorithm {private final int serverCount;public GeneralHashAlgorithm(int serverCount) {this.serverCount = serverCount;}@Overridepublic SortedMap<String, List<String>> hash(Set<String> clients) {SortedMap<String, List<String>> resultMap = new TreeMap<>();for (String client : clients) {// 执行hash，获取值int hashCode = Math.abs(client.hashCode());// 计算索引int index = hashCode % serverCount;// 获取选中的服务器地址String serverAddress = SERVER_ADDRESS_MAP.get(index);System.out.printf("客户端%s 选中了服务端序号为%s，地址为%s \r\n", client, index, serverAddress);List<String> newArrayList = resultMap.getOrDefault(serverAddress, new ArrayList<>());newArrayList.add(client);resultMap.put(serverAddress, newArrayList);}return resultMap;}
}

5.3 一致性哈希算法（不包含虚拟节点）

package com.example.demo;import java.util.*;/*** 一致性哈希算法-不包括虚拟节点** @author feng*/
public class ConsistencyExcludeVirtualNodeHashAlgorithm implements HashAlgorithm {@Overridepublic SortedMap<String, List<String>> hash(Set<String> clients) {SortedMap<String, List<String>> resultMap = new TreeMap<>();// 哈希散列服务端地址SortedMap<Integer, String> hashServerMap = serverHash();// 处理客户端地址for (String client : clients) {int clientHashCode = Math.abs(client.hashCode());// 从服务端地址中查找能够处理的服务器节点,tailMap表示返回此映射中键大于或等于key的部分的mapSortedMap<Integer, String> tempSortedMap = hashServerMap.tailMap(clientHashCode);// 从当前节点，顺时针转完一整圈，回到0点，仍未发现能够处理的服务器if (tempSortedMap.isEmpty()) {// 取哈希环中的第一个服务器Integer firstKey = hashServerMap.firstKey();String firstAddress = hashServerMap.get(firstKey);System.out.printf("客户端%s 选中了服务端序号为%s，地址为%s \r\n", client, firstKey, firstAddress);List<String> newArrayList = resultMap.getOrDefault(firstAddress, new ArrayList<>());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);} else {// 从哈希环取符合条件的服务器Integer firstKey = tempSortedMap.firstKey();String firstAddress = hashServerMap.get(firstKey);System.out.printf("客户端%s 选中了服务端序号为%s，地址为%s \r\n", client, firstKey, firstAddress);List<String> newArrayList = resultMap.getOrDefault(firstAddress, new ArrayList<>());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);}}return resultMap;}private SortedMap<Integer, String> serverHash() {SortedMap<Integer, String> hashServerMap = new TreeMap<>();SERVER_ADDRESS_MAP.forEach((k, v) -> {int serverAddressHashCode = Math.abs(v.hashCode());hashServerMap.put(serverAddressHashCode, v);});return hashServerMap;}
}

5.4 一致性哈希算法（包含虚拟节点）

package com.example.demo;import java.util.*;/*** 一致性哈希算法-包括虚拟节点** @author feng*/
public class ConsistencyIncludeVirtualNodeHashAlgorithm implements HashAlgorithm {/*** 虚拟节点个数*/private final int virtualNodeCount;public ConsistencyIncludeVirtualNodeHashAlgorithm(int virtualNodeCount) {this.virtualNodeCount = virtualNodeCount;}@Overridepublic SortedMap<String, List<String>> hash(Set<String> clients) {SortedMap<String, List<String>> resultMap = new TreeMap<>();// 哈希散列服务端地址，增加虚拟节点映射SortedMap<Integer, String> hashServerMap = serverHash();for (String client : clients) {int clientHashCode = Math.abs(client.hashCode());// 从服务端地址中查找能够处理的服务器节点,tailMap表示返回此映射中键大于或等于key的部分的mapSortedMap<Integer, String> tempSortedMap = hashServerMap.tailMap(clientHashCode);// 从当前节点，顺时针转完一整圈，回到0点，仍未发现能够处理的服务器if (tempSortedMap.isEmpty()) {// 取哈希环中的第一个服务器Integer firstKey = hashServerMap.firstKey();String firstAddress = hashServerMap.get(firstKey);System.out.printf("客户端%s 选中了服务端序号为%s，地址为%s \r\n", client, firstKey, firstAddress);List<String> newArrayList = resultMap.getOrDefault(firstAddress, new ArrayList<>());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);} else {// 从哈希环取符合条件的服务器Integer firstKey = tempSortedMap.firstKey();String firstAddress = hashServerMap.get(firstKey);System.out.printf("客户端%s 选中了服务端序号为%s，地址为%s \r\n", client, firstKey, firstAddress);List<String> newArrayList = resultMap.getOrDefault(firstAddress, new ArrayList<>());newArrayList.add(client);resultMap.put(firstAddress, newArrayList);}}return resultMap;}private SortedMap<Integer, String> serverHash() {SortedMap<Integer, String> hashServerMap = new TreeMap<>();SERVER_ADDRESS_MAP.forEach((k, v) -> {int serverAddressHashCode = Math.abs(v.hashCode());hashServerMap.put(serverAddressHashCode, v);// 增加虚拟节点for (int i = 0; i < virtualNodeCount; i++) {String virtualNodeName = v + "#" + i;int virtualNodeHashCode = Math.abs((virtualNodeName).hashCode());hashServerMap.put(virtualNodeHashCode, virtualNodeName);}});return hashServerMap;}
}

5.5 测试

package com.example.demo;import java.util.*;/*** 测试** @author feng*/
public class Client {static {HashAlgorithm.SERVER_ADDRESS_MAP.put(0, "11.123.32.3");HashAlgorithm.SERVER_ADDRESS_MAP.put(1, "23.43.41.1");HashAlgorithm.SERVER_ADDRESS_MAP.put(2, "192.169.21.3");}public static void main(String[] args) {Set<String> set = Set.of("10.78.12.3", "113.25.63.1", "126.12.3.8");SortedMap<String, List<String>> hash;// 简单hash算法hash = new GeneralHashAlgorithm(3).hash(set);hash.forEach((k, v) -> System.out.printf("简单hash算法-客户端地址%s已经映射到服务端%s \r\n", v, k));System.out.println();// 一致性hash算法（不包括虚拟节点）hash = new ConsistencyExcludeVirtualNodeHashAlgorithm().hash(set);hash.forEach((k, v) -> System.out.printf("一致性hash算法（不包括虚拟节点）-客户端地址%s已经映射到服务端%s \r\n", v, k));System.out.println();// 一致性hash算法（包括虚拟节点）hash = new ConsistencyIncludeVirtualNodeHashAlgorithm(3).hash(set);hash.forEach((k, v) -> {// 截取真实服务端地址String realServer = k;if (k.contains("#")) {realServer = k.substring(0, k.indexOf("#"));}System.out.printf("一致性hash算法（包括虚拟节点）-客户端地址%s已经映射到服务端%s ,真实的服务器地址是%s \r\n", v, k, realServer);});}
}

5.6 测试结果

客户端113.25.63.1 选中了服务端序号为2，地址为192.169.21.3 
客户端10.78.12.3 选中了服务端序号为1，地址为23.43.41.1 
客户端126.12.3.8 选中了服务端序号为1，地址为23.43.41.1 
简单hash算法-客户端地址[113.25.63.1]已经映射到服务端192.169.21.3 
简单hash算法-客户端地址[10.78.12.3, 126.12.3.8]已经映射到服务端23.43.41.1 客户端113.25.63.1 选中了服务端序号为1763606946，地址为192.169.21.3 
客户端10.78.12.3 选中了服务端序号为1763606946，地址为192.169.21.3 
客户端126.12.3.8 选中了服务端序号为47976546，地址为23.43.41.1 
一致性hash算法（不包括虚拟节点）-客户端地址[113.25.63.1, 10.78.12.3]已经映射到服务端192.169.21.3 
一致性hash算法（不包括虚拟节点）-客户端地址[126.12.3.8]已经映射到服务端23.43.41.1 客户端113.25.63.1 选中了服务端序号为1139178415，地址为23.43.41.1#2 
客户端10.78.12.3 选中了服务端序号为632380315，地址为11.123.32.3#0 
客户端126.12.3.8 选中了服务端序号为47976546，地址为23.43.41.1 
一致性hash算法（包括虚拟节点）-客户端地址[10.78.12.3]已经映射到服务端11.123.32.3#0 ,真实的服务器地址是11.123.32.3 
一致性hash算法（包括虚拟节点）-客户端地址[126.12.3.8]已经映射到服务端23.43.41.1 ,真实的服务器地址是23.43.41.1 
一致性hash算法（包括虚拟节点）-客户端地址[113.25.63.1]已经映射到服务端23.43.41.1#2 ,真实的服务器地址是23.43.41.1 

六、一致性哈希算法的应用场景

• PC框架Dubbo用来选择服务提供者
• 分布式关系数据库分库分表：数据与节点的映射关系
• LVS负载均衡调度器
• memcached 路由算法
• redis 的hash槽