聊聊一致性 hash 算法

4,490 阅读8分钟

最近在优化部门分布式调度任务,在读 XXL-JOB 源码时,发现它的负载均衡逻辑中用到了一致性 hash 算法。其实在分布式缓存集群中也用到了一致性 hash 算法,(如:redis集群)是为了提高缓存的容错性和可扩展性。至于 XXL-JOB 的源码就不多说了,在这里只针对一致性 hash 算法分析一波,以备知识巩固,另外也分享给小伙伴们一起成长。

hash 算法和一致性 hash 算法

说到一致性 hash 算法,不得不先聊一下 hash 算法,这个大家经常听到的名词,有多少同学真正了解其准确定义呢?

Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射 pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

说的简单点,hash 就是把输入值“压缩”并转成更小的值,这个值通常状况下是唯一、格式极其紧凑的。那么现在业务系统多数是微服务架构,在天然的分布式特性下,hash 算法就不太适合了。

比如,在分布式的存储系统中,要将数据存储到具体的节点上,如果我们采用普通的 hash 算法进行路由,将数据映射到具体的节点上,如 key%N,key 是数据的 key,N 是机器节点数,有一个机器加入或退出这个集群,则所有的数据映射都无效了。如果是持久化存储则要做数据迁移,使用的是分布式缓存,则其他缓存就失效了。造成大量的数据重新 hash,影响业务系统的正常运行。

这时候我们就没办法了吗?当然有办法:一致性 hash 算法

一致性 hash 算法

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

一致性 hash 算法有一下几大特点:

均衡性(Balance)

均衡性是指哈希的结果能够尽可能分布到所有的缓冲节点中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

单调性是指当缓冲区大小变化时一致性哈希(Consistent hashing)尽量保护已分配的内容不会被重新映射到新缓存区,来减少大量的重新hash提高性能。

分散性(Spread)

在分布式环境中,终端有可能看不到所有的缓存,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓存上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓存中去,降低了系统存储的效率。

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓存实例中,那么对于一个特定的缓存实例而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

应用场景

我们从一个具体场景来看:redis 是如何使用一致性 hash 算法保证缓存命中率、容错性和可扩展性的。

  • 首先求出 redis 服务器(节点)的哈希值,并将其配置到 0 ~ 2的32次方 的圆(continuum)上。

  • 然后采用同样的方法求出存储数据的键的哈希值,并映射到相同的圆上。

  • 然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。如果超过 2的32次方 仍然找不到服务器,就会保存到第一台 redis 服务器上。

(此图为百度百科盗图。。) 从上图的状态中添加一台 redis 服务器。采用余数分布式算法,会由于保存键的缓存实例发生变化而影响缓存的命中率。但一致性hash算法中,只有在增加节点(node5)的逆时针的一小部分hash会受到影响,如下图所示:

这种方式很好的解决了缓存命中率、容错性和可扩展性,但是当服务节点很少的时候,这时候会带来另外一个问题,就是“数据倾斜”,也就是很多 key 被分配到同一个服务实例上。这样的隐患也非常大,如果正好 key 很多的节点挂掉,对系统的使用也会造成很大影响。如何解决呢?虚拟节点

例如我们的系统中有两台服务器,其环分布如下:

此时必然造成大量数据集中到 Redis2 上,而只有极少量会定位到 Redis1 上。为了解决这种数据倾斜问题,一致性 hash 算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器 ip 或主机名的后面增加编号来实现。例如上面的情况,我们决定为每台服务器计算 2 个虚拟节点,于是可以分别计算“Redis2 #1”、“Redis2 #2”、“Redis1 #1”、“Redis1 #2”的哈希值,于是形成 4 个虚拟节点:

同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Redis2#1”、“Redis2#2” 两个虚拟节点的数据均定位到 Redis2 上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为 32 甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

上代码

输了这么多,还是要实践一下,否则只是纸上谈兵,实践出真知。搞起!

package com.demo.hash;

import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 一致性hash算法demo
 *
 * @author dongx on 2020/9/18
 */
public class ConsistentHashDemo {

    /**
     * 待添加入Hash环的服务器列表
     */
    private static String[] servers = {"10.0.0.1", "10.0.0.2", "10.0.0.3"};

    /**
     * key表示服务器的hash值,value表示服务器
     */
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();


    /**
     * 程序初始化,将所有的服务器放入sortedMap中
     */
    static {
        for (int i=0; i<servers.length; i++) {
            int hash = getHash(servers[i]);
            System.out.println("[" + servers[i] + "]加入map中, 其Hash值为" + hash);
            sortedMap.put(hash, servers[i]);
        }
    }

    /**
     * 得到路由到的节点
     * @param key
     * @return
     */
    private static String getServer(String key) {
        //得到该key的hash值
        int hash = getHash(key);
        //得到大于该Hash值的所有Map,这里用有排序功能的sortedMap,有很多api很方便
        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);
        }
    }

    /**
     * 使用FNV1_32_HASH算法计算Hash值(网上找的标准算法)
     * @param str
     * @return
     */
    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;
    }

    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]) + "]");
        }

    }
}

这段代码我注释写的比较清晰了,下伙伴可以结合之前的内容消化一下。其中FNV1_32_HASH是从网上找的一段标准算法方法。

运行结果如下:

结束

一致性 hash 算法在分布式场景下使用非常广泛,就像任务调度、缓存都使用了它。对于广大程序员来说,了解这一算法对问题排查、分析都很有帮助。另外对于面试人员来讲,hash 和一致性 hash 也是面试官通常会问到的。对于 java 开发来讲,这也是走向中高级路上的必修课。希望大家多了解,后续也会跟大家继续分享内容。