巧妙的 一致性 hash

问题

• raft 的局限：写请求只能在 Leader 节点上进行处理，集群性能约等于单机

• 普通 hash （取余）分集群问题：集群数量发送变更的时候就需要做数据迁移重新映射，由于集群扩容前后数量不一致导致 hash 计算后得到结果不一致

一致性 hash

本质是对 2 的 32 次方取模运算，将整个哈希值空间组成一个虚拟的圆环，也就是哈希环。下面看图说话。

key 如何定位

image.png

1. 一开始根据取模后可以计算出 abc 节点在环上的位置

2. key1 访问时也可以计算出在环上的位置

3. 然后顺时针向前走，就能找到对应 key 所对应的节点

节点移除

image.png

1. 当节点移除时原先的 key 会继续顺时针向前找到对应的新节点

2. 会影响的 key 是从 A 到 B 原先的 key，但是原来的 B 到 C 和 C 到 A 之前的数据不会被影响

   节点新增

image.png

1. 新节点加入后，原先的 key 可能顺时针走到新的节点上

2. 会影响的同样为从 A 到 B 原先的 key，但并不是全部

   虚拟节点

image.png

1. 对于同一个节点增加一个或多个虚拟节点来让整个哈希环分布更加均匀
2. 这样对应的 key 在访问的时候不会犹豫环中的空间过于密集从而冷热不均

总结

1. 哈希环利用环的性质让节点的增减变化只会影响到部分数据的路由
2. 相对应的如果要做数据迁移也会影响到更少的数据
3. 通过虚拟节点的加入还能减少节点访问的冷热不均的问题