上一篇文章以生活场景为例，介绍了RPC中一些核心和常用的技术。（什么是RPC？我们为什么要学习RPC？）在负载均衡的时候我们提到了一个“一致性Hash”，这个在RPC之外的很多场景也有使用。引言在业务开发中，我们经常会把数据持久化到数据库中。如果需要读取这些数据，除了直接从数据库中读取外，为了减轻数据库的访问压力，提高访问速度，我们引入了更多的缓存来访问数据。读取数据的过程一般如下：图1：添加到缓存中的数据读取过程对于分布式缓存，不同对象的数据存储在不同的机器上。为了实现这些缓存机器的负载均衡，可以通过公式1来定位对象缓存的存储机器：m=hash(o)modn——公式1其中o为对象名称，n为编号ofmachines，m是机器的编号，hash是哈希函数。图2中的负载平衡器使用等式1将客户端对不同对象的请求分配到不同的机器上执行。例如，对于对象o，经过式1的计算，得到m的值为3，那么所有对对象o的读和存储请求，都发送给机器3执行。图2：如何使用Hash取模实现负载均衡式1在大多数情况下可以很好地工作，但是当机器需要扩展或机器宕机时，事情就变得困难了。当机器扩容，需要增加缓存机器时，负载均衡器使用的公式变为：m=hash(o)mod(n+1)——公式2当机器宕机，机器数量为减一，负载均衡器使用的公式就变成了：m=hash(o)mod(n-1)——公式3下面我们以机器扩容的情况为例，说明简单的取模方法会带来哪些问题.假设机器数量从3台变为4台，那么通过公式1计算出来的对象o1的m值为2，但是通过公式2计算出来的m的值可能是0,1,2,3（3t+2的整数对4取模，其取值可能为0、1、2、3，读者可自行验证），缓存访问失败的可能性约为75%（3/4）。该比率随着机器集群规模的增加而线性增加。当1台机器加到99台机器上时，故障概率为99%（99/100）。这样的结果显然是不可接受的，因为这会导致数据库访问压力急剧增加，严重时还可能导致数据库宕机。一致性哈希算法正是解决这类问题的方法。可以保证当机器数量增加或减少时，对缓存访问攻击概率的影响最小。下面详细说一下一致性哈希算法的具体过程。一致性哈希环一致性哈希算法是通过一种称为一致性哈希环的数据结构来实现的。这个环的起点是0，终点是2^32-1，起点和终点相连。环中间的整数是逆时针分布的，所以这个环的整数分布范围是[0,2^32-1]，如下图3所示：图3：ConsistentHashRing将对象放入HashRing假设现在我们有4个对象，分别是o1,o2,o3,o4，用哈希函数计算这4个对象的哈希值（范围是0~2^32-1）：hash(o1)=m1hash(o2)=m2hash(o3)=m3hash(o4)=m4将m1、m2、m3、m4的4个值放到哈希环上得到如下图4：图4：ConsistencyHashRingwithObjectsPlacedMachines哈希环使用相同的哈希函数，我们也将机器放在哈希环中。假设我们有三台缓存机器，分别是c1，c2，c3，用hash函数计算这三台机器的hash值：hash(c1)=t1hash(c2)=t2hash(c3)=t3andt1,t2,t3三个值放在哈希环上，得到如下图5：图5：放置机器一致的哈希环为对象选择机器将对象和机器都放在后同一个hashring，在hashring上找距离顺时针方向距离这个对象hash值最近的机器就是这个对象所属的机器。比如对于对象o2，sequenceneedle找到最近的机器是c1，那么机器c1就会缓存对象o2。而机器c2缓存o3、o4，机器c3缓存对象o1。图6：为一致性Hash环上的对象选择机器，应对机器的增减对于线上业务，增加或减少一台机器的部署是很常见的。比如增加机器c4的部署，在哈希环的机器c3和c2之间增加机器c4。此时，只需要将机器c3和c4之间的对象重新分配给新机器。对于我们的示例，只有对象o4被重新分配给c4，其他对象仍在原始机器上。如图7所示：图7：添加机器后的consistentHash环的结构上面说过，使用简单的取模方法，在添加新机器时会导致大部分缓存失效，使用consistenthash算法后，这种情况将大大改善。前面说过，3台机器变成4台机器后，缓存失败率只有25%（失败率为75%）。使用一致性哈希算法，理想情况下，缓存失败率为75%。而且，随着机器尺寸的增大，故障率会进一步提高。增加一台到99台机器后，恢复率将达到99%，大大减轻了增加缓存机器带来的数据库访问压力。再比如，让机器c1下线（当然也有可能是机器c1宕机了），此时只需要将原来分配给机器c1的对象重新分配给新的机器即可。对于我们的示例，只有对象o2被重新分配给机器c3，其他对象仍在原始机器上。如图8所示：图8：减少机器数量后的一致性Hash环虚拟节点结构上面说的过程基本上就是一致性哈希的基本原理，但是还有一个小问题。新增加的机器c4只分担机器c2的负载，机器c1和c3的负载并没有因为机器c4的增加而减少负载压力。如果四台机器的性能是一样的，那么这个结果就不是我们想要的了。为此，我们引入虚拟节点来解决负载不均衡的问题。将每台物理机虚拟成一组虚拟机，并将虚拟机放在哈希环上。如果需要确定目标机，先确定目标虚拟机，再由虚拟机确定物理机。说起来有点复杂，其实过程很简单。还是用上面的例子，如果一开始有缓存机器c1、c2、c3，那么每个缓存机器对应三个虚拟节点，其一致的哈希环结构如图9所示：图9：机器c1，c2和c3一致的Hash环结构假设对于对象o1，它对应的虚拟节点是c11，虚拟节点c11对象缓存机器c1，所以对象o1分配给机器c1。新增一台缓存机c4，其对应的虚拟节点为c41、c42、c43。将这三个虚拟节点添加到哈希环中，得到的哈希环结构如图10所示：图10：机器c1、c2、c3，与c4一致的哈希环结构。新增的缓存机c4对应一组虚拟节点c41、c42、c43。添加到哈希环后，受影响的虚拟节点包括c31、c22、c11（找到第一个节点），这三个虚拟节点分别对应机器c3、c2、c1。即新增一台机器同时影响原来的三台机器。理想情况下，新加入的机器平均分担原有机器的负载，这就是虚拟节点的好处。而且新机器c4加入后，只有25%（1/4）的对象分配受到影响，也就是说攻击率还是75%，这和一致性哈希得到的结果是一样的没有虚拟节点的算法。总结一致性哈希算法解决了分布式环境下机器数量增减时，简单的取模运算无法获得较高攻击率的问题。通过使用虚拟节点，一致性哈希算法可以平均分担机器的负载，使该算法更符合实际。为此，一致性哈希算法在分布式系统中被广泛使用。【本文为专栏作家“侯书城”原创稿件，转载请通过作者微信公众号“Tomcat物语”获得授权】点此查看本作者更多好文
