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)
	}
}

执行完毕后，控制台输出如下：

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

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 结构体，该结构体包含了四个成员，每个字段的解释如下：

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

现在，我们首先查看 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 中数据倾斜问题。