普通Hash与一致性Hash

2024-03-04 16:35:59

1.Hash的介绍

Hash算法应用很广泛，比如MD5，SHA加密算法，数据存储和数据查找方面。
Hash算法最主要的应用场景还是在数据存储和数据查找方面。而设计得好的Hash算法，在数据查找方面可以时间复杂度可以达到O(1)。

1.1 常用2种Hash存储的方式介绍

除留余数法
定义一个固定大小的数组长度，把需要存储的数值%数组长度得到的数值，存储到数组的下标位置，这种方式就叫除留余数法。这种方法的缺点就是，容易产生Hash冲突，比如数组长度为5，需要存储的数值有1,2,3,4,6，那么在存储1和6的时候，就会产生冲突，因为1和6对5取余，长度都为1。所以在此基础上，引进了开放寻址法和拉链存储法。
开放寻址法
这种方式，在除留余数法的基础上，产生冲突时，把冲突的值放到被冲突的值的前面或者后面的空闲位置。
拉链存储法
这种方式，在除留余数法的基础上，产生冲突时，把冲突的值用链表的形式存储到被冲突的值的上面，及被冲突的值会产生一个链表，这个链表存储所有跟改值产生冲突的值。

2. Hash的应用场景

一般来说，我们如果不做hash算法研究，我们平时在工作当中，只需要使用已有的Hash算法就可以了。
那么Hash的应用场景有哪些了？主要的应用场景有请求负载均衡和分布式存储。

请求负载均衡
在使用nginx进行负载均衡时，就有一个ip_hash策略可以选择。那么使用ip_hash有什么好处了？它可以实现会话沾滞，从而避免处理session共享问题。因为同一个ip的请求会被映射到同一条服务器，从而使得session一直有效。而不是这次请求是这条服务器，服务器存储了session，下一次请求请求的是另外一台服务器导致session失效的。
在这里提一下，nginx的ip_hash策略默认使用的是普通Hash，并且在进行hash处理的时候，同一个网段的请求会落在同一条服务器，因为nginx处理ip_hash的代码中，只处理了客户端ip的前三段。如果想使用一致性Hash，需要自行下载模块，并进行编译安装。
分布式存储
在分布式的环境下，如果有多台mysql数据库或者多台redis，那么客户端需要存储到某条记录时，就可以使用hash(key) = index,来实现数据存储到某个服务器的功能了。

2.普通Hash

普通hash会不会存在什么问题了？答案肯定是有的。
举个例子，以nginx的ip_hash为例，如果后台服务器有5台，如果此时有一台服务器宕机了，那么大部分的客户端的hash得重新计算了，因为之前是hash(key%5)= index, 现在变成了hash（key%4）=index。当用户很多并且是使用的session会话沾滞的情况下，这种就会造成大量的用户登录失效从而导致用户体验很差。

3.一致性Hash

一致性Hash是为了解决普通Hash的，但是也只能说更大的程度的去优化普通Hash算法，从而减少客户端变更目标主机的解决方案。而不能完全百分之百解决所有用户都不替换目标主机。
一致性Hash思路为，定义一条线，线的两端分别为0和2的32次方-1（这个为int的最大值），然后把这条线的收尾两端相连形成一个环，我们称为Hash环。然后把服务器端的ipHash值落到这个环上，客户端的iphash值也落在这个环上，客户端产生的iphash以顺时针的方向查找服务器端生成的Hash值，离哪个最近，就访问哪台主机。
那么这种方案有没有什么缺点了？答案是有的，比如服务端机器刚开始的节点只有5台，而这个环总共有2的32次数-1个点，那么很容易造成大量客户端都落在一台服务端机器上，这种也被成为数据倾斜。
而为了解决数据倾斜的问题，又提出了一种解决方案，可以给每一个服务端主机都虚拟一些节点出来落在这个环上，这样就可以极大程度的避免了数据倾斜的问题。

4.手写Hash

4.1 普通Hash

	public static void main(String[] args) {
		// 定义模拟后台服务端机器数量为3
        int serverSize = 3;

		// 定义客户端请求ip
        String[] clientArr = new String[]{"192.168.10.1", "192.168.10.2", "192.168.10.3"};
        for (String client : clientArr) {
        	// 调用原生的hashcode方法生成code并取绝对值
            int clientCode = Math.abs(client.hashCode());

			// 取余
            int i = clientCode % serverSize;
	
            System.out.println("client ip :"+client+" ==> server No:"+i);
        }
    }

4.2 一致性Hash不带虚拟节点

	public static void main(String[] args) {
		// 定义一个服务端的服务器ip数组
        String[] serverArr = new String[] {"20.1.1.1", "26.2.2.2", "5.3.3.3"};

		// 定义一个排序的map来存储服务端的hashcode值，来模拟一个环
        SortedMap<Integer, String> treeMap = new TreeMap<>();
	
		// 生成hashcode，让每个服务端机器的ip落在这个环即map上
        for (String server : serverArr) {
            int serverCode = Math.abs(server.hashCode());

            treeMap.put(serverCode, server);
        }

		// 定义客户端请求ip
        String[] clientArr = new String[]{"30.95.10.1", "192.222.10.2", "10.168.10.3"};
        for (String client : clientArr) {
            int clientCode = Math.abs(client.hashCode());

            Integer key;
            // 在treeMap中找到key大于clientCode的所有值，会生成一个新的map
            SortedMap<Integer, String> sortedMap = treeMap.tailMap(clientCode);
            if (sortedMap.isEmpty()) {
            	// 如果为空，这个客户端的hashcode落在的最后一个服务端节点的后面，
            	// 需要查找第一个服务器节点
                key = treeMap.firstKey();
            } else {
            	// 不为空，则直接找第一个key就可以了
                key = sortedMap.firstKey();
            }

            System.out.println("client ip :"+client+" ==> server ip:"+treeMap.get(key));
        }

    }

4.3 一致性Hash带虚拟节点

	public static void main(String[] args) {
		// 定义一个服务端的服务器ip数组
        String[] serverArr = new String[] {"20.1.1.1", "26.2.2.2", "5.3.3.3"};
        // 虚拟节点数量
        int virtualNum = 10;

        SortedMap<Integer, String> treeMap = new TreeMap<>();

        for (String server : serverArr) {
            int serverCode = Math.abs(server.hashCode());
            treeMap.put(serverCode, server);

            for (int i=0; i<virtualNum; i++) {
            	// 在每个真实节点的后面，增加一些特有的标识，来生成虚拟节点
           		// 并且存储到treeMap 中
                int virtualCode = Math.abs((server+"/"+i).hashCode());
                treeMap.put(virtualCode, server+" virtual No" +i);
            }
        }

        String[] clientArr = new String[]{"30.95.10.1", "192.222.10.2", "10.168.10.3"};
        for (String client : clientArr) {
            int clientCode = Math.abs(client.hashCode());

            Integer key;
            SortedMap<Integer, String> sortedMap = treeMap.tailMap(clientCode);
            if (sortedMap.isEmpty()) {
                key = treeMap.firstKey();
            } else {
                key = sortedMap.firstKey();
            }

            System.out.println("client ip :"+client+" ==> server ip:"+treeMap.get(key));
        }

    }

码农公寓