架构师训练营 0 期第五周

用户头像
Blink
关注
发布于: 2020 年 07 月 09 日

作业

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。



package main
import (
"fmt"
"hash/crc32"
"math"
"sort"
"strconv"
"sync"
)
type Hash func(key string) uint32
type Node struct {
host string
data map[int]int
}
func NewNode(h string) *Node {
return &Node{
host: h,
data: make(map[int]int),
}
}
func (n *Node) Set(k int, v int) {
n.data[k] = v
}
func (n *Node) Count() int {
return len(n.data)
}
func (n *Node) Print() {
fmt.Printf("Node:%s,Count:%d\n", n.host, n.Count())
}
type Map struct {
hash Hash
replicas int
keys []int
hashMap map[int]*Node
Nodes []*Node
sync.RWMutex
}
func NewMap(replicas int) *Map {
return &Map{
hash: func(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
},
replicas: replicas,
hashMap: make(map[int]*Node),
}
}
func (m *Map) AddNode(h string) {
m.Lock()
defer m.Unlock()
rNode := NewNode(h)
for i := 0; i < m.replicas; i++ {
node := NewNode(h + strconv.Itoa(i))
hash := int(m.hash(node.host))
m.keys = append(m.keys, hash)
m.hashMap[hash] = rNode
}
m.Nodes = append(m.Nodes, rNode)
sort.Ints(m.keys)
}
func (m *Map) GetNode(k string) *Node {
hash := int(m.hash(k))
idx := sort.Search(len(m.keys), func(i int) bool {
return m.keys[i] >= hash
})
return m.hashMap[m.keys[idx%len(m.keys)]]
}
func main() {
m := NewMap(200)
for i := 1; i <= 10; i++ {
m.AddNode("server-" + strconv.Itoa(i))
}
for i := 1; i <= 1000000; i++ {
m.GetNode(strconv.Itoa(i)).Set(i, i)
}
for i := range m.Nodes {
m.Nodes[i].Print()
}
var variance float64
for i := range m.Nodes {
variance += math.Pow(float64(m.Nodes[i].Count())-100000, 2)
}
fmt.Println("σ:", math.Sqrt(variance/float64(10)))
}



Node:server-1,Count:101717
Node:server-2,Count:100221
Node:server-3,Count:104626
Node:server-4,Count:99440
Node:server-5,Count:112020
Node:server-6,Count:124128
Node:server-7,Count:97952
Node:server-8,Count:110756
Node:server-9,Count:88892
Node:server-10,Count:60248
σ: 16046.327299416524



总结

(待完善)

缓存



消息队列



负载均衡



分布式数据库

用户头像

Blink

关注

还未添加个人签名 2017.02.09 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 0 期第五周