共计 1505 个字符，预计需要花费 4 分钟才能阅读完成。
一致性hash算法也是一种hash算法，目的是为了解决分布式缓存问题。在添加或移除服务器的时候，能尽可能的保证已存在的请求和处理请求的服务器之间的映射关系。一致性hash算法解决了简单hash算法在分布式hash表中存在的动态伸缩的问题。
假设场景
公司有3台缓存服务器，用来存储用户头像的图片，编号0，1，2。现在有9万个用户头像需要存储，现在希望能够均匀的缓存到3台服务器上，也就是每台服务器缓存3万个头像，平衡每个服务器的负载压力。
方案一
没有任何规律，将图片平均的缓存到3台服务器上。
引发的问题：在查询的时候，就没有办法知道所需数据落在哪台服务器，每次查询都要遍历所有服务器查询，效率低速度慢。
方案二
- 以头像图片的名字作为key进行缓存，假设图片的名字不重复。
- 对图片的名字做hash运算，再对服务器的数量进行取模，得到的结果就是这张图片要缓存的服务器编号。（本场景里，对图片名字做hash运算后，对3进行取模mod，得到的结果一定是0，1，2）
- 查询时，只要再次对图片的名字hash取模后，就能知道缓存在哪台服务器上，就不需要遍历所有服务器了。
存在的问题：这样做看似可以均匀的缓存在每台服务器上，查询也不需要遍历服务器。但是，如果服务器的数据发生了变化，若增加一台或者减少一台，那么用同样的算法进行计算后，得到的结果就不一样了。比如，hash运算后对4取模，结果就是0，1，2，3了，这样就跟图片和服务器的映射关系就乱了。
这个时候，一致性hash算法就出现了。
一致性hash算法
一致性hash算法也是hash取模运算，只不过，它不是根据上述的服务器数量进行取模，而是对232进行取模。（因为IPv4是32位的，它的最大数量就是232，这样就能保证对ip地址进行取模时不会重复，能够对应到hash环上的正数。）
计算公式：hash(服务器的ip地址) % 232
计算的结果一定是0到232-1之间的一个整数。
结合场景解释一致性hash算法
假设3台服务器被映射到如下的位置，红点为图片的位置
问题1：这个图片应该被缓存到哪个服务器上呢？
原则：按照红点在的位置，顺时针遇到的第一个服务器就是它的存储服务器，即服务器A。
问题2：如果服务器不是均匀的分布在hash环上，那么每个服务器缓存的数量不是不均匀了吗？
如果是上图这样的情况，那么服务器C肯定是被分配到的图片是最多的。
hash环倾斜问题
理想状态下，是均匀的分布在hash环上，但是事实往往不会是理想状态的。
虚拟节点
虚拟节点就是实际节点（实际物理服务器）在hash环上的复制品，一个实际节点可以对应几个虚拟节点。
ABC三个服务器都增加一个虚拟节点，也可以增加更多的虚拟节点，这样缓存的分布就会均匀多了，减少了hash倾斜环的问题。一般可以根据服务器ip加编号的方式给每个节点计算虚拟节点的位置（nodeA#1，nodeA#2，nodeA#3）。
一致性hash算法的优点
假设服务器B故障了，被移除了
这样根据顺时针原则，1还是被缓存到服务器A，3和4被缓存到服务器C都没有发生变化，但是2会被计算出来是缓存到服务器C，实际是缓存在服务器B。而如果是简单的hash算法，很可能，1，2，3，4被分配到的缓存服务器完全发生变化。这就是一致性hash算法的优点。
- 使用简单hash算法，服务器数量变化时，缓存全部失效，会出现缓存雪崩；
- 使用一致性hash算法，服务器数量变化时，缓存部分失效，没失效的缓存还是可以抗住大部分访问压力，失效的部分访问DB，而不至于缓存全部失效，导致瞬间压力全部落在DB上，可能打崩DB。
