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

前言
　　之前也了解到过一致性哈希算法，但是没有用go实现过，刚好最近看GeeCache，动手实现下一致性哈希算法
正文:
　　我们先来想下一致性哈希算法的数据结构含有哪些内容:
　　1.map 用来存储虚拟节点对应的真实节点，是一个映射表
　　2.hash 哈希函数
　　3.key 哈希环，存储所有虚拟节点
　　4.replicas 虚拟节点的倍数
了解过一致性哈希算法的朋友，应该是能够理解为什么要有上面的内容，下面我们用代码实现下:

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

复制代码

下面，我们实现获取节点的方法:
　　将key经过hash运算，在哈希环上顺时针找到第一个节点，存入

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

复制代码

添加节点的方法

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

复制代码

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

| 不骄不躁，保持学习

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！