1.前言

在"一文让你彻底明白什么是一致性哈希"该文中，我们已经了解到了什么是一致性哈希及其的若干问题。还不了解的或者需要温习的请戳以下链接进行回味。

原文链接：http://www.toutiao.com/i6685547708570141188/

文中最后留下了两个小问题，最后的两个小问题将在以下进行详细美妙的回答。

2.问题回顾

问题1：hash函数是在大样本的情况下才会均匀，如果现在机器比较少的情况下，hash后机器的位置分布不均匀怎么办？

 

​

问题2：即使刚开始机器分布很均匀，但是加机器后也会导致不均匀的情况。

 

 

​

如果问题不明白的话，还是请戳“一文让你彻底明白什么是一致性哈希”这篇文章。

原文链接:http://www.toutiao.com/i6685547708570141188/

3.解决方案

上述问题1提到，如果机器很少的话，他们经过hash之后落在环有可能形成不均匀的情况，会造成负载不均衡的情况，即:

 

因为hash函数必须在足够大的样本里，hash之后的分布才会显得均匀，因此针对问题1，我们引入虚拟节点的概念，例如，有三台物理机，分别是m-1、m-2和m-3，假设虚拟节点个数为1000.

将m-1虚拟化m-1-1、m-1-2、m-1-3...... m-1-1000

m-2虚拟化m-2-1、m-2-2、m-2-3.....m-2-1000

m-3虚拟化m-3-1、m-3-2、m-3-3.....m-3-1000，

然后设置一张物理机和虚拟机的对应表，目的是为了找到可以通过物理机找到对应的虚拟机，通过虚拟机找到相对应的物理机，如下。

 

 

​

那这样的话，通过每台真实的物理机虚拟化后的节点，经过hash，映射到环上，注意，是虚拟节点去抢环上的点，又因为每台物理机都有等量的虚拟节点，故它们在环上的分布可以看作是比较均匀的。

当数据来的时候，同样是按照数据找到其在环上的位置，然后通过顺时针法则找到离它最近的虚拟节点，然后将该数据存到该虚拟节点所对应的物理机上(通过虚拟节点-物理机对应表寻找)。

 

 

​

如图，环上的节点均为虚拟节点，为简单起见，假设每台物理机只有3个虚拟节点，那当数据经过hash后映射到环上是上图的位置时，顺时针找到离它最近的m-1-1，然后通过“虚拟节点-物理机”映射表找到m-1-1对应的m-1物理机进行存储。

4.加、减机器的数据迁移

同样的，如果新增一台m4机器，将它虚拟化成等量的虚拟节点，然后分布在环上。简单起见，每个物理机只有3个虚拟节点，实际上是虚拟化成很多很多的，例如上文提到的1000个虚拟节点。

 

 

​

所以，原本图中绿色的数据属于m-1中的m-1-1部分的，但是现在中间多了个m-4-1，因此，按顺时针法则，灰色部分的数据从m-1上的m-1-1虚拟节点转移到m-4上的m-4-1节点。同样满足虚拟节点均匀分布(即说明每台物理机都负载均衡)和数据迁移代价低的条件。

 

 

​

5.哈希冲突

哈希冲突问题，即两个虚拟节点在环上发生冲突了，目前的解决方案是两个虚拟节点分别对应的两个真实物理机都存同样一份数据。另外冲突的概率是很小的，是个小概率事件，比如环上的哈希值范围为0~2^64，即环上总共可以有2^64个点，但是虚拟节点数目远比这个总数要小，所以发生冲突的可能性比较低，因此可采用以上策略进行解决。