一致性哈希算法分析与 go 语言实现

发布于: 2020 年 07 月 08 日

1:一致性哈希算法与场景

 一致性哈希算法实现关键节点分散平衡性与查询节点实现算法

1.1 场景

在分布式集群情况下,请求路由到哪个节点上,有轮询,哈希等算法,

如果在提供的服务是有状态的,相同的请求每次都路由到同一个节点,相同请求需要路由用哈希比较简单方便,并

并且在节点变动的时候尽量减少受影响的请求。

 

典型的场景比如分布式数据库,分布式缓存等分布式存储情况下,不同节点都存储一部分数据,请求时计算数据的落位节点,去这个节点存取。

 

1.2 一致性哈希算法

 

1:将0到2的32次方-1  范围内的数顺时针组成一个虚拟的环

2:服务节点计算其哈希值,放到环上对应位置,组成服务节点环。

3:请求路由,根据请求的key计算哈希值,以这个哈希值在环上的位置开始顺时针寻找距离这个位置最近的服务节点,将请求发到这个节点上。

2:实现分析

实现过程逻辑上分为两个阶段

1:由服务节点逐步落位到环上,即构建节点环。

2:请求时根据请求key寻找服务节点,即请求路由。

第一步是第二步的前提

2.1 构建节点环

 

根据服务节点的特征值,比如取ip地址,进行运算,得到0-2的32次方-1间的值,服务节点按得其计算后到的值由小到大顺时针组成一个节点环。

 

节点环功能要求

      可以添加,移除节点,根据请求key查询就近节点。

api:

type HashRing interface {
PutNode(key string)
DeleteNode(key string)
FindNearNode(dataKey string ) string
PrintRing()//输出节点在环上的分步-测试用
}
type HashRingVirtual interface {
HashRing
PutNodeExtend(nodeKey string ,virtualCount int )
}

 节点环的特性要求

节点环用在分布式集群的场景要求下,目的是多个节点分担大量请求,因此节点环要符合以下两个特征。

节点间负载均衡:大量请求要尽量分散到不同的节点上

查询节点性高性能:集群就是应对大量请求的,查询节点的性能一定要高。

 

节点间负载均衡:

节点分散,数据分散 就可以满足节点均衡,关键点就是如何进行哈希运算。

代码中用了两种算法crc32, key取md5后再做crc32,crc32(md5(key+md5(key)))。验证后发现多次md5后crc32更分散。

一个物理节点虚拟为多个节点,不同的物理节点可以给不同权重(虚拟节点数)实现分散。

 

查询节点高性能

相比请求量,节点的变动次数很少,节点数据也有限,因此可以忽略构建环的时间消耗与空间消耗。选择合适的数据结构,满足查询性能。

在一个数值集合中查询最近的数据,有多种算法。代码中尝试两种方法。

节点哈希值放入排序数组,在排序数组上进行二分查找,时间复杂度为O(logn)。

节点分到固定范围数量的槽上,查询时先对查询数据key哈希后取模确定归属槽位,然后直接获取节点,即用空间换时间。可以保证节点间槽位均衡及查询高效(查询作弊了)。redis集群采用类似方案分为16384个固定槽。

2.2 请求路由

对请求key进行哈希,然后查找,实际key可能是某种符合规律的比如user-1,user-2.

保证哈希后的分散度即可。可以与哈希环使用相同或不同的哈希函数。

3:关键代码实现(golang)

 

3.1 哈希函数

用三种哈希方法比较散列情况

//哈希算法-crc32(md5(key+md5(key)))
func getHashCode4KeyWithMd5(key string)uint32{
var newKey=key+Md5([]byte(key))
return getHashCode(newKey)
}
//哈希算法-crc32(md5(key))
func getHashCode(key string )uint32{
return getCrcHash(Md5([]byte(key)))
}
//哈希算法-crc32(key)
func getCrcHash(key string)uint32{
return crc32.ChecksumIEEE([]byte(key))
}

3.2 二分查找环

 

算法逻辑从头尾中间查,折半逐步查找

数组环实现

type SortArrayRingImpl struct {
data []uint32
}
func(this *SortArrayRingImpl)Put(value uint32){
if len(this.data)==0{
this.data= append(this.data, value)
return
}
findIndex:=this.findNearIndex(value)
if findIndex==0{
if value<=this.data[0]{//添加到头部
this.insertBefore(value,0)
}else{//添加到尾部
this.insertBefore(value, len(this.data))
}
}else{//中间添加
this.insertBefore(value,findIndex)
}
}
func(this *SortArrayRingImpl)Delete(value uint32){
if len(this.data)>0{
index:=this.findNearIndex(value)
if this.data[index]==value{
this.data=deleteAt(this.data,index)
}
}
}
func (this *SortArrayRingImpl)findNearIndex(code uint32) int{
keys:=this.data
if len(keys)==0{
return -1
}
if keys[0]>=code||keys[len(keys)-1]<code{
return 0
}
if keys[len(keys)-1]==code{
return len(keys)-1
}
var beginIndex=0
var endIndex =len(keys)-1
for endIndex-beginIndex>1{//二分查找
middle:=int((endIndex+beginIndex)/2)
if keys[middle]>code{
endIndex =middle
continue
}
if keys[middle]==code{
return middle
}else{
beginIndex=middle
}
}
if keys[beginIndex]==code{
return beginIndex
}
return endIndex
}

哈希环用数组环做内部环存储,添加一层哈希计算 及哈希值与key的映射即可。

type SortArrayHashRing struct {
keys map[uint32]string //反向索引,hashcode->key
hashCodeRing SortArrayRing//排序队列实现数据环
hashCodeFunc func(key string )uint32
}
func(hashRing *SortArrayHashRing)PutNode(key string){
hashCode:=hashRing.getHashCode(key)
hashRing.keys[hashCode]=key
hashRing.hashCodeRing.Put(hashCode)
}
func (hashRing *SortArrayHashRing)DeleteNode(key string){
code:=hashRing.getHashCode(key)
if existKey,ok:=hashRing.keys[code];ok{
if existKey==key{//find ,完全匹配,删除
delete(hashRing.keys, code)//map中移除
hashRing.hashCodeRing.Delete(code)//数据环移除
}
}
}
func (hashRing *SortArrayHashRing)FindNearNode(key string) string{
code:=hashRing.getHashCode(key)
findValue,find:=hashRing.hashCodeRing.FindNear(code)
if find{
return hashRing.keys[findValue]
}else{
return ""
}
}

3.3 预分槽模式

redis集群采用的方案,将节点分布到确定的16384 槽中(slot),占满。没有空槽。请求时根据key计算出哈希,然后与槽数取模,确定落位的节点。

优点:可以精确各个节点的分散度。比如各个节点槽数相等(有余数除不尽时差一个),数据请求时不用查询,计算后直接落位。

分槽模式关键在分槽过程中保持节点槽数均衡。代码中用简单算术平均,节点包括 key与节点占用分槽 ,

节点用一个排序列表保存,排序按照节点分槽数排序,添加节点时计算需要分配的槽数,从尾部节点开始平均分(有余数尾部开始多分一个),移除节点相反操作。

type SegmentHashRing struct {
slotSize uint32
slotNodeMap map[uint32]string //slot->nodekey
nodeList NodeList //节点列表(按槽位多少升序排列)
hashCodeFunc func(key string) uint32
}
func (this *SegmentHashRing)offerDataForNextNode() []uint32{
//新节点添加时从现有节点列表中取槽位
var offerData []uint32
if len(this.nodeList)==0{//初始化全部槽位
offerData =make([]uint32,0,this.slotSize)
var i uint32
for i=0;i<this.slotSize;i++{
offerData=append(offerData, i)
}
return offerData
}
//计算新节点应该获取多少:新节点个数=总个数/(当前节点数+1) ,平均数等于新节点个数(有余数时部分节点会多)。
newNodeSlotSize :=this.slotSize/ uint32(len(this.nodeList)+1)
averageSlotSize:=newNodeSlotSize
var offerTotal uint32 =0
for i:=len(this.nodeList)-1;i>=0;i--{//出借从底部开始(底部节点个slot多)
//逐个节点取-//每个节点给多少? 取小(当前节点个数-平均数 新节需要个数-已经分配个数)
node:=this.nodeList[i]
surplus:=node.size()-averageSlotSize//当前节点个数-平均数=本节点多余
needs:=newNodeSlotSize-offerTotal//新节点还差个数
if needs<=surplus{//差的个数小于多余的 给差的个数就行-够了。
offerData=append(offerData,node.offer(needs)...)
return offerData
}else{
offerData=append(offerData,node.offer(surplus)...)
offerTotal+=surplus
}
}
return offerData
}
func(this *SegmentHashRing)sendBackData(backData []uint32){
//节点删除,将数据归还给剩下的节点。
//如果没有节点,退出,一个节点,全部归还
nodeSize:=len(this.nodeList)
if nodeSize==0 {
return
}
if nodeSize==1{
this.sendBackToNode(this.nodeList[0],backData)
return
}
totalBackCount :=len(backData)
averageBackCound:=totalBackCount/nodeSize
remainder:=totalBackCount%nodeSize
currentIndex:=0
haveBackCount:=0
for i:=0;i<len(this.nodeList);i++{//归还从头部还,头部节点slot少
if remainder>0{
//归还 平均数+1
backCount:=averageBackCound+1
nextDataIndex:=currentIndex+backCount
remainder=remainder-1
haveBackCount=haveBackCount+backCount
this.sendBackToNode( this.nodeList[i],backData[currentIndex:nextDataIndex])
}else{
backCount:=averageBackCound
nextDataIndex:=currentIndex+backCount
haveBackCount=haveBackCount+backCount
this.sendBackToNode( this.nodeList[i],backData[currentIndex:nextDataIndex])
}
if haveBackCount== len(backData){//还完了
return
}
}
}

路由就很简单了

func (this *SegmentHashRing)FindNearNode(key string) string{
code:=this.getHashCode(key)
slot:=code%this.slotSize
nodeName,find:=this.slotNodeMap[slot]
if find{
return nodeName
}else{
return ""
}
}

3.4 虚拟节点方案

 

将物理节点拆分为多个虚拟节点,可以更让请求更平衡。

实现用其他节点环做内部环实现,包装下节点的key既可。key=虚拟下标+节点key

type NodeManagerImpl struct {
hashRing HashRing
nodes map[string]Node
}
func(manager *NodeManagerImpl)PutNodeExtend(nodeKey string ,virtualCount int ){
var node Node
node.NodeIdentity=nodeKey
node.VirtualCount=virtualCount
manager.nodes[nodeKey]=node
//manager.hashRing.Put(nodeKey)
vNods:=manager.getVirtualNodes(nodeKey,virtualCount)
for _,vNode:=range vNods{
manager.hashRing.PutNode(vNode)
}
}
func(manager *NodeManagerImpl)DeleteNode(nodeKey string ){
if node, ok:=manager.nodes[nodeKey];ok{
delete(manager.nodes,nodeKey)
vNods:=manager.getVirtualNodes(nodeKey,node.VirtualCount)
for _,vNode:=range vNods{
manager.hashRing.DeleteNode(vNode)
}
}
}
func(manager *NodeManagerImpl)getVirtualNodes(nodeKey string ,virtualCount int) []string{
var keys []string
for i:=1;i<=virtualCount;i++ {
var key string = nodeKey + "_" + strconv.Itoa(i)
keys= append(keys, key)
}
return keys
}
func(manager *NodeManagerImpl)FindNearNode(dataKey string) string{
var nodeIdentityWithPrefix =manager.hashRing.FindNearNode(dataKey)
if nodeIdentityWithPrefix!=""{
s:=strings.Split(nodeIdentityWithPrefix,"_")
return s[0]
}else{
return nodeIdentityWithPrefix//""
}
}

4:测试验证

4.1均衡性验证

负载均衡性跟节点数及哈希算法相关

哈希算法验证

10个节点,二维数组环,不带虚拟节点,节点key用ip:192.168.1.序号 格式

依次 :crc32,crc32(md5(key),crc32(md5(key+md5(key))) 哈希方法验证

节点数10,测试数据量1000000,标准差126568.357,标准差/数据量= 0.127

节点数10,测试数据量1000000,标准差113088.071,标准差/数据量= 0.113

节点数10,测试数据量1000000,标准差84911.254,标准差/数据量= 0.085

可以看到crc32(md5(key+md5(key))) 的标准差明显较小。

//虚拟节点添加后标准差明显减少方差

虚拟节点验证均衡性

crc32(md5(key+md5(key)))哈希,10个节点,不同虚拟节点

节点数10,虚拟节点数2, 测试数据量1000000,标准差58829.664,标准差/数据量= 0.059

节点数10,虚拟节点数20, 测试数据量1000000,标准差18823.756,标准差/数据量= 0.019

节点数10,虚拟节点数200, 测试数据量1000000,标准差5903.259,标准差/数据量= 0.006

节点数10,虚拟节点数2000, 测试数据量1000000,标准差1413.411,标准差/数据量= 0.001

预分槽的均衡性验证

crc32(md5(key+md5(key)))哈希,10个节点

预分槽模式-槽位数16384

节点数10,测试数据量1000000,标准差340.131,标准差/数据量= 0.000

4.2 性能验证

100万数据计算路由性能测试

数组排序环,节点数10,耗时1861 ms

数组排序环-节点数10,每个节点200个虚拟节点,耗时2559 ms

预分槽模式-槽位数16384,10个节点,耗时2156 ms

看数据后很不解,理论上预分槽的只做取余,不搜索应该更快,怎么比数组排序模式还慢?

再跑一次发现跟数组排序的耗时相当了。因为是测试启动后依次计算3种模式的耗时,实际放到后面的多少受程序资源影响。多跑几次后两者差异很小。

其实10个节点的排序数组二分查找最多才几次比较跟取中间数计算。已经可以不去考虑性能。

100万次路由 2秒,没有优化的必要了。

5:完整代码地址

https://github.com/juluzhch/studygo/tree/master/src/jiagoushi/homework/algorithm/consistent_hashing

发布于: 2020 年 07 月 08 日 阅读数: 20
用户头像

superman

关注

还未添加个人签名 2018.07.20 加入

还未添加个人简介

评论

发布
暂无评论
一致性哈希算法分析与go语言实现