写点什么

第五周作业

用户头像
fmouse
关注
发布于: 2020 年 10 月 25 日

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

package consistent_hash
import (
"fmt"
"hash/crc32"
"sort"
"sync"
)
const (
VirtualNodesFactor = 150
)
type node struct {
key string
Data interface{}
}
type ConsistentHash struct {
sync.RWMutex
virtualNodes map[uint32]*node
actNodes map[string]*node
sortRing []uint32
}
func NewConsistentHash() *ConsistentHash {
return &ConsistentHash{
virtualNodes: make(map[uint32]*node),
actNodes: make(map[string]*node),
sortRing: []uint32{},
}
}
func (c *ConsistentHash) Add(nk string, nd interface{}) bool {
c.Lock()
defer c.Unlock()
if _, ok := c.actNodes[nk]; ok {
return false
}
n := &node{
key: nk,
Data: nd,
}
for i := 0; i < VirtualNodesFactor; i++ {
c.virtualNodes[c.hashStr(fmt.Sprintf("%s#%d", nk, i))] = n
}
c.actNodes[nk] = n
c.sortHashRing()
return true
}
func (c *ConsistentHash) Get(key string) *node {
hash := c.hashStr(key)
c.RLock()
defer c.RUnlock()
if len(c.virtualNodes) == 0 {
return nil
}
i := c.search(hash)
return c.virtualNodes[c.sortRing[i]]
}
func (c *ConsistentHash) search(hash uint32) int {
i := sort.Search(len(c.sortRing), func(i int) bool { return c.sortRing[i] >= hash })
if i < len(c.sortRing) {
if i == len(c.sortRing)-1 {
return 0
} else {
return i
}
} else {
return len(c.sortRing) - 1
}
}
func (c *ConsistentHash) Remove(key string) {
c.Lock()
defer c.Unlock()
_, ok := c.actNodes[key]
if !ok {
return
}
delete(c.actNodes, key)
for i := 0; i < VirtualNodesFactor; i++ {
delete(c.virtualNodes, c.hashStr(fmt.Sprintf("%s#%d", key, i)))
}
c.sortHashRing()
}
func (c *ConsistentHash) hashStr(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
func (c *ConsistentHash) sortHashRing() {
c.sortRing = []uint32{}
for k := range c.virtualNodes {
c.sortRing = append(c.sortRing, k)
}
sort.Slice(c.sortRing, func(i, j int) bool {
return c.sortRing[i] < c.sortRing[j]
})
}



不知道是不是对题目理解有误。想完整的实现一致性哈希,但是力不从心。

用户头像

fmouse

关注

还未添加个人签名 2018.08.07 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业