分布式一致性哈希算法

最近看到一篇关于分布式下一致性哈希算法,主要用于实现缓存数据的均匀分布,看完后也按照自己的理解实现了一个,权当总结。

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分别存储在了不同的节点之上。由于时间和场景,至于节点加入和退出的时候的数据迁移这里没有实现。