一致性hash
算法解释
- 将hash空间虚拟成一个环形的空间，将服务器节点进过hash运算后分布在环形空间上。
- item经过hash运算后，得到其在hash环上的位置，然后顺时针或者逆时针就近取其应该存储的节点。
以下是一致性hash的示意图：
一致性hash示意图
图中存在Node1-4 4个节点，顺时针就近取,item1-item4分别放置在4个节点上。
传统Hash VS 一致性Hash
hash
hash其实是将item与其存储在hash空间中的位置进行了映射，能够快速查找指定的item。
因此好的hash应该满足以下几点：
- Balance：尽可能让item能存储到空间的每一个地方，是所有的空间都能够得到利用。
- Monotonicity(单调)：hash空间节点的改变，尽可能地不影响现有数据的位置。
- Spread（分散）
- 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
