一文搞懂一致性hash的原理和实现计算 [复制链接]

在go-zero的分布式缓存系统分享里，Kevin重点讲到过一致性hash的原理和分布式缓存中的实践。本文来详细讲讲一致性hash的原理和在go-zero中的实现。

以存储为例，在整个微服务系统中，我们的存储不可能说只是一个单节点。

一是为了提高稳定，单节点宕机情况下，整个存储就面临服务不可用；

二是数据容错，同样单节点数据物理损毁，而多节点情况下，节点有备份，除非互为备份的节点同时损毁。

那么问题来了，多节点情况下，数据应该写入哪个节点呢？

所以本质来讲：我们需要一个可以将输入值“压缩”并转成更小的值，这个值通常状况下是唯一、格式极其紧凑的，比如uint64：

幂等：每次用同一个值去计算hash必须保证都能得到同一个值

这个就是hash算法完成的。

但是采取普通的hash算法进行路由，如：key%N。有一个节点由于异常退出了集群或者是心跳异常，这时再进行hashroute，会造成大量的数据重新分发到不同的节点。节点在接受新的请求时候，需要重新处理获取数据的逻辑：如果是在缓存中，容易引起缓存雪崩。

此时就需要引入consistenthash算法了。

我们来看看consistenthash是怎么解决这些问题的：

先解决大量rehash的问题：

如上图，当加入一个新的节点时，影响的key只有key31，新加入（剔除）节点后，只会影响该节点附近的数据。其他节点的数据不会受到影响，从而解决了节点变化的问题。

这个正是：单调性。这也是normalhash算法无法满足分布式场景的原因。

其实上图可以看出：目前多数的key都集中在node1上。如果当node数量比较少的情况下，可以回引发多数key集中在某个node上，监控时发现的问题就是：节点之间负载不均。

为了解决这个问题，consistenthash引入了virtualnode的概念。

既然是负载不均，我们就人为地构造一个均衡的场景出来，但是实际node只有这么多。所以就使用virtualnode划分区域，而实际服务的节点依然是之前的node。

先来看看Get()：

先说说实现的原理：

计算key的hash

找到第一个匹配的virtualnode的index，并取到对应的h.keys[index]：virtualnodehash值

对应到这个ring中去寻找一个与之匹配的actualnode

其实我们可以看到ring中获取到的是一个[]node。这是因为在计算virtualnodehash，可能会发生hash冲突，不同的virtualnodehash对应到一个实际node。

这也说明：node与virtualnode是一对多的关系。而里面的ring就是下面这个设计：

这个其实也就表明了一致性hash的分配策略：

virtualnode作为值域划分。key去获取node，从划分依据上是以virtualnode作为边界

virtualnode通过hash，在对应关系上保证了不同的node分配的key是大致均匀的。也就是打散绑定

加入一个新的node，会对应分配多个virtualnode。新节点可以负载多个原有节点的压力，从全局看，较容易实现扩容时的负载均衡。

看完Get其实大致就知道整个一致性hash的设计：

好了这样，基本的一个一致性hash就实现完备了。