架构师训练营第 0 期 - 第 5 周 - 命题作业

package main
import (
	"fmt"
	"hash/crc32"
	"math"
	"math/rand"
	"sort"
	"strconv"
	"sync"
)
// Node 代表节点，存储数据
type Node struct {
	Name   string
	values map[string]string
	lock   sync.RWMutex
}
// Get ...
func (n *Node) Get(key string) string {
	n.lock.RLock()
	defer n.lock.RUnlock()
	return n.values[key]
}
// Set ...
func (n *Node) Set(key, value string) {
	n.lock.Lock()
	defer n.lock.Unlock()
	n.values[key] = value
}
// Del ...
func (n *Node) Del(key string) {
	n.lock.Lock()
	defer n.lock.Unlock()
	delete(n.values, key)
}
// Count 计算存储的数据量
func (n *Node) Count() int {
	n.lock.RLock()
	defer n.lock.RUnlock()
	return len(n.values)
}
// ConsistHash 一致性哈希
type ConsistHash struct {
	virtualScale int
	hashRing     []int
	vNodes       map[int]*Node
	lock         sync.RWMutex
}
// NewConsistHash scale: 每个节点的虚拟节点数量
func NewConsistHash(scale int) *ConsistHash {
	c := &ConsistHash{
		scale,
		make([]int, 0),
		make(map[int]*Node),
		sync.RWMutex{},
	}
	return c
}
func (c *ConsistHash) sortRing() {
	sort.Ints(c.hashRing)
}
func (c *ConsistHash) search(key string) *Node {
	if len(c.hashRing) < 1 {
		return nil
	}
	pos := int(crc32.ChecksumIEEE([]byte(key)))
	for i := 0; i < len(c.hashRing)-1; i++ {
		if pos > c.hashRing[i] && pos < c.hashRing[i+1] {
			return c.vNodes[c.hashRing[i]]
		}
	}
	return c.vNodes[c.hashRing[0]]
}
// AddNode 新增节点
func (c *ConsistHash) AddNode(n *Node) {
	c.lock.Lock()
	defer c.lock.Unlock()
	for i := 0; i < c.virtualScale; i++ {
		p := int(crc32.ChecksumIEEE([]byte(n.Name + strconv.Itoa(i))))
		c.vNodes[p] = n
		c.hashRing = append(c.hashRing, p)
	}
	c.sortRing()
}
// GetNode 取出节点
func (c *ConsistHash) GetNode(key string) *Node {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.search(key)
}
// DelNode ...
func (c *ConsistHash) DelNode(n *Node) {
	// TODO:省略，待补充
}
// 直接在这里写测试用例了
func main() {
	// 测试: 10台服务器，100万个kv，计算每台服务器最终存下数据量的标准差
	// 创建一致性哈希对象
	chash := NewConsistHash(200)
	// 创建server0~server9，并添加到chash中
	nodes := make([]*Node, 0)
	for i := 0; i < 10; i++ {
		node := &Node{
			"server" + strconv.Itoa(i),
			make(map[string]string),
			sync.RWMutex{},
		}
		chash.AddNode(node)
		nodes = append(nodes, node)
	}
	// 随机生成100万个k(string)和v(string)，存入节点
	rand.Seed(233)
	for i := 0; i < 1000000; i++ {
		// 随机生成k,v
		k := strconv.Itoa(rand.Int())
		v := strconv.Itoa(rand.Int())
		// 用k取出命中的node
		n := chash.GetNode(k)
		// 将v存入node
		n.Set(k, v)
	}
	// 求标准差
	var avg, sum int
	// 先求平均值
	for _, n := range nodes {
		sum += n.Count()
		fmt.Printf("服务器:%s,数据量:%d\n", n.Name, n.Count())
	}
	avg = sum / len(nodes)
	sum = 0
	for _, n := range nodes {
		sum += (avg - n.Count()) * (avg - n.Count())
	}
	sd := math.Sqrt(float64(sum / len(nodes)))
	fmt.Printf("标准差:%f", sd)
}