Raft 算法

背景

在分布式系统中，一致性至关重要，其中以 Paxos 最为闻名。然而 Paxos 难以了解，实现简单。于是有了 Raft。

Raft 角色

一个集群通常蕴含若干个节点，Raft 把这些节点分为三种角色：Leader,Follower,Candidate，各个角色分工不同，失常状况下，只会存在Leader,Follower。

Leader

负责客户端的申请和日志的同步，对Follower 发送心跳。Leader 是通过随即计时器和投票选举进去的。

Follower

此角色只负责响应来自 Leader 或 Candidate 的申请，并且不会被动发动任何申请。Follower 有一个随机的选举超时工夫，如果在这个工夫内没有收到 Leader 的心跳包或者 Candidate 的投票申请， 它就会变成 Candidate, 并开始发动新一轮的选举。Follower 会承受 Leader的日志并同步到本人的状态机中并回复Leader。在同步的时候，Follower 会查看是否存在日志失落，如果存在失落，则会开始回溯。删除不统一的日志，并从 Leader 从新同步。

Candidate

负责选举投票，集群刚启动或者 Leader 宕机的时候，状态为 Follower 的节点将转为 Candidate 并发动选举，如果超过半数对立，转变为 Leader 角色。

问题宰割

Raft 是基于操作转移的算法，它将一致性合成为多个子问题：Leader选举(Leader election)，日志复制(Log replication)，安全性(Safety)。

Leader 选举

对于选举，其实无非就是少数遵从多数的问题，当取得的投票数量超过一半时，本人就能够升为Leader。无非须要留神几个问题。

何时选举

  • [ ] 如何防止同时成为 Candiate，而全副投票给本人？

通过心跳机制，能够晓得 Leader 宕机或者不存在。每一个 Follower 在初始化的时候便会启动一个随机的选举超时工夫。随机是为了不让所有Follower 同时成为 Candidate，而全副投票给本人。

选举中的状态

  • 选举胜利：一个Candidate 博得了大多数选票，成为新的Leader。
  • 选举失败：未博得大多数选票，选举工夫超时，进入下一个任期。
  • 勾销选举：其余Candidate 博得了大多数选票，收到心跳后转为Follower。

如何保障选举出的Leader领有最新的日志

当一个节点成为候选人时，它会向其余节点发送RequestVote RPC申请，申请其余节点投票反对它成为新的leader。这个申请中蕴含了以后的任期号、候选人的id以及候选人的日志信息等内容。其余节点在收到这个申请后，会依据候选人的信息来判断是否反对候选人成为新的leader。

在判断过程中，每个节点都会比拟候选人的日志和本人的日志。如果候选人的日志比本人的日志要新，那么就会反对候选人成为新的leader，否则就会回绝候选人的申请。这就能阐明Candidate 比大多数的Follower的日志都要新。

  • [ ] 通过何种形式进行比拟？

Raft算法采纳了"最初日志条目标任期号"作为比拟的根据。具体而言，每个节点在投票时会比拟本人的"最初日志条目标任期号"和候选者的"最初日志条目标任期号"，如果候选者的任期号比本人的任期号要大，那么就认为候选者的日志比本人的日志要新，否则就认为本人的日志比候选者的日志要新。

  • [ ] 即便能比拟最新，但也仅仅是和大多数节点进行了比拟，如果保障是所有节点最新的呢？

如果一个 Leader 在和大多数的 Follower 进行比拟的时候，发现自己的日志比它们都要新，这并不能保障所有的 Follower 都曾经提交了比 Leader 更加新的日志，因为有一些 Follower 可能还没有和 Leader 进行比拟。

不过，这种状况不会影响 Raft 算法的正确性，因为 Raft 算法中，只有某个日志条目被大多数的节点复制，那么这个日志条目就会被认为是曾经提交了，且肯定会被后续的 Leader 复制。因而，如果 Leader 确信本人的日志是最新的，并且这些日志曾经被大多数的节点复制了，那么这些日志就会被认为是曾经提交的，并且后续的 Leader 会肯定会复制它们，以保证系统的一致性。

Leader的必要条件

具体而言，在Raft算法中，如果一个节点想要成为Leader，它须要满足以下两个条件：

  1. 它的日志必须蕴含了所有曾经提交的日志。
  2. 它的日志必须比其余节点的日志新。

为了满足第一个条件，Raft算法中的日志复制机制能够保障Leader的日志蕴含了所有曾经提交的日志。

日志复制

在呈现各种状况，比方宕机，网络分区等，就有可能呈现日志不统一的状况。新选举出的Leader 肯定是日志最新的，也不肯定是日志最全的。而因为各种分区，导致多个Leader呈现，所以也有可能导致Follower 的日志不是最新的状况。这些问题正是日志复制解决的问题。

Leader 的日志当先

心跳的时候会查看日志。AppendEntries RPC 中会蕴含一个 prevLogIndex 和 prevLogTerm 字段，它们用于让 Follower 查看本人的日志是否和 Leader 的日志统一。具体来说，Leader 会在 prevLogIndex 和 prevLogTerm 指定的地位之前的日志条目都曾经匹配的状况下，才会发送新的日志条目给 Follower。

这就保障了，如果 prevLogIndex 和 prevLogTerm 统一，那么 prevLogIndex 之前的所有日志都能放弃相对的统一。所以只须要查看 prevLogIndex 和 prevLogTerm，如果呈现不匹配的状况。这时，Leader 就会回退 prevLogIndex，持续发送更早的日志条目，直到 Follower 承受了 Leader 发送的日志条目为止。而后笼罩Followers在该地位之后的条目。

Leader 的日志落后

Leader 在比照的过程中，当 Leader 发送 AppendEntries RPC 时，它会蕴含 prevLogIndex 和 prevLogTerm 两个参数，这两个参数用于通知 Follower 在哪里匹配 Leader 的日志。如果 Follower 发现 prevLogIndex 和 prevLogTerm 与本人的日志不匹配，它会返回 false，并且将本人日志中匹配 prevLogIndex 的最初一条日志的 term 值返回给 Leader，从而帮忙 Leader 找到本人缺失的日志。

通过这种形式，Leader 能够得悉本人缺失的日志是哪些，而后从新发送这些缺失的日志，在这个申请中，Leader 会携带上一条匹配的日志条目标索引以及之后的所有未提交日志条目。通过这个申请，Follower 能够将缺失的日志条目从新发送给 Leader。如果 Follower 的日志比 Leader 更长，那么这些额定的日志条目也会在这个申请中被蕴含，Leader 能够通过这些日志条目将本人的日志欠缺。

安全性

总的来说，安全性贯通于整个流程。不论是 Leader 选举的时候，还是日志复制的时候。

  • [ ] 如果 Leader 在同步的时候故障，也就是这个写入申请并没有被大多数节点所承受。这个问题有什么解决方案吗？还是无可避免的造成了失落更新。

如果这个故障统一没有方法解决，那这条日志缺失永久性缺失了。然而如果故障复原了，持续同步日志，就很有可能造成日志错乱。举一个网上的广泛例子。

  • (a) S1是Leader，并且局部地复制了index-2；
  • (b) S1宕机，S5失去S3、S4、S5的投票入选为新的Leader（S2不会抉择S5，因为S2的日志较S5新），并且在index-2写入到一个新的条目，此时是term=3（注：之所以是term=3，是因为在term-2的选举中，S3、S4、S5至多有一个参加投票，也就是至多有一个晓得term-2，尽管他们没有term-2的日志）；
  • (c) S5宕机，S1复原并被选举为Leader，并且开始持续复制日志（也就是将来自term-2的index-2复制给了S3），此时term-2，index-2曾经复制给了少数的服务器，然而还没有提交；
  • (d) S1再次宕机，并且S5复原又被选举为Leader（通过S2、S3、S4投票，因为S2、S3、S4的term=4<5，且日志条目(为term=2,index=2)并没有S5的日志条目新，所以能够选举胜利），而后笼罩Follower中的index-2为来自term-3的index-2；（注：此时呈现了，term-2中的index-2曾经复制到三台服务器，还是被笼罩掉）；
  • (e) 然而，如果S1在宕机之前曾经将其以后任期（term-4）的条目都复制进来，而后该条目被提交（那么S5将不能博得选举，因为S1、S2、S3的日志term=4比S5都新）。此时所有在前的条目都会被很好地提交。

如果上述情况(c)中,term=2,index=2的日志条目被复制到大多数后，如果此时入选的S1提交了该日志条目，则后续产生的term=3，index=2会笼罩它，此时就可能会在同一个index地位先后提交一个不同的日志，这就违反了状态机安全性，产生不统一。也就是说当一个新Leader入选时，因为所有成员的日志进度不同，很可能须要持续复制后面term的日志条目，就算复制到少数服务器并且提交，还是可能被笼罩，因为后面term对应的日志条目较旧，容易使的没有这些条目标其余服务器入选Leader，此时就会笼罩这些日志条目。

为了打消上述场景就规定Leader能够复制后面任期的日志，然而不会被动提交后面任期的日志。而是通过提交以后任期的日志，而间接地提交后面任期的日志。

参考 https://www.cnblogs.com/gaoro...