乐趣区

关于golang:一文搞懂一致性hash的原理和实现

在 go-zero 的分布式缓存零碎分享里,Kevin 重点讲到过一致性 hash 的原理和分布式缓存中的实际。本文来具体讲讲一致性 hash 的原理和在 go-zero 中的实现。

以存储为例,在整个微服务零碎中,咱们的存储不可能说只是一个单节点。

  • 一是为了进步稳固,单节点宕机状况下,整个存储就面临服务不可用;
  • 二是数据容错,同样单节点数据物理损毁,而多节点状况下,节点有备份,除非互为备份的节点同时损毁。

那么问题来了,多节点状况下,数据应该写入哪个节点呢?

hash

所以实质来讲:咱们须要一个能够将 输出值“压缩”并转成更小的值,这个值通常情况下是惟一、格局极其紧凑的,比方 uint64

  • 幂等:每次用同一个值去计算 hash 必须保障都能失去同一个值

这个就是 hash 算法实现的。

然而采取一般的 hash 算法进行路由,如:key % N。有一个节点因为异样退出了集群或者是心跳异样,这时再进行 hash route,会造成大量的数据从新 散发 到不同的节点。节点在承受新的申请时候,须要重新处理获取数据的逻辑:如果是在缓存中,容易引起 缓存雪崩

此时就须要引入 consistent hash 算法了。

consistent hash

咱们来看看 consistent hash 是怎么解决这些问题的:

rehash

先解决大量 rehash 的问题:

如上图,当退出一个新的节点时,影响的 key 只有 key31,新退出(剔除)节点后,只会影响该节点左近的数据。其余节点的数据不会收到影响,从而解决了节点变动的问题。

这个正是:枯燥性。这也是 normal hash 算法无奈满足分布式场景的起因。

数据歪斜

其实上图能够看出:目前少数的 key 都集中在 node 1 上。如果当 node 数量比拟少的状况下,能够回引发少数 key 集中在某个 node 上,监控时发现的问题就是:节点之间负载不均。

为了解决这个问题,consistent hash 引入了 virtual node 的概念。

既然是负载不均,咱们就人为地结构一个平衡的场景进去,然而理论 node 只有这么多。所以就应用 virtual node 划分区域,而理论服务的节点仍然是之前的 node。

具体实现

先来看看 Get()

Get

先说说实现的原理:

  1. 计算 key 的 hash
  2. 找到第一个匹配的 virtual node 的 index,并取到对应的 h.keys[index]:virtual node hash 值
  3. 对应到这个 ring 中去寻找一个与之匹配的 actual node

其实咱们能够看到 ring 中获取到的是一个 []node。这是因为在计算 virtual node hash,可能会产生 hash 抵触,不同的 virtual node hash 对应到一个理论 node。

这也阐明:nodevirtual node 是一对多的关系。而外面的 ring 就是上面这个设计:

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

  1. virtual node 作为值域划分。key 去获取 node,从划分根据上是以 virtual node 作为边界
  2. virtual node 通过 hash,在对应关系上保障了不同的 node 调配的 key 是大抵平均的。也就是 打散绑定
  3. 退出一个新的 node,会对应调配多个 virtual node。新节点能够负载多个原有节点的压力,从全局看,较容易实现扩容时的负载平衡。

Add Node

看完 Get 其实大抵就晓得整个一致性 hash 的设计:

type ConsistentHash struct {
  hashFunc Func                            // hash 函数
  replicas int                            // 虚构节点放大因子
  keys     []uint64                    // 存储虚构节点 hash
  ring     map[uint64][]interface{}                    // 虚构节点与理论 node 的对应关系
  nodes    map[string]lang.PlaceholderType    // 理论节点存储【便于疾速查找,所以应用 map】lock     sync.RWMutex
}

好了这样,根本的一个一致性 hash 就实现齐备了。

具体代码:https://github.com/tal-tech/g…

应用场景

结尾其实就说了,一致性 hash 能够宽泛应用在分布式系统中:

  1. 分布式缓存。能够在 redis cluster 这种存储系统上构建一个 cache proxy,自在管制路由。而这个路由规定就能够应用一致性 hash 算法
  2. 服务发现
  3. 散布式调度工作

以上这些分布式系统中,都能够在负载平衡模块中应用。

我的项目地址

https://github.com/tal-tech/go-zero

欢送应用 go-zero 并 star 反对咱们!

微信交换群

关注『微服务实际 』公众号并点击 交换群 获取社区群二维码。

退出移动版