为什么需要一致性哈希算法？

    分布式系统每个节点都可能失效，在节点失效或者加入新节点后，如何把对数据的影响降到最低？在分布式缓存中，如果没有好的算法，某个节点失效或者加入新节点后，会对当前缓存的命中率产生巨大的影响。

    定义：一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^-1（即哈希值是一个32位无符号整形），如何将一个key，映射到一个节点， 这里分为两步.

    1. , 将服务的key按该hash算法计算,得到在服务在一致性hash环上的位置.

    2. 将缓存的key，用同样的方法计算出hash环上的位置，按顺时针方向，找到第一个大于等于该hash环位置的服务key，从而得到该key需要分配的服务器。

    168f69205ef99590.png

    当减少或者增加一个节点时，只对顺时针方向第一个原有节点的数据有影响，其他节点不变。当节点比较少时，这个算法还是存在数据分布不均匀的情况，这时候可以引入虚拟节点。在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。