什么是 Hash

Hash 就是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。例如Integer.hashCode()、String.hashCode()等。就算是输入的那内容不一致也有可能导致输出的 hash 值一致，这种情况就是 hash 碰撞，hash 碰撞是不可避免的，设计出高效的 hash 算法是不容易的。

普通 Hash 的分析

当用户来访问我的服务我们对请求和服务数量进行简单的运算得到 hash，然后根据算出的 hash 分发请求到不同的服务上。hash 计算方式为：hash = 请求 % serverCount

假设现在有四个请求分别是请求1、请求2、请求3、请求4，现在对四个请求进行计算分发请求到不同非服务上，计算结果如下图：

2021-04-18 17.27.28.png

普通 Hash 存在的问题

通过上图我们可以看到通过计算我们把不同的请求通过计算分别分发对应的服务器了，但是这个方式会存在一定的问题，接下来我们就要分析了。我们假设 server3 宕机，name 重新计算后的请求分发如下图

2021-04-18 17.29.07.png

在实际情况下发生服务宕机或者扩容的情况是很普遍的，当发生宕机或者扩容的时候，我们之前计算的所有 hash 都需要重新计算，在生产环境下我们后台服务器很多台，客户端也有很多，那么影响是很⼤的，缩容和扩容都会存在这样的问题，⼤量⽤户的请求会被路由到其他的⽬标服务器处理，⽤户在原来服务器中的会话都会丢失。

很多面试官喜欢拿着个吓唬面试，其实就是普通hash的缺点而已，别那么多套路

一致性 Hash 概念

一致性 Hash 的出现就解决了上述的问题，在发生宕机或者和扩容的时候尽可能少的影响请求的分发。一致性 Hash 的思路如下

2021-04-18 17.34.54.png

首先有一条直线，直线的开始为 0，结尾为 2 的 32 次方减 1，这相当于一个地址，然后把直线弯曲形成一个圆环形成闭环，这就是 hash 环。
我们对服务器求 hash 然后把服务器放到 hash 环上的对应位置上，当有请求到来时，对请求进行计算，把请求放到 hash 环的对应位置，然后顺时针获得最近的服务器节点。示意图如下：

2021-04-18 17.47.45.png

当发生服务宕机或者扩容是请求转发也是会发生变化的，这次我用扩容示例，宕机同理 假如我们在 server1 和 server2 之间加个 server4，请求转发如下图：

2021-04-18 17.49.14.png

由上图我们可以得出当发生扩容或者宕机的时候只会影响极少数一部分的用户，最大限度上提高的体验。当然一致性 hash 也可能存在一些问题的，比如如下图所示，服务器分布及其不合理，大量的请求都落在同一个服务器上，对服务的压力较大。

2021-04-18 17.52.06.png

Hash的这个思想用的很广，服务器只是一个例子而已

针对这种情况我们可以用增加虚拟节点的方式来尽可能更合理的分发请求来，减轻对某一服务的压力。如下图我们对每个节点增加两个虚拟节点：

2021-04-18 17.57.51.png

这个也算是解决hash问题的一种

实现普通 Hash 和一致性 Hash

public static void main(String[] args) {
    String[] ips = new String[] { "101.1.1.1","101.1.1.2","101.1.1.3","101.1.1.4" };
    int serverCount = 4;
    for (String ip : ips) {
        System.out.println(ip + " 的请求分发到 server" + ip.hashCode()%serverCount);
    }
    
    System.out.println("======================宕机分割线==========================================");
    // 模拟宕机一个
    serverCount = 3;
    for (String ip : ips) {
        System.out.println(ip + " 的请求分发到 server" + ip.hashCode()%serverCount);
    }
}

一致性Hash实现（不带虚拟节点实现）

public static void main(String[] args) {
    String[] serverIps = new String[] {"101.231.123.11","11.1.112.234","123.112.11.123","232.12.11.22"};
    // 用来存放服务器的
    SortedMap<Integer, String> hashServerMap = new TreeMap<>();
    for (String ip : serverIps) {
        hashServerMap.put(Math.abs(ip.hashCode()), ip);
    }
    // 客戶端ip
    String[] clientIps = new String[] {"101.23.234.33","11.1.112.2","123.112.11.12","23.121.11.22"};
    for (String ip : clientIps) {
        // tailMap 方法返回的是大于参数的集合
        SortedMap<Integer, String> serverMap = hashServerMap.tailMap(Math.abs(ip.hashCode()));
        // 取hash环上的第一个服务器
        if (serverMap.isEmpty()) {
            Integer firstKey = hashServerMap.firstKey();
            System.out.println(ip + " 的请求分发到 " + hashServerMap.get(firstKey));
        } else {
            // 获取结果集的第一个服务器
            System.out.println(ip + " 的请求分发到 " + hashServerMap.get(serverMap.firstKey()));
        }
    }
}