白话一致性协议 - Paxos、Raft和PacificA[1]

书接上文 - Multi Paxos

在上一篇文章中，我们提到了Basic Paxos和Multi Paxos的异同。在 Paxos Made Simple 论文中，作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数据流（也可以称为复制日志，replicated log）达成共识，从而实现节点状态的一致性复制。

确定性状态机

我们可以将系统中的每一个节点抽象为一个有着确定性状态机，即给定多个状态一致的状态机，在执行同一个命令之后，其状态仍保持一致。（可以想一想编译原理里面的DFA）

Leader - 系统中唯一的proposer

如果系统中存在有多个proposer，那么就很可能会出现多个提案相互干扰的情况。虽然根据证明，最终这些提案都会收敛到一致，但是性能会非常低下。所以我们可以在系统中通过选举，选出一个leader做为主proposer（distinguishied proposer），所有的提案都由leader提出。

这样一来，在绝大多数情况下都不会出现提案相互干扰的情况。只有在leader切换的瞬间，可能会出现相同编号的不同提案，但是我们的算法可以很好的处理这种情况。

分布式系统中的“TCP”

类似于TCP协议中序列号，Multi Paxos中的每一个命令都有一个递增的编号。即我们前一个执行的命令是100号，那么下一个执行的命令一定是101号。每一个命令都是一个Paxos实例，Leader向所有节点发布这个提案，在提案达成一致之后（多数节点返回ACK），就可以认为这个命令已经达成了一致。

和TCP一样，如果我们顺序的发布并表决提案，效率会非常低下（TCP停等模型）。所以，Multi Paxos采用类似滑动窗口的方案，每次对N个提案进行表决，以增加表决的带宽。

和TCP不同的是，如果某些序号的TCP包在传输中丢失，最坏的情况是我们会RST这条链接，其它的工作都交给应用层逻辑来解决。

但是对于Multi Paxos来说，如果某些提案没有被表决，那么就会在日志中留下空洞（gap）。这会直接影响系统的一致性。如果恰巧这个时候发生了Leader失效，那么新选举出来的Leader节点就要处理日志中的空洞。

解决空洞的原理也很简单，就是Leader向所有成员询问，对于这个提案，是否已经有达成共识的值。如果有的话，就使用这个值。如果没有，就用一个no-op（无操作）命令来填补这个空位。但是，对于实际工程中来说，我们还需要解决未达成共识时值的冲突等情况。

为什么我们还需要Raft？

Multi-Paxos在现实的工程当中更多的是一种符号。因为理论与实践上的隔阂是如此之大，如果想在工程意义上实现一个可用的Multi-Paxos算法，必然会在原算法的基础上进行一系列的魔改，这些魔改虽然均声称自己实现了Multi-Paxos算法，但是这些算法大多不能被证明是正确的。

Raft的目标是，即让算法满足工程化需要，又能保证其正确性。

Raft论文当中说Paxos算法难以理解，我并不这么觉得。因为Paxos论文里面把困难的部分都一笔带过了。只剩下简单的那部分了。

Raft vs. Paxos

Leader选举

在Paxos论文中，Leader选举被视作一种特殊的“提案选举”。只需要Proposer和Acceptor进行一轮或多轮（取决于运气）投票，就可以确定Leader。

但在实际工程中，我们需要考虑以下的问题：

1. 如何判断Leader是否存活

2. 是否每一个节点都有资格担当Leader

Leader的任期

Leader在被选举出来之后，都会被赋予一个任期编号（term）。在任期里，Leader会向所有成员发送心跳包以延续自己的任期。

如果Leader失效无法发送心跳包的话，成员就会产生一个“选举超时”，此时就会重新触发一轮选举。

选举的流程和Basic-Paxos算法类似，proposer向所有成员发送“我要当老大”的提案，成员们会酌情回复。如果得到了多数成员的肯定，这个proposer就是下一个任期的Leader了。

从本质上说，每一个任期的Leader选举，都是一个独立的Basic-Paxos实例。任期号相当于Paxos里面的提案编号。

Leader资格的认定

Raft采用强一致性的模型，对于已经ACK的用户请求，要尽力保证其状态不丢失。

如果你问我，现在来一核弹把机房炸了，数据都丢了，那你怎么能保证强一致性。

其实这个问题非常简单。很明显，我们保证了丢数据的强一致性。

所以我们要选出一个Leader，使其能够包含所有已经ACK的提案。当一个proposer向其它节点发送提案时，就会收到其它节点的响应。因为一个已经ACK的提案必然被多数节点所认可，所以如果一个proposer没有包含所有被ACK的提案时，它的提案就会被其它包含更多状态的节点驳回。最后被选出来的Leader，一定是包含所有被ACK的状态的节点。

日志复制

当Leader被选出后，Leader就会开始处理用户的请求。用户的请求可以看做一系列的命令，在接收到提案后，提案首先被分发到所有节点，节点的状态机顺序执行这些命令。在多数节点返回ACK后，这个命令就被视为“已提交”（commited）。

上文中已经提到了一致性算法中的日志非常类似于网络协议中的TCP。即如果两个命令的ID一样，那么其内容必定也一样；如果两个节点都有认可了编号为p的命令，那么所有编号小于p的命令也必定保持一致。（被称为Log Matching Property）

Raft为了简化算法的工程实现，把节点的状态抽象为严格append only的日志。即我们可以将日志指针向后或向前移动，来“回滚”或“更新”状态。但是绝对不允许在日志中间添加或删除日志条目。所以，在Leader发生变化时，如果leader和其他follower之间的日志不同，那么follower需要回滚日志以保持和leader日志的一致性。

安全性

不归我管的事我不拿主意

前文我们说到，一个节点要成为Leader，一定要拥有所有已经被ACK的状态，否则就会被其它节点驳回。

但是现实都会出现一些小小的意外。在系统的运行过程中，如果有一些提案只被少数节点认可，与此同时发起提案的Leader意外退出。那么在不同节点上的日志会产生“分叉”，那么我们如何解决日志当中的冲突呢？

很明显，因为这些以少数节点认可的提案并没有被确认。所以我们无论是接受提案还是驳回提案，都不影响我们强一致性的要求。所以关键是处理冲突，使其不产生影响系统一致性的后效。

假设在Term1，最后一个提案是"Value:3"，这个提案并没有得到多数节点的认可，Leader就挂掉了。选出来了一个新Leader，Term数加1。在Term2，被提出的第一个提案是"Value:1"，这个提案也没有得到多数节点的认可，Leader也挂掉了。

因为这两个分叉的提案都没有得到多数节点的认可，所以下一个Leader可能已经确认这两个提案，或者两个中的一个，也可能一个都没有确认。新的Leader在被选出后，需要面对的第一个问题是如何处理属于旧Term的提案。

解决方案有两种：

1. 新Leader将日志中仍没有被多数节点认可的提案重新提出，直到被多数节点认可为止
2. 新Leader忽略属于旧的Term的提案，只提交属于本Term的提案；对于日志冲突，使用复制日志的方法解决，但不会显式认可旧Term的提案。

对于方案1，有一个隐含的问题。如上图所示，在时间点1，S2为Leader，标红的两个提案并没有被确认。此时如果Leader在时间点2重新提出"Term1/Value3"，并且得到了S1和S2的认可，那么这条提案已经被多数节点认可。但是在时间点3，S3被选举为了Leader。S1和S2需要回滚日志以保持与S3日志的一致。此时就出现了一种情况，那就是已经被确认的日志被回滚掉了，强一致性就不能满足了。

如果我们采用方案2，那么被选出的新Leader提出的第一个提案的Term一定为3。确认新提案的节点接下来会复制Leader的日志，回滚掉没有被认可的提案"Term2/Value1"。对于标绿的"Term1/Value3"，虽然被复制到了其它的节点上，但是这个值并不会被确认。这样一来，我们既保证了已经被确认的提案不会被回滚，又保证了日志的一致性。

在具体实现中，“T3/V1”往往是一个空命令(no-op)。这样一来，即使没有写请求，Leader就可以更快的确认新的任期并同步Log了。

如何证明

那么怎么保证上面的作法它是正确的呢？

假设当前任期为T1，此时由于系统故障，我们选出了新的Leader - S2，并记Term为T2。因为我们严格遵守了Log Matching Property。

那么，对于以下两种情况：

1. T2的Leader和Voter的Log中最后一个提案的编号是一致的，那么可以知道他们日志中的提案都是完全一致的
2. T2中Leader的Log比Voter更新，那么Leader一定包含比Voter更多的提案；否则Voter就不会给Leader投票

我们都可以证明，对于前一个Term已经被确认的提案，一定会被包含在后一个Term的日志中。也就是说，一个被确认的提案不会中途丢失。

成员变化

以上我们的讨论都基于系统的节点不会发生变更，但是在现实工程中，我们很难对此进行任何保证。所以一个实用的系统，一定能解决成员变化的问题。

成员变化问题的本质是系统中不能同时出现两个Leader。

在Raft中，我们将过渡期的配置称为“共同一致”（joint consensus），一但它被确认，说明系统已经过渡到了新的成员配置。

具体的策略如下：

1. 系统中只有旧的配置C_old，新加入的成员不可能成为Leader
2. 当前系统的Leader接受到新的配置C_new。然后Leader向所有节点发起修改配置为C_old+new的提案。
3. 即使这个时间点Leader挂掉了，新的Leader也只会拥有旧配置C_old或者过渡期配置C_old+new。这取决于Leader选举的时机（和运气）。
4. 当过渡期配置C_old+new被多数节点确认后，Leader向所有节点发起修改配置为C_new的提案。
5. 如果这个时间点Leader挂掉了，新Leader会从拥有C_old+new和C_new的节点中选出。新的Leader仍然可以进行配置的变更，而不影响整个系统的安全性。
6. 直到C_new被确认，配置更换宣告完成。

“共同一致”允许节点无需考虑安全性的情况下，在任意时间进行配置的更换。配置的更换也不会影响客户端的请求。

以上我们解决的是安全性问题，但是在实际工程中我们还需要兼顾效率问题。

例如新加入的节点可以视作“non-voting members”，只同步数据，不能对提案进行投票。直到数据同步基本完成，才进行配置变更。这样避免了新的节点由于缺少Log不能及时的处理提案。

又如新的成员列表中，不包含原先的Leader节点。在旧Leader认可了新的配置提案之后，就可以退位让贤，让其它节点选举出新的Leader。

以及被清除出成员列表的节点，不会收到后续的心跳，它们会认为Leader已经失效，所以自己跳出来竞选Leader。这样一来，就会触发新的（无意义 的）Leader选举，影响系统的可用性。解决方案是，如果一个节点在一个时间段内收到了Leader的心跳，那么就会忽略Leader的竞选请求。这样既不会影响正常的选举，又可以屏蔽无效的选举请求。

快照

我们的提案越来越多，日志也越来越长。随之而来的是漫长的恢复时间以及磁盘空间的浪费。快照技术可以帮我们清除旧的无用日志，只保留有用的状态信息。

在Raft算法中，每个节点都能自主的生成快照。好处是避免Leader分发快照造成的效率降低，也简化了Leader的功能和职责。又由于日志的“TCP特性”，所以不同节点上，只要保证提案编号一致，那么其内容就可以保证一致。

客户端交互

由于客户端不了解系统内部的选举情况，所以在开始通信时，会随机选一台节点发送请求。如果这个节点不是Leader，就会拒绝这个请求，会告知客户端哪个节点是当前任期的Leader。如果Leader失效，客户端请求超时，就会重新随机选择节点，获取新任Leader信息。

对于客户端发送的写请求，Leader需要记录其唯一的请求ID，以避免客户端发送的重复请求。

对于客户端发送的读请求，Leader需要再次确认它是仍是当前任期的Leader，避免向客户端发送过期数据。如果对数据正确性和时效性的敏感性不高，就可以向系统中的任意节点发送请求，

写在后面

Paxos的亮点在于把复杂的东西说简单了。而Raft的亮点是把简单的东西具体化，使之成为能落地的工程项目。

但是Paxos做为一种Quorum协议（俗称P2P），其工程复杂性是难以避免的。Raft在Paxos协议上面加入了很多限制以简化实现，但是想要完整的实现其功能仍不是一件容易的事。（有兴趣的同学可以 挑战一下自己 ）

下面一篇文章我们会换一种新思路，学习PecificA算法，看一看如何使用Paxos实现一个主从复制协议。

写在更后面

个人觉得，Raft论文的一个更大亮点是充分的思考了Paxos/Multi-Paxos在工程实践上的缺陷。思考并提出有价值的质疑，而不是被他人的观点带着走，真的是最重要的能力之一了。

大胆猜测是因为有足够的理解能力，有额外的带宽去发问？这是一个有意思的问题。