分布式应用解决方案之一致性Hash

Myth丶恋晨 2024-03-29 16:08 45阅读 0赞

**什么是一致性Hash**  
一致性Hash就是将整个hash值空间按照顺时针方向形成一个虚拟的环，整个环状结构就称之为Hash环。那为什么叫做一致性Hash环？一致性是由于Hash环应用场景一般在分布式应用服务中，各个服务提供者分布在hash环中，当某一个服务出现问题的时候，我们还是能够保证绝大多数服务保持正常使用，对于绝大多数数据前后是一致的。

**hash函数 VS 一致性hash**  
我们以分布式应用服务负载均衡来提供分析场景  
1、hash函数路由到服务器，需要根据服务提供者数量取模，比如 hash(ip) % serverNum。如果服务数量变动，会导致绝大多数服务路由异常。  
2、一致性hash，我们均匀的将服务提供者ip分布在环上，当我们获取服务ip时候会根据hash值找到第一个大于当前hash的节点即为路由ip。如果服务数量变动，也只会影响部分少量的数据，大部分数据还是正确的路由地址。  
综上所述，一致性hash函数在分布式数据缓存的应用场景下完全碾压普通hash函数。

**一致性hash原理**  
我们以分布式应用服务负载均衡来提供分析场景  
1、由于int的存储位数为32位，那么可以保存2^32个数。我们的一致性hash通过固定的hash算法的结果用int保存，那么hash环的取值范围则为 0~2^32 -1。  
2、一致性hash首先会将服务器ip通过hash运算后放置在虚拟环上  
比如我们三个服务ip1~3 【10.10.10.202,10.10.10.203,10.10.10.204】  
![在这里插入图片描述][4296d0ccb75f4ce3bc419708aefc4ad4.png]

3、我们在实际业务中可以通过用户ID等其他信息计算出hash值，然后找到hash环上大于当前值的第一个节点，该节点则为目标路由节点。  
比如:user1\\user3的hash值小于ip1的hash，那么ip1节点就这两个用户的实际路由节点  
![在这里插入图片描述][f4f679eebce6434e9e3443952913316d.png]

4、当前的hash环上的ip节点都是实际节点，如果全部为实节点会有一个问题，就是如果某个服务掉线会将掉线服务请求全部打在后续节点，就会造成路由不均衡，严重情况会导致后续服务雪崩。那么，如果解决这个问题呢？我们可以采用虚节点，就是在各个实际节点处分散为多个虚拟节点，各个hash路由也都映射在虚节点上，这样就能够做大限度保证数据的均衡性。  
比如：ip2服务宕机，本来该路由到ip2的请求全部会打在ip3  
![在这里插入图片描述][4bee02d2ee4748f5ada43e79096afbb7.png]

我们象征性添加9个虚拟节点，每个ip增加三个虚节点，每个虚节点都均匀的分散在环上  
![在这里插入图片描述][76d0f5696eb34a8fac0afc04551e4079.png]

ip2服务不可用，直接将ip2的虚节点路由均衡的打在了ip1、ip3上面  
![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/b00fa8c63abf4cf6a0d709e9c47eb15b.png][https_img-blog.csdnimg.cn_b00fa8c63abf4cf6a0d709e9c47eb15b.png]

**小试牛刀**  
我们直接实战一致性hash环虚拟节点这中方式，而且在实际业务场景中我们也是优先选用该种方式。  
我们定义三个服务节点ip，分别为：ip1~3【10.10.10.202,10.10.10.203,10.10.10.204】。  
为了演示方便我们每个实节点增加三个虚拟节点分别为 ip13-VN13。

**1、一致性hash带虚拟节点工具类，提供初始化hash环、获取hash值、获取目标路由等方法**

/**
     * 一致性hash函数--虚拟节点
     * @author senfel
     * @version 1.0
     * @date 2023/1/17 10:41
     */
    @Slf4j
    public class ConsistentHashVirtualNode {
        
    
        /**
         * 实际节点虚节点数量
         */
        private static int virtualNodeNum = 3;
    
        /**
         * 实际节点集合
         * 本次测试我们用hash(ip)作为环上实际节点
         */
        private static List<String> realNodeList = new ArrayList<>();
    
        /**
         * 虚拟节点集合
         * map key-虚拟节点hash
         *     value-虚拟节点
         */
        private static SortedMap<Integer,String> virtualNodeMap = new TreeMap<Integer,String>();
    
    
        /**
         * 计算hash值
         * 计算方法很多，普通hashcode相近数据分布不明显，我们采用FNV32进行测试
         * 1. 加法Hash；
         * 2. 位运算Hash；
         * 3. 乘法Hash；
         * 4. 除法Hash；
         * 5. 查表Hash；
         * 6. 混合Hash
         * 目前比较流行的是乘法hash FNV32
         * @param str
         * @author senfel
         * @date 2023/1/17 10:54
         * @return int
         */
        private static int getHash(String str){
        
            //return Math.abs(str.hashCode()); hash值分布不明显弃用
            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;
        }
    
    
        /**
         * 初始化hash环
         * @param ipArray
         * @author senfel
         * @date 2023/1/17 10:48
         * @return void
         */
        public static void initHashNode(String[] ipArray){
        
            if(null == ipArray || ipArray.length == 0){
        
                return;
            }
            //将ip写入实际节点
            for(int i=0;i<ipArray.length;i++){
        
                realNodeList.add(ipArray[i]);
            }
            //获取各个节点的虚拟节点，将虚拟节点加入hash环
            realNodeList.forEach(ip ->{
        
                for(int j=1;j<=virtualNodeNum;j++){
        
                    String virtualNode = ip+"&VN"+j;
                    //计算虚拟节点hash
                    int virtualHash = getHash(virtualNode);
                    //将节点放置在环上
                    virtualNodeMap.put(virtualHash,virtualNode);
                    log.error("一致性hash环初始化-虚拟节点：{}加入hash环，当前节点hash值为：{}",virtualNode,virtualHash);
                }
            });
        }
    
    
        /**
         * 我们实战场景是根据用户ID进行hash，然后找到路由ip
         * @param userId
         * @author senfel
         * @date 2023/1/17 10:57
         * @return java.lang.String
         */
        public static String getServerIp(int userId){
        
            //获取用户hash
            int hash = getHash(userId + "");
            //根据用户hash获取hash环中大于当前值的后续节点
            SortedMap<Integer,String> sortedMap = virtualNodeMap.tailMap(hash);
            int firstKey = 0;
            String nodeIp = null;
            if(sortedMap == null){
        
                //没有大于当前hash数据,应该是等于最小节点hash，直接取第一个节点即可
                firstKey = virtualNodeMap.firstKey();
                //获取到当前节点的ip
                nodeIp = virtualNodeMap.get(firstKey);
            }else{
        
                //直接获取节点
                firstKey = sortedMap.firstKey();
                nodeIp = sortedMap.get(firstKey);
            }
            return nodeIp;
        }
    
    }

**2、测试方法，模拟服务注册初始化hash环，模拟用户访问路由**

public static void main(String[] args) {
        
            //测试ip 10.10.10.202,10.10.10.203,10.10.10.204
            String[] ipArray = {
        "10.10.10.202","10.10.10.203","10.10.10.204"};
            initHashNode(ipArray);
            //测试用户模拟9个用户
            List<Integer> userList = new ArrayList<>();
            int userId = 2023011700;
            for(int i=0;i<9;i++){
        
                userId += i * 100;
                userList.add(userId);
            }
            //模拟用户访问
            for (Integer id : userList) {
        
                String serverIp = getServerIp(id);
                String realIp = null != serverIp ? serverIp.substring(0, serverIp.indexOf("&")) : null;
                log.error("用户{}访问系统,路由到虚拟节点：{}，实际路由ip为：{}",id,serverIp,realIp);
            }
        }

**3、查看测试结果，展示初始化hash环各个虚拟节点加入、用户访问路由真实ip**

> hash环初始化

*  一致性hash环初始化-虚拟节点：10.10.10.202&VN1加入hash环，当前节点hash值为：1417355037
 *  一致性hash环初始化-虚拟节点：10.10.10.202&VN2加入hash环，当前节点hash值为：1001023951
 *  一致性hash环初始化-虚拟节点：10.10.10.202&VN3加入hash环，当前节点hash值为：744395883
 *  一致性hash环初始化-虚拟节点：10.10.10.203&VN1加入hash环，当前节点hash值为：573863409
 *  一致性hash环初始化-虚拟节点：10.10.10.203&VN2加入hash环，当前节点hash值为：197370571
 *  一致性hash环初始化-虚拟节点：10.10.10.203&VN3加入hash环，当前节点hash值为：1087274216
 *  一致性hash环初始化-虚拟节点：10.10.10.204&VN1加入hash环，当前节点hash值为：944575377
 *  一致性hash环初始化-虚拟节点：10.10.10.204&VN2加入hash环，当前节点hash值为：2022065171
 *  一致性hash环初始化-虚拟节点：10.10.10.204&VN3加入hash环，当前节点hash值为：1365766942

> 用户访问ip路由

*  用户2023011700访问系统,路由到虚拟节点：10.10.10.204&VN3，实际路由ip为：10.10.10.204
 *  用户2023011800访问系统,路由到虚拟节点：10.10.10.204&VN1，实际路由ip为：10.10.10.204
 *  用户2023012000访问系统,路由到虚拟节点：10.10.10.204&VN2，实际路由ip为：10.10.10.204
 *  用户2023012300访问系统,路由到虚拟节点：10.10.10.203&VN1，实际路由ip为：10.10.10.203
 *  用户2023012700访问系统,路由到虚拟节点：10.10.10.204&VN1，实际路由ip为：10.10.10.204
 *  用户2023013200访问系统,路由到虚拟节点：10.10.10.204&VN3，实际路由ip为：10.10.10.204
 *  用户2023013800访问系统,路由到虚拟节点：10.10.10.202&VN3，实际路由ip为：10.10.10.202
 *  用户2023014500访问系统,路由到虚拟节点：10.10.10.203&VN1，实际路由ip为：10.10.10.203
 *  用户2023015300访问系统,路由到虚拟节点：10.10.10.204&VN2，实际路由ip为：10.10.10.204

**总结：  
一致性hash能够满足分布式服务路由场景，服务的波动对用户影响不大。为了达到各个路由真正的负载均衡，建议采用带有虚拟节点的一致性hash函数。**

[4296d0ccb75f4ce3bc419708aefc4ad4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/696630226bd74367aba63669e255dfd6.png
[f4f679eebce6434e9e3443952913316d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7b612bb43c4f4474bdcb437f462bc513.png
[4bee02d2ee4748f5ada43e79096afbb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/15700e568d9f42e0a57e9173782a6842.png
[76d0f5696eb34a8fac0afc04551e4079.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/71061a0544164a0c8cf0f6228f3b5317.png
[https_img-blog.csdnimg.cn_b00fa8c63abf4cf6a0d709e9c47eb15b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/3ba6b84efd8342ddb1f2ad6fa0f0e264.png