一致性hash理解

一句话解释：当新增或者删除节点时，原有的数据能够保旧的数据能够按照老算法映射到数据所在的服务器，而新的数据能够按照新的散列算法映射到数据所在的服务器。

问题
原有的hash算法，当新增或者减少节点时，会导致近乎全局的数据移动。如果用在缓存中，那么大量的缓存会在某个时刻失效，将会导致系统的震荡。

解决
一致性hash。
一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏：
平衡性：结果尽可能均匀分布
单调性：新增或删除节点不会影响原有的分配
分散性：相同内容被hash到不同的节点的严重程度，应尽可能避免
负载：对于一个特定的分区可能被不同端映射为不同的内容


引入问题
一致性hash能够较好的解决单调性、分散性和负载的问题，但是没有很好的解决平衡性。当其中一台机器挂了，它的数据统一迁移到另一台机器后可能引起另一台机器超负荷，从而导致机器服务的雪崩。
解决
可以通过“虚拟节点”解决一致性hash平衡性的问题。

虚拟节点的具体实现

目的
一致性Hash是一种特殊的Hash算法，解决了简单Hash算法在分布式Hash表中存在的动态伸缩问题。
栗子
redis做数据分布式存储（高并发，海量数据）

方法演进
1、Hash算法
hash(节点属性name)=200

200 % 3 = 2

新增一个节点

200 % 4 = 0
问题：

新增节点后，缓存失效，造成缓存雪崩。
2、一致性Hash
用hash的非负整数值范围做一个圆环

对集群的节点的某个属性（比如节点名）求hash值，放在环上

对数据key求hash值，也放在环上，按顺时针方向找到离它最近的节点。

问题：

在一致性Hash算法服务节点太少的情况下，容易因为节点分布不均匀面造成数据倾斜（被缓存的对象大部分缓存在某一台服务器上）问题

加一个节点不能均衡所有节点的压力
3、一致性Hash+虚拟节点
这里的一致性是指：新加节点对已有节点的影响保持一致。

前面提到分布式数据库数据分区规则有

【节点取余分区】

【一致性哈希分区】

【虚拟hash槽分区】

一致性HASH原理：在处理负载策略时：

一个hash环，从0到正整数
	
四个服务器ip计算的hash值肯定会落到这个hash环上的某一个点
	
根据hash(用户id)计算路由规则（hash值），然后看hash值落到了hash环的那个地方，根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip
数据分区也是同理。

如图：

user1的请求会落到服务器ip1进行处理
	
user2,user3的请求会落到服务器ip3进行处理
	
user4的请求会落到服务器ip4进行处理


public class IdenticalHash {

    //服务器列表
    public static String[] serverIps = {"192.168.0.1",
            "88.89.90.91", "77.78.79.80", "127.0.0.1"};

    //key表示服务器的hash值，value表示服务器
    public static TreeMap<Integer, String> hashRing = new TreeMap<Integer, String>();


    //通过用户ip得到处理该ip的服务器地址
    public static String getServerByIdHash(String userId) {
        int hash = hash(userId);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> moreThanIpMap = hashRing.tailMap(hash);
        if (moreThanIpMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            return hashRing.get(hashRing.firstKey());
        }
        //第一个Key就是顺时针过去离node最近的那个结点
        return moreThanIpMap.get(moreThanIpMap.firstKey());
    }

    //根据key获取hash值(复用hashmap中的hash算法)
    public static int hash(String str) {
        int h;
        return (str == null) ? 0 : (h = str.hashCode()) ^ (h >>> 16);
    }

    //将服务器ip放到hash环中
    public static void putHashRing() {
        for (int i = 0; i < serverIps.length; i++) {
            int hash = hash(serverIps[i]);
            hashRing.put(hash, serverIps[i]);
            System.err.println(serverIps[i] + " 在hash环中的位置：" + hash);
        }
    }

    public static void main(String[] args) {

        putHashRing();
        String[] userIds = {"1241414", "42452356", "4214", "777789"};
        for (int i = 0; i < userIds.length; i++) {
            System.out.println("用户id:" + userIds[i] + " 的hash值为" + hash(userIds[i])
                    + ", 交由服务器:" + getServerByIdHash(userIds[i]) + " 处理");
        }
    }
}

上诉hash环中的服务器ip分配不均。也可能会导致某服务器处理大量的请求，有服务器会闲置

均匀一致性hash

均匀一致性hash的目标是如果服务器有N台，客户端的hash值有M个，那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡.