分布式缓存中的一致性Hash算法

分布式缓存中的一致性Hash算法：在分布式缓存服务器集群中，所有的缓存服务器中缓存的数据各不相同，这时路由算法就至关重要了，路由算法负责根据应用程序输入的缓存数据KEY计算得到应该将数据写入到哪台缓存服务器（写缓存） 。 或则 应该从哪台缓存服务器读取数据（读缓存）。也就是说根据KEY存入某台缓存服务器S1，当应用使用同样的Key时能从这台缓存服务器S1中读出缓存。

这时的路由算法和负载均衡算法一样至关重要，路由算法决定着究竟该访问集群中的哪台服务器，先看一个简单的路由算法。

比方说，字符串str对应的HashCode是51、服务器的数目是3，取余数得到0，str对应节点Node0，所以路由算法把str路由到Node0服务器上。由于HashCode随机性比较强，所以使用余数Hash路由算法就可以保证缓存数据在整个缓存服务器集群中有比较均衡的分布。

如果不考虑服务器集群的伸缩性，那么余数Hash算法几乎可以满足绝大多数的缓存路由需求，但是当分布式缓存集群需要扩容的时候，就会出现很严重的问题

就假设缓存服务器集群由3台变为4台吧，更改服务器列表，仍然使用余数Hash，51对4的余数是3，对应Node3，但是str原来是存在Node0上的，这就导致了缓存没有命中。如果这么说不够明白，那么不妨举个例子，原来有HashCode为0~19的20个数据，那么：

现在我扩容到4台，加粗标红的表示命中：

这时就是只有6个命中了；比例也就是6/20。

如果我扩容到20+的台数，只有前三个HashCode对应的Key是命中的，也就是15%。当然这只是个简单例子，现实情况肯定比这个复杂得多，不过足以说明，使用余数Hash的路由算法，在扩容的时候会造成大量的数据无法正确命中（其实不仅仅是无法命中，那些大量的无法命中的数据还在原缓存中在被移除前占据着内存）。这个结果显然是无法接受的，在网站业务中，大部分的业务数据度操作请求上事实上是通过缓存获取的，只有少量读操作会访问数据库，因此数据库的负载能力是以有缓存为前提而设计的。当大部分被缓存了的数据因为服务器扩容而不能正确读取时，这些数据访问的压力就落在了数据库的身上，这将大大超过数据库的负载能力，严重的可能会导致数据库宕机。

这个问题有解决方案，解决步骤为： （1）在网站访问量低谷，通常是深夜，技术团队加班，扩容、重启服务器。 （2）通过模拟请求的方式逐渐预热缓存，使缓存服务器中的数据重新分布。

下面介绍一个更加优秀的路由算法：一致性Hash算法。

一致性Hash算法通过一个叫做一致性Hash环的数据结构实现Key到缓存服务器的Hash映射，下面看一下一个示意图：

具体算法过程为：先构造一个长度为2^32的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2^32-1]）将缓存服务器节点放置在这个Hash环上，然后根据需要缓存的数据的Key值计算得到其Hash值（其分布也为[0, 2^32-1]），然后在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。

就如同图上所示，三个Node点分别位于Hash环上的三个位置，然后Key值根据其HashCode，在Hash环上有一个固定位置，位置固定下之后，Key就会顺时针去寻找离它最近的一个Node，把数据存储在这个Node的缓存服务器中。使用Hash环如果加了一个节点会怎么样，看一下：

看到我加了一个Node4节点，只影响到了一个Key值的数据，本来这个Key值应该是在Node1服务器上的，现在要去Node4了。采用一致性Hash算法，的确也会影响到整个集群，但是影响的只是加粗的那一段而已，相比余数Hash算法影响了远超一半的影响率，这种影响要小得多。更重要的是，集群中缓存服务器节点越多，增加节点带来的影响越小，很好理解。换句话说，随着集群规模的增大，继续命中原有缓存数据的概率会越来越大，虽然仍然有小部分数据缓存在服务器中不能被读到，但是这个比例足够小，即使访问数据库，也不会对数据库造成致命的负载压力。

对于具体应用，这个长度为2^32的一致性Hash环通常使用二叉查找树实现，至于二叉查找树，就是算法的问题了。

但是：上面的算法还有一个小问题：带来了缓存服务器负载不均衡。 新加入的Node4只影响到了它的下一个节点，并没有影响到其他的两个节点，导致4台机器的负载压力不一样。比如说有Hash环上有A、B、C三个服务器节点，分别有100个请求会被路由到相应服务器上。现在在A与B之间增加了一个节点D，这导致了原来会路由到B上的部分节点被路由到了D上，这样A、C上被路由到的请求明显多于B、D上的，原来三个服务器节点上均衡的负载被打破了。某种程度上来说，这失去了负载均衡的意义，因为负载均衡的目的本身就是为了使得目标服务器均分所有的请求。

在计算机领域有句名言：计算机的任何问题都可以通过增加一个虚拟层来解决。

解决上诉的一致性hash 算法带来的负载不均衡也可以通过加一个虚拟曾来解决。其工作原理是：将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。采取这样的方式，就可以有效地解决增加或减少节点时候的负载不均衡的问题。

至于一个物理节点应该拆分为多少虚拟节点，下面可以先看一张图：

横轴表示需要为每台福利服务器扩展的虚拟节点倍数，纵轴表示的是实际物理服务器数。可以看出，物理服务器很少，需要更大的虚拟节点；反之物理服务器比较多，虚拟节点就可以少一些。比如有10台物理服务器，那么差不多需要为每台服务器增加100~200个虚拟节点才可以达到真正的负载均衡。