应用场景

我们的业务通常会使用缓存来提高系统的吞吐，不过单节点缓存存在明显的缺陷：单节点的缓存大小有明显的限制，当业务体量达到一定的规模时候，无法通过 增加机器的数量来解除这种限制。

为了解决上面这种问题，我们可以增加节点并将缓存在这些节点上均匀的打散，一般的，均匀的打散的方式可以采用hash(key) % n，这里的key为对应的缓存 的key，n为缓存节点的数量。不过这种方案也存在明显的缺陷：如果缓存节点掉电或者由于业务的扩展需要增加新的缓存节点，这种情况下将会使得已有的 缓存的数据重新hash找到新的存放的节点，这将会使得缓存失效，缓存的失效会使得大量的请求直奔数据库而去，最终可能会压垮数据库，导致整个服务不可用。

为了解决由于缓存服务器数量的改变导致缓存数据重新分配的问题，歪果仁发明了一种神奇的算法：一致性hash。提到一致性hash通常都会提到hash环，听着 名字很拽的样子，简单点来说就是一个环状的hash空间，之所以是环状的，和其缓存对象寻找缓存节点的策略是相关的；一般hash环大小为2^32，之所以是这个 值而不是其他的值，猜测应该是IP4的空间相关的，环中一个槽位代表一个缓存节点。

一致性hash流程

构建hash环

构建一个大小为2^32的数组，并将该数组当作一个环来对待

缓存对象映射

把需要映射的缓存对象通过hash函数将其映射到hash环之上

缓存节点映射

选取缓存节点的IP或者机器名称通过同一个hash函数将其映射到hash环之上

缓存对象绑定缓存节点

经过以上步骤，缓存对象和缓存节点都已经使用同一个hash函数映射到了同一个hash环上了，接下来选定缓存对 象，沿着该hash环顺时针方向寻找缓存节点， 找到的第一个缓存节点就是该缓存对象的存放节点,上述流程如下图所示：

下面来看一下缓存节点的变动对已经分配的缓存带来的影响： 假设D2所在的服务器挂掉了，那么D2所在节点的缓存将会失效，D2将会顺时针寻找下一个缓存节点来进行存放缓存数据，这样旧的缓存数据都还继续对外提供服务， 如下图所示：

小结

上述hash过程解决了缓存节点变更导致的缓存大批量失效的问题，但是这种方案仍然有不完美的地方:

  • hash冲突可能会导致某一台缓存节点负载过重
  • hash的查找效率退化成了链表的查找效率

为了解决第一个问题，引入了虚拟节点，虚拟节点可以认为是实际节点的一个镜像，这样可以将hash环划分的更均匀、随机，缓存也就分布的更均匀。

第二个问题是由于分布式缓存中不同的缓存节点对其他缓存节点的信息一无所知（没有一个controller的角色存在），这样查找的过程就成了链表的查找。为了解决第二个问题，给每一个缓存节点增加一个 跳转链表，该跳转表记录的是距离该缓存节点1、2、4距离的数字存放的节点，这样不论查询落到哪一个查询节点都可以在log(k)的时间复杂度内确定缓存所在的桶。