Golang一致性哈希算法

groupcache一致性哈希算法

groupcache 中的一致性哈希算法是定义在 consistenthash 文件夹下面的 consistenthash.go 文件里面,一致性哈希算法用于在集群中计算某个 key 所属的具体的节点,我们先写个代码,看具体如何使用,具体代码如下:

package main import ( "fmt" "github.com/golang/groupcache/consistenthash" ) func main(){ fmt.Println("嗨客网(www.haicoder.net)") consistMap := consistenthash.New(5, nil) //模拟集群中的节点 nodes := []string{"NodeA", "NodeB", "NodeC", "NodeD", "NodeE"} //向集群中添加节点 consistMap.Add(nodes...) //键 keys := []string{"Haicoder", "Jobs", "William", "Gates", "Jack", "Tindy"} for _, key := range keys{ //获取某个键所在的节点 node := consistMap.Get(key) fmt.Println(key, "=>", node) } }

执行完毕后,控制台输出如下:

02_groupcache一致性hash算法.png

我们看到,我们首先模拟向集群中添加五个节点,接着,我们将六个键添加到集群中去,最后,我们获取每个键所在的集群的节点。

groupcache一致性哈希源码解析

我们查看 consistenthash.go 文件,首先看到的是 Map 结构体,具体代码如下:

type Hash func(data []byte) uint32 type Map struct { hash Hash replicas int keys []int // Sorted hashMap map[int]string }

一开始,定义了一个 Hash 函数的原型,是一个接受一个 byte 数组类型的参数,返回 uint32 类型返回值的函数,用于将一个 key 值 hash 成一个 32 位的整数。接着,定义了一个 Map 结构体,该结构体包含了四个成员,每个字段的解释如下:

字段 作用
hash 具体使用的哈希函数
replicas 哈希环中虚拟节点的个数
keys 所有的key哈希后的32位整数的集合,经过了排序
hashMap hashMap就是存放具体的对应,将key对应上hash后的32位整数

现在,我们查看 Map 结构提供的所有的接口,一共就提供了四个接口,具体含义如下:

接口 作用
New 创建一个 map 结构
IsEmpty 判断集群是否为空
Add 向集群中添加节点
Get 获取某个键所在的集群节点

现在,我们首先查看 New 接口的具体实现,具体代码如下:

func New(replicas int, fn Hash) *Map { m := &Map{ replicas: replicas, hash: fn, hashMap: make(map[int]string), } if m.hash == nil { m.hash = crc32.ChecksumIEEE } return m }

New 接口其实就是创建 Map 对象并返回,如果没有传入自定义的 hash 函数,那么就使用 crc32.ChecksumIEEE 函数。接着,我们查看 IsEmpty 函数的具体实现,具体代码如下:

// IsEmpty returns true if there are no items available. func (m *Map) IsEmpty() bool { return len(m.keys) == 0 }

该函数其实非常简单,就是判断 map 对象的集群的所有键的长度是否为 0,如果为 0,则返回 true。现在,我们看 Add 函数的实现,具体代码如下:

// Add adds some keys to the hash. func (m *Map) Add(keys ...string) { //遍历所有的需要添加的集群节点名 for _, key := range keys { //这里是虚拟节点,需要遍历所有的虚拟节点,与集群节点名拼接起来多次计算 for i := 0; i < m.replicas; i++ { //计算hash值 hash := int(m.hash([]byte(strconv.Itoa(i) + key))) //将hash值保存起来 m.keys = append(m.keys, hash) //增加集群节点名与hash值的映射 m.hashMap[hash] = key } } //排序 sort.Ints(m.keys) }

Add 函数这里的 keys 是集群的节点名,而不是我们要缓存的数据的键,这里需要注意的就是我们需要对每个节点名计算虚拟节点次,从而解决 hash 中数据倾斜问题。最后,我们看 Get 函数的实现,具体代码如下:

// Get gets the closest item in the hash to the provided key. func (m *Map) Get(key string) string { //如果map为空,则直接返回 if m.IsEmpty() { return "" } //计算当前节点的hash值 hash := int(m.hash([]byte(key))) //找到key对应hash值之后的最近的一个节点 // Binary search for appropriate replica. idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash }) //如果idx是keys的最后一个元素,则定向到第一个,因为模拟的是环 // Means we have cycled back to the first replica. if idx == len(m.keys) { idx = 0 } //返回对应的节点 return m.hashMap[m.keys[idx]] }

Get 函数的作用就是首先计算要寻找的节点的 hash 值,接着,在保存的切片中,寻找hash值之后的最近的一个节点的索引,并从 map 中根据 hash 值返回即可。

groupcache一致性哈希算法总结

groupcache 中的一致性哈希算法的原理比较简单,但要注意的就是一定要对每个节点计算多次,以解决 hash 中数据倾斜问题。