分布式缓存中一致性 hash 算法原理解析与实现
![avatar](/_astro/avatar.3ed85dfa_Z22q9UU.webp)
分布式缓存服务中,提供缓存服务的节点可能有很多个。在单机缓存服务中,数据被缓存的流程是这样的:
第一次查询数据时首先从源数据查询(比如数据库),找到之后,同时放入缓存服务器中,下次查询同样的数据时会直接从缓存服务器上查找。
但是缓存服务器一般不太可能是单机的,往往有多个节点。转换为分布式之后,会出现一些问题。
问题一数据冗余
考虑一下,单机服务的时候,利用 LRU 算法实现缓存的存取,一个 key 对应一个数据 value。分布式条件下,如果只是单纯的增加节点,这次查找 key 对应的数据在 A 节点上,下次查找的时候却在 B 服务器上。同一个 key 有多个缓存,完全没必要嘛,这样就是数据冗余了。
怎么解决?
利用哈希。首先对 key 值 hash,然后利用节点数取余。
h = hash(key) %len(node)
这样同一个 key 的数据只会被一个节点缓存。很 awesome 有没有。
But,我不可能一直是这几个节点呀,万一有的节点挂了呢,或者我要添加节点呢?
问题二容错性和扩展性
如果有节点挂了或者新增节点,都会导致len(node) 的变化,那么利用 hash 计算出来的值跟之前的就不一样。这样导致新增或者删除一个节点,之前的所有缓存都失效了!我的天哪!!!
这种问题就是 缓存雪崩 。
怎么办呢?利用一致性 hash 算法。
一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。
它的原理是,把所有的 hash 值空间(就是上面公式计算出来的 h)看成是一个环,取值范围从 0 到 2^32-1。将每个服务器节点通过 hash 映射到环上,同时将数据 key 通过 hash 函数也映射到环上,按顺时针方向,数据 key 跟哪个节点近就属于哪个节点。
举个例子,现在有三个缓存服务器节点 2,4,6,假设这个 hash 算法就是原样输出,我们将节点和数据(1,3,7,9)经过 hash 之后到环上:
按顺时针方向,数据 1 属于 node2,数据 3 属于 node4,数据 7、9 输入 node6。
貌似看起来不错,但是还有个问题。在节点较少的情况上,会发生 数据倾斜 的问题。比如上图所示,数据可能大量的堆积在 node6 和 node2 之间。
解决办法是添加虚拟节点,利用虚拟节点负载均衡每个数据。虚拟节点的做法是,对一个真实节点计算多个 hash,放到环上,所有这些虚拟节点的数据都属于真实节点。
这样所有的数据都均匀的分布在环上了。
算法实现
了解了原理,来动手实现一下一致性 hash 算法。整个算法模仿 go 语言的分布式缓存服务groupcache 实现,groupcache 可以说是memcached 的 go 语言实现。
首先定义一致性 hash 环结构体:
type Hash func(data []byte) uint32
// ConHash 一致性 hash
type ConHash struct {
hash Hash // hash 算法
replicas int // 虚拟节点数
nodes []int // hash 环节点数
hashMap map[int]string // 虚拟节点 - 真实节点
}
可以看到,类型 Hash 就是个回调函数,用户可以自定义 hash 算法。
然后需要往 hash 环上添加节点,根据指定的虚拟节点数用 hash 算法放到环上。
// Add 添加节点到 hash 环上
func (m *ConHash) Add(nodes ...string) {
for _, node := range nodes {
// 将节点值根据指定的虚拟节点数利用 hash 算法放置到环中
for i := 0; i < m.replicas; i++ {
h := int(m.hash([]byte(strconv.Itoa(i) + node)))
m.nodes = append(m.nodes, h)
// 映射虚拟节点到真实节点
m.hashMap[h] = node
}
}
sort.Ints(m.nodes)
}
同样还需要根据 key 值从环上获取对应的节点,获取到节点之后从该节点查找数据。
// Get 从 hash 环上获取 key 对应的节点
func (m *ConHash) Get(key string) string {
if len(m.nodes) == 0 {
return ""
}
// 计算 key 的 hash 值
h := int(m.hash([]byte(key)))
// 顺时针找到第一个匹配的虚拟节点
idx := sort.Search(len(m.nodes), func(i int) bool {
return m.nodes[i] >= h
})
// 从 hash 环查找
// 返回 hash 映射的真实节点
return m.hashMap[m.nodes[idx%len(m.nodes)]]
}
有的人说不对啊,为啥添加的都是服务器节点,数据不是也放在环上吗?
其实是因为 groupcache 将数据划分出一个 group 的概念,数据在内部存储上利用 hash+ 双向链表实现,缓存的数据被放在链表中。
整个流程是这样的,查找 key 值对应的数据时,根据 url 链接中的 group 和 key 值确定节点,如何确定的?上面的代码已经解释了,计算 key 值的 hash,看它属于哪个节点。
然后从该节点的双向链表中查找。如果节点不存在这个 key,从用户定义的数据源查找(比如数据库),找到之后将数据存入该 group 中。
以上,希望有帮助。
© CC BY-NC-SA 4.0 | Chaojie