最近看到一篇关于分布式下一致性哈希算法,主要用于实现缓存数据的均匀分布,看完后也按照自己的理解实现了一个,权当总结。
Part1: 分布式下如何保证缓存数据的一致性?
在单机版本下,即单存储介质下,我们只需要保证数据具备唯一的ID就可以了。其实在分布式环境下,也是可以这么做的,比如用hash(time+ip+mac+key)
的方式也可以保证在多台机器下的数据的一致性。但是怎么标明这个数据存储在这台机器上呢?解决方式有两个,一个是做一个中心化的映射关系,将某个key
映射到某台机器,然后去这台机器取这个key
,这种方式很明显需要额外的数据存储,很不方便。那么,有没有可能通过计算就知道数据在哪台机器上呢?答案是肯定的,因为我们所能想到的,前辈们基本也都想到并找到解决办法了。那就是一致性哈希算法。
一致性哈希(Consistent hashing
)算法是由MIT的Karger等人于1997年在一篇学术论文(《Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web》
)中提出来的,专门用于解决分布式缓存数据分布问题。仔细想想,这个算法都提出来已经二十几年了。
Part2: 如何确定某个Key在某个节点上?
传统方式是通过hash%count
的方式来决定某个key
存储在哪台机器上,举个例子,比如有下面三台服务器(三个节点):
servers = ["node1","node2","node3"] #3个节点
n = len(servers) #即3
假设有下面这个key-value
需要存储:
data = {'key':'value'}
计算md5:
anderson@anderson:~/Desktop$ echo 'key' | md5sum
146c07ef2479cedcd54c7c2af5cf3a80 -
取末尾4位,即3a80
,转化位10进制后取模运算:
anderson@anderson:~/workspace/src/personal_storage$ printf %d 0x3a80
14976
anderson@anderson:~/workspace/src/personal_storage$ echo 14976%3|bc
0
所以这个key就保存在下标为0
的节点上node1
。这里为什么能够取末尾4位呢?原因很简单,因为在大量数据的场景下,哈希的每一部分都具备均匀分布的特性,用全部位和取末尾4位的差别不是很大,更重要的是能够节省计算资源。
那有什么缺点呢?
试着想下,如果增加了一个节点,或者减少了一个节点,那么是不是全部的数据定位都要重新计算一遍呢?在分布式场景下,自动伸缩是很常见的,如果每一次Scale都要将全部数据重新计算并刷新缓存,那么这个效率是存在很大的问题的。所以,为了解决这个问题,在这个基础上使用了环形节点的概念。
Part3: 一致性哈希解决方案
- 首先将哈希映射到一个虚拟的闭环上,环上的数值分从
0
到2^64-1
(比如64位系统),那么我们就可以通过取模的方式在这个闭环上进行操作。 - 将节点也映射到这个闭环上,可以使用
hash(serverIp+port)%(2^64-1)
。 - 然后是计算
key
在闭环上的位置,hash(key)%(2^64-1)
。 - 按照某一个固定的方向,比如顺时针或者逆时针,找到最近的一台节点的闭环位置。这个节点就是存储该数据的节点。
- 当有一台新节点加入的时候,计算新节点的位置,然后按照相同方向寻找最近的一台服务器,将新旧节点之间相邻的闭环数据反向迁移到新节点上。
- 当有一台节点删除的时候,同样将该节点的数据迁移到顺时针相邻的节点上。
Part4: Golang版本实现
package main
import (
"crypto/md5"
"encoding/hex"
"fmt"
"math"
"strconv"
)
func main() {
nodes := []string{"202.192.18.1", "202.192.18.2", "202.192.18.3"}
hashing := NewConsitentHash(nodes, 3)
fmt.Println("key_hello store in: ", hashing.Calc("key_hello"))
fmt.Println("key_world store in: ", hashing.Calc("key_world"))
}
type ConsistentHash struct {
Nodes []string //缓存节点
virtualNodeCount int //每个缓存节点所能提供的虚拟节点的数量
virtualNodeMap map[int64]int //虚拟节点与实体节点的映射
}
func NewConsitentHash(nodes []string, virtualNodeCount int) *ConsistentHash {
x := &ConsistentHash{
virtualNodeMap: make(map[int64]int, 0),
virtualNodeCount: virtualNodeCount,
}
x.Nodes = make([]string, len(nodes))
for i, node := range nodes {
x.addNode(node, i)
}
return x
}
//哈希计算,返回存储的虚拟节点的下标
func (self *ConsistentHash) hashing(key string) int64 {
if key == "" {
return -1
}
h := md5.New()
h.Write([]byte(key))
cipherStr := h.Sum(nil)
hexStr := hex.EncodeToString(cipherStr)
if dec, err := strconv.ParseInt(hexStr[0:15], 16, 64); err == nil {
return dec % int64(math.Pow(2, 64)-1)
}
return -1
}
//创建节点
func (self *ConsistentHash) addNode(node string, index int) {
self.Nodes[index] = node
for i := 0; i < self.virtualNodeCount; i++ {
key := fmt.Sprintf("%s_%d", node, i)
hash := self.hashing(key)
if hash == -1 {
continue
}
self.virtualNodeMap[hash] = index
}
}
//返回要存储的位置
func (self *ConsistentHash) Calc(key string) (node string) {
dec := self.hashing(key)
if dec == -1 {
return
}
var rTmp float64 = float64(math.Pow(2, 64))
for vNode, rNodeIndex := range self.virtualNodeMap {
if x := math.Abs(float64(dec - vNode)); x <= float64(rTmp) {
node = self.Nodes[rNodeIndex]
rTmp = x
}
}
return
}
程序的输出结果如下:
anderson@anderson:~/workspace/src/demo_test/consistent_hashing$ go run *.go
key_hello store in: 202.192.18.3
key_world store in: 202.192.18.1
说明这两个key
分别存储在了不同的节点之上。由于时间和场景,至于节点加入和退出的时候的数据迁移这里没有实现。