乐趣区

关于golang:一文讲透一致性哈希的原理和实现

jiezi

为什么须要一致性哈希

首先介绍一下什么是哈希

Hash，个别翻译做散列，或音译为哈希，是把任意长度的输出（又叫做预映射 pre-image）通过散列算法变换成固定长度的输入，该输入就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输出的空间，不同的输出可能会散列成雷同的输入，所以不可能从散列值来确定惟一的输出值。简略的说就是一种将任意长度的消息压缩到某一固定长度的音讯摘要的函数。

在分布式缓存服务中，常常须要对服务进行节点增加和删除操作，咱们心愿的是节点增加和删除操作尽量减少数据 - 节点之间的映射关系更新。

如果咱们应用的是哈希取模(hash(key)%nodes ) 算法作为路由策略:

哈希取模的毛病在于如果有节点的删除和增加操作，对 hash(key)%nodes 后果影响范畴太大了，造成大量的申请无奈命中从而导致缓存数据被从新加载。

基于下面的毛病提出了一种新的算法：一致性哈希。一致性哈希能够实现节点删除和增加只会影响一小部分数据的映射关系，因为这个个性哈希算法也经常用于各种均衡器中实现零碎流量的平滑迁徙。

一致性哈希工作原理

首先对节点进行哈希计算，哈希值通常在 2^32-1 范畴内。而后将 2^32-1 这个区间首尾连贯形象成一个环并将节点的哈希值映射到环上，当咱们要查问 key 的指标节点时，同样的咱们对 key 进行哈希计算，而后顺时针查找到的第一个节点就是指标节点。

依据原理咱们剖析一下节点增加和删除对数据范畴的影响。

  1. 节点增加

    只会影响新增节点与前一个节点（新增节点逆时针查找的第一个节点）之间的数据。

  2. 节点删除

    只会影响删除节点与前一个节点（删除节点逆时针查找的第一个节点）之间的数据。

这样就完了吗？还没有，试想一下如果环上的节点数量非常少，那么十分有可能造成数据分布不均衡，实质上是环上的区间散布粒度太粗。

怎么解决呢？不是粒度太粗吗？那就退出更多的节点，这就引出了一致性哈希的虚构节点概念，虚构节点的作用在于让环上的节点区间散布粒度变细。

一个实在节点对应多个虚构节点，将虚构节点的哈希值映射到环上，查问 key 的指标节点咱们先查问虚构节点再找到实在节点即可。

代码实现

基于下面的一致性哈希原理，咱们能够提炼出一致性哈希的外围性能：

  1. 增加节点
  2. 删除节点
  3. 查问节点

咱们来定义一下接口：

ConsistentHash interface {Add(node Node)
    Get(key Node) Node
    Remove(node Node)
}

事实中不同的节点服务能力因硬件差别可能各不相同，于是咱们心愿在增加节点时能够指定权重。反馈到一致性哈希当中所谓的权重意思就是咱们心愿 key 的指标节点命中概率比例，一个实在节点的虚构节点数量多则意味着被命中概率高。

在接口定义中咱们能够减少两个办法：反对指定虚构节点数量增加节点，反对按权重增加。实质上最终都会反馈到虚构节点的数量不同导致概率分布差别。

指定权重时：理论虚构节点数量 = 配置的虚构节点 * weight/100

ConsistentHash interface {Add(node Node)
    AddWithReplicas(node Node, replicas int)
    AddWithWeight(node Node, weight int)
    Get(key Node) Node
    Remove(node Node)
}

接下来思考几个工程实现的问题：

  1. 虚构节点如何存储？

    很简略，用列表（切片）存储即可。

  2. 虚构节点 – 实在节点关系存储

    map 即可。

  3. 顺时针查问第一个虚构节点如何实现

    让虚构节点列表放弃有序，二分查找第一个比 hash(key) 大的 index，list[index] 即可。

  4. 虚构节点哈希时会有很小的概率呈现抵触，如何解决呢？

    抵触时意味着这一个虚构节点会对应多个实在节点，map 中 value 存储实在节点数组，查问 key 的指标节点时对 nodes 取模。

  5. 如何生成虚构节点

    基于虚构节点数量配置 replicas，循环 replicas 次顺次追加 i 字节 进行哈希计算。

go-zero 源码解析

core/hash/consistenthash.go

具体正文可查看：https://github.com/Ouyangan/g…

花了一天工夫把 go-zero 源码一致性哈希源码看完，写的真好啊，各种细节都思考到了。

go-zero 应用的哈希函数是 MurmurHash3，GitHub：https://github.com/spaolacci/…

go-zero 并没有进行接口定义，没啥关系，间接看构造体 ConsistentHash：

// Func defines the hash method.
// 哈希函数
Func func(data []byte) uint64

// A ConsistentHash is a ring hash implementation.
// 一致性哈希
ConsistentHash struct {
    // 哈希函数
    hashFunc Func
    // 确定 node 的虚构节点数量
    replicas int
    // 虚构节点列表
    keys []uint64
    // 虚构节点到物理节点的映射
    ring map[uint64][]interface{}
    // 物理节点映射，疾速判断是否存在 node
    nodes map[string]lang.PlaceholderType
    // 读写锁
    lock sync.RWMutex
}

key 和虚构节点的哈希计算

在进行哈希前要先将 key 转换成 string

// 能够了解为确定 node 字符串值的序列化办法
// 在遇到哈希抵触时须要从新对 key 进行哈希计算
// 为了缩小抵触的概率后面追加了一个质数 prime 来减小抵触的概率
func innerRepr(v interface{}) string {return fmt.Sprintf("%d:%v", prime, v)
}

// 能够了解为确定 node 字符串值的序列化办法
// 如果让 node 强制实现 String()会不会更好一些？func repr(node interface{}) string {return mapping.Repr(node)
}

这里 mapping.Repr 里会判断 fmt.Stringer 接口，如果合乎，就会调用其 String 办法。go-zero 代码如下：

// Repr returns the string representation of v.
func Repr(v interface{}) string {
    if v == nil {return ""}

    // if func (v *Type) String() string, we can't use Elem()
    switch vt := v.(type) {
    case fmt.Stringer:
        return vt.String()}

    val := reflect.ValueOf(v)
    if val.Kind() == reflect.Ptr && !val.IsNil() {val = val.Elem()
    }

    return reprOfValue(val)
}

增加节点

最终调用的是 指定虚构节点增加节点办法

// 扩容操作，减少物理节点
func (h *ConsistentHash) Add(node interface{}) {h.AddWithReplicas(node, h.replicas)
}

增加节点 – 指定权重

最终调用的同样是 指定虚构节点增加节点办法

// 按权重增加节点
// 通过权重来计算方法因子，最终管制虚构节点的数量
// 权重越高，虚构节点数量越多
func (h *ConsistentHash) AddWithWeight(node interface{}, weight int) {
    replicas := h.replicas * weight / TopWeight
    h.AddWithReplicas(node, replicas)
}

增加节点 – 指定虚构节点数量

// 扩容操作，减少物理节点
func (h *ConsistentHash) AddWithReplicas(node interface{}, replicas int) {
    // 反对可反复增加
    // 先执行删除操作
    h.Remove(node)
    // 不能超过放大因子下限
    if replicas > h.replicas {replicas = h.replicas}
    // node key
    nodeRepr := repr(node)
    h.lock.Lock()
    defer h.lock.Unlock()
    // 增加 node map 映射
    h.addNode(nodeRepr)
    for i := 0; i < replicas; i++ {
        // 创立虚构节点
        hash := h.hashFunc([]byte(nodeRepr + strconv.Itoa(i)))
        // 增加虚构节点
        h.keys = append(h.keys, hash)
        // 映射虚构节点 - 实在节点
        // 留神 hashFunc 可能会呈现哈希抵触，所以采纳的是追加操作
        // 虚构节点 - 实在节点的映射对应的其实是个数组
        // 一个虚构节点可能对应多个实在节点，当然概率十分小
        h.ring[hash] = append(h.ring[hash], node)
    }
    // 排序
    // 前面会应用二分查找虚构节点
    sort.Slice(h.keys, func(i, j int) bool {return h.keys[i] < h.keys[j]
    })
}

删除节点

// 删除物理节点
func (h *ConsistentHash) Remove(node interface{}) {
    // 节点的 string
    nodeRepr := repr(node)
    // 并发平安
    h.lock.Lock()
    defer h.lock.Unlock()
    // 节点不存在
    if !h.containsNode(nodeRepr) {return}
    // 移除虚构节点映射
    for i := 0; i < h.replicas; i++ {
        // 计算哈希值
        hash := h.hashFunc([]byte(nodeRepr + strconv.Itoa(i)))
        // 二分查找到第一个虚构节点
        index := sort.Search(len(h.keys), func(i int) bool {return h.keys[i] >= hash
        })
        // 切片删除对应的元素
        if index < len(h.keys) && h.keys[index] == hash {
            // 定位到切片 index 之前的元素
            // 将 index 之后的元素（index+1）前移笼罩 index
            h.keys = append(h.keys[:index], h.keys[index+1:]...)
        }
        // 虚构节点删除映射
        h.removeRingNode(hash, nodeRepr)
    }
    // 删除实在节点
    h.removeNode(nodeRepr)
}

// 删除虚构 - 实在节点映射关系
// hash - 虚构节点
// nodeRepr - 实在节点
func (h *ConsistentHash) removeRingNode(hash uint64, nodeRepr string) {
    // map 应用时应该校验一下
    if nodes, ok := h.ring[hash]; ok {
        // 新建一个空的切片, 容量与 nodes 保持一致
        newNodes := nodes[:0]
        // 遍历 nodes
        for _, x := range nodes {
            // 如果序列化值不雷同，x 是其余节点
            // 不能删除
            if repr(x) != nodeRepr {newNodes = append(newNodes, x)
            }
        }
        // 残余节点不为空则从新绑定映射关系
        if len(newNodes) > 0 {h.ring[hash] = newNodes
        } else {
            // 否则删除即可
            delete(h.ring, hash)
        }
    }
}

查问节点

// 依据 v 顺时针找到最近的虚构节点
// 再通过虚构节点映射找到实在节点
func (h *ConsistentHash) Get(v interface{}) (interface{}, bool) {h.lock.RLock()
    defer h.lock.RUnlock()
    // 以后没有物理节点
    if len(h.ring) == 0 {return nil, false}
    // 计算哈希值
    hash := h.hashFunc([]byte(repr(v)))
    // 二分查找
    // 因为每次增加节点后虚构节点都会从新排序
    // 所以查问到的第一个节点就是咱们的指标节点
    // 取余则能够实现环形列表成果，顺时针查找节点
    index := sort.Search(len(h.keys), func(i int) bool {return h.keys[i] >= hash
    }) % len(h.keys)
    // 虚构节点 -> 物理节点映射
    nodes := h.ring[h.keys[index]]
    switch len(nodes) {
    // 不存在实在节点
    case 0:
        return nil, false
    // 只有一个实在节点，间接返回
    case 1:
        return nodes[0], true
    // 存在多个实在节点象征这呈现哈希抵触
    default:
        // 此时咱们对 v 从新进行哈希计算
        // 对 nodes 长度取余失去一个新的 index
        innerIndex := h.hashFunc([]byte(innerRepr(v)))
        pos := int(innerIndex % uint64(len(nodes)))
        return nodes[pos], true
    }
}

我的项目地址

https://github.com/zeromicro/go-zero

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

微信交换群

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

退出移动版