一致性哈希

1、产生由来：

随着时代的发展，数据量与日俱增，相比纵向扩展单机的性能，人们更倾向于横向扩展，将多台一般的廉价机器组成集群来充当超级计算机，节省了大量的成本，代价是极大地增加了系统的复杂性。为了应对这些复杂性，一批又一批分布式领域的技术相继诞生，其中不乏一些看过之后令人拍案叫绝的精彩的想法。
从存储来说，数据量大的时候，一台机器不能胜任时，那么通常的做法是将数据分片，存储到多台机器上，通过集群的方式完成数据存储的需求，举个例子，你有大量的数据需要缓存，比如100G，一般的机器显然没有这么大的内存，于是不得不把这100G分布到比如10台机器上，每台存储10G的数据。数据分配的算法有很多种，一种比较容易想到的就是hash，通过将数据对10取模，hash到各个机器上。看似很美好，但是有两点因素是不得不考虑的:

1、组成集群的机器都是廉价的小型计算机，机器故障是在正常不过的事情了。

2、随着数据量的持续增加，你发现10台机器不够用了，想增加1台上去，过一段时间，又需要加一台。
以上两种情况有一个共同点：机器数量的变动。而机器数量变动之后，对数据重新取模时，会造成大量的缓存失效。举个例子：
本来10台机器，有个key是100，通过key % 10将数据均匀分布到各个机器上，这时100 % 10 = 0，这个key被分配到地0号机器上存储了，然后一台机器挂了，这时，去获取刚才存储的key，100 % 9 = 1，重新hash后，变成了去第1号机器上获取key，自然获取不到，缓存未命中，于是不得不把key重新存储到第1号机器上。。。
于是乎，人们感叹，如果有什么办法，能在增减机器节点的时候，不需要或者尽可能少的需要为各个key重新分配机器就好了。然后聪明绝顶的程序员们想出了一致性hash的办法。

2、一致性哈希

2.1、定义：

一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n 个关键字重新映射，其中 K 是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

详解图中的信息

1、和一般hash表使用数组表示不太一样，一致性hash使用一个hash环来实现，因为一般的hash函数都可以返回一个int型的整数，所以将hash环平均分成2的32次方份，然后key的hashcode对2的32次方取模，一定会落到环上的一点。

2、各个节点（比如机器名称或者ip）的hashcode经过对2的32次方取模后，也一定会落到环上的一点

3、如果key和机器落到同一个位置，那么key存储到这个节点上，如果key没有落到某个机器节点上，那么沿着环顺时针寻找，将key存储到遇到的第一个节点上。

4、当删除一个节点（比如机器故障）时，获取被删除的节点上存储的key时，因为节点不存在了，所以沿着环继续顺时针走，会遇到下一个节点，这样就将原属于被删除节点的key移动到了下一个节点上，而所有属于其他节点的key并不受影响，无需重新分配。

5、增加一个节点时，也是同样的道理，这里不再详细描述。

问题1：数据分布不均匀：node节点并不是无线的多，所以这里不能体现哈希函数的均匀性，各个node节点并不是平均分配，所以还是会有负载不均衡的问题

大多数key都被分配到节点A上，只有很少一部分key会被分配到节点B上，造成分布的极度不均衡。

解决办法1：

为了解决数据分布不均匀的缺点，我们可以在hash环中添加一些虚拟节点，使得key尽可能的均匀分布到虚拟节点上，然后把虚拟节点存储的数据映射到真实节点上即可。

如下图所示：

添加虚拟节点后，key1被分配到Node B存储，key2被存储到NodeB的虚拟节点Virtual B1上存储，这样最终key1、key2被分配到了Node B上，key3、key4、key5被分配到了Node A上，比之前的分布均匀多了。

3、code

可以认为节点在环上是有序的，节点编号顺时针递增，java中可以用TreeMap来记录机器节点在hash环中的顺序和虚拟节点到真实节点的映射，代码实现如下：

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

public class ConsistentHash<T> {
    private final HashFunction hashFunction;
    private final int numberOfReplicas;// 节点的复制因子,实际节点个数 * numberOfReplicas =
                                        // 虚拟节点个数
    private final SortedMap<Long, T> circle = new TreeMap<Long, T>();// 存储虚拟节点的hash值到真实节点的映射

    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
            Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes)
            add(node);
    }

    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++)
            // 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点
            /*
             * 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node
             * 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上
             */
            circle.put(hashFunction.hash(node.toString() + i), node);
    }

    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++)
            circle.remove(hashFunction.hash(node.toString() + i));
    }

    /*
     * 获得一个最近的顺时针节点,根据给定的key 取Hash
     * 然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点
     */
    public T get(Object key) {
        if (circle.isEmpty())
            return null;
        long hash = hashFunction.hash((String) key);// node 用String来表示,获得node在哈希环中的hashCode
        if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器
	//SortedMap的tailMap函数返回Map中所有大于该key的元素组成的子map
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
		//返回存储key的真实的节点
        return circle.get(hash);
    }

    public long getSize() {
        return circle.size();
    }
    
}

4、应用场景

1. OpenStack的swift对象存储
2. 亚马逊的DynamoDB
   ng getSize() {
   return circle.size();
   }

}

## 4、应用场景

1. OpenStack的swift对象存储
2. 亚马逊的DynamoDB
3. Apache的Cassandra