文章目录
  1. 普通哈希
    1. 测试代码
  2. 一致性哈希
    1. 测试代码
  3. 虚拟节点
    1. 测试代码
  4. 附-测试主程序

Golang模拟一致性哈希

参考链接- 一致性哈希原理与实践
关于一致性哈希算法的原理网上很多讲解和实践,这里不再赘述。本文主要是通过代码验证一致性哈希带来的变化以及问题。

普通哈希

直接对数据进行哈希计算后取模确定数据存入的节点,如果集群的节点数量发生变更时,几乎需要对所有数据进行重新映射。 普通哈希的优势在于数据的分布比较均匀。
程序测试结果如下,增加一个节点的情况下,需要转移的数据比例达到99%,几乎所有数据都需要进行节点迁移。

CaculateChange needTransNum:990173  Percentage:0.990173 
CaculateDist Avg:10000.00 Max:10254(102.54) Min:9791(97.91)

测试代码

const NodesNum = 100      //原始节点数量
const NewNodesNum = 101 //扩充后的节点数量
const ItemsNum = 1000000 //数据数量


type HashTest interface {
CaculateDist() //计算各个节点的数据数量,可以反馈出数据的均匀成都
CaculateChange() //计算在增加一个节点的情况下,数据迁移量及占比
}

type NormalHash struct {}

func (n NormalHash) CaculateDist() {
nodeStat := make(map[int64]int64)
for i := 0; i < ItemsNum; i++ {
hashi := GetHash("item:" + strconv.Itoa(i))

saveNode := GetByteMode(hashi, NodesNum) //普通哈希算法,直接取模得到节点数
nodeStat[saveNode] += 1
}

avg := ItemsNum * 1.0 / NodesNum
var max int64 = 0
var min int64 = math.MaxInt64
for _, n := range nodeStat {
if n > max {
max = n
}

if n < min {
min = n
}
}

fmt.Printf("CaculateDist Avg:%.2f Max:%d(%.2f) Min:%d(%.2f)", avg, max, float64(max) / avg * 100, min, float64(min) / avg * 100)
}

//当增加一个节点时,需要进行迁移的数据
func (n NormalHash) CaculateChange() {
needTrans := 0
for i := 0; i < ItemsNum; i++ {
hashi := GetHash("item:" + strconv.Itoa(i))

saveNode := GetByteMode(hashi, NodesNum)
saveNodeNew := GetByteMode(hashi, NewNodesNum)

if (saveNode != saveNodeNew) {
needTrans += 1
}
}
fmt.Printf("CaculateChange needTransNum:%d Percentage:%f \n", needTrans, float64(needTrans) / ItemsNum)
}

一致性哈希

一致性哈希如图,通过将节点进行哈希后映射到环上,数据计算哈希后存储到最近的节点中。优势是节点数量变更时,迁移的数据量大大减少,问题是会带来数据分布不均。

测试结果,在增加一个节点场景下,数据转移比例只有0.4%。但是也可以看出来,数据的分布极其不均匀

ConsistHash:
CaculateChange needTransNum:4057 Percentage:0.004057
CaculateDist Avg:10000.00 Max:39257(392.57) Min:32(0.32)

测试代码

type ConsistHash struct {}

func (c ConsistHash) CaculateDist() {
nodeStat := make(map[int64]int64)
chInstance := ConsistHashInstance{}
chInstance.Init(NodesNum)

for i := 0; i < ItemsNum; i++ {
node := chInstance.GetItemNode("item:" + strconv.Itoa(i))
nodeStat[node]++
}

avg := ItemsNum * 1.0 / NodesNum
var max int64 = 0
var min int64 = math.MaxInt64
for _, n := range nodeStat {
if n > max {
max = n
}

if n < min {
min = n
}
}

fmt.Printf("CaculateDist Avg:%.2f Max:%d(%.2f) Min:%d(%.2f)", avg, max, float64(max) / avg * 100, min, float64(min) / avg * 100)
}

//当增加一个节点时,需要进行迁移的数据
func (c ConsistHash) CaculateChange() {

chInstance := ConsistHashInstance{}
chInstance.Init(NodesNum)

chInstance2 := ConsistHashInstance{}
chInstance2.Init(NodesNum + 1 )

needTrans := 0


for i := 0; i < ItemsNum; i++ {
node := chInstance.GetItemNode("item:" + strconv.Itoa(i))
nodeNew := chInstance2.GetItemNode("item:" + strconv.Itoa(i))
if(node != nodeNew) {
needTrans++
}
}
fmt.Printf("CaculateChange needTransNum:%d Percentage:%f \n", needTrans, float64(needTrans) / ItemsNum)

}

type ConsistHashInstance struct {
hashToNode map[string]int64
nodeHashs NodeHashArray
}

type NodeHashArray []string
//实现排序接口
func (p NodeHashArray) Len() int { return len(p) }
func (p NodeHashArray) Less(i, j int) bool { return p[i] < p[j] }
func (p NodeHashArray) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p NodeHashArray) Sort() {sort.Sort(p)}

//获取数据分配的节点
func (ci *ConsistHashInstance) GetItemNode(item string) int64 {
//计算item-hash
hashi := GetHash(item)
hashiStr := hex.EncodeToString(hashi)

//获取距离hash最近的node, sort.Search返回第一个f(i) == true 的index
//注意此处的i并非实际的节点索引,而是环上的slot索引
i := sort.Search(len(ci.nodeHashs), func(idx int) bool {
return ci.nodeHashs[idx] >= hashiStr
})

if (i >= len(ci.nodeHashs)) {
i = len(ci.nodeHashs) - 1
}
nodeI := ci.hashToNode[ci.nodeHashs[i]] //根据slot中的哈希值找到实际的节点索引

return int64(nodeI)
}

func (ci *ConsistHashInstance) Init(nodeN int64) {
ci.hashToNode = make(map[string]int64)
ci.nodeHashs = make([]string, 0, nodeN)

i := nodeN
for i = 0; i < nodeN; i++ {
hashi := GetHash("node:" + strconv.FormatInt(i, 10))
hashiStr := hex.EncodeToString(hashi)

ci.hashToNode[hashiStr] = int64(i)
ci.nodeHashs = append(ci.nodeHashs, hashiStr)
}

//排序(将节点映射到环中)
ci.nodeHashs.Sort()

}

虚拟节点

一致性哈希的分布不均本质上是由于节点在环上的分布不均造成的,一种解决办法是增加节点数量,即可以把一个节点映射为多个虚拟节点。

测试结果,同样的节点数量,每个节点建立10个虚拟节点,测试结果如下,可以看出数据比普通的一致性哈希更均匀

ConsistVirtualHash:
CaculateChange needTransNum:13334 Percentage:0.013334
CaculateDist Avg:10000.00 Max:19887(198.87) Min:3344(33.44)

测试代码

在实现上,和普通的一致性算法相比,区别只在于节点数量增加

func (ci *ConsistVirtualHashInstance) Init(nodeN int64, virtualNum int64) {
allVirtualNum := nodeN * virtualNum

ci.hashToNode = make(map[string]int64)
ci.nodeHashs = make([]string, 0, allVirtualNum)

i := nodeN
j := virtualNum
for i = 0; i < nodeN; i++ {
for j = 0; j < virtualNum; j++ {
nodehash := GetHash("node:" + strconv.FormatInt(i, 10) + strconv.FormatInt(j, 10))
hashiStr := hex.EncodeToString(nodehash)

ci.hashToNode[hashiStr] = int64(i) //记录虚拟节点对应的实际节点
ci.nodeHashs = append(ci.nodeHashs, hashiStr)
}
}

//排序(将节点映射到环中)
ci.nodeHashs.Sort()

}

附-测试主程序

func main() {
fmt.Println("NormalHash:")
normal := dist_hash.NormalHash{}
normal.CaculateChange()
normal.CaculateDist()

fmt.Println("\n\nConsistHash:")
consist := dist_hash.ConsistHash{}
consist.CaculateChange()
consist.CaculateDist()

fmt.Println("\n\nConsistVirtualHash:")
consistV := dist_hash.ConsistVirtualHash{}
consistV.CaculateChange()
consistV.CaculateDist()
}