写点什么

Week_05 作业

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

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

题目分析:

// 一、比较hashcode大小需要排序,排序使用数组,成员中需要有一个数组sortedHashCodes和更新数组排序的函数,数组里存放hashcode
// 每次插入新值时需要进行排序, hashcode为uint32,hash环为0~2^(32-1)
// 二、通过hash环需要获取与某个key邻近的key,因此需要一个能保存该key的结构, map[key]
// 三、需要并发安全,因此要加读写锁 sync.RWMutex
// 四、Add和Remove操作,是通过key计算得出hashcode,放入sortedHashCodes,同时需要在member中保存该key
// 五、Get和GetN操作,需要根据key计算得出hashcode,找比其大的hashcode对应的key,因此,需要通过hashcode找到key。结构为map[uint32]string
// 六、Set操作是Add的变体,批量增加key
// 七、需要通过不同的hash算法进行计算, 因此需要有一个hash函数 hashFunc

接口定义:

type IConsistent interface {
Add(string)
Remove(string)
Set([]string)
Get(string) (string, error)
GetN(string, int) ([]string, error)
Members() []string
}

类定义:

type Consistent struct {
ring map[uint32]string
sortedHashCodes uints
members map[string]struct{}
hashFunc func(string) uint32
sync.RWMutex
}

New函数:

func New(hashFunc func(string) uint32) *Consistent {
if hashFunc == nil {
hashFunc = func(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
}
return &Consistent{
ring: make(map[uint32]string),
members: make(map[string]struct{}),
hashFunc: hashFunc,
}
}

接口函数实现:

func (c *Consistent) Add(key string) {
c.Lock()
defer c.Unlock()
c.add(key)
}
func (c *Consistent) add(key string) {
// 加入ring中
c.ring[c.hashFunc(key)] = key
// 加入members中
c.members[key] = struct{}{}
// 更新排序
var hashCodeList uints
for hashCode, _ := range c.ring {
hashCodeList = append(hashCodeList, hashCode)
}
sort.Sort(hashCodeList)
c.sortedHashCodes = hashCodeList
}
func (c *Consistent) Remove(key string) {
c.Lock()
defer c.Unlock()
c.remove(key)
}
func (c *Consistent) remove(key string) {
// 移除从members中
delete(c.members, key)
// 移除从ring中
delete(c.ring, c.hashFunc(key))
// 更新排序
var hashCodeList uints
for hashCode, _ := range c.ring {
hashCodeList = append(hashCodeList, hashCode)
}
sort.Sort(hashCodeList)
c.sortedHashCodes = hashCodeList
}
func (c *Consistent) Set(keys []string) {
c.Lock()
defer c.Unlock()
// 先把不在keys中的member都清理了
for m, _ := range c.members {
found := false
for _, key := range keys {
if m == key {
found = true
break
}
}
if !found {
c.remove(m)
}
}
// 把不在member中key加入
for _, key := range keys {
if _, ok := c.members[key]; ok {
continue
}
c.add(key)
}
}
func (c *Consistent) Get(key string) (string, error) {
c.RLock()
defer c.RUnlock()
if len(c.ring) == 0 {
return "", ErrorEmptyRing
}
hashCode := c.hashFunc(key)
// 在数组中找到大于该hashcode的hashcode,通过反向索引找到对应的key
index := sort.Search(len(c.sortedHashCodes), func(i int) bool {
return c.sortedHashCodes[i] > hashCode //这里应该没有可能等于
})
// Search在没找到的情况下,会返回len(c.sortedHashCodes),没找到时返回从0开始最近的key
if index >= len(c.sortedHashCodes) {
index = 0
}
return c.ring[c.sortedHashCodes[index]], nil
}
func (c *Consistent) GetN(Key string, n int) ([]string, error) {
c.RLock()
defer c.RUnlock()
if len(c.ring) == 0 {
return nil, ErrorEmptyRing
}
if len(c.sortedHashCodes) < n {
n = len(c.sortedHashCodes)
}
hashCode := c.hashFunc(Key)
index := sort.Search(len(c.sortedHashCodes), func(i int) bool {
return c.sortedHashCodes[i] > hashCode
})
if index >= len(c.sortedHashCodes) {
index = 0
}
var result []string
result = append(result, c.ring[c.sortedHashCodes[index]])
if len(result) == n {
return result, nil
}
var i = index + 1
for ; i != index; i++ {
if i >= len(c.sortedHashCodes) {
i = 0
}
key := c.ring[c.sortedHashCodes[i]]
if !containsKey(result, key) {
result = append(result, key)
}
if len(result) == n {
break
}
}
return result, nil
}
func containsKey(result []string, key string) bool {
for _, k := range result {
if key == k {
return true
}
}
return false
}
func (c *Consistent) Members() []string {
c.RLock()
defer c.RUnlock()
var result []string
for m, _ := range c.members {
result = append(result, m)
}
return result
}

简单测试:

func main() {
c := New(nil)
c.Add("cacheA")
c.Add("cacheB")
c.Add("cacheC")
users := []string{"key1", "key2", "key3", "key4", "key5"}
for _, u := range users {
server, err := c.Get(u)
if err != nil {
log.Fatal(err)
}
fmt.Printf("%s => %s\n", u, server)
}
}



[root@erlangboy consistent]# go run consistent.go
key1 => cacheB
key2 => cacheA
key3 => cacheA
key4 => cacheB
key5 => cacheB

小结:

关键之处在于先定义接口,确定用户用例。之后定义合适的数据结构,呈现相应的数据信息。娃叫唤,今天先到这。不足的地方在于未实现虚拟节点的逻辑,以及未能完成第二个题目

todo

  • 增加虚拟节点逻辑

  • 进行题目2的测试

用户头像

golangboy

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论

发布
暂无评论
Week_05 作业