一致性哈希实现负载均衡

1 为什么需要哈希算法

解决同一个用户访问服务器是，访问的是不同的服务器的问题

场景：集群造成的session没有同步

当一个用户访问服务器A的时候，该台服务器A会保存这台服务器的session，但是当下次再访问的时候，被负载均衡算法可能算到了不同的服务器B，服务器B中没有用户的session，会要求用户再次登录。

解决：

1. 加入redis，将session存到redis中
2. Tomcat同步session
3. 一致性哈希算法

2 什么是一致性哈希算法

服务器集群接收到一次请求调用时，可以根据请求的信息，比如客户端的ip地址，或请求路径与请求参数等信息进行哈希，可以得出一个哈希值，特点是对于相同的ip地址，或请求路径和请求参数哈希出来的值是一样的，只要能再增加一个算法，能够把这个哈希值映射成一个服务端ip地址，就可以使用相同的请求（相同的ip地址，或请求路径和请求参数）落到同一服务器上。

因为客户端发起的请求是无穷无尽的（客户端地址不同，请求参数不同等等），所以对于的哈希值也是无穷大的，所以我们不能把所有的哈希值都进行映射到服务端ip上，所有这里需要用到哈希环。

3 虚拟节点

1. 解决一个服务器挂掉造成的服务不均匀问题
2. 使得哈希环更加平滑

当时当一台服务器挂掉的话，会造成服务器服务不均匀的情况

会发现，ip3和ip1直接的范围是比较大的，会有更多的请求落到ip1上，这是“不公平”，解决这个问题需要加入虚拟节点，比如：

其中，ip2-1,ip3-1就是虚拟节点，并不能处理节点，而是等同于对应的服务器。
实际上，这只是处理这种不均衡性的一种思路，实际上就算哈希环本身是均衡的，你也可以增加更多的虚拟节点来使得这个环更加的平滑。

上面的哈希环更加的散列，平滑

只需要找到大于hashcode的以一个虚拟节点即可

由于哈希环上的点是有序的，那么采用的数据结构是TreeMap

4 代码实现

public class ServerIps {

    public static final List<String> LIST = (List<String>) Arrays.asList(
            "192.168.0.1",
            "192.168.0.2",
            "192.168.0.3",
            "192.168.0.4",
            "192.168.0.5",
            "192.168.0.6",
            "192.168.0.7",
            "192.168.0.8",
            "192.168.0.9",
            "192.168.0.10"
            );

}

======================================

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash {

    private static TreeMap<Integer, String> virtualNodes = new TreeMap<>();
    private static final int VIRTUAL_NODES = 160;

    static {
        for(String ip: ServerIps.LIST) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(ip+i);
                virtualNodes.put(hash, ip);
            }

        }
    }

    private static String getServer(String client) {
        int hash = getHash(client);

        //大于hash，virtualNodes的子树的firstkey
        //tailMap，能获得大于等于hash值的一棵子红黑树
        SortedMap subMap = virtualNodes.tailMap(hash);
        Integer firstKey = null;

        if(subMap == null) {
            firstKey = virtualNodes.firstKey();
        } else {
            firstKey = (Integer) subMap.firstKey();
        }

        return virtualNodes.get(firstKey);
    }

    private 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;
    }

    public static void main(String[] args) {

        for (int i = 0; i < 12; i++) {
            System.out.println(getServer("client"+i));
        }
    }

}

5 最小活跃数

由于服务的时间并不是固定，如果平均分配服务器有的时候并不合理

比如：
有3个消息，分别请求了A、B、C三台服务器，处理的时间依次为3s、2s、1s，当1s后有一个新的请求过来，按道理说应该A服务器来服务，但是C台服务器已经空闲了，所有这样的分配方式有时候并不合理。

解决：
采用最小活跃数，哪台机器服务最少，用哪台机器，当都大致相等的时候可以根据前面的随机、轮询等。

6 算法的魅力

• 将程序“复杂化”，提升程序效率到极致