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)
}
}
执行完毕后,控制台输出如下:
我们看到,我们首先模拟向集群中添加五个节点,接着,我们将六个键添加到集群中去,最后,我们获取每个键所在的集群的节点。
我们查看 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 中的一致性哈希算法的原理比较简单,但要注意的就是一定要对每个节点计算多次,以解决 hash 中数据倾斜问题。