一致性Hash算法原理

比如有{Node0, Node1, Node2}三个节点，陆续有多个资源要分配到这三个节点上，如何尽可能均匀地分配到这些节点上？

一致性哈希算法的思路为：先构造出一个长度为232整数环，根据Node0-2的节点名称的hash值（分布为[0,232-1]）放到这个环上。现在要存放资源，根据资源的Key的Hash值（也是分布为[0,232-1]）Hxxx，在环上顺时针的找到离Hxxx最近（第一个大于或等于Hxxx）的一个节点，就建立了资源和节点的映射关系。

为什么要用环存储节点，并用hashKey顺时针寻找对应节点？

理论上分配节点最简单的办法是取余算法，即有3个节点，资源key=5, 5%3=2，选取N2，key=3，3%3=0，选取N0。虽然简单，但有个缺点，如果节点数增加或减少，就会有大量的key不命中，造成请求压力转移，可能对系统整体有很大的影响，甚至发生宕机危险。

而一致性哈希算法增加或减少节点，只会引起少部分key不命中，如下图，增加一个Node3节点，只会将加粗部分的key值从Node0移到Node3，对数据影响很小。

通过以上方法一致性哈希解决了hash值分布不均的问题，但还存在一个问题，在没有Node3节点时，资源相对均匀的分布在[Node0,Node1,Node2]上。增加Node3节点后，Node0到Node2节点中间的所有资源从Node0迁移到了Node3上。这样，Node1,Node2存储的资源多，Node0,Node3存储的资源少，资源分布不均匀。我们如何解决这个问题呢？

因此，引入虚拟节点，将一个真实节点Node0映射成100个虚拟节点分布在Hash环上，与这100个虚拟节点根据哈希环匹配的资源都存到真实节点Node0上。[Node0,Node1,Node2]以相同的方式拆分虚拟节点映射到Hash环上。

当集群增加节点Node3时，在Hash环上增加Node3拆分的100个虚拟节点，这新增的100个虚拟节点更均匀地分布在了哈希环上，可能承担了[Node0,Node1,Node2]每个节点的部分资源，资源分布仍然保持均匀。