# Go语言实现一致性哈希(Consistent Hashing)算法

xcltapestry · · 8498 次点击 · · 开始浏览

一致性哈希可用于解决服务器均衡问题。 用Golang简单实现了下，并加入了权重。可采用合适的权重配合算法使用。

```package main

//一致性哈希(Consistent Hashing)
//author: Xiong Chuan Liang
//date: 2015-2-20

import (
"fmt"
"hash/crc32"
"sort"
"strconv"
"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()
}

func main() {

cHashRing := NewConsistent()

for i := 0; i < 10; i++ {
si := fmt.Sprintf("%d", i)
}

for k, v := range cHashRing.Nodes {
fmt.Println("Hash:", k, " IP:", v.Ip)
}

ipMap := make(map[string]int, 0)
for i := 0; i < 1000; i++ {
si := fmt.Sprintf("key%d", i)
k := cHashRing.Get(si)
if _, ok := ipMap[k.Ip]; ok {
ipMap[k.Ip] += 1
} else {
ipMap[k.Ip] = 1
}
}

for k, v := range ipMap {
fmt.Println("Node IP:", k, " count:", v)
}

}

/*

Node IP: 172.18.1.2  count: 115
Node IP: 172.18.1.8  count: 111
Node IP: 172.18.1.3  count: 94
Node IP: 172.18.1.1  count: 84
Node IP: 172.18.1.7  count: 107
Node IP: 172.18.1.6  count: 117
Node IP: 172.18.1.4  count: 92
Node IP: 172.18.1.5  count: 112
Node IP: 172.18.1.0  count: 63
Node IP: 172.18.1.9  count: 105
*/
```
上面是简单测试后的结果。

MAIL:  xcl_168@aliyun.com

BLOG: http://blog.csdn.net/xcl168

1 回复  |  直到 2000-01-01 00:00:00

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

一致性哈希可用于解决服务器均衡问题。 用Golang简单实现了下，并加入了权重。可采用合适的权重配合算法使用。

```package main

//一致性哈希(Consistent Hashing)
//author: Xiong Chuan Liang
//date: 2015-2-20

import (
"fmt"
"hash/crc32"
"sort"
"strconv"
"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()
}

func main() {

cHashRing := NewConsistent()

for i := 0; i < 10; i++ {
si := fmt.Sprintf("%d", i)
}

for k, v := range cHashRing.Nodes {
fmt.Println("Hash:", k, " IP:", v.Ip)
}

ipMap := make(map[string]int, 0)
for i := 0; i < 1000; i++ {
si := fmt.Sprintf("key%d", i)
k := cHashRing.Get(si)
if _, ok := ipMap[k.Ip]; ok {
ipMap[k.Ip] += 1
} else {
ipMap[k.Ip] = 1
}
}

for k, v := range ipMap {
fmt.Println("Node IP:", k, " count:", v)
}

}

/*

Node IP: 172.18.1.2  count: 115
Node IP: 172.18.1.8  count: 111
Node IP: 172.18.1.3  count: 94
Node IP: 172.18.1.1  count: 84
Node IP: 172.18.1.7  count: 107
Node IP: 172.18.1.6  count: 117
Node IP: 172.18.1.4  count: 92
Node IP: 172.18.1.5  count: 112
Node IP: 172.18.1.0  count: 63
Node IP: 172.18.1.9  count: 105
*/
```
上面是简单测试后的结果。

MAIL:  xcl_168@aliyun.com

BLOG: http://blog.csdn.net/xcl168