一致性哈希的原理，可以直接看小林coding的什么是一致性哈希

Golang——groupcache

在golang官方的仓库中有个名叫groupcache的仓库，里面提供了个简单的一致性哈希算法是实现，先简单分析一下这个的源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package consistenthash

import (
    "hash/crc32"
    "sort"
    "strconv"
)

type Hash func(data []byte) uint32

type Map struct {
    hash     Hash	// 哈希函数
    replicas int	// 每个节点对应的虚拟节点的数量
    keys     []int 	// Sorted
    hashMap  map[int]string	// 虚拟节点对应的实际节点
}

func New(replicas int, fn Hash) *Map {
    m := &Map{
        replicas: replicas,
        hash:     fn,
        hashMap:  make(map[int]string),
    }
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}

// IsEmpty returns true if there are no items available.
func (m *Map) IsEmpty() bool {
    return len(m.keys) == 0
}

// Add adds some keys to the hash.
func (m *Map) Add(keys ...string) {
    for _, key := range keys {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
            m.keys = append(m.keys, hash)
            m.hashMap[hash] = key
        }
    }
    // 排序，方便二分查找，否则只能一个一个遍历
    sort.Ints(m.keys)
}

// Get gets the closest item in the hash to the provided key.
func (m *Map) Get(key string) string {
    if m.IsEmpty() {
        return ""
    }

    hash := int(m.hash([]byte(key)))

    // 找到第一个虚拟节点
    idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })

    // 没找到，则是第一个虚拟节点（环形）
    if idx == len(m.keys) {
        idx = 0
    }

    return m.hashMap[m.keys[idx]]
}

consistenthash包对外提供了三个函数：

  1. New(replicas int, fn Hash)：返回一个Map对象，这个Map对象是重新定义过的，其中replicas代表每个节点对应的虚拟节点的数量，fn代表哈希函数（nil的话会使用默认的哈希函数crc32.ChecksumIEEE），并且初始化一个map。
  2. Add：向哈希环上添加节点
  3. Get：传入一个key，获取其对应分配的实际节点