一致性哈希

普通哈希存在的问题

简单求取 Hash 值解决了缓存性能的问题，但是没有考虑 节点数量变化 的场景。假设n个节点的集群，移除了其中一台节点，只剩下 n - 1 个，那么之前 hash(key) % n 变成了 hash(key) % (n-1)，也就意味着几乎缓存值对应的节点都发生了改变。即 几乎所有的缓存值都失效了 。节点在接收到对应的请求时，均需要重新去数据源获取数据，容易引起 缓存雪崩 。

缓存雪崩 : 缓存在同一时刻全部失效，造成瞬时DB请求量大、压力骤增，引起雪崩。常因为缓存服务器宕机，或缓存设置了相同的过期时间引起。

一致性哈希

原理

一致性哈希算法将 key 映射到 2^32 的空间中，将这个数字首尾相连， 形成一个环 。

1. 计算节点/机器(通常使用节点的名称、编号和 IP 地址)的哈希值，放置在环上。
2. 计算 key 的哈希值，放置在环上，顺时针寻找到的第一个节点，就是应选取的节点/机器。

如下图所示:

环上有 peer2，peer4，peer6 三个节点，key11，key2，key27 均映射到 peer2，key23 映射到 peer4。此时，如果新增节点/机器 peer8，假设它新增位置如图所示，那么只有 key27 从 peer2 调整到 peer8，其余的映射均没有发生改变。

也就是说，一致性哈希算法，在新增/删除节点时，只需要重新定位该节点附近的一小部分数据，而不需要重新定位所有的节点，这就解决了上述的问题。

数据倾斜

如果 服务器的节点过少 ，容易引起 key 的倾斜。例如上面例子中的 peer2，peer4，peer6 分布在环的上半部分，下半部分是空的。那么映射到环下半部分的 key 都会被分配给 peer2，key 过度向 peer2 倾斜，缓存节点间负载不均。

为了解决这个问题，引入了 虚拟节点 的概念，一个真实节点对应多个虚拟节点。

假设 1 个真实节点对应 3 个虚拟节点，那么 peer1 对应的虚拟节点是 peer1-1、 peer1-2、 peer1-3（通常以添加编号的方式实现），其余节点也以相同的方式操作。

第一步，计算虚拟节点的 Hash 值，放置在环上。
第二步，计算 key 的 Hash 值，在环上顺时针寻找到应选取的虚拟节点，例如是 peer2-1，那么就对应真实节点 peer2。
虚拟节点扩充了节点的数量，解决了节点较少的情况下数据容易倾斜的问题。而且代价非常小，只需要增加一个字典(map)维护真实节点与虚拟节点的映射关系即可。

具体实现示例

一致性哈希简单实现

添加节点

1. Add 函数允许传入 0 或 多个真实节点的名称。
2. 对每一个真实节点 key，对应创建 m.replicas 个虚拟节点，虚拟节点的名称是：strconv.Itoa(i) + key，即通过添加编号的方式区分不同虚拟节点。
3. 使用 c.hashFunc 计算虚拟节点的哈希值，使用 append(c.keys, hash) 添加到环上。
4. 在 hashMap 中增加虚拟节点和真实节点的映射关系。
5. 环上的哈希值排序。

读取节点

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

删除节点

1. 扫描现有的节点, 剔除要溢出的节点
2. 重置哈希环与hashMap
3. 调用 Add 将要保留的节点重新创建