一致性HASH算法介绍，附代码
一致性Hash算法介绍
概述
一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
一致性哈希算法很好地解决了分布式系统在扩容或者缩容时，发生大量的数据迁移的问题，一致哈希算法里面用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值。
可以理解一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环，就像钟表一样，钟表的圆可以理解成由 60 个点组成的圆，而此处我们把这个圆想象成由 2^32 个点组成的圆，这个圆环被称为哈希环，如下图：
举个例子，有 3 个节点经过哈希计算，映射到了如下图的位置：
接着，对要查询的 key1 进行哈希计算，确定此 key1 映射在哈希环的位置，然后从这个位置往顺时针的方向找到第一个节点，就是存储该 key1 数据的节点。
比如，下图中的 key1 映射的位置，往顺时针的方向找到第一个节点就是DB1
所以，当需要对指定 key 的值进行读写的时候，要通过下面 2 步进行寻址：
- 首先，对 key 进行哈希计算，确定此 key 在环上的位置；
- 然后，从这个位置沿着顺时针方向走，遇到的第一节点就是存储 key 的节点。
知道了一致哈希寻址的方式，我们来看看，如果增加一个节点或者减少一个节点会发生大量的数据迁移吗？
可以看到，key1、key3 都不受影响，只有 key2 需要被迁移DB4。
假设节点数量这会从3 减少到了 2，将DB3 移除：
如上图，可以看到key2和key1不受影响，只需要把key3迁移到DB1即可，因此在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。
一致性hash存在的问题
上文中3 个节点映射在哈希环相对还是比较分散的，因此看起来请求都会「均衡」到每个节点，但是实际情况是一致性hash并不能保证节点能够在哈希环上均匀分布，这样就会带来一个问题，会有大量的请求集中在一个节点上。
这时候有一半以上的数据的寻址都会找到DB1，说好的负载均衡呢，这种情况一点都不均衡！
另外，在这种分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。
例如，上图中如果DB1被移除了，当DB1宕机后，根据一致性哈希算法的规则，其上数据应该全部迁移到相邻的DB2 上，这样DB2数据量和访问量都会迅速增加很多倍，一旦新增的压力超过了DB2 的处理能力上限，就会导致DB2 崩溃，以此类推就会形成雪崩式的连锁反应。
所以，一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题。
通过虚拟节点提高均衡度
要想解决节点能在哈希环上分配不均匀的问题，就是要有更多的节点，节点数越多，哈希环上的分布节点就越均匀。
但实际中我们没有那么多节点。所以这个时候就需要加入虚拟节点，也就是对一个真实节点做映射节点。
具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到真实节点，所以这里有「两层」映射关系。
比如对每个节点分别设置 3 个虚拟节点：
- 对DB1 加上编号来作为虚拟节点：DB1-1、DB1-2、DB1-3
- 对DB2 加上编号来作为虚拟节点：DB2-1、DB2-2、DB2-3
- 对DB3 加上编号来作为虚拟节点：DB3-1、DB3-2、DB3-3
引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。
你可以看到，节点数量多了后，节点在哈希环上的分布就相对均匀了。这时候，如果有访问请求寻址到「DB1-1」这个虚拟节点，接着再通过「DB1-1」虚拟节点找到真实节点 DB1，这样请求就能访问到真实节点 DB1 了。
上面为了方便理解，每个真实节点仅包含 3 个虚拟节点，这样能起到的均衡效果其实很有限。而在实际的工程中，虚拟节点的数量会大很多。
虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。
比如，当某个节点被移除时，对应该节点的多个虚拟节点均会移除，而这些虚拟节点按顺时针方向的下一个虚拟节点，可能会对应不同的真实节点，即这些不同的真实节点共同分担了节点变化导致的压力。
而且有了虚拟节点后，还可以为硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点即可。
因此，带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。
一致性哈希算法实现
以下代码摘自mycat的一致性hash代码，并进行部分修改。
这里设置虚拟节点为16个，计算1千万数据的分布情况，hash类引用的guava包中的HashFunction，如果要测试，需要引入guava包
public class PartitionByMurmurHash {
private static final int DEFAULT_VIRTUAL_BUCKET_TIMES = 16;
private static final int DEFAULT_WEIGHT = 1;
private int seed;
private int count;
private int virtualBucketTimes = DEFAULT_VIRTUAL_BUCKET_TIMES;
private Map<Integer, Integer> weightMap = new HashMap<>();
private HashFunction hash;
private SortedMap<Integer, Integer> bucketMap;
public void init() {
try {
bucketMap = new TreeMap<>();
generateBucketMap();
} catch (Exception e) {
throw new MurmurHashException(e);
}
}
private void generateBucketMap() {
hash = Hashing.murmur3_32(seed);//计算一致性哈希的对象
for (int i = 0; i < count; i++) {//构造一致性哈希环，用TreeMap表示
StringBuilder hashName = new StringBuilder("SHARD-").append(i);
for (int n = 0, shard = virtualBucketTimes * getWeight(i); n < shard; n++) {
bucketMap.put(hash.hashUnencodedChars(hashName.append("-NODE-").append(n)).asInt(), i);
}
}
weightMap = null;
}
/**
* 得到桶的权重，桶就是实际存储数据的DB实例
* 从0开始的桶编号为key，权重为值，权重默认为1。
* 键值必须都是整数
*
* @param bucket
* @return
*/
private int getWeight(int bucket) {
Integer w = weightMap.get(bucket);
if (w == null) {
w = DEFAULT_WEIGHT;
}
return w;
}
/**
* 虚拟节点倍数，virtualBucketTimes*count就是虚拟结点数量
*
* @param virtualBucketTimes
*/
public void setVirtualBucketTimes(int virtualBucketTimes) {
this.virtualBucketTimes = virtualBucketTimes;
}
/**
* 计算hash值
*
* @param columnValue
* @return
*/
public Integer calculate(String columnValue) {
//返回大于等于这个hash值得key
SortedMap<Integer, Integer> tail = bucketMap.tailMap(hash.hashUnencodedChars(columnValue).asInt());
if (tail.isEmpty()) {
return bucketMap.get(bucketMap.firstKey());
}
return tail.get(tail.firstKey());
}
private static void hashTest(Integer virtualBucketTimes, int count) throws IOException {
PartitionByMurmurHash hash = new PartitionByMurmurHash();
hash.count = count;//分片数
hash.setVirtualBucketTimes(virtualBucketTimes);
hash.init();
int[] bucket = new int[hash.count];
Map<Integer, List<Integer>> hashed = new HashMap<>();
int total = 1000_0000;//数据量
int c = 0;
for (int i = 100_0000; i < total + 100_0000; i++) {//假设分片键从100万开始
c++;
//计算hash值
int h = hash.calculate(Integer.toString(i));
//更新对应节点的数据量
bucket[h]++;
//记录每个节点的数据值
List<Integer> list = hashed.get(h);
if (list == null) {
list = new ArrayList<>();
hashed.put(h, list);
}
list.add(i);
}
//总数量占比
double d = 0;
//数据总数
c = 0;
//节点索引
int idx = 0;
System.out.println("节点 数据量 占比");
for (int i : bucket) {
//计算每个节点的数据量占比
double ratio = i / (double) total;
//计算总比例，所有节点数量加起来，最终应该等于1
d += ratio;
//累加数据量，后面打印出来应该与总数量相等
c += i;
//打印每个节点的数据量和数据占比
System.out.println((idx++) + " " + i + " " + ratio);
}
Properties props = new Properties();
//获取虚拟节点key和实际对应的节点
for (Map.Entry entry : hash.bucketMap.entrySet()) {
props.setProperty(entry.getKey().toString(), entry.getValue().toString());
}
ByteArrayOutputStream out = new ByteArrayOutputStream();
props.store(out, null);
props.clear();
props.load(new ByteArrayInputStream(out.toByteArray()));
System.out.println("*************虚拟节点与物理节点映射关系***************");
//打印映射关系
System.out.println(props);
}
public static void main(String[] args) throws IOException {
}
}
数据分布测试
修改main方法为以下代码
public static void main(String[] args) throws IOException {
System.out.println("******************设虚拟节点数16,物理节点为2测试******************");
hashTest(16, 2);
System.out.println("\n\n");
System.out.println("******************虚拟节点数为0，物理节点为2测试******************");
hashTest(1, 2);
}
以上代码运行完会打印以下信息，有虚拟节点的和没有虚拟节点的数据分布情况以及物理节点与虚拟节点的映射关系，可以看到没有虚拟节点数据分布很不均衡
******************设虚拟节点数16测试******************
节点 数据量 占比
0 5002425 0.5002425
1 4997575 0.4997575
*************虚拟节点与物理节点映射关系***************
{200332588=1, 1296449864=0, 2057762094=1, 1572653839=1, 999922443=0, -645649416=1, -1807095086=0, -1388869216=0, 1542099937=0, 2069669860=0, 276793709=1, 1061899120=1, 1024545989=1, -915504677=1, 722846884=0, -1316369830=1, -1711177021=0, 450739710=1, 1447771381=1, -1576564361=1, -459771630=0, -713347722=0, -880637439=1, -167820385=1, -1598857122=0, 1102813202=0, -1497574221=0, -788019661=1, 1756943855=0, -1533394541=0, 1918189761=1, 1538310795=0}
******************虚拟节点数为0测试******************
节点 数据量 占比
0 8066217 0.8066217
1 1933783 0.1933783
*************虚拟节点与物理节点映射关系***************
{-880637439=1, -1711177021=0}
数据迁移测试
修改main方法为以下代码，测试节点数由2修改3节点时需要迁移得数据量，正常结果应为总节点数由2节点变成3节点时，只有1个节点数据需要迁移
public static void main(String[] args) throws IOException {
System.out.println("***********************数据迁移测试******************");
System.out.println("物理节点为2，数据分布情况");
hashTest(1, 2);
System.out.println("\n\n");
System.out.println("物理节点为3，数据分布情况");
hashTest(1, 3);
}
执行完以上代码，可以看到只迁移到编号为0节点数据，编号为1的节点数据不需要迁移
***********************数据迁移测试******************
物理节点为2，数据分布情况
节点 数据量 占比
0 8066217 0.8066217
1 1933783 0.1933783
*************虚拟节点与物理节点映射关系***************
{-880637439=1, -1711177021=0}
物理节点为3，数据分布情况
节点 数据量 占比
0 6094467 0.6094467
1 1933783 0.1933783
2 1971750 0.197175
*************虚拟节点与物理节点映射关系***************
{-880637439=1, -1711177021=0, -33802706=2}
总结
一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上，增加或者移除一个节点，只影响该节点在哈希环上顺时针相邻的后继节点，其它数据不会受到影响。
一致性哈希算法不能够均匀的分布节点，会出现大量请求都集中在一个节点的情况，在这种情况下进行容灾与扩容时，容易出现雪崩的连锁反应。
为了解决一致性哈希算法不能够均匀的分布节点的问题，就需要引入虚拟节点，对一个真实节点做多个映射节点。不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到真实节点，所以这里有两层映射关系。
引入虚拟节点后，可以会提高节点的均衡度，还会提高系统的稳定性。所以，带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景