package consistency_hash
var PointUsed = make(map[uint32]bool, 4096) // 记录已经使用的虚拟节点
type Node struct {	Host string // 服务器 IP + PORT	Code uint32	VirtualNumber uint	VirtualCodeList []uint32}
func NewNode(host string, virtualNumber uint) *Node {	node := &Node{		Host: host,		VirtualNumber:virtualNumber,	}	node.setVirtualNode() // 设置虚拟节点
	return node}
// 设置虚拟节点func (n *Node) setVirtualNode() {	n.VirtualCodeList = GetHashCodeList(n.VirtualNumber)}

package consistency_hash
import (	"sort")
const (	RingMin = 0	RingMax = 4294967295)
// hash环type Ring struct {	min uint	max uint	PointList []uint32}
func NewRing() *Ring {	ring := &Ring{		min:             RingMin,		max:             RingMax,		PointList:       make([]uint32,0, 4096),	}
	return ring}
// 获得顺时针虚拟节点func (r *Ring) GetNearestVirtualNode(hashCode uint32) uint32 {	var nearestPoint uint32	for _, point := range r.PointList{		if hashCode > point {			continue		}
		nearestPoint = point		break	}
	// 如果key的hash code大于所有虚拟节点，则放在第一个虚拟节点	if nearestPoint == 0 {		nearestPoint = r.PointList[0]	}
	return nearestPoint}

// 设置环上的虚拟节点func (r *Ring) SetPointList(node *Node) {	r.PointList = append(r.PointList, node.VirtualCodeList...)
	// 重新排序	sort.Slice(r.PointList, func(i, j int) bool {		return r.PointList[i] < r.PointList[j]	})}

package consistency_hash
import (	"fmt"	"math")
type ConsistencyHash struct {	ring *Ring	NodeNumber float64	NodeList []*Node	PointNodeMap map[uint32]*Node	NodeKeyCountMap map[*Node]float64}

func NewConsistencyHash() *ConsistencyHash {	consistencyHash := &ConsistencyHash{		NodeNumber:      0,		ring: NewRing(),		NodeList:        make([]*Node,0,16),		PointNodeMap:    make(map[uint32]*Node, 4096),		NodeKeyCountMap: make(map[*Node]float64,16),	}
	return consistencyHash}
// 保存缓存到服务器上。这里只是key对应节点保存的key的数量加1func (c *ConsistencyHash) Set(key string) {	node := c.GetNode(key)	c.NodeKeyCountMap[node]++}
// 按key读取缓存，这里只是返回节点的hostfunc (c *ConsistencyHash) Get(key string) string {	node := c.GetNode(key)
	return node.Host}
// 添加节点func (c *ConsistencyHash) AddNode(node *Node) {	c.NodeList = append(c.NodeList,node)	c.NodeKeyCountMap[node] = 0	c.NodeNumber++
	for _,point := range node.VirtualCodeList{		c.PointNodeMap[point] = node	}
	c.ring.SetPointList(node)}
// 获得物理节点func (c *ConsistencyHash) GetNode(key string) *Node {	hashCode := GetHashCode(key)	nearestPoint := c.ring.GetNearestVirtualNode(hashCode)
	return c.PointNodeMap[nearestPoint]}
// 获取标准差func (c *ConsistencyHash) GetSigma(){
	var sum float64 = 0	for _, value := range c.NodeKeyCountMap{		sum += value	}
	mean := sum / c.NodeNumber	fmt.Printf("平均值：%0.2f", mean)
	var variance float64	for _, v := range c.NodeKeyCountMap {		variance += math.Pow(v - mean, 2)	}
	σ := math.Sqrt(variance / c.NodeNumber)	fmt.Printf("标准差：%0.3f\n", σ)}

package consistency_hash
import (	"fmt"	"hash/crc32"	"math/rand"	"time")
// 全局的随机种子var r *rand.Rand
func init() {	r = rand.New(rand.NewSource(time.Now().Unix()))}
// 生成指定长度的hash code（虚拟节点）func GetHashCodeList(number uint) []uint32 {	var index uint = 0	codeMap := make(map[uint32]bool,number)	codeList := make([]uint32,0,number)	for {		if index >= number {			break		}
		key := GetRandom(10)		code := GetHashCode(key)
		// 如果虚拟节点以及被使用，则继续取下一个		if ok:= PointUsed[code]; ok {			continue		}
		if ok := codeMap[code]; ok {			continue		}
		if code < RingMin || code > RingMax {			fmt.Printf("异常的code：%d\n", code)			continue		}
		index++		codeMap[code] = true		codeList = append(codeList, code)	}
	return codeList}
// 获取key的hash codefunc GetHashCode(key string) uint32 {
	hashCode:=crc32.ChecksumIEEE([]byte(key))
	return hashCode}
//生成随机字符串func GetRandom(size int) string {	str := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"	result := make([]byte, 0, size)	for i := 0; i < size; i++ {		result = append(result, str[r.Intn(len(str))])	}
	return string(result)}

package consistency_hash
import (	"fmt"	"testing")

func TestConsistencyHash(t *testing.T) {	nodeNum := 10 // 10个服务器	nodePrefix := "10.35.5.%d:8888"	var virtualNumber uint = 150 // 每个节点 150个虚拟节点
	consistencyHash := NewConsistencyHash()	// 10个服务器节点	for i := 0; i < nodeNum; i++ {		key := fmt.Sprintf(nodePrefix, i)		consistencyHash.AddNode(NewNode(key, virtualNumber))	}
	// 生成100万个key，通过一致性算法放到集群内	keyNum := 1000000	for i:=0;i<keyNum;i++ {		consistencyHash.Set(GetRandom(10))	}
	// 求标准差	consistencyHash.GetSigma()	t.Log("集群各个服务器内key的数量:\n")	for node,count := range consistencyHash.NodeKeyCountMap{		t.Log(node.Host, ": ",count)	}}