乐趣区

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

jiezi

在 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。

这也阐明：node 与 virtual 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 反对咱们！

微信交换群

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

退出移动版