groupcache源码(六)-一致性哈希实现

一. 简介

groupcache分布式集群下，使用了一致性哈希算法，代码实现比较简单

二. 基本结构

type Map struct {
	hash     Hash // 缓存key进行hash得方法
	replicas int // 虚拟节点数 
	keys     []int // Sorted // 所有节点hash
	hashMap  map[int]string // hash的key和节点的映射
}

Map的字段比较少, keys切片数组可以看成一个环，寻找值时，索引为切片的len时变为0, 就变成了环

三. 节点添加

// Add adds some keys to the hash.
func (m *Map) Add(keys ...string) {
// 遍历所有节点
	for _, key := range keys {
// 循环所有虚拟节点
		for i := 0; i < m.replicas; i++ {
// key和索引i 组成新的虚拟节点
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
// 存储所有虚拟节点
			m.keys = append(m.keys, hash)
// 保存虚拟节点和原始信息的映射
			m.hashMap[hash] = key
		}
	}
// 排序
	sort.Ints(m.keys)
}

1. 节点key和i组成虚拟节点，防止数据倾斜

 2.hashMap方便通过虚拟节点直接查到原始节点信息

3. 排序，使数据组成哈希环

四. 节点获取

// Get gets the closest item in the hash to the provided key.
func (m *Map) Get(key string) string {
// 判断是否为空
	if m.IsEmpty() {
		return ""
	}

// 计算缓存key的hash值 
	hash := int(m.hash([]byte(key)))

	// Binary search for appropriate replica.
// 查找对应的hash值
// 在keys切片中最接近的值
	idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })

	// Means we have cycled back to the first replica.
// 组成环
	if idx == len(m.keys) {
		idx = 0
	}
// 返回对应的节点信息
	return m.hashMap[m.keys[idx]]
}

五. 总结

1. 分布式启动时，将各节点信息注册到Map中，注册节点选择方法

2. 当需要加载数据时，判断是否为分布式，如果是，则根据缓存key在Map中查询出对应的节点

3. 通过http获取该节点缓存数据，按几率将数据加入到hotCache中