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

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

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

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

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

hash

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

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

hash

hashkey % Nhash route散发

consistent hash

consistent hash

consistent hash

rehash

rehash

key31

normal hash

数据歪斜

node 1node

consistent hashvirtual node

virtual node

具体实现

Get()

Get

先说说实现的原理：

keyvirtual nodeh.keys[index]ringactual node

ring[]nodevirtual node hashvirtual node hash

nodevirtual nodering

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

virtual nodekeynodevirtual nodevirtual nodehashvirtual node

Add Node

Get

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能够宽泛应用在分布式系统中：

redis clustercache proxy

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

我的项目地址

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

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

微信交换群

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