一致性哈希算法

一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。
Memcached client 也选择这种算法，解决将 key-value 均匀分配到众多 Memcached server 上的问题。
它可以取代传统的取模操作，解决了取模操作无法应对增删 Memcached Server 的问题(增删 server 会导致同一个 key,在 get 操作时分配不到数据真正存储的 server，命中率会急剧下降)

一致性 Hash 特性

 平衡性(Balance)：

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

 单调性(Monotonicity)：

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。
哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
容易看到，上面的简单求余算法hash(object)%N 难以满足单调性要求。

 平滑性(Smoothness)：

平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的

一致性 Hash 原理

1.建构环形 hash 空间：

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；
我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环。

2.把需要缓存的内容(对象)映射到 hash 空间

接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布

3.把服务器(节点)映射到 hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中，并且使用相同的 hash 算法。
一般的方法可以使用 服务器(节点) 机器的 IP 地址或者机器名作为hash 输入。

4.把对象映射到服务节点

现在服务节点和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，
首先确定对象hash 值在环上的位置，从此位置沿环顺时针“行走”，
第一台遇到的服务器就是其应该定位到的服务器。

5. 通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时，cache 会失效。

5.1 移除 cache：考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象。
5.2 添加 cache：再考虑添加一台新的 cache D 的情况，这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache 之间的对象，将这些对象重新映射到 cache D 上即可