一致性Hash（Consistent Hash）

╰半夏微凉° 2022-06-06 02:16 227阅读 0赞

**一致性Hash算法简介**

一致性Hash算法是在1997年由麻省理工提出的一种分布式Hash实现算法，设计的目标是为了解决英特网中的热点问题。

一致性Hash算法提出了在动态变化的Cache环境中，判定Hash算法好坏的四个定义。

1.  **平衡性（Balance）**：平衡性是指哈希的结果能够尽可能的分布到所有的节点中去，这样从算法上解决负载均衡的问题。
2.  **单调性（monotonicity）**：单调性是指在新增或者删减节点时, 不影响系统正常运行。
3.  **分散性（Spread）**：分散性是指数据应该分散地存放在分布式集群中的各个节点 (节点自己可以有备份) , 不必每个节点都存储所有的数据。
4.  **负载（Load）**：负载为题其实是从另外一个角度去看分散性问题。既然不同的终端可能将相同的内容映射到不同的节点，那么对于特定的节点而言，也可能被不同的用户映射不同的内容。与分散性一样，这种情况也要尽量避免，因此好的Hash算法应尽量减低节点的负荷。

**简单的Hash算法**

哈希（hash）计算是常见的数据分布技术，其通过求模运算来计算哈希值，然后据此将数据映射到存储空间中。 设有由 N 个存储节点组成的存储空间，采用简单哈希计算将一个数据对象 object 映射到存储空间上的公式为：hash（object）%N。 由于只是采用了简单的求模运算，使得简单哈希计算存在很多不足：

1.  增删节点时，更新效率低。 当系统中存储节点数量发生增加或减少时，映射公式将发生变化为 hash(object)%(N±1)，这将使得所有 object 的映射位置发生变化，整个系统数据对象的映射位置都需要重新进行计算，系统无法对外界访问进行正常响应，将导致系统处于崩溃状态。
2.  平衡性差，未考虑节点性能差异。 由于硬件性能的提升，新添加的节点具有更好的承载能力，如何对算法进行改进，使节点性能可以得到较好利用，也是亟待解决的一个问题。
3.  单调性不足。

**一致性Hash算法原理**

一致性哈希简单地说在移除或者添加一个服务器时, 此算法能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系,尽可能满足单调性的要求。

在普通分布式集群中, 服务请求与处理请求服务器之间可以一一对应, 也就是说固定服务请求与处理服务器之间的映射关系, 某个请求由固定的服务器去处理。 这种方式无法对整个系统进行负载均衡, 可能会造成某些服务器过于繁忙以至于无法处理新来的请求。 而另一些服务器则过于空闲, 整体系统的资源利用率低, 并且当分布式集群中的某个服务器宕机, 会直接导致某些服务请求无法处理。

进一步的改进可以利用 hash 算法对服务请求与处理服务器之间的关系进行映射, 以达到动态分配的目的。 普通的Hash算法采用简单取模的方式 ，取模后的值就是服务请求对应的请求处理服务器。这在节点不变的情况下能够取得让人满意的结果，但是在节点动态变化的情况下，这种方式显然不满足单调性的需求（当增加或者减少一台机器时，所有存储的内容都会被重新散列）。

一个设计良好的分布式系统应该具有良好的单调性,即服务器的添加与移除不会造成大量的哈希重定位, 而一致性哈希恰好可以解决这个问题。

一致性Hash算法的基本实现原理是将机器节点和key值都按照相同的hash算法映射到一个0-2^32的圆环上。当一个写入请求到来时，计算Key值k对应的Hash(k)，如果该值正好对应之前某个机器节点的Hash值，则直接将数据写入该机器，如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过2^32还没找到对应节点，则从0开始查找。

![这里写图片描述][SouthEast]

当Hash环上机器数量比较少时，可能会出现环上机器分部不均匀，导致某些机器需要处理很多数据，而有些机器只能处理很少数据的情况。所以在机器映射时，可以根据机器的处理能力，将一个实体节点映射为多个虚拟节点。

“虚拟节点”（ virtual node ）是实际节点（机器）在 hash 空间的复制品（ replica ），一个实际节点（机器）对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。

经过一致性Hash算法的散列之后，当有新的机器加入时，将只影响一台机器的存储情况。例如新加节点H到A和B之间，则原先由B处理的数据可能将移至H处理，而其他所有节点的处理情况都将保持不变，因此表现出很好的单调性。

如果删除一台机器，例如删除C节点，原先由C处理的数据都将转移到D节点，而其他节点的处理情况仍然没变。而由于在机器节点散列和缓存数据散列都采用了相同的散列算法，因此很好的降低了分散性和负载。

通过引入虚拟节点，也大大提高了平衡性。

**无虚拟节点一致性Hash Java实现**

/** * @Comment 无虚拟节点一致性Hash实现 * @Author Ron * @Date 2017年10月27日 上午11:42:09 * @return */
    public class ConsistentHashNoVirtualNode { 
        // 待添加入Hash环的服务器列表
        private static String[] servers = { "192.168.1.0:111", "192.168.1.1:111", "192.168.1.2:111", "192.168.1.3:111",
                "192.168.1.4:111" };
    
        // key表示服务器的hash值，value表示服务器
        private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
    
        // 程序初始化，将所有的服务器放入sortedMap中
        static {
            for (int i = 0; i < servers.length; i++) {
                int hash = getHash(servers[i]);
                System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
                sortedMap.put(hash, servers[i]);
            }
            System.out.println();
        }
    
        // 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
        private static int getHash(String str) {
            final int p = 16777619;// 32位prime
            int hash = (int) 2166136261L;// 32位offset basis
            for (int i = 0; i < str.length(); i++)
                hash = (hash ^ str.charAt(i)) * 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;
        }
    
        // 得到应当路由到的结点
        private static String getServer(String key) {
            // 得到该key的hash值
            int hash = getHash(key);
            // 得到大于该Hash值的所有Map
            SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
            if (subMap.isEmpty()) {
                // 如果没有比该key的hash值大的，则从第一个node开始
                Integer i = sortedMap.firstKey();
                // 返回对应的服务器
                return sortedMap.get(i);
            } else {
                // 第一个Key就是顺时针过去离node最近的那个结点
                Integer i = subMap.firstKey();
                // 返回对应的服务器
                return subMap.get(i);
            }
        }
    
        public static void main(String[] args) {
            String[] keys = {
       "太阳", "月亮", "星星","白云","蓝天"};  
            for(int i=0; i<keys.length; i++)  
                System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i])  
                        + ", 被路由到结点[" + getServer(keys[i]) + "]");  
        }
    }

**有虚拟节点一致性Hash Java实现**

/** * @Comment 有虚拟节点一致性Hash实现 * @Author Ron * @Date 2017年10月27日 上午11:42:51 * @return */
    public class ConsistentHashHasVirtualNode { 
        // 待添加入Hash环的服务器列表
        private static String[] servers = { "192.168.1.0:111", "192.168.1.1:111", "192.168.1.2:111", "192.168.1.3:111",
                "192.168.1.4:111" };
    
        // 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
        private static List<String> realNodes = new LinkedList<String>();
    
        // 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
        private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
    
        // 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
        private static final int VIRTUAL_NODES = 5;
    
        static {
            // 先把原始的服务器添加到真实结点列表中
            for (int i = 0; i < servers.length; i++)
                realNodes.add(servers[i]);
    
            // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
            for (String str : realNodes) {
                for (int i = 0; i < VIRTUAL_NODES; i++) {
                    String virtualNodeName = str + "&&VN" + String.valueOf(i);
                    int hash = getHash(virtualNodeName);
                    System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                    virtualNodes.put(hash, virtualNodeName);
                }
            }
            System.out.println();
        }
    
        // 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
        private static int getHash(String str) {
            final int p = 16777619;
            int hash = (int) 2166136261L;
            for (int i = 0; i < str.length(); i++)
                hash = (hash ^ str.charAt(i)) * 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;
        }
    
        // 得到应当路由到的结点
        private static String getServer(String key) {
            // 得到该key的hash值
            int hash = getHash(key);
            // 得到大于该Hash值的所有Map
            SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
            String virtualNode;
            if (subMap.isEmpty()) {
                // 如果没有比该key的hash值大的，则从第一个node开始
                Integer i = virtualNodes.firstKey();
                // 返回对应的服务器
                virtualNode = virtualNodes.get(i);
            } else {
                // 第一个Key就是顺时针过去离node最近的那个结点
                Integer i = subMap.firstKey();
                // 返回对应的服务器
                virtualNode = subMap.get(i);
            }
            // virtualNode虚拟节点名称要截取一下
            if (virtualNode != null && virtualNode != "") {
                return virtualNode.substring(0, virtualNode.indexOf("&&"));
            }
            return null;
        }
    
        public static void main(String[] args) {
            String[] keys = {
       "太阳", "月亮", "星星","白云","蓝天"};  
            for (int i = 0; i < keys.length; i++)
                System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[i]) + "]");
        }
    }

[SouthEast]: /images/20220606/ef35fba7a6604b6d9c73bf45d65d8ae1.png