TiDB 5.0 已于上周正式公布，在这个大版本更新中晋升 TiDB 集群的跨核心部署能力是一个重要的着力点，在共识算法这一层，最激动人心莫过于 Joint Consensus 反对了。这个个性帮忙 TiDB 5.0 在跨 AZ 的调度中齐全容忍少数派数目的 AZ 不可用。 本文会先谈成员变更在 TiDB 历史，而后介绍新个性的设计，最初说下咱们在实现过程中遇到的问题和解决方案。
成员变更
TiKV 作为 TiDB 的存储层，负责数据的治理和读写操作。TiKV 将数据划分为大小大致相同的分片，每个分片会有多个正本，别离贮存在不同的 AZ (Available Zone) 中，并应用 Raft 算法来保障强统一的读写。当须要做平衡调度时，TiDB 的元数据管理组件 PD 会挑选出须要做调整的分片，并下发命令给 TiKV 实现正本的搬迁。因为 Raft 算法自身有对于在线成员变更的设计，所以搬迁正本很天然地就通过成员变更算法实现了。
TiKV 所应用的 Raft 算法最开始 port 自 Etcd 的 Raft。 Etcd 并未实现残缺的 Joint Consensus 算法，它实现的是一个非凡的单步变更（和 Diego Ongaro 在其博士论文里提到的单步变更相似，然而不齐全一样）。因而做正本搬迁的时候，整个流程须要分多步实现。
比方，当 PD 决定须要将某正本从 TiKV 2 移到 TiKV 3 时，它会先通过 AddNode 的命令，在 TiKV 3 增加一个新的正本。而后再通过 RemoveNode 命令，将 TiKV 2 上的正本删掉，从而实现变更。实践上也能够先 RemoveNode，再 AddNode 来实现变更，然而这样的操作程序会导致产生 2 正本的中间状态，而 2 正本无奈容忍任意节点宕机，比拟危险。
先加后减的步骤尽管只会产生 4 正本的状态，能容忍单节点宕机，然而还不是 100% 可用的。当须要思考跨 AZ 的场景时，PD 有可能须要将正本搬迁到同一个 AZ 的另一个 TiKV 上。上图中，如果 AZ 2 在 Raft group 4 正本状态时不可用了，就只剩下 AZ 0 和 AZ 1 的 2 正本，无奈造成 quorum，导致整个 Raft group 不可用。 在 5.0 以前的实现里，咱们引入了 learner 角色，并在进入 4 voter 之前，先通过 AddLearner 命令将要增加的正本作为 learner 角色增加到 Raft group 里。 等追上足够的数据，再进行先加后减的操作。这样的步骤能够极大缩小 4 正本存在的工夫窗口（顺利的话是毫秒级），然而仍然不是 100% 可用的。
Joint Consensus
其实 Raft 论文里早已提供了 100% 可用的成员变更算法：Joint Consensus。咱们用 C(a, b, c) 示意一个别离领有 a、b、c 三个正本的 Raft group。当要从 C(a, b, c) 变更成 C(a, b, d)，引入一个中间状态 joint C(a, b, c) & C(a, b, d)。当 group 处于 joint 状态时，日志只有在两个成员列表里都复制到 quorum 能力算 commit。要进行变更时，先从 C(a, b, c) 变更成 C(a, b, c) & C(a, b, d)。每个节点收到这个命令时，立即将本地成员变更成 joint 状态。当这个命令被 commit 当前，再提交一个新的命令退出 joint 状态，从 C(a, b, c) & C(a, b, d) 变成 C(a, b, d)。对于这个算法的正确性证实曾经超出了本文的领域，感兴趣的能够参阅 Raft 论文。
因为 quorum 是基于两个 3 正本的成员列表来计算的，两头 joint 状态和上文提到的屡次单步变更一样，能够容忍任意单节点宕机。和屡次单步操作相比，joint 还能实现 100% 可用。例如图中 4 正本状态，AZ 2 不可用会导致 2 个节点不可用，然而对于两个 3 正本成员列表来说都只是单节点不可用，所以 joint 状态下还是能够放弃可用。
落地
上文咱们提到，Etcd 的 Raft 算法实现和 Diego Ongaro 在论文里提到单步变更的不一样。其实 Etcd 算法实现在博士论文之前就开始做了，次要区别在于成员变更日志只有被 commit 当前才会被真正执行。而论文里的做法是收到就立即执行。咱们从 3.0 便开始调研 joint consensus 的可行性。咱们最开始的做法是与论文齐全保持一致，然而带来的兼容性问题和调整切实太多了。与此同时，CockroachDB 也开始给 Etcd 增加了晚期的 Joint Consensus 反对。咱们最终决定拥抱社区，和 Etcd 保持一致，一起进行优化和测试。
Etcd 的 Joint Consensus 实现并不齐全和论文统一，而是持续连续了下面提到的做法，commit 才执行。这样的益处是成员变更日志和一般日志解决逻辑没有区别，能够应用对立的流程。因为 commit 当前的日志不会被复写，所以也不须要像收到即执行那样做非凡的变更回退，实现起来更简略。然而因为 commit 信息只有 leader 才有，所以非凡场景下因为信息同步不及时会呈现可用性的 bug。感兴趣的同学能够去 Etcd 我的项目查看咱们提交的相干 issue12。这里只举一个其中简略的例子。假如某个 joint 状态 C(a, b, c) & C(a, b, d)，a 是 leader。如果退出 joint 的命令被复制到 a、b、c 当前，a 能够认为命令曾经被 commit，并将 commit index 同步给 c 当前就 crash 了。所以 c 会执行 commit log，认为 joint 曾经退出，从而把本人删除；b、d 并不知道 joint 退出命令曾经被 commit，当发动选举时会仍然会寻求两个 quorum 的投票。然而 a 曾经 crash、c 曾经自毁了，所以 b、d 无奈从 (a, b, c) 中取得 quorum 投票，从而不可用。
这些问题最终导致和原始论文比，commit 才执行的 Joint Consensus 实现增加了两个限度 ：
1. Voter 被移除之前须要先降级成 Learner。
2. 选举时退出同步 commit index 机制。
再来看上文举的例子，因为 voter 不会被间接删除，所以 c 不会把本人删除，而是成为一个 learner。当 b 向 c 寻求投票时，会获知最新的 commit index，得悉 joint 状态曾经退出，从而只会尝试从 C(a, b, d) 中寻找 quorum，最终胜利选举。
总结
在 5.0 咱们增加了 Joint Consensus 反对，实现了跨 AZ 调度过程中能齐全容忍少数派数目的 AZ 不可用。Raft 算法自身比拟清晰简略，然而落地在工程上会有不同的调整和取舍。如果你对于解决分布式系统中相似的问题十分感兴趣，欢送参加咱们的我的项目 TiKV、raft-rs，或简历发送至 jay@pingcap.com 间接退出咱们。