一致性 hash 算法

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())
}

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()
}