图解一致性哈希算法原理+代码实现

1 传统哈希

分布式系统中，假设有 n 个节点，传统方案使用 mod(key, n) 映射数据和节点。
当扩容或缩容时(哪怕只是增减1个节点)，映射关系变为 mod(key, n+1) / mod(key, n-1)，绝大多数数据的映射关系都会失效

2 哈希指标

评估一个哈希算法的优劣，有如下指标，而一致性哈希全部满足：

• 均衡性(Balance)：将关键字的哈希地址均匀地分布在地址空间中，使地址空间得到充分利用，这是设计哈希的一个基本特性。
• 单调性(Monotonicity): 单调性是指当地址空间增大时，通过哈希函数所得到的关键字的哈希地址也能映射的新的地址空间，而不是仅限于原先的地址空间。或等地址空间减少时，也是只能映射到有效的地址空间中。简单的哈希函数往往不能满足此性质。
• 分散性(Spread): 哈希经常用在分布式环境中，终端用户通过哈希函数将自己的内容存到不同的缓冲区。此时，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。
• 负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

3 一致性哈希映射原理

一致性哈希不在对一个固定的N进行取模运算，而是对2^32 -1进行取模运算，各哈希值在上图 Hash 环上的分布：时钟12点位置为0，按顺时针方向递增，临近12点的左侧位置为2^32 -1。
上图中有四个物理节点：NodeA、NodeB、NodeC、NodeD，其ip地址分别对应：

NodeA：192.168.1.102
NodeB：192.168.1.101
NodeC：192.168.1.103
NodeD：192.168.1.104

四个节点通过Hash算法后得到的hash值为：

NodeA：10
NodeB：20
NodeC：30
NodeD：40

注：这里的hash值是一个Long类型的大数，如NodeA得到的hash值为：352446220610898519，为了简便我用很小的数字代替

此时有3个对象需要进行hash映射，映射到对应的物理节点上。三个对象通过Hash算法得到的hash值为：

ObjectA：11  因为11大于10，小于20，所以根据顺时针定位后ObjectA就映射到了NodeB上
ObjectA：28 依次类推
ObjectA：39

3.1 删除节点

如果此时NodeC挂掉，受影响的只会是在NodeC与NodeC之前的那个节点（NodeB）之间的对象，ObjectB的映射会自动寻找下一个节点（这里的自动寻找是通过SortMap实现的，可以看后面的代码实现）NodeD。其他对象不会受到影响。

增加节点的原理是一样的

3.2 虚拟节点

对于前面的方案，节点数越少，越容易出现节点在哈希环上的分布不均匀，导致各节点映射的对象数量严重不均衡(数据倾斜)，那么三个节点；相反，节点数越多越密集，数据在哈希环上的分布就越均匀。

如上图，四个物理节点的hash值分布不均匀

NodeA：10
NodeB：37
NodeC：38
NodeD：40

导致三个对象都定位在NodeC上面，这就违背了哈希指标的均衡性

解决方法就是添加更多的物理节点，但是实际的物理节点有限，所以就引入了虚拟节点。

如上图，引入了两个虚拟节点NodeA#1和NodeD#1，这样ObjectA的映射就指向了虚拟节点A#1，ObjectB的映射指向了虚拟节点D#1，这样就不会出现大量的对象映射到节点C上的情况了。

3.3 代码实现

public class ConsistentHashing {
    // 物理节点
    private Set<String> physicalNodes = new TreeSet<String>() {
        {
            add("192.168.1.101");
            add("192.168.1.102");
            add("192.168.1.103");
            add("192.168.1.104");
        }
    };

    //虚拟节点
    private final int VIRTUAL_COPIES = 1; // 物理节点至虚拟节点的复制倍数
    private TreeMap<Long, String> virtualNodes = new TreeMap<>(); // 哈希值 => 物理节点

    // 32位的 Fowler-Noll-Vo 哈希算法
    // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
    private static Long FNVHash(String key) {
        final int p = 16777619;
        Long hash = 2166136261L;
        for (int idx = 0, num = key.length(); idx < num; ++idx) {
            hash = (hash ^ key.charAt(idx)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

    // 根据物理节点，构建虚拟节点映射表
    public ConsistentHashing() {
        for (String nodeIp : physicalNodes) {
            addPhysicalNode(nodeIp);
        }
    }

    // 添加物理节点
    public void addPhysicalNode(String nodeIp) {
        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
            long hash = FNVHash(nodeIp + "#" + idx);
            virtualNodes.put(hash, nodeIp);
        }
    }

    // 删除物理节点
    public void removePhysicalNode(String nodeIp) {
        for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
            long hash = FNVHash(nodeIp + "#" + idx);
            virtualNodes.remove(hash);
        }
    }

    // 查找对象映射的节点
    public String getObjectNode(String object) {
        long hash = FNVHash(object);
        //这里是实现hash自动定位下一个节点的精髓
        SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
        Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
        return virtualNodes.get(key);
    }

    // 统计对象与节点的映射关系
    public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
        // 统计
        Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
        for (int object = objectMin; object <= objectMax; ++object) {
            String nodeIp = getObjectNode(Integer.toString(object));
            Integer count = objectNodeMap.get(nodeIp);
            objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
        }

        // 打印
        double totalCount = objectMax - objectMin + 1;
        System.out.println("======== " + label + " ========");
        for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
            long percent = (int) (100 * entry.getValue() / totalCount);
            System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
        }
    }

    public static void main(String[] args) {
        ConsistentHashing ch = new ConsistentHashing();

        // 初始情况
        ch.dumpObjectNodeMap("初始情况", 0, 65536);

        // 删除物理节点
        ch.removePhysicalNode("192.168.1.103");
        ch.dumpObjectNodeMap("删除物理节点", 0, 65536);

        // 添加物理节点
        ch.addPhysicalNode("192.168.1.108");
        ch.dumpObjectNodeMap("添加物理节点", 0, 65536);
    }

}

参考：https://blog.csdn.net/kefengwang/article/details/81628977?utm_source=app&app_version=5.2.0&utm_source=app