一致性hash算法（hash环）-吉桂权的个人主

一、引言

近期做的项目中正好用到了hash环实现了负载均衡：

使用hash环实现的负载均衡不同于nginx等实现的负载均衡，nginx负载均衡有轮训算法，同样的一个客户端，在多次请求时，每次访问的服务器节点可能都不一样，但是对于有些场景来说，肯定是不行的；

最经典的就是memcached，redis这类分布式kv缓存（当然我说的不是简单的一主两从三哨兵这样的简单部署），是真的会分布在不同的节点上的那种；

我们项目中是工业互联网项目，有设备连接，连接session维护，这些相当于每个节点都是有状态的，我设备明明连接在这台节点上，我们得很多信息也得在这个节点处理的，最优的方案肯定是我一下子就能定位到固定机器，而且每次请求到达，都能到同一个节点上去处理；

这里，我们就使用了一致性hash算法（hash环），找到对应的服务地址，然后使用 grpc 定向调用；

二、什么是一致性hash（hash环）——以经典的分布式缓存为例

1、首先，我们了解一下什么是“普通hash”？

普通hash：一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值；

这样举例就很好理解了：

把[1、3、7、8、14、16]变换到固定长度5的输出，那么就是我们使用mod取模算法，得到的输出结果就是：[1、3、2、3、4、1]；

这就是最简单的hash算法，而其中1和3都出现了2次，这种就是“hash碰撞”；

Hash表（散列表）：根据散列函数和冲突处理将一组关键字分配在连续的地址空间内，并以散列值记录在表中的存储位置，这种表成为散列表。

2、使用普通hash在分布式系统缓存数据？

hash算法被普遍用在很多地方，但是普通hash用在分布式环境中会有一些问题，假设有5个cache主机：cacheA、cacheB、cacheC、cacheD、cacheE

当程序进行hash时，首先每个节点要根据自己的唯一参数哈希出一个值来（如根据ip进行哈希）

主机哈希完成后形成的哈希值如下（使用最简单的hash公式：ip/N，N为机器总数）

cacheA 0
cacheB 1
cacheC 2
cacheD 3
cacheE 4

现在我们有了需要缓存的数据（key，value），我们为了让这组数据肯定落在这5台机器上，我们对key进行hash运算（hash(key)/N）,这里只能是N，多了可能会落不到这5台机器上；少了就有机器一直没有数据；

现在问题来了，如果其中一台机器down掉了，我们hash运算公式还是(hash(key)/N)，这时候所有的数据算出来都会跟之前不一样，后果是什么？到对应的机器上找缓存时，找不到了，缓存全部失效！！！

这就是为什么说：普通hash用在分布式环境中会存在问题！

3、什么是一致性hash？

假定有一个hash函数，其值空间为(0 ~ 2^32-1)。也就是说，其hash值是个32位无整型数字，这些数字组成一个环（完整的hash空间被构成了收尾相连的环，所有的hash运算最终肯定会落在这个环上，这就是hash环）。

使用hash环，需要涉及到2次hash运算：

（1）把所有机器编号hash到这个环上——对机器进行hash(比如根据机器的ip)，算出每台机器在这个环上的位置；

（2）把key也hash到这个环上——再对key进行hash，算出该key在环上的位置

然后从这个位置往前走（顺时针跑），遇到的第一台机器就是该key对应的机器，就把该(key, value) 存储到该机器上。

最终效果为：

下次，取的时候，也根据相同的方法，找到对应的节点，自然就找到了正确的机器；

这时候，我们再考虑当某台机器down机后，比如Cache服务器2宕机了，那么先前的Cache1和Cache2之间key值全部会由Cache3承担缓存业务；

同样，增加一台机器，只需要将影响范围内的key值hash任务分摊到新的机器上；

无论如何，受影响得也只是少部分数据，且如果涉及数据迁移，也只需要迁移一部分；

三、数据倾斜及解决方案——虚拟节点

1、什么是数据倾斜问题？

就想上面描述的，当增加或者减少某个节点时，受影响得只会是一个节点，这样的话，hash环上的Cache机器对应的节点肯定会变得不再均匀，对应的结果就是有些机器负荷很大，有些机器负荷很小，这就产生了“数据倾斜”问题；

2、解决思路：

我们假设，现在我们不是只有5台Cache服务器，而是1000台Cache服务器，当这1000台服务器随机散列在这个hash环上时，如果此时随机down掉20%的机器，hash环的倾斜问题还像刚刚5台时候那么严重吗？

大难肯定是No，所以当我们得基数越大时，抵抗“数据倾斜”的能力就越强；

3、解决方案：

我们不可能真的搞1000台Cache服务器，我们只有5台，那怎么办，我们可以用这5台虚拟出1000台机器出来呀（正式机器和虚拟机器之间存在一定的映射关系，可以找到）；然后这1000台虚拟的机器就对应着hash环上的1000个虚拟节点；

此时，再有（key, value）需要缓存到机器的时候，使用hash(key)计算hash，然后找到顺时针第一个“虚拟节点”，再由“虚拟节点”找到“真实节点”，就是真正要处理的机器，这样就解决了“数据倾斜”的问题！

四、代码测试准备——寻找合适的hash算法

1、首先，我们需要寻找一个“能够对输入进行均匀散列的hash算法”，正巧，String有一个hashCode()方法，不妨试一试：

public static void main(String[] args)
{
    System.out.println("192.168.0.0:111的哈希值：" + "192.168.0.0:1111".hashCode());
    System.out.println("192.168.0.1:111的哈希值：" + "192.168.0.1:1111".hashCode());
    System.out.println("192.168.0.2:111的哈希值：" + "192.168.0.2:1111".hashCode());
    System.out.println("192.168.0.3:111的哈希值：" + "192.168.0.3:1111".hashCode());
    System.out.println("192.168.0.4:111的哈希值：" + "192.168.0.4:1111".hashCode());
}

测试结果：

这个就问题大了，[0,232-1]的区间之中，5个HashCode值却只分布在这么小小的一个区间，什么概念？[0,232-1]中有4294967296个数字，而我们的区间只有114516604，从概率学上讲这将导致97%待路由的服务器都被路由到"192.168.0.0"这个集群点上，简直是糟糕透了！

因此，String重写的hashCode()方法在一致性Hash算法中没有任何实用价值，得找个算法重新计算HashCode。

这种重新计算均匀散列Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法，用别的Hash算法也可以，比如FNV1_32_HASH算法的计算效率就会高一些。

我们将选择“FNV1_32_HASH”hash算法！

五、代码测试虚拟节点方案“抗数据倾斜”能力

1、使用“FNV1_32_HASH”算法计算hash工具类：

public class HashUtil {
    /**
     * 计算Hash值, 使用FNV1_32_HASH算法
     * @param str
     * @return
     */
    public 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;
    }
}

2、先编写一个没有“虚拟节点”的hash环测试：

public class ConsistentHashingWithoutVirtualNode {
    /**
     * 集群地址列表
     */
    private static String[] groups = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"};
    /**
     * 用于保存Hash环上的节点
     */
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();

    /**
     * 初始化，将所有的服务器加入Hash环中
     */
    static {
        // 使用红黑树实现，插入效率比较差，但是查找效率极高
        for (String group : groups) {
            int hash = HashUtil.getHash(group);
            System.out.println("[" + group + "] launched @ " + hash);
            sortedMap.put(hash, group);
        }
    }

    /**
     * 计算对应的widget加载在哪个group上
     *
     * @param widgetKey
     * @return
     */
    private static String getServer(String widgetKey) {
        int hash = HashUtil.getHash(widgetKey);
        // 只取出所有大于该hash值的部分而不必遍历整个Tree
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，应该映射到第一个group上
            return sortedMap.get(sortedMap.firstKey());
        }
        return subMap.get(subMap.firstKey());
    }

    public static void main(String[] args) {
        // 生成随机数进行测试
        Map<String, Integer> resMap = new HashMap<>();
        for (int i = 0; i < 100000; i++) {
            Integer widgetId = (int) (Math.random() * 10000);
            String server = getServer(widgetId.toString());
            if (resMap.containsKey(server)) {
                resMap.put(server, resMap.get(server) + 1);
            } else {
                resMap.put(server, 1);
            }
        }
        resMap.forEach((k, v) -> {
            System.out.println("group " + k + ": " + v + "(" + v / 1000.0D + "%)");
        });
    }
}

测试结果：

显然，压力分布得根本不均匀，数据倾斜严重；

3、再编写一个使用“虚拟节点”的hash环测试：

public class ConsistentHashingWithVirtualNode {
    /**
     * 集群地址列表
     */
    private static String[] groups = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"};
    /**
     * 真实集群列表
     */
    private static List<String> realGroups = new LinkedList<>();
    /**
     * 虚拟节点映射关系
     */
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
    private static final int VIRTUAL_NODE_NUM = 1000;

    static {
        // 先添加真实节点列表
        realGroups.addAll(Arrays.asList(groups));
        // 将虚拟节点映射到Hash环上
        for (String realGroup : realGroups) {
            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
                String virtualNodeName = getVirtualNodeName(realGroup, i);
                int hash = HashUtil.getHash(virtualNodeName);
                System.out.println("[" + virtualNodeName + "] launched @ " + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
    }

    private static String getVirtualNodeName(String realName, int num) {
        return realName + "&&VN" + String.valueOf(num);
    }

    private static String getRealNodeName(String virtualName) {
        return virtualName.split("&&")[0];
    }

    private static String getServer(String widgetKey) {
        int hash = HashUtil.getHash(widgetKey);
        // 只取出所有大于该hash值的部分而不必遍历整个Tree
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNodeName;
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，应该映射到第一个group上
            virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
        } else {
            virtualNodeName = subMap.get(subMap.firstKey());
        }
        return getRealNodeName(virtualNodeName);
    }

    public static void main(String[] args) {
        // 生成随机数进行测试
        Map<String, Integer> resMap = new HashMap<>();
        for (int i = 0; i < 100000; i++) {
            Integer widgetId = i;
            String group = getServer(widgetId.toString());
            if (resMap.containsKey(group)) {
                resMap.put(group, resMap.get(group) + 1);
            } else {
                resMap.put(group, 1);
            }
        }
        resMap.forEach((k, v) -> {
            System.out.println("group " + k + ": " + v + "(" + v / 1000.0D + "%)");
        });
    }
}

再看看测试结果：

很明显，这次的测试结果很理想，分布基本趋于均匀，达到了负载均衡的目的！

六、ZooKeeper的引入

上面我们提到了服务器的机器增加、减少，问题是客户端怎么知道呢？

一种笨办法就是手动的，当服务器机器增加、减少时候，重新配置客户端，重启客户端。

我们项目采用的方案是，引入了Zookeeper，服务器的节点列表注册到Zookeeper上面，使用客户端专门监听Zookeeper。当发现有新的Server实例加入时，会将实例作为参数，调用服务中的onServerAdded(ServerInstance server)方法，此方法将会为此server添加virtualNodesSize数量的虚拟节点到hash环上（我们项目为每个真实节点配置16个虚拟节点）；

减少操作操作类似；

当然，不用Zookeeper，采用其他的分布式协调方案也可以，只要能实现服务注册发现通知机制即可。