一致性哈希算法
普通哈希算法带来的缺陷
假设一批数据分别存储在n台机器上，为了避免数据查找过程中对所有机器进行遍历，采用哈希规则将数据首先进行哈希计算得出其要存储的机器号，然后将数据存储在特定机器上。
但简单的哈希算法采用对于同一个数据计算得出的哈希值是一样的，所以当某台机器故障需要移除或者增加机器时，需要对每个数据重新计算哈希值，其映射关系可能全部改变，这样是一种灾难。
什么是一致性哈希算法
为了解决以上问题，提出了一致性哈希算法。单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1。我们选择机器ip或者机器名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置a；同样数据也使用该哈希函数找到其在哈希环上的位置b；从b位置开始顺时针找到的第一个机器位置上的机器即为存储这个数据的机器。
一致性哈希算法的优势
容错性和可扩展性
一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
- 如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
- 如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。
解决数据倾斜问题
一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题。
为了解决这个问题，引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。