场景

如果有N个缓存服务器，将一个对象缓存到某个服务器上，也许可以这样计算对象的hash值，然后映射到某个cache上：

hash(object) % N

这样做存在这两个问题：

  1. 如果其中一台服务器发生故障或者被移除，则映射到该服务器上的所有对象都会失效，而且映射公式就变为：hash(object) % (N-1)
  2. 相反，如果缓存已经不满足需求，需要增加缓存服务器时，映射公式变为：hash(object) % (N+1)

这就意味着几乎所有的cache都会失效，也有两种解决方案：

  1. 清空所有缓存服务器，重新建立缓存。本来缓存就是为了减小数据库压力而设计的，这样做对后端来说，如同一场灾难，严重的可能会到时数据库崩溃。所以，一般应该不会这样做。
  2. 夜深人静，流量最小的时候，使缓存服务器中的数据重新分布。

这两种做法的成本都非常大。

一致性hash算法

基本原理

简单来说，一致性hash算法主要做的就是在添加或者移除一个缓存服务器的时候，能够尽可能小的改变已存在的映射关系。一致性hash算法用的也是取模的方法，只不过是对2^32取模：

  1. 先构造一个0～2^32-1的整数环，也称一致性hash环，也可以把它看成一个首尾相接的圆环
  2. 根据节点服务器的名称计算hash值，对hash值进行取模，然后将服务器节点放置在hash环上
  3. 根据需要缓存数据的key值计算hash值，对hash值进行取模，接着在hash环上顺时针查找离这个值最近的服务器节点
  4. 完成映射查找

虚拟节点

同样一致性hash算法也有缺点，在实际映射中，有可能缓存服务器会被映射到环上的其中一段弧上，这就造成大部分对象可能会集中缓存到某一台服务器上，这就诞生了虚拟节点。

虚拟节点就是实际节点的一个影子，或者说是复制品，一个实际节点对应多个虚拟节点，同样将虚拟节点映射到hash环上，这样一来缓存的分布就均衡多了，减少hash环的偏斜所带来的影响。

hash环上的节点越多，缓存被均匀分布的概率也就越大