一致性哈希环

传统的hash算法在节点数量变化的时候会出现映射关系前后不一致的现象，如果每个节点提供的服务不一致，映射关系的改变将是致命的，比如无法找到已经映射了的数据。以哈希取模算法为例子，其公式是：node_index = hash(key) % N 。

节点减少的前后对比：对于新的key来说，映射没有问题，但是对于旧的key来说，映射关系发生了变化，本来如果hash(key)==3，那么会映射到编号为0的节点上，节点数量变化之后，却将映射到编号为1的节点上。这时去1节点取数据将访问不到，出现错误，对于分布式缓存系统而言，可能出现“缓存雪崩”。节点增加的情况同理。这成为简单哈希算法在分布式哈希表中存在的动态伸缩问题。

要解决映射不一致的问题，直观的方法是通过重新分配已有的key来迎合新的映射关系，但这代价昂贵。更好的方法是使用一致性哈希算法。

一致性哈希算法是一种特殊的哈希算法，在移除或者添加一个服务器的时候能够尽可能小地改变已经存在的服务请求和处理请求的服务器之间的映射关系。

一致性哈希算法通过一个叫作一致性哈希环的数据结构实现，一致性哈希环的主要思想是减少需要移动的已映射数据。原先的mod函数将key映射到一个特定的值上，并且为这个值提供一个服务器，一致性哈希算法首先将key映射到一个很大的范围内，并且为每个范围内的值提供一个服务器。如果负责某一范围的数据的服务器被删除，其上存储的数据将顺时针迁移到下一台服务器上，下一台服务器将负责映射到这两个连续范围内请求的处理。增加节点同理进行数据迁移。通过这种方式，节点数量发生变化时也不会改变其他范围的数据映射关系，尽可能地减少了需要迁移的数据数量。

如图所示，橙色节点表示数据映射到的环上的位置，蓝色节点表示服务器。初始时刻K1和K2由B服务器负责，如果B服务器被删除，K1和K2将迁移到C服务器上。

当然，这种方法也存在问题。当删除了一系列连续的节点之后，这些被删除节点的负载将交由环上的下一台机器统一处理。这台机器将承载大量的负载，可能因此崩溃，由此循环下去，造成雪崩，整个集群最后可能完全崩溃。

为了解决这一问题，引入虚拟节点的概念。数据的存储首先根据映射关系在环上找到对应的虚拟节点，每个虚拟节点都会关联到一个真实节点。例如下图中的A1、A2关联到真实节点A，数据都在A上存储，B1、B2关联到真实节点B，数据都在B上存储。由于节点数量很多，分布均匀，即使在连续范围内有机器崩溃，也不会给同一台机器增加负载，因此不容易造成雪崩。

【参考】
https://segmentfault.com/a/1190000021199728

https://zhuanlan.zhihu.com/p/379724672