突破领导者的限制
问题
假设我们使用 Raft 算法实现了一个 KV 服务。虽然领导者简化了共识协商，但是写请求只能在领导者上处理（如果系统设计要求强一致性，那么读请求也应该由领导者处理），所以集群的接入性能相当于单机。随着业务的发展，系统很容易到达性能瓶颈。
那么，怎么突破领导者的限制呢？方法就是数据分片，即每个集群只负责存储一部分数据。所有集群的数据合起来才是全部数据。
为了方便，以下用节点来代替集群。
那怎么决定哪些数据由哪个节点存储呢？我们需要在客户端和节点之间加一层 Proxy 层：Proxy 层接收客户端的请求，通过对 key 哈希，然后取模来决定由哪个节点来处理该请求。
哈希算法
使用哈希算法，我们是这样切分流量的：假设客户端的请求中有一个 key，Proxy 层接收到请求后，根据下列公式，计算出处理该请求的节点：cluster_index = hash(key) % cluster_num。
这种哈希算法优点是简单、快速。但是当节点的数量发生变更时，同一个 key 计算出的节点索引也会变化，导致无法定位到数据。这种情况下，我们就需要迁移数据。迁移数据的成本非常高。例如，从 3 个节点变更为 4 个节点，75% 的数据需要迁移，成本非常高。
一致性哈希算法
我们希望有一种哈希算法：在发生节点数量变更时，迁移尽量少的数据。一致性算法能满足我们的要求。
算法原理
算法原理为：
将一个虚拟圆环分为 2^32 份，按顺时针方向，从 0 开始，直到 2^32 - 1。
使用某种哈希算法，将各个节点映射到圆环上。
-
当需要对指定的 key 读写时，需要
- 使用某种哈希算法，计算出 key 在圆环上的位置
- 沿着顺时针方向找到的第一个节点，就是 key 对应的节点。
假设，如果节点 C 故障了，那么只会影响故障节点与其前一个节点间的数据，它们都会被路由到故障节点的下一个节点。
所以，相比哈希算法，如果使用一致性哈希算法，从 3 个节点变更为 4 个节点，只有 25% 的数据需要迁移，成本为原来的 1/3。
假设，如果新增一个节点 D，那么只会影响新节点与其前一个节点间的数据，它们都会被路由到新节点。
[站外图片上传中...(image-58f87f-1590412658301)]
总的来说，一致哈希算法具有较好的容错性和可扩展性。
虚拟节点
在哈希寻址中，经常会出现这样的问题：客户端请求的 key 比较集中，有的机器负载高，有的机器负载低，那有什么办法使得访问均匀分布吗？答案是虚拟节点。
其实，每个节点有多个哈希值分布在虚拟圆环上，并且同一个节点的多个哈希值是相邻的，不会出现交叉的情况。一个哈希值对应一个虚拟节点，并将虚拟节点映射到实际节点。
对比
当节点数量越多时，哈希算法的迁移数量越大，一致性哈希算法的迁移数量越小。使用一致哈希实现哈希寻址时，可以通过增加节点数降低节点宕机对整个集群的影响，以及故障恢复时需要迁移的数据量。
提高 Raft 集群的可用性
在多个 Raft 集群组成的 KV 系统中，如何设计一致哈希，实现当某个集群的节点出现了故障时，整个系统还能稳定运行呢？
答：数据要同时写入当前集群和下一个集群。某个Raft集群挂掉后，原本路由到这个集群的请求，现在都到下一个Raft集群去了。只要下一个Raft集群保存了上一个集群的数据，即使某个集群挂了，整个系统还能正常提供服务。只有两个相邻集群都同时挂掉时，某个集群数据才不能访问。
