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

发布于: 20 小时前

作业一:

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

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

运行结果:(时间关系,用了顺序查找实现的节点搜索,所以运行耗时较慢)

代码:

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)
}

用户头像

关注

还未添加个人签名 2018.09.10 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 0 期 - 第 5 周 - 命题作业