一致性hash

算法解释

1. 将hash空间虚拟成一个环形的空间，将服务器节点进过hash运算后分布在环形空间上。
2. item经过hash运算后，得到其在hash环上的位置，然后顺时针或者逆时针就近取其应该存储的节点。

以下是一致性hash的示意图：

一致性hash示意图

图中存在Node1-4 4个节点，顺时针就近取,item1-item4分别放置在4个节点上。

传统Hash VS 一致性Hash

hash

hash其实是将item与其存储在hash空间中的位置进行了映射，能够快速查找指定的item。

因此好的hash应该满足以下几点：

1. Balance：尽可能让item能存储到空间的每一个地方，是所有的空间都能够得到利用。
2. Monotonicity(单调)：hash空间节点的改变，尽可能地不影响现有数据的位置。
3. Spread（分散）
4. Load（负载）

传统hash VS 一致性hash

类别	普通hash	一致性hash
结构	线性	虚拟环形
节点改变影响	大	小

一致性hash节点变化造成的影响

删除Node的影响

图为删除节点3时，受影响的部分，仅仅是node3与node2之间。

添加Node的影响

图为增加一个节点5时，受影响的部分节点5和2之间的部分

上面其实可以看出，一致性hash在节点修改增加或者删除的时候，仅仅只影响变更节点与其前一个节点之前的部分（顺时针，逆时针则是与其后一个节点）

一致性hash存在的问题

数据倾斜

当节点数较少的时候，容易出现数据倾斜问题。

数据倾斜问题

以灰色先为边界，左侧部分全部会分配给node1，右边全部分配给Node2,分配不均，导致数据倾斜问题。

虚拟节点解决

为节点多进行几次hash，产生一些虚拟节点，这些虚拟节点映射到实际节点。（item-->虚拟节点--> 实际节点），从而达到尽可能让数据分布均匀。

引入虚拟节点

为Node1，Node2分别建立3个虚拟节点

item# --> (Node1#1/Node1#2/Node1#3) --> Node1

item# --> (Node2#1/Node2#2/Node2#3) --> Node2