[共识算法] 1 - Raft Basic

0. 引

在什么应用场景下我们需要分布式共识算法，是否还有其他的解决方案

当我们的应用场景从单机数据库转向分布式数据库时，我们需要考虑如何保证分布式事务的ACID性质。在单个节点上我们可以认为只要事务成功提交，整个数据库状态就是一致的，这通过日志系统或者影子页面机制就能实现；但是在分布式场景下，我们需要保证在所有节点上该事务的执行结果都是一致的，而各个节点的内存和日志通常是独立的，所以上述两种方法无法确保，我们需要其他手段来保证分布式事务的原子性提交。

因此有一系列的提交协议用于解决这一问题¹：

Two-Phase Commit(2PC)
Three-Phase Commit(3PC)
Percolator

其他还有一些算法能够实现集群数据一致的，如：

Paxos // TODO
Raft
ZAB // TODO
Viewstamped Replication // Undone

后面这些算法我只略微了解过 Raft 和 ZAB，感觉上来说它们似乎跟前面几种分布式事务提交协议略有不同，虽然目的都是为了保证数据一致性。嗯…这块内容之后再深入看一下。

update 2023-10-29：“共识算法”这一名称似乎会在语义理解上带来一些困扰：如果集群对数据达成了共识是不是就相当于完成了分布式事务呢？这是我之前一直没搞清楚的地方，其实可以把这个问题放在单机数据库中理解。单机数据库只有一个节点，所以日志和状态机总是一致的，但是在此之上我们依然需要采用WAL、2PL等机制来保证事务的原子性、隔离性等性质；那么推广到分布式数据库中，相当于我们需要分布式提交协议来保证事务的原子性，还额外需要共识算法来保持日志的一致（从而使状态机保持一致），所以提交协议和共识算法是在解决两个不同的问题。其中共识算法更为底层，或者说是分布式事务能够进行的基石：如果日志都不能保证一致，那么分布式事务的一致性根本无从谈起。

可以简单介绍一下 2PC 协议，在2PC中会有一个协调者（coordinator）来负责接收客户端请求提交事务，并协调其他参与者（participant）来共同提交事务，同时协调者也将根据全体参与者的提交结果来决议本次提交是否成功，如果提交失败需要全体回滚事务并且告知客户端。2PC 将事务的提交分为两个阶段²：

Prepare阶段：协调者收到客户端的提交请求之后，进入Prepare阶段。此时协调者向所有参与者发送prepare消息，收到消息的参与者根据本地事务的执行状态判断能否进入两阶段提交，若可以则在日志中写下ready日志，表示该事务在此参与者可以完成prepare操作，然后向协调者返回ready消息；协调者等待所有参与者都返回ready之后，在协调者的日志中<Ready T>，随后进入Commit阶段；若有一个参与者返回abort或者超时，协调者都需要写入<Abort T>并回滚事务；
Commit阶段：进入Commit阶段后，协调者先给自己写下一条<Commit T>（这个动作可以看为事务T的提交点），然后再次向所有参与者发送commit消息，收到的参与者在日志中写下<Commit T>，然后参与者向协调者返回消息；协调者收到所有的 Commit OK 之后可以得知事务在所有参与者上提交成功，可以向客户端返回 Commit OK。

这些日志是为了能够在故障之后判断事务的执行状态：假如发生故障恢复后，发现事务T1在一部分参与者上状态为Commit或者在协调者上记录为Commit，那么我们知道该事务已经进入提交阶段，需要重做T1；如果在协调者上只存在Ready而没有Commit，或者发现了Abort记录，那么该日志需要回滚。实际的故障情况还包括网络分区、协调者故障等，这里暂且略过。

这是教材上给出的 2PC 流程，虽然是应用较广泛的分布式提交协议，但是也还存在许多优化空间；后来略微了解了一些OB中对 2PC 的优化措施：// TODO：找能够/已经公开的部分介绍一下吗？

1. raft共识算法

根据原始论文³，个人认为可以将 Raft 的运行原理拆分为三部分理解，分别是：

Leader Election
Log Replication
Snapshot

其中选举和日志复制就能够构建出基础的 Raft 协议，但是为了处理不断增多的日志，我们还需要实现快照机制，以便能够清理生成快照时间点之前的旧日志。另外论文 section 6 是关于 Membership Changes（节点加入或离开）时如何实现在线更新集群配置，但是有些 raft 实现并没使用这些方案，因此暂时不作介绍（主要是因为我没做，理解不透）。

在实现快照往往需要改动前两部分的代码，如果编码之前设计不当可能会产生各种乱七八糟的Bug，或者导致项目结构支离破碎，非常锻炼（zhe mo）人

接下来会简要介绍各部分的主要思想，更多参考资料可以看看这个网页，上面有一些相关论文、talk、公开课的链接，甚至还有一个raft运行过程的动画演示（虽然我没玩明白怎么调参数）

Leader Election

在介绍如何选举 leader 之前，需要先介绍一下 raft 的一些基本概念。

raft 与其他共识算法类似，都采用了复制状态机（replicated state machine）的方式来实现容错，即 raft 尽力使每个节点存储的 state machine 都是完全一样的，这样当某个节点宕机后能由其他节点接手它的任务。而复制状态机的实现，依靠于日志的复制：raft 将修改状态机的请求记录在日志中，然后将这一记录在所有节点上进行复制，并且每个节点都按照日志记录的顺序来应用修改，就能得到状态一致的 state machine。如此便将维护状态机一致的问题转化为维护日志的一致，raft 日志复制的细节我们将在下一小节中进行介绍。

raft 集群中会有一个 leader 节点主导安排日志的顺序，其他节点均以 leader 的排序为准。节点共有三种身份：

leader：一个集群只能有一个有效的leader，负责响应 client 的读写请求，并且将请求对应的日志发送给其他 follower 进行复制；当一个请求在集群中得到共识之后（对应日志在大多数节点上复制成功），leader 将请求应用到 state machine，并向 client 回复请求应用成功
follower：无条件接受 leader 的命令写入日志，跟随 leader 将已达成共识的日志对应请求应用到 state machine 中
candidate：follower 检测不到有效 leader 时，将自身升级为 candidate，请求其他 follower 投票给自己；得到半数以上投票的 candidate 成为新一任 leader。

raft 中还有“任期”（term）这一概念，每个新当选的 leader 都有自己的任期（上一任 leader 的 term + 1），并且所有日志也需要标识是在哪个任期内写入的，以便我们用任期和下标来唯一标识一个日志项。所有节点会将包含着更小任期的 message 当作过期消息而忽略，收到更高任期的 message 则会更新自己的 term 字段（如果是 leader 或 candidate 还会将自己身份降为 follower）。

被问到任期是什么概念的时候，一时不知道怎么回答。现在让我重新组织语言的话，我觉得可以这么说：可以类比现实世界，理解成一个朝代的年号，或者国家领导人的任期，比如现在有一个节点宣布自己将参加第八任 leader 的选举，请求其他节点给它投票，当它得到多数派的选票，那么它就当选并且拥有对集群其他节点的绝对领导权，leader在此期间的政绩（日志）需要标记出是第八任领导人完成的；如果因为网络或节点故障没有在 term 8 选出 leader，那么该任期 id 作废，下一轮选举从 term 9 开始。（我理解来说，这是为了避免旧主或者网络分区恢复后的旧candidate对正常多数派数据的扰乱）

在不考虑日志压缩归档的情况下，日志长度应该是不断增长的，而日志一旦生成后位置不会移动（即在数组中占了一个坑），为何需要任期和下标才能唯一标识一条日志项，只用下标不够吗？
考虑这样一种情况：在出现网络分区的情况下，若leader与 majority 被分隔开，此时 majority 将会选出新的 leader，但是旧 leader 仍有可能因 client 的请求而不断试图追加日志，导致旧 leader 的日志长度也在不断增长，会与新 leader 的日志出现分歧（都具有相同的下标但任期不同），而旧 leader 这部分日志是无效的，对应的请求也不会被应用到 state machine（因为没有得到 majority 的承认），需要用新 leader 的日志覆盖掉。因此我们还需要通过比较日志项中任期才能判断哪些日志是最新且有效的。

leader 需要不断向 follower 发送心跳来维护自己的统治，一旦 follower 超过时间没收到 leader 的心跳，则会发起新的 leader 选举，大致过程如下：

follower 将自己的升级为 candidate，更新自己的任期为old_term+1
candidate 投票给自己，并向其他所有节点请求选票
收到投票请求的 follower 按照先到先得的顺序给 candidate 投票，并且更新自己的 term 字段；每个任期只能投1票
candidate 检查选票数量是否超过半数，若超过则走马上任，开始处理请求和追加日志；若否，则继续等待直到下一次 election timeout 发起下一次选举。或者收到其他有效 leader 的消息后，将自己退回 follower 身份。

以上只是比较简略的过程描述，其中还有一些细节我们需要注意：

节点的 election timeout 不能设为相同时长，至少要在某个范围内随机产生，如论文给出的150～300ms；如果某一时刻同时多个节点发起投票容易分散选票导致无法选出 leader，延长选举时间。
follower 投票的逻辑是：只投给日志至少与自己一样新的节点，且每个任期只能投一票。日志更加“新”（more up-to-date）的定义是：先比较最后一条日志的 term，term 更大的比较新；如果 term 相同，则比较日志的长度，长度长的比较新（实现了日志压缩的则比较日志的 index）。所以并不一定是日志最新那个节点当选，某个相对整个集群而言比较新的节点先发送 voteRequest 也是有可能当选的。
Leader 在当选之后需要向自己日志中写入一条数据段为空的日志，这一操作的目的是为了及时提交之前任期留下的未提交日志（如果有的话）

选举出 leader 之后，复制状态机的实现变得简单了：我们只要以 leader 的日志为准即可，如果日志内容发生冲突则直接用 leader 的日志覆盖冲突部分，然后直接按照日志记录的请求顺序来应用修改便能得到一致的状态机。下面我们将介绍为何日志会出现冲突、以及怎样判断冲突并完成日志的复制。

Log Replication

leader 每次收到 client 请求都会写入日志，并且将日志广播给所有节点。按照之前所说，raft 的节点都以 leader 安排的日志顺序为准，那冲突从何而来？如果集群从启动之后所有节点一直稳定运行且没有网络分区，leader 从未更换，那自然是没有冲突的。所以答案其实已经出来了：如果因为节点故障、网络分区、消息丢失等原因，导致 leader 多次换届，“短命”的 leader 没有来得及将任期内的日志复制到整个集群便选出了新 leader，那么这部分没有复制或未提交的日志便是冲突；或者在实现中我也大概发现，没有实现租约的 raft leader 被分区隔离为少数派后也可能继续接受 client 请求从而写入一定日志（虽然这些日志因为得不到共识而不会提交，但至少会在 leader 节点上新增一部分日志），这些日志在网络恢复后也是冲突所在。

注意我们这里一直提的是 未提交的日志，因为已提交的日志一定是在集群大多数节点上得到共识的，这部分日志是不可能发生冲突的，一旦日志提交了便可以认为这条日志在之后必然会被应用到状态机，同时之后所有的查询也应该能够看到这条日志。

那么具体如何判断哪些日志是冲突的呢，我们只需要对比一个日志项的 term 和 index 是否相等即可，如果 follower 跟 leader 相同下标的日志项 term 不同，那么该日志就应该被 leader 的日志覆盖。因为 leader 创建日志时，下标是递增的，且每个 term 也只有1个leader，所以如果 index 和 term 相同则定是来自同一个leader的日志（如果该 index 存在其他日志，必定属于不同任期的 leader，需要用 term 更大的那个日志来覆盖掉）。

raft 能够保证两个节点的日志如果 index 和 term 都相等，那么从两个节点从头开始到该 index 的所有日志都相同（Log Matching Property）。这对于实现集群日志一致非常重要，现在我们检查两个节点的日志是否一致，只要查看某个相同下标的日志项对应的 term 是否一致即可，而不用遍历检查所有日志项。而这一特性的实现，依赖于 raft 节点追加日志时进行的检查步骤：如果 follower 收到 AppendEntriesRPC 中包含了$[i, i+1, … , j]$下标的日志和 index $i-1$ 日志项对应的 term，那么它需要先检查自己下标 $ i - 1 $ 的日志是否与请求中附带的 index 和 term 一致，如果一致说明 RPC 中日志是自己日志的 valid extension，可以将其追加到自己日志中（如果 leader 是合法的话）。只要追加日志时严格遵守这一约束，就能保证我们需要的性质。

日志能够顺利复制到集群大部分节点后，我们便可以将对应的修改请求应用到 statme machine 中。raft 中每个节点都有一个 commitIndex 字段来记录 已经在半数以上节点中完成备份的日志下标，该下标及之前的日志请求都能安全应用到 state machine 中。通常来说，leader 的 commitIndex 会略微领先于 follower，因为 leader 通过 AppendEntriesResponseRPC 得知可以提交哪些日志之后，才会在下一次心跳或 Append 过程中将这一更新通知 follower。所以可能存在这样的情况：leader 检测到日志 index 101 能够提交，因此向 client 回应 request 101 执行成功，但 leader 回复之后还未来得及将这一提交通知其他 follower 就宕机了，raft 如何处理这种情况？

事实上虽然其他 follower 还不知道 index 101 能够提交，但是“日志101可提交” 意味着该日志起码存在于半数以上的节点中。而 raft 的选举机制保证新的 leader 只能从这些节点中产生（假设 index 101 就是最新的），而新的 leader 当选后提交新日志时，会将这些旧的日志一并提交、应用到 state machine，然后通知 follower 更新它们的 commitIndex，由此完成前任 leader 未尽的工作，客户端依然能够查到该日志对应的操作，保证了数据的一致性。

但是有没有可能某条日志已经复制到大多数节点，但是依然被覆盖掉了呢？
存在的，论文中也提到了这种情况（Figure 8），不过条件有些绕，大概是5节点[A, B, C, D, E]，leader A只将日志 N 复制了到[A, B]共2份然后挂掉了，D 超时发起选举得到 [C, D, E] 的选票成为新leader，并写入日志 N + 1但是直接挂掉；然后 A 恢复并将日志N复制到C中，此时日志N已经复制了3份形成多数派共识了，但是还没提交A又挂了；此时再选举将 D 选为leader（因为D有一个日志N+1，虽然缺少多数派中的日志N，但D持有的是新任期的“更加新”的日志，所以D当选是合法的。此后D就会将未提交的日志N覆盖为自己本地日志中的N+1。

这确实有点反直觉：既然一条日志已经复制到多数派中了，逻辑上来说它是应该是得到共识了，为什么还会被覆盖掉。出现这样情况，说明 leader 仅仅完成了该日志的复制而没来得及进行提交（可能消息丢失了或者 leader 在收到多数派完成复制之前宕机了），也就是在 leader 的视野里这条日志还没有完成共识，也就还没有向 client 返回响应。从这一角度而言，被覆盖是合理的。

新 leader 提交前任 entry 的过程是通过插入一个自己任期的 empty entry 来完成的。
插入这个 entry 产生的 Append 操作会强制将所有节点的日志刷为与 leader 一致。最后只要这个新的 entry 提交了，比它下标小的 entry 在这一过程中也能一并达成提交条件了（复制到半数以上节点中）。否则 leader 难以确定哪些日志已经存在于半数节点中，leader 如果通过统计某条日志是否在多数派中复制来决定是否提交旧日志的话，那么如上述情况的日志仅存在于大多数节点，但是当前 leader 不持有的，要提交这样的日志会与 raft 设计的”日志只从 leader 传向 follower“ 特性发生冲突，要打破这一冲突的话，需要使用更复杂的机制来使 leader 能够从多数派中获取日志，增加了实现的复杂度（是paxos了）；目前的实现方式相对来说是比较简单容易理解的。

Snapshot

原始论文中用一页左右的篇幅介绍了快照的作用和实现思路，算是比较简略的。但是实现过程中因为需要加入新的 RPC，同时 leader 对待落后节点时，也要增加判断是否需要发送快照的逻辑，需要在之前两部分的代码中进行不少修改，一不小心就会写出新的bug（我前面两部分写出来的bug加起来都不如增加snapshot之后的多）。所以这里我还是单独拎出来讲一讲。

实现快照的思路整体而言并不复杂：我们将当前已提交的日志全部应用到 state machine，并记录下最后一条被应用日志的 index 和 term，即可将这些日志删除。raft 的每个节点都独立生成自己的快照，但是也存在某些落后的 follower 需要从 leader 这里获取最新快照的可能性。因此需要增加一个 SnapshotRPC 消息用于 leader 发送快照。follower 收到 RPC 后同样检查消息中 快照应用的最后一条日志 对应的 index 和 term 与自己日志中的是否吻合（与处理 AppendEntriesRPC 的逻辑差不多），若一致则接受该快照并丢弃 index 之前的日志；如果 index 对应的日志领先于 follower 最新日志，则全盘接受快照并丢弃所有日志；如果 index 对应日志已经被 follower 截断，则说明 follower 已经生成了比 RPC 中更新的快照，则无需应用。

在 tinyKV 的架构中，state machine 其实是底层的一个 badger 单机kv数据库，生成快照其实无需其他操作，只要截断日志即可；发送快照对应打包整个数据库并发送。

raft如何解决“脑裂”的问题，呃不过我不是很喜欢这个用词。不如这样说：raft如何防止出现多个 leader？
其实 raft 的选举机制是能够保证一个任期只出现1个 leader 的，因为：1)每个节点每个任期只能投1票；2)需要超过半数的选票才能当选为该任期的 leader。但是现在问题在于如果出现网络分区，把 leader 分到了少数派这边，那么多数派会在一个新的任期里选出一个 leader：虽然两个 leader 任期不同，但是客观来说我们集群中还是出现了两个 leader。对于写操作来说，少数派这边的 leader 因为无法达成共识，是不会完成写请求的响应的，客户端最终会发现超时从而尝试向其他节点发送请求；对于读操作，朴素的解法是我们将读操作当作写操作来处理避免客户端从旧 leader 处读取 stale data：即把读操作也记录到日志里，等待集群完成共识之后才从状态机中取数据给返回给客户端。当然这样的性能上挺差的，对于这个办法可以采用 ReadIndex 或 LeaseRead 等优化⁴。也就是客观上 raft 允许分区中存在两个主节点，但是通过上述机制保证只有其中一个是有效且能够正常响应客户端请求。

2. etcd raft架构初探

// TODO

The End