Raft算法

State

AppendEntries RPC

1. 只从Leader-->Follower，复制日志条目(§5.3)
2. 也用于心跳连接(§5.2)

Follower处理逻辑

1. 若term<CurrentTerm

   返回false(§5.1)

2. 若Follower日志中没有与prevLogIndex、prevLogTerm匹配的项

   返回false(§5.3)

3. 若Follower的日志和发来的日志冲突(比如相同index条目的term不同)

   删除冲突条目及后面所有的条目(§5.3)

4. 将Leader发来的日志中，自己没有的追加到日志中

5. IF leaderCommit > commitIndex：

   SET commitIndex=min(leaderCommit, 最后一个新表项的索引)

RequestVote RPC

由Candidate发起，收集投票(§5.2).

Receiver implementation:

1. if term < currentTerm: return false(§5.1)
2. 如果votedFor是 null 或 candidateId，并且候选人与接收人的日志一样是最新的，则投票(§5.2, §5.4)。

各个Server要遵守的规则

所有Server:

1. 如果RPC请求或回复中包含的term大于自身term

   更新自己的term，并转为follower(§5.1)

2. IF commitIndex > lastApplied:

   增加lastApplied，将log应用到状态机(§5.3)

Followers:

1. 对来自候选人和Leader的RPC进行回复

2. 如果超时未收到现任Leader的AppendEntries RPC，就转换为Candidate，开启选举

   收到其他Candidate的RequestVote时也算作收到RPC，重置超时器，推迟选举，防止多个Follower同时开始选举

Candidates:

1. 转换为Follower后，启动选举：

   • 增加当前任期
   • 投票给自己
   • 重置选举超时时间
   • 发送RequestVote RPC给其他所有服务器

2. 如果收到超过半数的投票

   成为新Leader

3. 如果选举期间收到来自新Leader的AppendEntries RPC

   停止选举，转换回Follower

4. 如果选举时再次超时

   重新启动一场新选举

Leaders:

1. 当选Leader后:

   向所有Server发送空的AppendEntries RPC(心跳)

   在空闲期间重复发送以防止Server们选举超时。(§5.2)

2. 如果收到客户端的指令:

   将指令包装为日志项，然后添加到日志中，待条目应用到状态机后再响应客户端(§5.3)

3. 如果Leader日志的最大索引 ≥ 某个Follower的nextIndex:

   发送AppendEntries RPC，附上从nextIndex开始的日志项

   • 如果成功

     更新nextIndex和matchIndex(§5.3)

   • 如果因为日志不一致而失败

     减小nextIndex并重试(§5.3)

4. 如果存在某个N，使得N>commitIndex，并且大多数的matchIndex[i]≥N，且log[N].term == currentTerm(这点尤其重要，不要使用计数规则提交以前任期的日志):

   设置commitIndex = N (§5.3, §5.4).

Leader选举

RequestVote RPC

0.新服务器加入集群

初始状态为Follower

只要持续收到Leader或Candidate的心跳信息，就保持Follower。

1.开始选举：

Follower通过选举超时(election timeout)时间间隔来决定是否启动选举。

如果在选举超时时间内未收到有效的心跳信息(一般是不包含日志条目的AppendEntries RPC)，则认为当前Leader失效，开启选举。

选举超时时间是在一个固定的时间区间内随机选择(例如，150-300毫秒)，这样大多数情况下只有一个服务器超时并发起选举，赢得选举并在其他服务器超时前发送心跳信号。

2.Follower的工作(投票规则)

Server收到RequestVote RPC时，根据以下规则进行投票：

• 如果RPC中的Term < 服务器当前的任期

  拒绝投票

• 如果已经在当前任期投过票

  拒绝投票

• 确保Candidate包含所有已提交的日志

  RequestVote RPC中包含日志信息，收到投票请求时，投票人会对比日志

  • 如果Candidate的日志和投票方一样新或者更新

    投票

  • 如果Candidate的日志不如投票人新

    不投票

  日志新的定义：如果Term不同，则Term较大者更新，如果Term相同，则Index较大者更新。

• 如果以上都没有

  投票，并重置自己的选举超时器。

3.Candidate的工作

• 如果获得超过半数的选票，则成为新Leader。向所有服务器发送心跳消息，以防止新的选举。

• 如果在选举过程中，收到心跳消息，且该消息的任期>=候选人的任期，则转回Follower，并将心跳消息发送方当做新Leader

• 如果选举超时也没有选出Leader，则触发新一轮选举。

4.无法获胜

还有一种情况，同时有多个Follower成为了Candidate，因此没人能获得多数票。

这种情况，Candidate在选举超时后，会触发新一轮选举。

Log replication

AppendEntries RPC

只从Leader-->Follower

1.Leader的工作

1. 接收客户端请求，每个请求包含一个要执行的命令

2. 将命令封装成日志条目追加到日志中。日志条目由命令和任期编号组成

3. 向所有Follower并行发送AppendEntries RPC

4. 一旦收到大多数Follower(包括Leader在内的半数以上)的确认，就认为日志条目被safely replicated

5. Leader执行条目到自己的状态机

   将已执行的最大日志目录编号记录到lastApplied，下次与Follower通信时，写入leaderCommit，这样Follower就知道lastApplied之前的所有条目都已执行，Follower同样执行这些条目到状态机。

6. 返回结果：Leader执行命令到状态机后，将操作结果返回给客户端

   此时，分布式系统中的大多数服务器就达成一致并成功执行了客户端的请求。

   

   图6：日志由按顺序编号的条目组成。每个条目包含创建它的任期(方框中的数字)和要执行的命令。如果一个条目可以安全地应用于状态机，那么它就被认为是Commited的。

2.Follower的工作

1. 如果RPC term<CurrentTerm

   返回false

2. 如果Follower日志中没有与prevLogIndex、prevLogTerm匹配的项

   返回false

3. 如果Follower的日志和发来的日志冲突(比如相同index条目的term不同)

   删除最早的冲突条目及后面所有的条目

4. 将Leader发来的日志中、自己没有的追加到日志中

5. 如果leaderCommit > commitIndex：

   SET commitIndex=min(leaderCommit, 最后一个新表项的索引)

日志修复

日志冲突处理步骤：

Leader为每个Follower维护一个nextIndex，这是Leader将发送给Follower的下一个日志条目的索引

Leader首次当选时，将所有nextIndex值初始化为日志中最后一个值之后的索引(图7中的11)。如果Follower与Leader的日志不一致，下一次AppendEntries RPC肯定会失败。失败后，Leader减少nextIndex并重试AppendEntries RPC。最终，nextIndex将达到Leader和Follower日志匹配的点。

成功匹配后，AppendEntries将成功，Follower将删除日志中的所有冲突条目，并从Leader日志(如果有的话)中追加条目。一旦AppendEntries成功，Follower与Leader的日志将一致，并且在该Term内始终保持一致。

如果需要，可以对协议进行优化，以减少被拒绝的AppendEntries rpc的数量。For example, when rejecting an AppendEntries request, the follower can include the term of the conflicting entry and the first index it stores for that term. With this information, the leader can decrement nextIndex to bypass all of the conflicting entries in that term; one AppendEntries RPC will be required for each term with conflicting entries, rather than one RPC per entry。实际上，我们怀疑这种优化是否必要，因为故障很少发生，并且出现大量不一致条目的可能性很小。

CH-7 日志压缩

Raft日志在正常操作过程中会不断增长，但随着日志变长，它占用的空间越来越多，重放所需的时间也越来越长。这最终会导致可用性问题，因此需要某种机制丢弃日志中的过时信息。

快照(Snapshot)是最简单的压缩方法。在快照中，整个当前系统状态被写入稳定存储的快照中，然后就可以丢弃掉快照包含的所有日志。

图12：服务器用一个新的快照替换其日志中已提交的条目(索引1到5)，快照存储最终状态(上图中的x<-0和y<-9)。快照的last included index和last included term用于快照在日志中定位，即快照包含了条目6之前的数据。

图12展示了Raft快照的基本思想。每个服务器独立地进行快照，只涵盖其日志中已提交的条目。大部分工作由状态机将其当前状态写入快照来完成。快照中还包含一些元数据：last included index:快照中包含的最后一个条目的索引(状态机已经应用的最后一个条目)，last included term是该条目的任期。这些数据被保留下来以支持快照之后第一个日志条目的AppendEntries一致性检查。为了支持集群成员变更(见第6节)，快照还包括最新的配置，截至最后包含的索引。一旦服务器完成了快照写入，它可以删除所有已包含的日志条目，以及所有先前的快照。

虽然服务器通常独立地进行快照，但Leader有时必须将快照发送给落后的Follower。当Leader已经删除了它需要发送给某个Follower的下一个日志条目时，就会出现这种情况。幸运的是，这种情况在正常操作中很少发生：跟随Leader保持同步的Follower已经拥有了该条目。然而，一个异常缓慢的Follower或新加入集群的服务器(见第6节)可能没有该条目。使这样的Follower赶上最新进度的方法是Leader向其发送快照。

Leader使用一个新的RPC:InstallSnapshot，将快照发送给落后的Follower；见图13。当Follower通过这个RPC接收到快照时，它必须决定如何处理现有的日志条目。通常情况下，快照会包含接收者日志中尚未存在的新信息。在这种情况下，Follower会丢弃其整个日志；因为它的日志全部被快照取代，且可能包含与快照冲突的未提交条目。如果Follower接收到一个描述其日志前缀的快照（由于重传或错误），则由快照覆盖的日志条目会被删除，但快照后续的条目仍然有效，必须保留。

接收方需实现的逻辑

1. 如果Arguments/term<currentTerm，立即回复。

2. 如果是第一个数据块(偏移量为 0)，则创建一个新的快照文件。

3. 将数据写入快照文件中的给定偏移量位置。

4. 如果done为false，回复Leader并等待更多的数据块到来。

5. 保存快照文件，丢弃所有索引小于该快照的现有或部分快照。

6. 如果现有日志条目与快照的最后包含条目具有相同的索引和任期，保留其后的日志条目并回复。

7. 丢弃整个日志。

8. 使用快照内容重置状态机（并加载快照的集群配置）。

使用快照偏离了Raft的强领导原则，因为Follower可以在不通知Leader的情况下进行快照。然而，我们认为这是合理的。虽然有Leader有助于避免在达成共识时出现冲突的决策，但在进行快照时，已经达成共识，因此不会有冲突的决策。数据仍然只从Leader流向Follower，只是Follower重新组织了自身的数据。

我们也考虑过基于Leader的快照，其中只有Leader创建快照，然后将此快照发送给其每个Follower。然而，这种方法有两个缺点。首先，将快照发送给每个Follower会浪费网络带宽并减慢快照过程。每个Follower已经拥有创建其自身快照所需的信息，而且服务器从其本地状态生成快照通常比通过网络发送和接收快照便宜得多。其次，Leader的实现将更加复杂。例如，Leader需要在向Follower复制新的日志条目时并行发送快照，以免阻塞新的客户端请求。

还有两个问题影响快照性能。

1. 何时进行快照？如果服务器过于频繁地进行快照，会浪费磁盘带宽和能量；如果快照频率过低，则可能耗尽存储空间，并增加在重启时重放日志所需的时间。

   一种简单的策略是当日志达到固定字节大小时进行快照。如果将这个大小设置为显著大于快照预期大小，那么快照产生的磁盘带宽开销将很小。

2. 性能问题，写入快照可能需要大量时间，而我们不希望这延迟正常操作。

   解决方案是写时复制，以便可以在不影响正在写入的快照的情况下接受新更新。例如，使用功能性数据结构构建的状态机自然支持这一点。或者，可以使用操作系统的写时复制支持（例如，Linux上的fork）来创建整个状态机的内存快照(我们的实现使用了这种方法)。

CH-8 客户端交互

本节描述客户端如何与Raft交互，包括客户端如何找到集群Leader以及Raft如何支持线性化语义。这些问题适用于所有基于共识的系统，Raft的解决方案与其他系统类似。

找到集群Leader

Raft的客户端将所有请求发送给Leader。当客户端首次启动时，它会连接到一个随机选择的服务器。如果这个服务器不是Leader，那服务器会拒绝客户端的请求，并提供它所知道的Leader信息(AppendEntries 请求包含Leader的网络地址)。如果Leader崩溃，客户端请求将超时；此时，客户端会再次尝试连接随机选择的服务器。

支持线性化语义

Raft 的目标是实现线性化语义(每个操作看起来在其调用与响应之间的某个时刻瞬间执行且仅执行一次)。然而，如前所述，Raft可能会多次执行一个命令：例如，如果Leader在提交日志条目后、响应客户端之前崩溃，客户端将重新提交该命令到新Leader，导致命令再次执行。解决方案是让客户端为每个命令分配唯一的序列号。然后，状态机会跟踪每个客户端处理的最新序列号及其关联的响应。如果它收到的命令的序列号已经执行过，它会立即响应，而不重新执行请求。

对于只读操作，可在不写入日志的情况下进行处理。然而，如果没有额外限制，可能会返回过时数据，因为响应请求的Leader可能已被更新的Leader取代，而旧Leader并不知情。线性化读取必须确保不返回过时数据，Raft采取两项预防措施来保证这一点而不使用日志。

1. Leader必须掌握最新的已提交条目信息。Leader完整性属性保证了Leader拥有所有已提交的条目，但在任期开始时，它可能不知道哪些条目是已提交的。为了解决这个问题，Leader需要提交一个来自其任期的条目。Raft通过在每个Leader任期开始时提交一个空的无操作条目到其日志中来解决这一问题。
2. Leader在处理只读请求之前，必须检查自己是否已被罢免（如果更近期的Leader已经当选，其信息可能已经过时）。Raft通过让Leader在响应只读请求之前与集群的多数节点交换心跳消息来进行确认。或者，Leader可以依赖心跳机制来提供某种租约[9]，但这依赖于时间安全性（假设时钟偏移受限）。