一致性 hash

package cache
type Node struct {
	begin    uint32 // 起始位置,它为上一个节点的结束位置值
	end      uint32 // 结束位置
	nodeName string // 节点名
	virName  string // 虚拟节点名
}
type nodeListType []*Node
func (n nodeListType) Len() int {
	return len(n)
}
func (n nodeListType) Swap(i, j int) {
	n[i], n[j] = n[j], n[i]
}
func (n nodeListType) Less(i, j int) bool {
	return n[i].end < n[j].end
}

package cache
import (
	"fmt"
	"hash/crc32"
	"sort"
)
//获取hash值
func hashkey(key string) uint32 {
	if len(key) < 64 {
		//声明一个数组长度为64
		var srcatch [64]byte
		//拷贝数据到数组中
		copy(srcatch[:], key)
		//使用IEEE 多项式返回数据的CRC-32校验和
		return crc32.ChecksumIEEE(srcatch[:len(key)])
	}
	return crc32.ChecksumIEEE([]byte(key))
}
var MAX_UINT uint32 = 4294967295
type DataInfo struct {
	keyHash uint32
	data    interface{}
}
type Cache struct {
	nodeCount    uint32 // 实际物理节点数
	virtualCount int    // 每个节点对应虚拟节点个数
	nodeList nodeListType // 服务器节点列表
	dataMap map[string]*DataInfo // 保存kv数据
}
// 添加节点
func (c *Cache) AddNode(nodeName string) {
	c.nodeCount++
	for i := 0; i < c.virtualCount; i++ {
		virName := fmt.Sprintf("%s_%d", nodeName, i)
		hashVal := hashkey(virName)
		// 插入到节点列表中
		c.nodeList = append(c.nodeList, &Node{
			begin:    0,
			end:      hashVal,
			nodeName: nodeName,
			virName:  virName})
	}
	// 重新排序
	sort.Sort(c.nodeList)
	// 重新计算起始区间
	tmp := c.nodeList[0]
	length := len(c.nodeList)
	tmp.begin = c.nodeList[length-1].end // 起始节点,以最后一个节点作为结束
	for i := 1; i < length; i++ {
		c.nodeList[i].begin = tmp.end
		tmp = c.nodeList[i]
	}
}
// 添加元素
func (c *Cache) Add(key string, val interface{}) {
	c.dataMap[key] = &DataInfo{
		data:    val,
		keyHash: hashkey(key),
	}
}
// 删除元素
func (c *Cache) Del(key string) {
	delete(c.dataMap, key)
}
// 获取key所在的节点
func (c *Cache) GetNodeName(key string) (nodeName string, virName string) {
	nodeName = ""
	virName = ""
	length := len(c.nodeList)
	if length == 0 {
		return
	}
	hash := hashkey(key)
	idx := sort.Search(length, func(i int) bool { return c.nodeList[i].end >= hash })
	if idx >= length {
		// 超出最后一个节点,取第一个节点最近
		idx = 0
	}
	nodeName = c.nodeList[idx].nodeName
	virName = c.nodeList[idx].virName
	return
}
// 获取节点下的数据总数
func (c *Cache) GetNodeDataCount(nodeName string) int {
	nodeLst := []*Node{}
	for i := 0; i < len(c.nodeList); i++ {
		if c.nodeList[i].nodeName == nodeName {
			nodeLst = append(nodeLst, c.nodeList[i])
		}
	}
	length := len(nodeLst)
	if length == 0 {
		return 0
	}
	total := 0
	for _, v := range c.dataMap {
		for _, node := range nodeLst {
			if node.begin > node.end { // 处理第一节点
				if (node.begin < v.keyHash && v.keyHash <= MAX_UINT) ||
					(0 <= v.keyHash && v.keyHash <= node.end) {
					total++
				}
			} else if node.begin < v.keyHash && v.keyHash <= node.end {
				total++
			}
		}
	}
	return total
}
func (c *Cache) PrintNodeList() {
	for _, v := range c.nodeList {
		fmt.Println("node:", v.begin, v.end, v.virName)
	}
	fmt.Println("total:", len(c.nodeList))
}
// 创建缓存
func CreateCache(virtualCnt int) *Cache {
	return &Cache{virtualCount: virtualCnt,
		dataMap: map[string]*DataInfo{}}
}

package main
import (
	"fmt"
	"math"
	"math/rand"
	"test/cache"
	"time"
)
func GetRandomString(l int) string {
	str := "0123456789abcdefghijklmnopqrstuvwxyz"
	bytes := []byte(str)
	result := []byte{}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := 0; i < l; i++ {
		result = append(result, bytes[r.Intn(len(bytes))])
	}
	return string(result)
}
func CalcStandardDeviation(lst []float64, agv float64, total float64) float64 {
	var tmp float64 = 0
	for i := 0; i < len(lst); i++ {
		tmp += math.Pow(lst[i]-agv, 2)
	}
	return math.Sqrt(tmp / 10)
}
func main() {
	nodeCount := 10
	virNodeCount := 150
	c := cache.CreateCache(virNodeCount)
	// 添加节点
	nodeLst := []string{}
	for i := 0; i < nodeCount; i++ {
		nodeName := fmt.Sprintf("node_%s_%d", GetRandomString(4), i)
		c.AddNode(nodeName)
		nodeLst = append(nodeLst, nodeName)
	}
	// 添加数据
	for i := 0; i < 1000000; i++ {
		key := fmt.Sprintf("%s_%d", GetRandomString(6), i)
		c.Add(key, i)
	}
	c.PrintNodeList()
	fmt.Println("-----------------------------------")
	// 打印节点对应数据数量
	total := 0
	countList := []float64{}
	for i := 0; i < nodeCount; i++ {
		nodeName := nodeLst[i]
		cnt := c.GetNodeDataCount(nodeLst[i])
		fmt.Printf("node :%s  count: %d\n", nodeName, cnt)
		total += cnt
		countList = append(countList, float64(cnt))
	}
	fmt.Println("-----------------------------------")
	// 标准差计算
	var agv float64 = float64(total) / float64(nodeCount)
	fmt.Println("总数:", total, "平均:", agv, "标准差:", CalcStandardDeviation(countList, float64(agv), float64(total)))
}