前言

Raft是一种共识算法，用于在分布式系统中维护一致性，解决分布式系统的FT(Fault tolerance)问题，一个2N + 1 的集群可以承受最多N次Fault 。raft算法的基石包括2部分：选举和日志复制。

基本共识算法仅需要以下两种类型的RPC，具体的参数可以参考论文

• AppendEntries RPC：leader发起，用来复制日志条目或者发送心跳。
• RequestVote RPC：由candidate在选举期间启动

raft协议保证了以下性质：

• 选举安全：在给定的期限内，最多只能选举一位leader。
• leader只能添加日志：leader永远不会覆盖或删除自己日志中的条目；
• 日志匹配：如果两个日志包含具有相同索引和任期的条目，则在给定索引之前的所有条目的内容都是相同的。
• leader完整性：如果某一任期内一条日志被提交，则该条目将出现在之后任期leader中。
• 状态机安全性：如果服务器已在其状态机应用给定索引日志条目，则其他任何服务器都不会在该索引处应用其他内容的日志条目

选举

在raft集群中，节点有以下3种状态：

• leader：接收client的请求，追加日志到自己的日志，然后给其他节点发送 AppendEntries RPC，当leader收到了集群的大部分服务器的响应OK报文，服务器就把请求应用（apply 或 commit）到复制状态机，最后生成响应报文发送给client。leader还会定时发送heatbeat维持自己的权威。
• follower：普通节点，只是响应leader或者candidate的报文，当心跳超时的时候，变成candidate。
• candidate：先投自己一票，然后发送报文向集群其他节点收集投票，当其赢得大多数节点的投票的时候，变成leader。

每一个节点在一个term只能投一票，这保证了一个任期最多选出一个leader。

这里详细讲述一下选举的流程：

为了开始一次选举，follower增加它的当前任期号，然后转换为candidate状态。它为自己投票，而且给集群中所有的服务器并行发出RequestVote RPC。他会一直保存candidate的状态，直到以下情况发生：

• 它赢得了选举，获取了超过集群一半以上的投票，这时候他成为了leader，然后开始周期性发送心跳确认自己的领导地位。
• 也有可能在等待投票的时候，收到了比如第一种情况下已经成为了leader的心跳报文，如果这个leader的任期不小于自己，并且日志也比自己的更新，自己就承认他的领导，变成follower状态。
• 还有一种情况就是大家自己投自己，导致没有人获得了一半以上的投票。这时候就会产生分裂投票。如果出现分裂投票（split vote）的情况，即每个节点都投自己，这个term就无法选出leader，会出现选举超时(election timeout)然后进入下一个term，因为选举超时具有随机性（randomized ），在大多数情况下会有一个节点进入下一个任期（term + 1），然后由于他的term更大，所以他应该当选。

raft在选举的时候为了更好的一致性有一些规定。

• 如果一个节点发现自己的任期比其他节点小，他就会更新自己的节点任期。比如，节点 B 的任期编号为 0，当收到来自节点 A 的请求投票 RPC 消息，消息中包含节点的任期编号为 1，那么节点 B 将把自己的任期编号更新为 1
• 如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那就不应该成为领导者，应该成为follower，那么它会立即恢复成跟随者状态。
• 如果一个节点接收到一个包含较小任期编号值的请求，那么它会直接拒绝这个请求。

日志复制

在 Raft 集群中，每个服务器可以看成是一个复制状态机（Replicated State Machine）。复制状态机通常基于复制日志（replicated log）实现。每个服务器存储一个包含一系列指令的日志，并且按顺序执行指令。由于日志都包含相同顺序的指令，状态机会按照相同的顺序执行指令，由于状态机是确定的（deterministic），因此状态机会产生相同的结果。 保持这些日志的一致性（consistent）正是共识（consensus）算法的工作。

上图中复制状态机工作过程：

1. 客户端请求；发送指令到raft集群的leader，如果发给follower，会重定向。
2. leader首先把日志添加到自己的条目中，然后发送 AppendEntries RPC报文，在收到了大多数follower的确定操作之后。执行3
3. 日志应用到复制状态机；
4. leader返回client结果。

集群内只有领导者才能接收客户端请求，其他所有节点都接收来自领导者的AppendEntries RPC，以达到所有节点日志的一致，并最终达到状态的一致。指令以日志形式存在。日志由日志项（log entry）构成。日志项至少包含日志项索引、任期编号以及指令。

日志复制的流程如下：

1. 客户端发送请求，领导者接收到客户端请求，根据请求中的指令，创建一个新的日志项，并附加（append）到领导者日志中

2. 领导者通过日志复制 AppendEntries RPC，将新的日志项复制至其他节点

3. 当领导者将日志项成功复制至集群大多数节点的时候，日志项处于 committed 状态，领导者可将这个日志项应用（apply）到自己的状态机中，领导者将客户端请求结果返回给客户端

4. 当其他节点，即跟随者，接收到领导者的心跳消息，或新的日志复制消息（该消息均会附上领导者最大已提交日志项索引），如果跟随者发现领导者已提交某日志项，而自己还没将该日志项应用至状态机，那么，跟随者就将该日志项应用至自己的状态机中。

   由于领导者与跟随者之间的 RPC 通信 AppendEntries RPC，包括日志复制 RPC 和心跳 RPC，都包含了领导者最大已提交日志项索引，通过此日志项索引，跟随者可以在知道领导者已提交日志项，然后将该日志项按顺序应用至自己的状态机中，达到最终一致性。

日志一致性

为了保证状态机的一致性，保持日志的一致性是必须的。raft算法维持以下规定：

• 如果两个在不同日志的条目有相同的索引和任期，那么他们储存同样的指令

  why：因为一旦同步了之后leader在该任期是不会覆盖条目的。

• 如果两个在不同日志中的条目有相同的索引和任期，这两个日志中该索引之前的条目都是相同的

  why：发送AppendEntries RPC 或者 发送心跳的时候，leader在其中包括其日志中下一条新条目之前的索引和任期(当前已提交的最大索引和任期)。 如果follower在其日志中找不到具有相同索引和任期的条目，它拒绝该条目。并且返回一些信息用来同步日志。

结论是：只要AppendEntries成功返回，leader就会知道follower的日志和自己的新条目之前的日志完全相同。正常运行中，leader和follower的日志保持一致，所以AppendEntries的一致性检查不会失败。但是，leader宕机会导致日志不一致(上任leader可能没有完全复制它的日志)。在Raft中，leader通过强制follower复制leader的日志来解决不一致问题。这意味着follower中冲突的条目会被leader的日志覆盖。

为了使日志同步，leader必须找到与follower中相同的日志条目，然后从这个条目开始，把日志全部复制给follower，让2个服务器的日志完全相同。大概分为2种方法：

• 每次后退一个条目，一直找到和leader相同的条目。每一个条目需要一个 AppendEntries RPC 进行确认。
• 当拒绝一个AppendEntries请求时，follower可以在其中包括冲突条目的任期以及该任期下第一条储存的条目索引。 有了这些信息，leader可以按term来查找是否有相同的日志条目。每个具有冲突条目的任期都需要一个AppendEntries RPC。

通过这种机制，leader掌权时无需采取任何特殊措施即可恢复日志的一致性。 它刚刚开始正常运行，并且响应AppendEntries RPC的一致性检查失败，日志自动收敛。

安全性

raft协议依靠什么保证一致性呢。详细可以参考论文5.3。

leader需要保证2个，日志（up-to-date）以及term（up-to-date）。前者是日志最后一项的logterm以及索引最新，保证了是更新的日志。后者term越大越新。

考虑一个情况，当一个节点A掉线了很久，他在不停的自我选举，导致term很大，然后重新加入集群的时候，这时候已经在日志上滞后了很久了，但是term却很大。这时候它会导致leader下台，Leader就会重置currentTerm，增加到A节点的term，再次选举，这次选举leader肯定会成功（因为日志滞后决定了A不可能选成leader）。把日志复制给A，正常执行。

leader不管做任何事情都需要集群的一半以上同意。当这个leader崩溃了，处于提交状态的命令一定会被执行的。

• 因为大多数服务器都有这个命令，（因为被提交了，所以肯定大多数服务器日志中都有这个命令）那么新的leader一定会是在有新命令的服务器中产生，这是因为新的leader的产生不光取决于任期，还取决于日志的索引。

  Raft使用投票过程来阻止没有所有提交日志的candidate赢得选举。candidate必须联系集群的大多数才能被选举，这意味着每个提交的条目都必须至少存在于这些服务器中的一个里。如果candidate的日志与大多数服务器的日志(在下面精确定义了”up-to-date”)一样新(up-to-date)，则它将保存所有提交的条目。 RequestVote RPC实施了此限制：RPC包含有关candidate日志的信息，如果follower自己的日志比candidate的日志新，则拒绝投票。

  Raft通过比较日志中最后一个条目的索引和任期来确定两个日志中哪个是最新(up-to-date)。 如果日志中的最后一个条目具有不同的任期，则带有较新任期的日志将是最新的。 如果日志以相同的任期结尾，则更大索引的日志是最新的。

我们将在之后讨论集群成员变化和快照等优化操作