Raft | Hexo

Raft一致性算法

Raft 协议是一个分布式共识(consensus)算法, 可以参考 ATC-Raft 和 Thesis-Raft 这两篇文章. 两篇文章是同一个作者, 第一篇是小论文, 第二篇是大论文, 阐释地更加全面、详细

5.3 日志复制

5.4 安全性

任何领导人对于给定的任期号,都拥有了之前任期的所有被提交的日志条目.

5.4.1 选举限制

前提是:领导人都必须存储所有已经提交的日志条目

在任何基于领导人的一致性算法中，领导人都必须存储所有已经提交的日志条目,在某些一致性算法中,通过某些补偿机制将丢失的日志条目并把他们传送给新的领导人,raft增加了选举限制,保证领导人日志的完整性.这意味着日志条目的传送是单向的，只从领导人传给跟随者，并且领导人从不会覆盖自身本地日志中已经存在的条目
请求投票 RPC 实现了这样的限制： RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。
Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

通过选举策略实现

5.4.2 提交之前任期内的日志条目

Raft算法保证所有已提交的日志条目都是持久化的,只要一条记录被复制到大多数机器上,领导人就能提交.

领导人宕机会有如下几种情况:

领导人在将日志记录保存到大多数服务器上时已经提交后宕机
领导人在将日志记录保存到大多数服务器但是还没来得及提交时宕机
领导人还没有将日志记录保存到大多数服务器上时宕机

对于2,3情况,日志被覆盖并没有什么问题,但是对于1,日志被覆盖就会丢数据出现问题.如下展示了一种情况，一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的领导人覆盖掉

在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。
在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处
然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交
如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志
反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）

所以综上,领导人无法决定是否对老任期号的日志条目进行提交.Raft为了简化问题使用一种更加保守的方法,引入任期号的概念

任期内提交的数据时,至少复制到多数机器时才能提交
无论上一个任期数据有没有提交,都会复制过来(保留之前的任期号),然后本任期内产生的日志的任期号都会加1(这不是存在多数据的问题?)

5.4.3 安全性论证

反证法是“间接证明法”一类，是从反方向证明的证明方法，即：肯定题设而否定结论，经过推理导出矛盾，从而证明原命题; 接下来通过反证法来证明领导人的完全特性(任何领导人对于给定的任期号,都拥有了之前任期的所有被提交的日志条目)

假设任期 T 的领导人（领导人 T）在任期内提交了一条日志条目，但是这条日志条目没有被存储到未来某个任期的领导人的日志中(假设大于T的最小任期U的领导人U没有这条日志条目)

图9: S1,S2,S3,S4,S5是5台机器,如果 S1 （任期 T 的领导者）提交了一条新的日志在它的任期里，然后 S5 在之后的任期 U 里被选举为领导人，然后至少会有一个机器，如 S3，既拥有来自 S1 的日志，也给 S5 投票了。

在领导人 U 选举的时候一定没有那条被提交的日志条目（领导人从不会删除或者覆盖任何条目）。
领导人 T 复制这条日志条目给集群中的大多数节点，同时，领导人U 从集群中的大多数节点赢得了选票。因此，至少有一个节点（投票者、选民）同时接受了来自领导人T 的日志条目，并且给领导人U 投票了，如图 9这个投票者是产生这个矛盾的关键。
这个投票者必须在给领导人 U 投票之前先接受了从领导人 T 发来的已经被提交的日志条目；否则他就会拒绝来自领导人 T 的附加日志请求（因为此时他的任期号会比 T 大）。
投票者在给领导人 U 投票时依然保存有这条日志条目，因为任何中间的领导人都包含该日志条目（根据上述的假设），领导人从不会删除条目，并且跟随者只有在和领导人冲突的时候才会删除条目。
投票者把自己选票投给领导人 U 时，领导人 U 的日志必须和投票者自己一样新。这就导致了两者矛盾之一。
首先，如果投票者和领导人 U 的最后一条日志的任期号相同，那么领导人 U 的日志至少和投票者一样长，所以领导人 U 的日志一定包含所有投票者的日志。这是另一处矛盾，因为投票者包含了那条已经被提交的日志条目，但是在上述的假设里，领导人 U 是不包含的。
除此之外，领导人 U 的最后一条日志的任期号就必须比投票人大了。此外，他也比 T 大，因为投票人的最后一条日志的任期号至少和 T 一样大（他包含了来自任期 T 的已提交的日志）。创建了领导人 U 最后一条日志的之前领导人一定已经包含了那条被提交的日志（根据上述假设，领导人 U 是第一个不包含该日志条目的领导人）。所以，根据日志匹配特性，领导人 U 一定也包含那条被提交的日志，这里产生矛盾。
这里完成了矛盾。因此，所有比 T 大的领导人一定包含了所有来自 T 的已经被提交的日志。
日志匹配原则保证了未来的领导人也同时会包含被间接提交的条目，例如图 8 (d) 中的索引 2。

5.5跟随者和候选人崩溃

如果跟随者或者候选人崩溃了，那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单的通过无限的重试
如果崩溃的机器重启了，那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC，但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的，所以这样重试不会造成任何问题

5.6 时间和可用性

领导人选举是 Raft 中对时间要求最为关键的方面。Raft 可以选举并维持一个稳定的领导人,只要系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；
通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能。
选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现。

集群成员变化

集群节点变更是很常见的需求,例如移除故障或者增加节点,首先来思考这个过程中会遇到什么问题?

这里把[server1,server2,server3] 叫做c_old,[server1,server2,server3,server4,server5] 叫做c_new
集群从c_old状态变成c_new状态,在不停c_old服务情况下,会有一个节点同时给c_old集群中的发送变更消息,通知server更新自己的配置,由于分布式服务,各个server应用通知存在时间差,就会存在如上图情况.

存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置,例如server5通过server3,server4,server5投票选举成leader,3个选票超过新配置总数5的一半, server1 通过server1,server2投票选举成leader,2个选票超过老配置3的一半

分布式情况中协调多个节点进行同一操作,最容易想到的最简单的就是2PC(两阶段提交),但这样其实是有问题的，先不说 2 PC 一些 corner case 需要处理，整个过程还可能会导致暂时的服务不可用，虽然这个时间在多数情况下面可能比较短