一致Hash（二）

图片来自于百度图片

内容提前知

1、一致Hash原理

一致Hash原理

前面我们已经说了为了解决在实际的分布式项目中服务器动态删减而导致命中率非常低的情况而引入了一致Hash。

一致性哈希将整个哈希值空间组织成一个虚拟的圆环，按照逆时针对数据进行排序，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

假设现在有4台服务器，我们按照对IP进行Hash计算出的Hash值在环上的位置如下图：

现在有4个数据，O1,O2,O3,O4通过Hash（key）后在环上的位置如下图：

IP服务器的HASH算法要和数据的HASH算法一致

下面按照顺时针寻找最近服务器的原则，将数据存储在就近的服务器上面去：

当出现服务宕机的情况

如上图，当出现（B服务器）宕机的情况时，新的数据将会自动将数据存到最近的服务器（C服务器），这样不会对A,D以及B的原始数据有任何影响。假设数据平均分布，则命中率依然有75%。

当出现新增服务器的情况

如下图，新增了（X服务器），这时候（O2）将会存到新的（X服务器），对于整个系统来说，只会对B服务器的原始数据有影响，而不会对A、C、D有任何的影响。

服务器越多，在出现宕机或者新增服务器的时候命中率越高。也就是说一致Hash在在服务器越多的情况下将能发挥更大的作用和优势。

Hash环的偏斜

在实际项目中，服务器的在Hash环上的分布不一定是我们理想中的状态，有可能大部分的数据都被分配到某一台服务器了，因此就引入了（虚拟节点）的概念。

虚拟节点：将一个服务器虚拟为两或者多个个服务器，增大在虚拟环上的分布，从而降低将数据存入一台服务器的概率。如下图:

虚拟节点的算法，可以使用下列方式：

Hash("192.168.1.100#1"); // NODE1-1

Hash("192.168.1.100#2"); // NODE1-2

遗留问题

假设有A、B、C三个服务器，还有一条数据O（ID，name，phone）：

1、开始在B中存的是O（1，www，13434343344）,

2、B宕机后，用户在C中查询，没有，因此在C中建一条缓存数据O（1，www，13434343344）,

3、这个时候，B好了，再次访问B，就会再次新建一条缓存数据O（1，www，13434343344），某个时间用户修改了电话，那么这时在B中的数据为O（1，www，13434343333），

4、假设用户修改数据后的某个时间B再次宕机了，用户只能访问C获取数据，发现C中有数据，但是在C中的数据是一条未修改的数据（用户不知，所以是一条错误数据）。

我们应该怎么防止这种情况的发生？