【修真院Java小课堂】什么叫一致性哈希，通常用来解决什么问题？

大家好，我是IT修真院北京分院第35期的学员赵君钊，一枚正直纯洁善良的Java程序员，今天给大家分享一下，修真院官网Java（职业）任务六，深度思考中的知识点——什么叫一致性哈希，通常用来解决什么问题？

1. 背景介绍

在了解一致性哈希算法之前，先了解一下一致性哈希算法的应用场景，在做缓存集群时，为了缓解服务器的压力，会部署多台缓存服务器，把数据资源均匀的分配到每个服务器上，分布式数据库首先要解决把整个数据集按照分区规则映射到多个节点的问题，即把数据集划分到多个节点上，每个节点负责整体数据的一个子集。

数据分布通常有哈希分区和顺序分区两种方式

顺序分布：数据分散度易倾斜、键值业务相关、可顺序访问、不支持批量操作

哈希分布：数据分散度高、键值分布业务无关、无法顺序访问、支持批量操作     

2. 知识剖析

节点取余分区

普通哈希算法，使用特定的数据，如Redis的键或用户ID，再根据节点数量N使用公式：hash（key）% N 计算出哈希值，用来决定数据映射到哪一个节点上。

优点

这种方式的突出优点是简单性，常用于数据库的分库分表规则。一般采用预分区的方式，提前根据数据量规划好分区数

缺点 

当节点数量变化时，如扩容或收缩节点，数据节点映射关系需要重新计算，会导致数据的重新迁移。所以扩容时通常采用翻倍扩容，避免 数据映射全部被打乱，导致全量迁移的情况，这样只会发生50%的数据迁移。

一致性哈希分区

一致性哈希的目的就是为了在节点数目发生改变时尽可能少的迁移数据，将所有的存储节点排列在收尾相接的Hash环上，每个key在计算Hash 后会顺时针找到临接的存储节点存放。而当有节点加入或退 时，仅影响该节点在Hash环上顺时针相邻的后续节点。

优点

加入和删除节点只影响哈希环中顺时针方向的相邻的节点，对其他节点无影响。

缺点 

数据的分布和节点的位置有关，因为这些节点不是均匀的分布在哈希环上的，所以数据在进行存储时达不到均匀分布的效果。

虚拟槽分区

本质上还是第一种的普通哈希算法，把全部数据离散到指定数量的哈希槽中，把这些哈希槽按照节点数量进行了分区。这样因为哈希槽的数量的固定的，添加节点也不用把数据迁移到新的哈希槽，只要在节点之间互相迁移就可以了，即保证了数据分布的均匀性，又保证了在添加节点的时候不必迁移过多的数据。

Redis的集群模式使用的就是虚拟槽分区，一共有16383个槽位平均分布到节点上

3.常见问题

4.解决方案

5.编码实战

普通哈希算法

public void hashTest() {
    int[] node = new int[100];
    for(Integer i = 0;i < NUM;i++){
        Integer h = MD5Util.encrypt(i.toString(),"").hashCode();
        int index = Math.abs(h) % 100;
        node[index]++;
    }
    int max = node[0];
    int min = node[0];
    for(int i : node){
        if (max < i){
            max = i;
        }
        if (min > i){
            min = i;
        }
    }
    Arrays.stream(node).forEach(logger::info);
    System.out.println("max :" + max);
    System.out.println("min :" + min);
}

节点变化时数据进行迁移

public void hashDiff() {
    int diff = 0;
    for(Integer i = 0;i < NUM;i++){
        Integer h = MD5Util.encrypt(i.toString(),"").hashCode();
        int index = Math.abs(h) % 100;
        int new_index = Math.abs(h) % 101;
        if(new_index != index){
            diff++;
        }
    }
    System.out.println("diff : " + diff);
}

一致性哈希算法

public void consistentHash() {
    int[] node = new int[100];
    int[] nodeHash = new int[100];
    for(int i = 0; i < 100; i++) {
        int h = MD5Util.encrypt(Integer.toString(i), "").hashCode();
        nodeHash[i] = Math.abs(h);
    }
    qSort(nodeHash, 0, nodeHash.length - 1);
    for(int i = 0; i < NUM; i++){
        int flag = 0;
        int h = Math.abs(MD5Util.encrypt(Integer.toString(i), "").hashCode());
        for (int j = 0; j < nodeHash.length; j++){
            if(h <= nodeHash[j]){
                node[j]++;
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            node[0]++;
        }
    }
    Arrays.stream(node).forEach(logger::info);
    System.out.println("max :" + max);
    System.out.println("min :" + min);
}

虚拟槽分区

public void clusterHash() {
    int[] node = new int[100];
    int[] nodeSlot = new int[100];
    for (int i = 0; i < 100; i++){
        // nodeSlot存储节点负责的哈希槽范围
        nodeSlot[i] = cluster / node.length * (i + 1);
    }
    for(int i = 0; i < NUM; i++){
        int h = MD5Util.encrypt(Integer.toString(i), "").hashCode();
        int index = Math.abs(h) % cluster;
        for(int j = 0; j < nodeSlot.length; j++){
            if(index <= nodeSlot[j]){
                node[j]++;
                break;
            }
        }
    }
    Arrays.stream(node).forEach(logger::info);
    System.out.println("max :" + max);
    System.out.println("min :" + min);
}

6.扩展思考

7.参考文献

参考资料：https://juejin.im/post/5b8fc5536fb9a05d2d01fb11

————深入剖析Redis系列(三) - Redis集群模式搭建与原理详解

8.更多讨论

一致性哈希算法会有哈希冲突吗？

不冲突的哈希算法是不存在的，但是只要虚拟节点够多，保证在概率上每个真实节点的负载是相等的就好了，一致性哈希的哈希环有细虚拟的2^32个节点。

一致性哈希的哈希槽数为什么是2^32

一致性哈希一定程度上也解决了哈希冲突，只要哈希槽的范围足够大就能尽可能的减少哈希冲突，因为通常的hashCode都是将数据映射到0 ~ 2^32 数值空间内，所以设置一个2^32个节点的哈希环会尽可能的减少哈希冲突。

有没有其他解决节点变化时数据迁移的方法？

实际上一致性哈希是把可变的哈希槽固定到哈希环上，整数最大值2^32个槽位，所以一致性哈希的本质已经不是节点取模了，每个数据的位置是固定的，只要能保证节点数变化时减少key在节点之间的重映射就可以，比如说虚拟槽分区。

9.鸣谢

感谢观看,如有出错,恳请指正

10.结束语

今天的分享就到这里啦，欢迎大家点赞、转发、留言、拍砖~