第五周 - 作业 1
发布于: 2020 年 11 月 22 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
package mainimport ( "fmt" "sort" "strconv" "hash/crc32" "sync" "math")const DEFAULT_REPLICAS = 160type HashRing []uint32func (c HashRing) Len() int { return len(c)}func (c HashRing) Less(i, j int) bool { return c[i] < c[j]}func (c HashRing) Swap(i, j int) { c[i], c[j] = c[j], c[i]}type Node struct { Id int Ip string Port int HostName string Weight int}func NewNode(id int, ip string, port int, name string, weight int) *Node { return &Node{ Id: id, Ip: ip, Port: port, HostName: name, Weight: weight, }}type Consistent struct { Nodes map[uint32]Node numReps int Resources map[int]bool ring HashRing sync.RWMutex}func NewConsistent() *Consistent { return &Consistent{ Nodes: make(map[uint32]Node), numReps: DEFAULT_REPLICAS, Resources: make(map[int]bool), ring: HashRing{}, }}func (c *Consistent) Add(node *Node) bool { c.Lock() defer c.Unlock() if _, ok := c.Resources[node.Id]; ok { return false } count := c.numReps * node.Weight for i := 0; i < count; i++ { str := c.joinStr(i, node) c.Nodes[c.hashStr(str)] = *(node) } c.Resources[node.Id] = true c.sortHashRing() return true}func (c *Consistent) sortHashRing() { c.ring = HashRing{} for k := range c.Nodes { c.ring = append(c.ring, k) } sort.Sort(c.ring)}func (c *Consistent) joinStr(i int, node *Node) string { return node.Ip + "*" + strconv.Itoa(node.Weight) + "-" + strconv.Itoa(i) + "-" + strconv.Itoa(node.Id)}// MurMurHash算法 :https://github.com/spaolacci/murmur3func (c *Consistent) hashStr(key string) uint32 { return crc32.ChecksumIEEE([]byte(key))}func (c *Consistent) Get(key string) Node { c.RLock() defer c.RUnlock() hash := c.hashStr(key) i := c.search(hash) return c.Nodes[c.ring[i]]}func (c *Consistent) search(hash uint32) int { i := sort.Search(len(c.ring), func(i int) bool { return c.ring[i] >= hash }) if i < len(c.ring) { if i == len(c.ring)-1 { return 0 } else { return i } } else { return len(c.ring) - 1 }}func (c *Consistent) Remove(node *Node) { c.Lock() defer c.Unlock() if _, ok := c.Resources[node.Id]; !ok { return } delete(c.Resources, node.Id) count := c.numReps * node.Weight for i := 0; i < count; i++ { str := c.joinStr(i, node) delete(c.Nodes, c.hashStr(str)) } c.sortHashRing()}func Variance(arr []int) int{ m := len(arr) sum := 0 for i := 0; i < m; i++ { sum += arr[i] } dAve := sum / m dVar := 0 for i := 0; i < m; i++ { dVar += (arr[i] - dAve) * (arr[i] - dAve); } return dVar / m}func main() { cHashRing := NewConsistent() for i := 0; i < 10; i++ { si := fmt.Sprintf("%d", i) cHashRing.Add(NewNode(i, "172.18.1."+si, 8080, "host_"+si, 1)) } //for k, v := range cHashRing.Nodes { // fmt.Println("Hash:", k, " IP:", v.Ip) //} ipMap := make(map[string]int, 0) for i := 0; i < 1000000; i++ { si := fmt.Sprintf("key%d", i) k := cHashRing.Get(si) if _, ok := ipMap[k.Ip]; ok { ipMap[k.Ip] += 1 } else { ipMap[k.Ip] = 1 } } var arr []int for k, v := range ipMap { fmt.Println("Node IP:", k, " count:", v) arr = append(arr, ipMap[k]) } variance := Variance(arr) fmt.Println("value of variance", math.Sqrt(float64(variance)))}
划线
评论
复制
发布于: 2020 年 11 月 22 日阅读数: 16
Mr_No爱学习
关注
还未添加个人签名 2019.09.13 加入
还未添加个人简介
评论