Raft论文手译（下）

继续上一篇，本篇文章将对Raft论文的后半部分进行翻译。

5.4、安全性

????????上一节讲述了Raft的领导者选举和日志条目复制。然而，刚刚讲述的这些机制还不足以保证每个状态机以同样的顺序执行同样的命令。举个例子，在领导者提交几个日志条目时，追随者这时可能还无法运作，接着集群可能选举出新的领导者并覆盖掉这些条目；结果就是，不同的状态机可能会执行不同的指令序列。

????????本节会在集群可能要选举领导者时增加一个限制，来完善Raft算法。这个限制可以保证任何一个任期的领导者都能持有前任已提交的所有日志条目（图3的“领导者完整性性质”）。考虑到领导者选举的限制，我们会制定更加详细的条目提交规则。最后，我们提供了一张“领导者完整性性质”的检验草图并展示领导者是如何校准复制状态机的行为的。

5.4.1 选举限制

????????在任何基于领导者的一致性算法中，领导者都必须最终保存所有的已提交日志。在某些一致性算法中，例如ViewStamped Replication [22]，集群可以选举出一个领导者，即便它一开始并没有所有的已提交条目。这些算法添加了更多机制来确定丢失的条目，并把它们转移到新的领导者中，这个过程会在选举领导者或不久之后进行。很遗憾的是，这导致增加了大量算法机制和复杂性。Raft通过一种更简单的方式保证之前提交的条目无需转移便存储在每一届选举出的领导者中。这就意味着日志是单向流动的，从领导者流向追随者，而领导者是绝不会覆盖掉自己的日志条目的。

????????图8：这个时间序列展示为什么无法改变前任领导者已提交的日志。在（a）中，S1是领导者且部分复制状态机的日志条目下标是2。在（b）中，S1领导者宕机；S5经S3、S4以及自己的选票成为第三任领导者，并在条目下标为2的位置接收了一个不同的条目。在（c）中，S5宕机；S1重启被选举为领导者，并继续条目复制。在这时，任期号为2的日志条目复制到了集群的大多数服务器，但还没提交。如果S1在（d）宕机，S5可能被选举为领导者（通过S2、S3、S4的选票）并通过自己任期号为3的条目覆盖掉原来未提交的条目。然而，如果S1在宕机前就把一个条目复制到集群中的大多服务器，像（e）那样，接着这个条目会被提交（S5无法赢得选举）。这时，之前日志里所有的条目也会被提交。

????????Raft通过选票进程阻止竞选者赢得选举，除非它的日志包含所有已提交条目。竞选者必须通知集群中大多数服务器来赢得选举，这就意味着每个已提交的条目必须至少存在于一个服务器中。如果竞选者的日志在其它大多数服务器中是最新的（所谓的“最新”会在下面详细定义），那么它将继续持有所有已提交的日志。“请求投票”远程调用实现了这个限制：这种远程调用包含了竞选者的日志，如果投票者的日志比竞选者的日志更新，则它会拒绝投票。

????????Raft通过对比最新条目的下标和任期号来决定两个日志谁是更新的。如果这些日志最新的条目任期号不同，那么任期号高的日志算是最新的。如果日志的任期号相同，则日志长的就是最新的。

5.4.2 从之前的任期提交条目

????????正如5.3所述，领导者能察觉到一旦条目在集群中大多服务器中存储，那么它就是在本任期提交的。如果领导者在提交条目前就宕机了，之后的领导者会尝试结束本条目的复制。然而，一个前任期的条目存储在大多服务器中，领导者不会马上判定这个条目已经提交。图8讲述了一种情况，旧的条目即便存储在大多数服务器中，依然也可能会被新的领导者覆盖掉。

???????图9：如果S1（T任期的领导者）在本任期提交了一个新日志条目，而S5在U任期被选举为领导者，那么必须至少有一个服务器（S3）接受这个日志条目并投S5一票。

???????为了解决图8的问题，Raft绝不会保存日志条目副本，在之前的任期里提交它们。只有本任期领导者的日志条目会以计数副本的形式提交；一旦条目在本任期这样提交上去，那么所有之前的条目都会因为“日志匹配性质”间接地提交。有些情况领导者可以安全地认为旧条目已经提交（举个例子，比如所有服务器都存储了这个条目），但Raft为了简洁性采取一种更保守的方法。

???????Raft在提交规则中引入这种额外的完整性，是因为日志条目会在领导者复制前任条目时重新获取原有的任期号。在其它的一致性算法中，如果新上任的领导者复制前任的条目，它必须用新的任期号来复制。Raft的方法能更容易推出日志条目，因为它们随着时间和条目数保持着相同的任期号。同时，在Raft中，领导者相对于其它算法发送前任条目的次数更少（其它算法的日志条目提交前必须发送冗余的条目来记录它们）。

5.4.3 安全性论点

???????考虑到Raft算法的完整性，我们现在可以更详细地讨论“领导者完整性性质”了（这个论点是基于安全性论证的；详见节9.2）。我们先假设“领导者完整性性质”不成立，接着找出一个反例。假设T任期的领导者在自己的任期里提交了一个日志条目，但这个日志条目并没有存储到之后的领导者中。考虑到任期U>T，U任期的领导并没有存储这个条目。

???????1.该提交的条目在领导者U选举时不能存在与它的日志中（领导者绝对不能删除或覆盖条目）

???????2.集群中大多服务器复制了领导者T的条目，而领导者U收到了大多选票，因此至少有一个服务器（投票者）既接受了T的条目，又投了U一票，如图9所示。投票者是达到这个条件的关键。

???????3.投票者在投票给领导者U前，必须接受领导者T的已提交条目；否则它就会拒绝领导者T的“添加日志”请求（投票者的任期会比T的高）。

???????4.投票者在投领导者U一票时，依然会保存这个条目，因为每个介于两个任期之间的领导者还持有这个条目，领导者是不会移除条目的，而追随者只有在它们的条目与领导者冲突时才会移除它们。

???????5.投票者同意投领导者U一票，则领导者U的日志必须和投票者的一样新。这就达到了两个条件的其中一个。

???????6.首先，如果投票者和领导者U拥有同样的最新日志任期号，那么领导者U的日志就必须至少和投票者的一样长。这是一个矛盾点，因为投票者持有这个已提交的条目，而领导者U认为它没有。

???????7.否则，领导者U的最新日志任期必须比投票者的大。此外，它也比T的任期大，因为投票者的最新日志任期至少是T（它包含了T任期提交的条目），给U创建的最新日志条目的前任领导者必须包含有它的已提交日志条目（假设是这样）。那么根据“日志匹配性质”，领导者U的日志必须也包含这个已提交的条目，而这就是另一个条件。

???????8.这完善了矛盾点（反证法）。因此，所有比T任期号更大的领导者必须必须持有T任期所有已提交的条目。

???????9.“日志匹配性质”保证之后的领导者会间接持有已提交的条目，例如图8（d）的下标2。