Raft简述

前言

本文主要参考于Raft论文《In Search of an Understandable Consensus Algorithm》和中文译文。也参考了一些同道写的博客。

Raft 是一种为了管理复制日志的一致性算法。Raft实际是Multi-Paxos的变种，它强化了Multi-Paxos中的Leader地位，限制了追加日志必须是连续的。
为了提升可理解性，Raft 将一致性算法分解成了几个关键模块，例如领导人选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。

定义

状态

两种RPC

AppendEntries RPC:被领导人用来日志复制或者心跳检测（空日志条目）。

RequestVote RPC

服务器遵守的规则

所有Server

• 如果commitIndex > lastApplied，lastApplied自增，将log[lastApplied]应用到状态机

• 如果 RPC 的请求或者响应中包含一个 term T 大于 currentTerm，则currentTerm赋值为 T，并切换状态为追随者（Follower）

Followers

• 响应来自候选人和领导人的 RPC
• 如果在超过选取领导人时间之前没有收到来自当前领导人的AppendEntries RPC或者没有收到候选人的投票请求，则自己转换状态为候选人

Candidates

• 转变为选举人之后开始选举

  • currentTerm自增
  • 给自己投票
  • 重置选举计时器
  • 向其他服务器发送RequestVote RPC

• 如果收到了来自大多数服务器的投票：成为领导人

• 如果收到了来自新领导人的AppendEntries RPC（heartbeat）：转换状态为Follower

• 如果选举超时：开始新一轮的选举

Leaders

• 一旦成为领导人：向其他所有服务器发送空的AppendEntries RPC（heartbeat）; 在空闲时间重复发送以防止选举超时

• 如果收到来自客户端的请求：向本地日志增加条目，在该条目应用到状态机后响应客户端

• 对于一个Follower来说，如果上一次收到的日志索引大于将要收到的日志索引（nextIndex）：通过AppendEntries RPC将 nextIndex 之后的所有日志条目发送出去

  • 如果发送成功：将该Follower的 nextIndex和matchIndex更新
  • 如果由于日志不一致导致AppendEntries RPC失败：nextIndex递减并且重新发送

• 如果存在一个满足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N，则将commitIndex赋值为 N

领导人选举

服务器启动时，初始化为Follower。Follower在一个周期没有收到来自Leader的心跳，就叫做选举超时，然后假定无可用领导人并且开始进行选举。
Follower会自增自己的Term并且状态转换为Candidate，然后向其他服务器发送RequestVote RPC。Candidate经过选举过程会出现三种情况：

• 赢得选举，状态转换为Leader
• 其他Server赢得选举，自身状态转换为Follower
• 没有任何一台服务器赢得选举，则继续进行选举（通过随机化选举超时时间来减小瓜分选票的可能性，因为响应投票是先到先服务的）

状态机的转换图如下：

日志复制

日志匹配原则（Log Matching）：如果两个日志在相同的索引位置上的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间的条目完全相同。

日志由有序序号标记的条目组成。每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令。一个条目当可以安全的被应用到状态机中去的时候，就认为是可以提交了。

日志条目被复制到大多数服务器以后，则Leader提交该日志条目，然后在下次的AppendEntries RPC 中告知其他服务器该日志已提交，则所有服务器可以将其应用到状态机。

日志复制特性：

• 如果在不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
• 如果在不同日志中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全一样的。

第一条特性源于Leader在一个任期里在给定的一个日志索引位置最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader会把新日志条目紧接着之前的条目的索引位置和任期号都包含在里面。如果Follower没有在它的日志中找到相同索引和任期号的日志，它就会拒绝新的日志条目。

当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

为了使得Follower的日志同自己的一致，领导人需要找到Follower同它的日志一致的地方，然后删除Follower在该位置之后的条目，然后将自己在该位置之后的条目发送给Follower。这些操作都在 AppendEntries RPC 进行一致性检查时完成。Leader给每一个Follower维护了一个nextIndex，它表示领导人将要发送给该Follower的下一条日志条目的索引。

安全性

选举限制

Raft 使用投票的方式来阻止没有包含全部日志条目的服务器赢得选举。日志条目只有一个流向：从领导人流向追随者。领导人永远不会覆盖已经存在的日志条目。

提交之前任期的日志条目

Raft 从来不会通过计算复制的数目来提交之前人气的日志条目。只有领导人当前任期的日志条目才能通过计算数目来进行提交。一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配原则（Log Matching Property），之前的日志条目也都会被间接的提交。

Follower和Candidate崩溃

如果一个追随者或者候选人崩溃了，那么之后的发送给它的 RequestVote RPC 和 AppendEntries RPC 会失败。Raft 通过无限的重试来处理这些失败；如果崩溃的服务器重启了，RPC 就会成功完成。如果一个服务器在收到了 RPC 之后但是在响应之前崩溃了，那么它会在重启之后再次收到同一个 RPC。因为 Raft 中的 RPC 都是幂等的，因此不会有什么问题。

时序和可用性

领导人选取是 Raft 中对时序要求最关键的地方。Raft 会选出并且保持一个稳定的领导人只有系统满足下列时序要求（timing requirement）：

broadcastTime << electionTimeout << MTBF

在这个不等式中，broadcastTime指的是一台服务器并行的向集群中的其他服务器发送 RPC 并且收到它们的响应的平均时间；electionTimeout指的就是选举超时时间；MTBF指的是单个服务器发生故障的间隔时间的平均数。

broadcastTime和MTBF是由系统决定的性质，但是electionTimeout是我们必须做出选择的。Raft 的 RPC 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，这取决于存储的技术。因此，electionTimeout一般在 10ms 到 500ms 之间。大多数的服务器的MTBF都在几个月甚至更长，很容易满足这个时序需求。

集群成员变化

在 Raft 中，集群先切换到一个过渡配置，我们称其为共同一致（joint consensus）；一旦共同一致被提交了，然后系统再切换到新的配置。共同一致是旧的配置和新的配置的组合：

• 日志条目被复制给集群中新、老配置的所有服务器。
• 新、老配置的服务器都能成为领导人。
• 需要分别在两种配置上获得大多数的支持才能达成一致（针对选举和提交）

共同一致允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换过程。此外，共同一致可以让集群在配置转换的过程中依然能够响应服务器请求。

图 -11：集群配置变更的时间线。虚线表示的是已经被创建但是还没提交的配置条目，实线表示的是最新提交的配置条目。领导人首先在它的日志中创建 Cold,new 配置条目并且将它提交到 Cold,new（使用旧配置的大部分服务器和使用新配置的大部分服务器）。然后创建它创建 Cnew 配置条目并且将它提交到使用新配置的大部分机器上。这样就不存在 Cold 和 Cnew 能够分别同时做出决定的时刻。

概念：
Cold，new：这个配置是指Cold，和Cnew的联合配置，其值为Cold和Cnew的配置的并集，比如Cold为[A, B, C]， Cnew为[B, C, D]，那么Cold,new就为[A, B, C, D]

Cold,new的大多数：是指Cold中的大多数和Cnew中的大多数，如下表所示，第一行因为Cnew的C, D没有Replicate到日志，所以并不能达到一致

集群配置在复制日志中用特殊的日志条目来存储和通信；图 -11 展示了配置变更的过程。当一个领导人接收到一个改变配置 Cold 为 Cnew 的请求，它会为了共同一致以前面描述的日志条目和副本的形式将配置存储起来（图中的 Cold,new）。一旦一个服务器将新的配置日志条目增加到它的日志中，它就会用这个配置来做出未来所有的决定（服务器总是使用最新的配置，无论它是否已经被提交）。这意味着领导人要使用 Cold,new 的规则来决定日志条目 Cold,new 什么时候需要被提交。如果领导人崩溃了，被选出来的新领导人可能是使用 Cold 配置也可能是 Cold,new 配置，这取决于赢得选举的候选人是否已经接收到了 Cold,new 配置。在任何情况下， Cnew 配置在这一时期都不会单方面的做出决定。

• issue1 ：开始的时候新的服务器可能没有任何日志条目，新的服务器以没有投票权的身份加入到集群中来（领导人复制日志给他们，但是不把它们考虑到大多数中）。一旦新的服务器追赶上了集群中的其它机器，重新配置可以像上面描述的一样处理。

• issue2：如果当前的Leader不在C-new的配置中会怎么样（即当前的Leader是一个要被下线的节点）。在C-old-new的状态下，Leader依旧可用；在C-new被commit之后Leader实际已经从集群中脱离，此时可以对Leader节点进行下线操作，而新集群则会在C-new的配置下重新选举出一个Leader。

• issue3：移除不在 Cnew 中的服务器可能会扰乱集群。这些服务器将不会再接收到心跳（heartbeat），所以当选举超时时，它们就会进行新的选举过程。它们会发送带有新的任期号的 RequestVote RPC，这样会导致当前的领导人回退成跟随者状态。新的领导人最终会被选出来，但是被移除的服务器将会再次超时，然后这个过程会再次重复，导致整体可用性大幅降低。

为了避免这个问题，当服务器确认当前领导人存在时，服务器会忽略 RequestVote RPC。特别的，当服务器在当前最小选举超时时间内收到一个 RequestVote RPC，它不会更新当前的任期号或者投出选票。这不会影响正常的选举，每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。然而，这有利于避免被移除的服务器扰乱：如果领导人能够发送心跳给集群，那么它就不会被更大的任期号废除。

就如下图所示，S4收到Cnew成员变更的请求，立马将其写入日志中，Cnew中并不包含S1节点，所以在S4将日志复制到S2，S3之前，如果S1超时了，S2，S3中因为没有最新的Cnew日志，仍让会投票给S1，此时S1就能选举成功，这不是我们想看到的。

Raft中提供了另一种方式来避免这个问题，如果每一个服务器如果在ElectionTimeout内收到现有Leader的心跳（换句话说，在租约期内，仍然臣服于其他的Leader），那么就不会更新自己的现有Term以及同意投票。这样每一个Follower就会变得很稳定，除非自己已经知道的Leader已经不发送心跳给自己了，否则会一直臣服于当前的leader，尽管收到其他更高的Term的服务器投票请求。

日志压缩

快照或者LSM-Tree