写点什么

一致性 hash 算法

用户头像
天涯若海
关注
发布于: 2020 年 11 月 20 日

一致性hash算法,基本代码如下。代码使用golang语言。比较粗糙。紫薯布丁紫薯布丁紫薯布丁紫薯布丁紫薯布丁紫薯布丁

package src
import (
"hash/fnv"
"math"
"math/rand"
"sort"
)
//一致性hash环大小为8192
const CircleLength = 8192
type ConsistentHashCircle struct {
//所有服务器节点集合
nodeSlice []*node
//指向所有服务器节点的虚拟节点的有序集合
allVnodeSlice [] *virtualNode
}
type virtualNode struct {
Id int
Keys [] string
Parent *node
}
type node struct {
vNode [] *virtualNode
Count int
}
//初始化服务器节点
func newNode(id int ,vNum int) *node {
node:= node{Count: 0}
vNodeSlice := make([]*virtualNode,vNum)
for i:=0;i<vNum;i++{
v:=virtualNode{}
v.Id =rand.Intn(CircleLength)
v.Parent =&node
v.Keys =make([]string,0)
vNodeSlice[i] = &v
}
node.vNode=vNodeSlice
return &node
}
//初始化hash一致性节点
func NewConsistentHashCircle(nodeNum int) *ConsistentHashCircle{
allvirtualNodeSlice := make([]*virtualNode,0)
allNode :=make([]*node,nodeNum)
for i:=0;i<nodeNum;i++{
node:= newNode(i,10)
allNode[i]=node
allvirtualNodeSlice = append(allvirtualNodeSlice, node.vNode...)
}
//虚拟节点按Id递增有序
sort.Slice(allvirtualNodeSlice, func(i, j int) bool {
return allvirtualNodeSlice[i].Id < allvirtualNodeSlice[j].Id
})
consistentHashCircle:=ConsistentHashCircle{nodeSlice: allNode,allVnodeSlice: allvirtualNodeSlice}
return &consistentHashCircle
}
func (c *ConsistentHashCircle) Put(k string){
h :=int(hash(k)%CircleLength)
i:=findVnode(h,c.allVnodeSlice)
c.allVnodeSlice[i].Keys = append(c.allVnodeSlice[i].Keys, k)
c.allVnodeSlice[i].Parent.Count++
}
func (c *ConsistentHashCircle) GetAllNode() []*node{
return c.nodeSlice
}
//计算标准差
func (c *ConsistentHashCircle) StandardDeviation() float64{
mean := func() float64{
sum:=0
for _,v:=range c.nodeSlice{
sum+=v.Count
}
return float64(sum*1.0/len(c.nodeSlice))
}()
var stde float64
for _,v:=range c.nodeSlice{
m:=float64(v.Count)
stde+=math.Pow(m-mean,2.0)
}
return math.Sqrt(stde/float64(len(c.nodeSlice)))
}
//顺时针,根据id确认选择的虚拟节点。因为每个服务器节点的虚拟节点数为10,总虚拟节点不多,直接顺序查找
func findVnode(h int,vList []*virtualNode) int{
i:=0
for j:=0;j<len(vList);j++{
if vList[j].Id >h{
i=j
break
}
}
return i
}
func hash(s string) uint32 {
h := fnv.New32a()
h.Write([]byte(s))
return h.Sum32()
}



测试几个回合

func main() {
for j:=0;j<10;j++{
c:=src.NewConsistentHashCircle(10)
for i:=0;i<1_000_000;i++{
c.Put(RandStringRunes(20))
}
//for _,v:=range c.GetAllNode(){
// fmt.Println(v.Count)
//}
fmt.Println(c.StandardDeviation())
}
}
func init() {
rand.Seed(time.Now().UnixNano())
}



标准差输出如下,由于虚拟节点是随机分配到一致性hash环上,所以标准差很大

修正版,虚拟节点均匀分布在一致性hash环上的

package src
import (
"hash/fnv"
"math"
"sort"
)
//一致性hash环大小为8192
const CircleLength = 8192
const Interval = 82
type ConsistentHashCircle struct {
//所有服务器节点集合
nodeSlice []*node
//指向所有服务器节点的虚拟节点的有序集合
allVnodeSlice [] *virtualNode
}
type virtualNode struct {
Id int
Keys [] string
Parent *node
}
type node struct {
vNode [] *virtualNode
Count int
}
//初始化服务器节点
func newNode(id int ,vNum int) *node {
node:= node{Count: 0}
vNodeSlice := make([]*virtualNode,vNum)
for i:=0;i<vNum;i++{
v:=virtualNode{}
v.Id =Interval*vNum*i+id*Interval //均匀分布
v.Parent =&node
v.Keys =make([]string,0)
vNodeSlice[i] = &v
}
node.vNode=vNodeSlice
return &node
}
//初始化hash一致性节点
func NewConsistentHashCircle(nodeNum int) *ConsistentHashCircle{
allvirtualNodeSlice := make([]*virtualNode,0)
allNode :=make([]*node,nodeNum)
for i:=0;i<nodeNum;i++{
node:= newNode(i,10)
allNode[i]=node
allvirtualNodeSlice = append(allvirtualNodeSlice, node.vNode...)
}
//虚拟节点按Id递增有序
sort.Slice(allvirtualNodeSlice, func(i, j int) bool {
return allvirtualNodeSlice[i].Id < allvirtualNodeSlice[j].Id
})
consistentHashCircle:=ConsistentHashCircle{nodeSlice: allNode,allVnodeSlice: allvirtualNodeSlice}
return &consistentHashCircle
}
func (c *ConsistentHashCircle) Put(k string){
h :=int(hash(k)%CircleLength)
i:=findVnode(h,c.allVnodeSlice)
c.allVnodeSlice[i].Keys = append(c.allVnodeSlice[i].Keys, k)
c.allVnodeSlice[i].Parent.Count++
}
func (c *ConsistentHashCircle) GetAllNode() []*node{
return c.nodeSlice
}
//计算标准差
func (c *ConsistentHashCircle) StandardDeviation() float64{
mean := func() float64{
sum:=0
for _,v:=range c.nodeSlice{
sum+=v.Count
}
return float64(sum*1.0/len(c.nodeSlice))
}()
var stde float64
for _,v:=range c.nodeSlice{
m:=float64(v.Count)
stde+=math.Pow(m-mean,2.0)
}
return math.Sqrt(stde/float64(len(c.nodeSlice)))
}
//顺时针,根据id确认选择的虚拟节点。因为每个服务器节点的虚拟节点数为10,总虚拟节点不多,直接顺序查找
func findVnode(h int,vList []*virtualNode) int{
i:=0
for j:=0;j<len(vList);j++{
if vList[j].Id >h{
i=j
break
}
}
return i
}
func hash(s string) uint32 {
h := fnv.New32a()
h.Write([]byte(s))
return h.Sum32()
}

然后再跑10个循环,结果如下



用户头像

天涯若海

关注

还未添加个人签名 2017.12.08 加入

还未添加个人简介

评论

发布
暂无评论
一致性hash算法