【golang】分布式缓存 - 一致性哈希算法

前言

最近两个月去博客园写文章了，好久没有更新博客了。现在把之前写的文章搬运一下~

正文

我们先来想下一致性哈希算法的数据结构含有哪些内容:

1.map 用来存储虚拟节点对应的真实节点，是一个映射表

2.hash 哈希函数

3.key 哈希环，存储所有虚拟节点

4.replicas 虚拟节点的倍数

了解过一致性哈希算法的朋友，应该是能够理解为什么要有上面的内容，下面我们用代码实现下:

type Hash func([]byte) uint32
type Map struct {
    hash    Hash  // hash算法
    key     []int // hash环
    replicas int  // 虚拟节点的数量
    m      map[int]string // 虚拟节点和真实节点的映射表
}
1
2
3
4
5
6
7

下面，我们实现获取节点的方法:

将key经过hash运算，在哈希环上顺时针找到第一个节点，存入

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))   // 获取key对应的hash值

    idx := sort.Search(len(m.key), func(i int) bool { // 顺时针找到第一个虚拟节点
        return m.key[i] >= hash
    })
    return m.m[m.key[idx % len(m.key)]]  //返回对应的真实节点:记得对哈希环取余
}
1
2
3
4
5
6
7
8

添加节点的方法：

func (m *Map) Add(key ...string)  {
    for _,realKey := range key{
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i)+realKey)))  // 真实节点对应的虚拟节点
            m.key = append(m.key,hash)  // 添加到换上
            m.m[hash] = realKey       // 添加到映射表上
        }
    }
    sort.Ints(m.key)    // 递增排序，方便顺时针查找
}
1
2
3
4
5
6
7
8
9
10

以上就是一致性哈希的实现方法，也挺好理解的。记录下~

| 不骄不躁，保持学习