第五周 作业一 第一题
package main
import (
"fmt"
"sort"
"strconv"
"hash/crc32"
"sync"
)
const DEFAULT_REPLICAS = 160
type HashRing []uint32
func (c HashRing) Len() int {
return len(c)
}
func (c HashRing) Less(i, j int) bool {
return c[i] < c[j]
}
func (c HashRing) Swap(i, j int) {
c[i], c[j] = c[j], c[i]
}
type Node struct {
Id int
Ip string
Port int
HostName string
Weight int
}
func NewNode(id int, ip string, port int, name string, weight int) *Node {
return &Node{
Id: id,
Ip: ip,
Port: port,
HostName: name,
Weight: weight,
}
}
type Consistent struct {
Nodes map[uint32]Node
numReps int
Resources map[int]bool
ring HashRing
sync.RWMutex
}
func NewConsistent() *Consistent {
return &Consistent{
Nodes: make(map[uint32]Node),
numReps: DEFAULT_REPLICAS,
Resources: make(map[int]bool),
ring: HashRing{},
}
}
func (c Consistent) Add(node Node) bool {
c.Lock()
defer c.Unlock()
if _, ok := c.Resources[node.Id]; ok {
return false
}
count := c.numReps * node.Weight
for i := 0; i < count; i++ {
str := c.joinStr(i, node)
c.Nodes[c.hashStr(str)] = *(node)
}
c.Resources[node.Id] = true
c.sortHashRing()
return true
}
func (c *Consistent) sortHashRing() {
c.ring = HashRing{}
for k := range c.Nodes {
c.ring = append(c.ring, k)
}
sort.Sort(c.ring)
}
func (c Consistent) joinStr(i int, node Node) string {
return node.Ip + "*" + strconv.Itoa(node.Weight) +
"-" + strconv.Itoa(i) +
"-" + strconv.Itoa(node.Id)
}
// MurMurHash算法 :https://github.com/spaolacci/murmur3
func (c *Consistent) hashStr(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
func (c *Consistent) Get(key string) Node {
c.RLock()
defer c.RUnlock()
hash := c.hashStr(key)
i := c.search(hash)
return c.Nodes[c.ring[i]]
}
func (c *Consistent) search(hash uint32) int {
i := sort.Search(len(c.ring), func(i int) bool { return c.ring[i] >= hash })
if i < len(c.ring) {
if i == len(c.ring)-1 {
return 0
} else {
return i
}
} else {
return len(c.ring) - 1
}
}
func (c Consistent) Remove(node Node) {
c.Lock()
defer c.Unlock()
if _, ok := c.Resources[node.Id]; !ok {
return
}
delete(c.Resources, node.Id)
count := c.numReps * node.Weight
for i := 0; i < count; i++ {
str := c.joinStr(i, node)
delete(c.Nodes, c.hashStr(str))
}
c.sortHashRing()
}
还未添加个人签名 2018.10.29 加入
还未添加个人简介
评论