分布式一致性Hash算法原理及手写简单实现

川长思鸟来 2023-06-07 08:12 7阅读 0赞

# 一、分布式一致性hash算法原理 #

> 在互联网项目中，海量数据和海量请求时常见的问题，常用的方法是使用缓存来处理，一般会采用分布式缓存集群，如Redis集群  
> 但这样也有两个问题：

*  1、海量数据，如果缓存的数据也很大，会超出单机内存容量（redis等缓存都是内存型数据库），这时怎么办？
 *  2、数据如何均衡分布到缓存集群的节点上？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhbnRhc2ljX3Zhbg_size_16_color_FFFFFF_t_70]

这时候想到的解决方法可能是 通过缓存key的hasn值，来和集群节点数来取余  
即：

## 1、均衡分布式方式一： hash(key) % 集群节点数 ##

![在这里插入图片描述][20191013202319953.png]

如图，当有3个节点集群时，需要新增一个缓存数据(key-value)，fantsey:666  
假如： hash(fantsey) = 200  
则数据需要放到的服务器节点为： 200%3=2

扩展： 当需要搞促销活动，数据量很暴增，此时需要临时增加一台服务器来提高集群性能，假如此时增加了一台服务器

![在这里插入图片描述][20191013202332729.png]

假如此时再新增fantsey:666到缓存中：  
hash(fantsey)=200, 200%4=0 跟3台服务器时存储的服务器节点处不一样了  
那么会有多大比例的数据缓存名不中呢？

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SCFGLEv2-1570969282623)(DF35A2EA737349B3ADC30B33F6D00061)\]][img-SCFGLEv2-1570969282623_DF35A2EA737349B3ADC30B33F6D00061]  
可以看出，增加一台服务器后，3→4，缓存命不中的几率为3/4=75%  
假如现有99台，再增加一台，则有99/100=99%的缓存命不中  
此时如果大量缓存突然查不到，则会都去数据库查找，则数据库压力突然暴增，甚至崩溃，此时就会造成著名的“**缓存雪崩**”问题。

## 2、均衡分布式方式二： 一致性Hash算法 + 虚拟节点 ##

一致性hash算法就是为了解决hash(key)/节点数算法导致缓存雪崩问题的。  
其核心思想：

*  1、把非负整数的值范围做成一个圆环，如0~65535；
 *  2、对集群的节点的某个属性求hash值（如节点名称），根据hash值，在环上增加一个节点；
 *  3、对数据的key求hash，一样把数据也放到环上，并按顺时针方向，找到最近的服务器节点，把数据存储到这个节点上。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qzdVL0l7-1570969282623)(796C7AC87144486692063BF5C2D7929C)\]][img-qzdVL0l7-1570969282623_796C7AC87144486692063BF5C2D7929C]

此时如果增加一个节点，则只会影响到当前节点和它逆时针方向最近一个节点之间的缓存数据，什么是一致性？ 一致性表示新增一个节点后，对其他节点的影响是一致的。  
此时就会有两个问题:

*  1、新增节点，能均衡缓存原有节点的压力吗？
 *  2、集群的节点，是否一定会均衡分布到环上？

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6fmvr3Ol-1570969282624)(BA484949E76B4BAB84474075535C0D42)\]][img-6fmvr3Ol-1570969282624_BA484949E76B4BAB84474075535C0D42]

为了解决如上两个问题，需要新增虚拟节点，来优化数据均衡分布的问题。

> 一个物理虚拟节点对应多个虚拟节点，此时虚拟节点环上分布的数据就会更均匀。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bpT0JyzA-1570969282624)(E195DF821DCB4EB2AD2E5BCE3B2DF729)\]][img-bpT0JyzA-1570969282624_E195DF821DCB4EB2AD2E5BCE3B2DF729]

## 3、一致性hash算法应用 ##

一般用户分布式数据存储，例如分布式缓存集群，如redis和memcached都采用了一致性hash算法，来保证分布式数据缓存的均衡分布及拓展灵活性（如新增或移除几点）。

# 二、 简单实现一致性Hash算法 #

思路：

*  1、物理节点信息
 *  2、虚拟节点信息
 *  3、hash算法
 *  4、物理节点和虚拟节点的对应关系
 *  5、虚拟节点环
 *  6、将虚拟节点放置到虚拟节点环上

问题：  
虚拟节点环的数据结构，原理是一个排序号的数字，此时用什么数据结构来保存比较好呢？

*  Array， 查找快，但变更不方便，需要扩容
 *  List, 链表，只有链头和链尾两个指针，所以查找只能从链头或者链尾一个去找，查询速度慢
 *  二叉树： 查找和变更都方便。但根节点不可变更，可能导致左右两边数据分布不均匀
 *  红黑树： 继承二叉树，并且可以通过左旋和右旋，变更二叉树根节点

TreeMap： java中，红黑树算法的实现者，即采用TreeMap实现最合适

#### 1、hash算法类 ####

package com.fantsey.consistentHash;
    
    /**
     * FNV1_32_HASH算法，比hash散列更均匀
     */
    public class FNV1_32_HASH {
    	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、一致性算法实现类 ####

package com.fantsey.consistentHash;
    
    import java.util.*;
    
    /**
     * 一致性hash算法简单实现
     * @author fantsey
     * @date 2019/10/13
     */
    public class ConsistentHash {
        // 1、物理节点
        private List<String> realNodes = new ArrayList<>();
    
        // 2、虚拟节点数
        private int virtualNodesCount = 100;
    
        // 物理节点与虚拟节点的对应关系,存储的是虚拟节点的hash值
        private Map<String, List<Integer>> real2VirtualMap = new HashMap<>();
    
    
        //虚拟节点排序存储结构 红黑树 ，key用虚拟节点的hash值，value用物理节点
        private SortedMap<Integer,String> sortedMap = new TreeMap<Integer,String>();
    
        public ConsistentHash(){}
    
        public ConsistentHash(int virtualNodesCount){
            this.virtualNodesCount = virtualNodesCount;
        }
    
        /**
         * 新增一个服务器节点
         * @param nodeName
         * @return
         */
        public void addServer(String nodeName){
            // 创建虚拟节点
            String virtualNode = null;
            int virtualNodeHash = 0;
            List<Integer> virtualNodeList = new ArrayList<>();
            int i=0, count = 0;
            while(count < this.virtualNodesCount){
                virtualNode = nodeName + "-" + i;
                i++;
                virtualNodeHash = FNV1_32_HASH.getHash(virtualNode);
                // 防止hash碰撞
                if (!this.sortedMap.containsKey(virtualNodeHash)) {
                    virtualNodeList.add(virtualNodeHash);
                    this.sortedMap.put(virtualNodeHash, nodeName);
                    count++;
                }
            }
            this.real2VirtualMap.put(nodeName, virtualNodeList);
        }
    
        /**
         * 移除一个物理节点
         * @param nodeName
         */
        public void removeServer(String nodeName){
            // 获取该物理节点对应的虚拟节点，并从虚拟节点圆环移除
            List<Integer> virtualHash = this.real2VirtualMap.get(nodeName);
            for(Integer hashValue : virtualHash){
                this.sortedMap.remove(hashValue);
            }
            // 移除物理节点和虚拟节点的映射关系
            this.real2VirtualMap.remove(nodeName);
            this.realNodes.remove(nodeName);
        }
    
        /**
         * 获得存储的物理服务器节点
         * @param key
         * @return
         */
        public String getServer(String key){
            int keyHashValue = FNV1_32_HASH.getHash(key);
    
            // 找到大于该hash值的一个节点，这个节点就是用于存储当前key的节点
            SortedMap<Integer, String> nodeMap = this.sortedMap.tailMap(keyHashValue);
    
            // 如果没有找到，则说明没有比当前key的hash值大的节点了，
            // 此时按顺时针方向，应该找到第一个节点
            if (nodeMap.isEmpty()) {
                return this.sortedMap.get(this.sortedMap.firstKey());
            } else
                return nodeMap.get(nodeMap.firstKey());
        }
        
        // 测试
        public static void main(String[] args) {
            ConsistentHash ch = new ConsistentHash();
            String server_1 = "192.168.0.1";
            String server_2 = "192.168.0.2";
            String server_3 = "192.168.0.3";
            ch.addServer(server_1);
            ch.addServer(server_2);
            ch.addServer(server_3);
            for (int i = 0; i < 10; i ++) {
                System.out.println("key" + i + " 对应的存储服务器节点为： " + ch.getServer("key" + i));
            }
    
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhbnRhc2ljX3Zhbg_size_16_color_FFFFFF_t_70]: /images/20230601/c4fcf9809734432cb73fa670155a37f4.png
[20191013202319953.png]: /images/20230601/66bf41d660ab4581912c58688194d411.png
[20191013202332729.png]: /images/20230601/940fa83b950e475593788f33705e5bdb.png
[img-SCFGLEv2-1570969282623_DF35A2EA737349B3ADC30B33F6D00061]: /images/20230601/96eb20590e4746bbbea6549825aeff64.png
[img-qzdVL0l7-1570969282623_796C7AC87144486692063BF5C2D7929C]: /images/20230601/78d23c9286d24b3dbba11744c5388391.png
[img-6fmvr3Ol-1570969282624_BA484949E76B4BAB84474075535C0D42]: /images/20230601/f9861cd2d7d64ff89fb123d6fdf19609.png
[img-bpT0JyzA-1570969282624_E195DF821DCB4EB2AD2E5BCE3B2DF729]: /images/20230601/6af4d2e7b1aa420ba3285073c6cf72c2.png