一文讲明白一致性hash算法

一致性Hash算法常用来解决数据分片时的数据扩容/缩容的性能问题。
一、业内数据分片用的Hash算法，将节点的hash值对节点数取余。
存取通过key / value的方式对节点取余。

二、数据分片使用hash算法的优缺点：
优点：简单，方便。
缺点：数据难以的扩容和维护。

1.当节点数从3变成4的时候前面的三个节点需要对里面的数据进行重新分配四个节点上。
2.当节点数从3变成2时，也需要对3个节点数的数据重新分配到两个节点上。
这样必然会带来大量数据进行迁移，在数据迁移的过程中，是无法进行读写的，必然会严重影响整个系统的性能。

三、用一致性hash算法解决扩容/缩容的问题
1.一致性hash算法的思路是将hash计算出来的 key 对 2的32次方取余，然后将其分配到计算后的节点上。
取得的余数再映射到各个节点上，如果没有找到节点，对去下一个节点上找。

2.当节点扩容时，假设在d~a之间增加一个e节点，那么只需要将a节点中的hash取余后的值在d-e之间的数据迁移到e节点即可，b、c、d节点的数据无需迁移。

3.当节点缩容时，假设a节点要去除，则将a节点的数据迁移到b节点即可，在e-b区间之间的请求到b节点上。

4.假设a节点宕机，则影响的只有(e,a] 之间的数据不可访问，其他区间的数据可以正常访问。

三、通过虚拟映射解决一致性hash算法分配不均的问题。
假设现在只有三个节点，a、b、c，a 是0节点，b是1节点，c是2节点。那么这时候a节点的数据远远大于b、c节点的数据。

通过建立虚拟节点将a1节点映射到a节点，b1、b2节点映射到b节点，将c1、c2映射到c节点，就可以解决数据分片不均的问题。