哈希一致性算法讲解

到目前为止是没有任何问题的，那么我们试试增加一台机器

第一张图片3号对应的是1号服务器
第二张图片3号对应的是0号服务器

增加服务器后如果我们对服务器请求三号图片，本来应该到1号服务器去找，但是我们由于取模的数发生改变后（2变成了3），我们最后会定位到0号服务器。

这里由于服务器数量发生变化，就会发生无法从缓存中获取数据的情况。那么就会从后端获取数据，如果这种情况很多，就会给后端很大的压力造成缓存血崩

第一部改进

我们模的数字不再是设备数了，而是m，m一般是2的32次方-1

（图片上有点小问题，服务器下标应该-1）
按照这个方法
c1存储在s0
c2,c3,c5,存储在s1
c6,C4,C7,C8存储在s2

这样子处理是不是很完美？没有，以但我们的服务器出现了一些聚集，那么我们的缓存就会集中在一个服务器上面：

除了C1存储在S0，其他的数据都存储在S2。会产生聚集，那么如何解决

改进方法，虚拟对称节点

假设虚拟节点，这样就能很好的解决聚集问题，我们存储在S0的虚拟节点也就相当于存储在S0本身的节点中

虚拟节点扩充了节点的数量，解决了节点较少的情况下数据容易倾斜的问题。而且代价非常小，只需要增加一个字典(map)维护真实节点与虚拟节点的映射关系即可。

代码实现

主要数据结构以及构造函数New()

package consistenthashimport ("hash/crc32""sort""strconv"
)type Hash func(data []byte) uint32type Map struct {hash     Hashreplicas intkeys     []int // SortedhashMap  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
}

定义了函数类型 Hash，采取依赖注入的方式，允许用于替换成自定义的 Hash 函数，也方便测试时替换，默认为 crc32.ChecksumIEEE 算法。

Map 是一致性哈希算法的主数据结构，包含 4 个成员变量：
1.Hash 函数 hash；
2.虚拟节点倍数 replicas；
3.哈希环 keys；
4。虚拟节点与真实节点的映射表 hashMap，键是虚拟节点的哈希值，值是真实节点的名称。

构造函数 New() 允许自定义虚拟节点倍数和 Hash 函数。

Add() 方法,添加会向哈希添加一些键

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)
}

Add 函数允许传入 0 或 多个真实节点的名称。

对每一个真实节点 key，对应创建 m.replicas 个虚拟节点，虚拟节点的名称是：strconv.Itoa(i) + key，即通过添加编号的方式区分不同虚拟节点。

使用 m.hash() 计算虚拟节点的哈希值，使用 append(m.keys, hash) 添加到环上。在 hashMap 中增加虚拟节点和真实节点的映射关系。

最后一步，环上的哈希值排序。

Get()方法，获取哈希中与提供的键最接近的项

func (m *Map) Get(key string) string {if len(m.keys) == 0 {return ""}hash := int(m.hash([]byte(key)))// Binary search for appropriate replica.idx := sort.Search(len(m.keys), func(i int) bool {return m.keys[i] >= hash})return m.hashMap[m.keys[idx%len(m.keys)]]
}

选择节点就非常简单了：

第一步，计算 key 的哈希值。
第二步，顺时针找到第一个匹配的虚拟节点的下标 idx，从 m.keys 中获取到对应的哈希值。如果 idx == len(m.keys)，说明应选择 m.keys[0]，因为 m.keys 是一个环状结构，所以用取余数的方式来处理这种情况。
第三步，通过 hashMap 映射得到真实的节点。