思辨｜Raft共识算法简介
分布式存储系统通常通过维护多个副本来进行容错，提高系统的可用性。要实现此目标，就必须要解决一个核心问题：维护多个副本的一致性，即共识。Raft 是一个容易理解和实现的共识算法，本文将介绍它的基本原理，以及在 CockroachDB 和 TiDB 两种数据库中的应用。
Raft 算法基于复制状态机的思想，所有的副本上有同样的状态机，它们有相同的初始状态，然后执行相同的日志序列，最后到达相同的状态。Raft 算法做为共识模块，用来保证日志序列的一致性。
图1：复制状态机架构。共识算法来维护日志的一致性
在任何时刻，Raft 的每个节点都会处于三种状态之一：Leader、Follower、Candidate。Raft 首先要选出一个特殊的 leader 节点，leader 会接收客户端的更新请求，写入日志，然后同步到 follower。follower 从 leader 接收日志，写入本地。如果 leader 宕机或者断开连接，会选出新的 leader。candidate 是选举成为 leader 之前要经过的中间状态。
Raft 中，时间被分为任意长度的任期 term，有连续的编号。term 以选举为开始，会有若干个 candidate 试图成为 leader。如果有 candidate 获胜，那么它将一直作为这个 term 内的 leader。如果选举未决出 leader，那么这个 term 会结束，并马上开启下一个 term。term 起着逻辑时钟的作用，可以发现过期的状态。每个节点会维护一个 current term 值，并在节点间交流时带上这个值。如果一个节点发现自己的 current term 比其它节点小，那么它会更新成更大的那个值。如果 leader 发现存在更高的 term，那么它会立刻转为 follower 状态。如果收到的请求来自更小的 term，那么拒绝这个请求。
图2：任期 term 示例
节点间通过 RPC 进行通信，有两种最基本的 RPC，RequestVote 在选举过程中由 candidate 发起，AppendEntries 由 leader 发起，用于复制日志，以及做为心跳。
Raft 通过心跳机制来触发 leader 选举。所有的节点启动时都是 follower，如果一段时间内没收到 leader 或者 candidate 的 RPC 消息，就会开始选举。开始选举后，follower 会增加 current term 值，转换为 candidate 状态，给自己投票，然后向其它节点发送 RequestVoteRPC 来获取选票。接下来可能有三种结果。
1. 如果收集到了超过半数节点的选票，那么 candidate 赢得选举，状态转为 leader。对于一个给定的 term，节点只会给第一个发来 RequestVoteRPC 的 candidate 返回选票，然后拒绝其它的 candidate，所以保证了最多只有一个 candidate 获胜。
2. 如果选举过程中收到了 AppendEntriesRPC 消息，而且 RPC 发送者的 term 值不小于自己的 term 值，则把 RPC 的发送者认为是 leader，自己退出选举，转为 follower。
3. 如果一段时间后，上面两个结果都没发生，那么 candidate 会开始新一轮的选举。
leader 为了维持自己的身份，需要定时发送心跳消息，即空的 AppendEntriesRPC。
日志由一个个连续的日志项组成，日志项有两个属性，index 表示它在整个日志中的下标，term 表示创建它的 leader 的 term。leader 被选出来后，会接受客户端发来的请求，把请求作为一个日志项添加到日志中，日志项的 term 设定为自己的 term。然后给其它的 follower 发 AppendEntriesRPC 请求，进行日志复制。
图3：leader 与 follower 日志不一致的一种场景
日志复制的目标是使得 follower 的日志与自己一样。当 leader 被选出来后，它的日志和其它的 follower 的日志可能不一样，如图3，所以需要一个机制来保证日志的一致性。leader 会为每个 follower 维护一个 nextIndex，表示 leader 给各个 follower 发送的下一条日志项的 index，初始值是 leader 被选中时的本地的最后一条日志项的下一个位置。leader 给 follower 发送 AppendEntriesRPC 消息时，会带着 (PrevLogTerm, PrevLogIndex) 信息，PrevLogIndex 等于 nextIndex-1，PrevLogTerm 即 prevLogIndex 这个位置的日志项的 term。follower 接收到 AppendEntriesRPC 后，会从自己的日志中找是不是存在这样的日志项，如果不存在，就给 leader 回复拒绝消息，然后 leader 将 nextIndex 减 1，再重复，直到 AppendEntriesRPC 消息被接收，此时可以证明 leader 和这个 follower 的日志有着相同的前缀，leader 可以放心地将后面的日志复制给 follower。如果某个 follower 宕机了，leader没收到响应，则会一直给这个 follower 重发 AppendEntriesRPC。
对于在自己任期内增加的日志项，如果 leader 确认了这条日志项已经复制到大部分的节点上（即收到了大部分节点对这条日志项的成功响应），则认为这条日志项已提交 committed，可以在状态机上执行此日志项。leader 会记录它知道的最高的已提交日志项的 index，放在 AppendEntries RPC 中，follower 发现已提交的日志项，则在本地状态机执行。
目前 Raft的应用，比如 Etcd / Consul 基本都是单一 raft 集群的实现，并不能用于存储海量的数据，所以它们主要的应用场景是配置管理，毕竟 raft 集群的参与节点越多，性能越差，但是如果不能横向的添加物理节点的话，整个系统没有办法扩展。CockroachDB 和 TiDB 都是使用 Raft 做为共识算法的分布式 SQL 数据库，它们的特殊点在于，它们同时存在多个 Raft 集群。在 CockroachDB 中，数据表示为键值对，并根据键的范围分为多个 Range，每个 Range 有一个相应的 Raft 集群来实现共识。每个节点上可以有多个 Range 中的数据，所以会参与多个 Raft 集群，也就是 MultiRaft。
管理多个 raft 集群引入了其它复杂度。在单个 Range 中，Raft 集群的 leader 要向其它节点定期发送心跳信息。随着 Range 数的增多，心跳信息需要的流量也增多。如下图所示，每个大圈表示一个节点，一种颜色表示一个 Range，箭头表示心跳消息。
图4：多个Raft集群的心跳消息
为了减少流量，每对节点在每个 tick 只发送一个合并后的心跳消息，而不用每个 Range 都发，如下图所示。
图5：心跳合并
另外，CockroachDB 还采用了 quiescing raft的技术，如果leader没有收到新的客户端请求，并且已经把日志复制到follower，那么它可以告诉follower，即使没有收到自己后续的心跳，也不进行新的选举。除了减少心跳消息的流量，MultiRaft 在其它方面也有改进，比如不需要为每个 range 创建一个 goroutine（Go 语言中的协程），而只需要维护常数级数量的 goroutine。
TiDB 底层的 TiKV，是一个分布式的 KV 系统，同样使用了 MultiRaft。它的基本单元称为 Region，对应于 CockroachDB 的 Range。
编辑：周佳杰
参考链接：
[1] Raft 算法, https://raft.github.io/
[2] What is a Multiraft, https://sergeiturukin.com/2017/06/09/multiraft.html
[3] CockroachDB应用, https://www.cockroachlabs.com/blog/scaling-raft/