说起一致性Hash算法，很多人的第一反应就是Memcached的路由算法。当Memcached服务分布式部署后，在一台机器上的数据缓存，在其他机器上是不存在的，我们请求缓存数据时，必须先找到拥有该数据的服务器。所以，我们需要一种路由算法来负责根据缓存数据的Key计算得到对应的Memcached服务器地址。
Memcached集群内部服务器不支持相互通信，正由于这种互不通信的机制，能使得Memcached集群可以做到几乎无限制的线性伸缩。但正因为Memcached服务器之间不会互相通信，所以查找缓存对应机器的路由算法就必须由客户端自行实现。
余数Hash算法
余数Hash算法是非常简单的路由算法，用缓存数据Key的哈希值对服务器数目求余，结果即为对应的服务器编号。因为计算得到的Hash值具有随机性，所以使用余数Hash算法可以保证缓存数据在各个Memcached服务器之间比较均匀的分布。
对于服务器数量固定的Memcached集群而言，余数Hash算法能很好的完成查找任务。但是集群容量一旦变换，就会遇到缓存无法命中的问题。当从N台服务器扩容到N+1台时，缓存不能命中的概率是N/(N+1)，当集群服务器数量很大时，几乎所有的缓存都会失效。
一旦缓存失效，压力就落到数据库上了，这对于服务来说是个灾难。
一致性Hash算法
为了解决集群容量变化带来的缓存失效问题，目前比较流行的路由算法是一致性Hash算法。
算法流程
一致性Hash算法是一个比较简单的算法，把Key值和服务器节点值都Hash到一个长度为0~2^32的整数环上，然后根据Key的Hash值和节点的Hash值，找到Key所对应的节点:
从上图可以很直观的看出一致性Hash算法的过程：
构造一个长度为0~2^32的整数环（一致性Hash环）
将Memcached服务器节点名称进行Hash后，放置在Hash环上（NODE 0、1、2）
计算缓存数据Key值的Hash，同样放置在Hash环上
在Hash环上顺时针查找离这个Key的Hash值最近的服务器节点，即为该缓存数据所存储的节点
集群容量变化
当集群扩容，增加了一个新节点NODE3后，将NODE3放入Hash环中，并对缓存数据Key进行重新查找，结果如下图：
可以看出，增加一个节点，仅仅影响这个新节点（NODE3）沿Hash环逆时针到前一个节点（NODE2）间的缓存数据，对于其他缓存数据，还能继续命中。随着集群规模增大，增加新节点影响到的数据命中就越小。此时虽然仍有小部分数据缓存无法命中，但是比例很低，通常不会对数据库造成致命的压力。
虚拟节点
除了影响缓存命中，直接增加一个节点后，对原有节点的负载也会有影响。比如NODE1的一部分缓存分配到了NODE3上，而NODE0和NODE2还是和以前一样，这样就造成了负载的不均衡。解决这个问题也很简单，那就是虚拟节点。
将每台物理服务器虚拟为一组虚拟服务器，然后将这些虚拟服务器的Hash值放置在Hash环上，先由Key找到虚拟服务器节点，然后再对应到物理服务器地址。
当加入一台新的服务器时，因为虚拟的节点是分散的，就会较均匀的影响原来集群中的所有服务器，就相当于分摊了负载。虚拟节点数越多，各个物理节点的负载就越均衡。但是太多的虚拟节点又会影响性能，所以要根据实际情况去选择虚拟节点的数量。