Week_05 作业

// 一、比较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}

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 => cacheBkey2 => cacheAkey3 => cacheAkey4 => cacheBkey5 => cacheB