背景及概念介绍

Raft是Diego Ongaro和John Ousterhout于2013年开发的一种基于领导者的共识算法，允许分布式系统中各节点在出现故障时可以针对一系列的数值达成一致，以可靠、复制、冗余、容错而闻名。比起Paxos协议来说Raft更加通俗易懂、易于实现。但需要注意的是Raft与Paxos不同，节点是信任当前的leader的，并不适用于拜占庭容错的算法。

Raft提供了一种在计算系统集群中分布多个状态机的通用方法，可以确保集群中的每个节点都同意相同的一系列状态变更，同时其采用了更强的领导形式。比如日志条目仅会从leader节点流向其他节点，如果客户端与其他节点建立通信，那么其他节点将会将其重定向给leader，简化了日志复制等操作的管理。

此处我们引入一个新的概念：复制状态机。

在分布式系统中，共识算法通常出现在复制状态机的背景下。复制状态机是解决系统中的各种容错问题的一个通用方法，可以通过复制日志并协调客户端与服务器副本的交互来构建容错系统。

复制状态机架构示例

如上图所示，在分布式系统中每个服务器都存储有一个日志（包含一系列命令），以及一个状态机。状态机按顺序执行这些命令。每个日志包含相同顺序的相同命令，因此每个状态机都从其日志中获取输入命令处理相同的命令序列。由于状态机是确定性的，所有节点从同一个 state 出发，每个状态机都会执行相同的操作序列，最终会产生相同的结果，达到相同的state。

我们只要保证集群中所有节点的log是一致的，那么经过一系列应用（apply）后最终得到的状态机也必然会是一致的。

问题来了，如何保证log复制时的一致性？

通过共识模块（Consensus Module）。

共识模块在接收到客户端的命令后会将其添加到日志中，并与其他服务器的共识模块进行通信来确保每台服务器的日志都包含相同顺序的请求。复制完成后每台服务器的状态机都会按照日志的命令序列进行处理，产生相同的输出后将输出返回客户端。至此，形成了一个单一的、高度可靠的复制状态机。

与其他共识算法略有不同，Raft将分布式系统中易出现的共识问题分成了几个相对独立的子问题：

1. 领导者选举（Leader election）：Raft 集群存在一个主节点（leader），客户端向集群发起的所有操作都必须经由主节点处理。主节点负责处理数据更新和复制的任务，因此没有leader，集群将无法工作。需要先进行领导者选举再进行下述操作；
2. 日志复制（Log replication）：Leader节点会负责接收客户端发过来的操作请求，将操作包装为日志条目并在集群中进行同步操作来确保其他节点的日志与自己的日志一致。在保证大部分节点都同步了本次操作后，就可以安全地给客户端回应响应了；
3. 安全属性（Safety）：分布式系统中有很多种情况可能发生，算法需要设置多项安全属性（限制）为系统的正确性以及可用性提供安全保证。具体有哪些关键的安全属性以及Raft如何确保，后面将详细介绍。

Raft核心算法其实就是由这三个子问题组成的：选主（Leader election）、日志复制（Log replication）、安全性（Safety）。这三部分共同实现了 Raft 核心的共识和容错机制。接下来我们针对这三个子问题进行深度剖析。

算法剖析

Raft算法中的节点角色

集群中的每个节点角色都处于三种状态中的任何一种，Leader（领导者）、Follower（跟随者）、Candidate（候选者）。通常只有一个leader，所有其他服务器都是follower。Leader是所有请求的处理节点，接收客户端发起的操作请求后写入本地之日后同步至集群其它节点。Follower不会发出请求，只被动响应来自Leader跟Candidate的请求。Candidate则主要用于选举新的leader。下图展现了状态转变的大致过程。

领导者选举（Leader election）

因为后续leader会负责将日志复制到follower节点上，因此会定期通过发送心跳消息来告知follower他还在正常运行。每个follower都有一个超时机制，通常150到300毫秒之间。在这段时间内如果follower收到了来自leader的心跳信息，时间则会重置，如果没有收到，follower 会将其状态更改为Candidate并发起leader选举。获得整个集群大多数选票的Candidate将成为新任leader，然后向所有其他服务器发送心跳消息防止出现新的选举。Leader通常会一直持续运行到失败为止。

比如如下图图解所示：

在这个阶段会涉及一个新的概念：任期（term），每个任期都由一个单调递增的数字（任期号）标识。

Raft将时间划分为任意长度的term，如上图所示，每当 candidate 触发 leader election 时都会增加 term。服务器每个任期只能投票一次，按照先到先得的原则。Candidate如果收到了来自其他服务器节点（follower）的多数选票，那么本届任期则由它担任新任leader执行数据更新、复制等操作直至任期结束。但并不是每个term都一定对应一个leader，有时候某个term内会由于分散投票导致选不出leader，这时candicate会递增任期号并开始新一轮选举。

题 外话：为什么要有任期号的概念？

服务器不会在每时每刻都去观察不同任期之间的变化，因此任期在Raft中承担逻辑时钟（logic clock）的作用，服务器可以通过任期号来检测leader的状态是否已过期，就像前面提到的每个节点都保存了一个current term number，在通信时会互相进行交换做出决策。比如说下方情况出现：

• 在Raft算法中的节点角色部分中提到的状态转换图，有一条状态线是discovers server with higher term。这条线的背景是当leader发生了宕机或网络断连，此时其它follower无法收到leader的心跳信息，首个触发超时的节点会变为candidate并开始拉票（此时也会新增一个term），由于该candidate的term大于原leader的term，因此所有follower都会投票给它，这名candidate会变为新的leader。一段时间后原leader恢复了，收到了来自新leader的心跳包，发现自己当前的term小于心跳中的term，那么他会立即恢复为follower状态并将其term进行更新。

当然还有许多用途，比如可以通过任期号来检测leader是否已过期等等，具体细节可以继续看下去~

节点间主要通过两种类型的远程过程调用（RPC）来进行通信：

• RequestVotes RPC：由候选节点发送，用于在选举期间向其他节点请求选票；
• AppendEntries RPC：这个RPC由leader发起，携带最新收到的命令。它还用作心跳消息。当follower收到此消息时，选举计时器将被重置。

大概流程我们稍微了解了，下面我们来具体了解一下选举领导者的详细过程。

启动阶段

Raft采用心跳机制来触发leader选举。当服务器启动时，服务器首先作为follower。只要服务器从leader或者candidate接收到有效的RPC，他们就会保持其follower状态。

状态转换，候选状态出现：

为了维护集群Leader的权威，Leader节点会向其他Follower节点发送心跳来表达统治权。如果Follower节点在一段时间内（选举超时机制）没有收到任何通信，他就会过渡到候选状态并增加其当前任期，开始新的选举；

请求投票：

此时，超时节点将其状态更改为Candidate状态，它会为自己投票并向集群中的所有其他节点并行发送RequestVote RPC以建立多数并尝试成为Leader。其中，RequestVote RPC信息中包括候选人的任期、候选节点日志中最后的索引（lastLogIndex）以及任期（lastLogterm）。候选者继续保持这种状态，直到发生以下三种情况之一：（a）它赢得选举，（b）另一台服务器将自己确立为领导者，或（c）一段时间内没有获胜者。

投票流程：

每台服务器都存储一个当前的任期号，该任期号随着时间的推移单调增加。 每当服务器通信时都会交换当前任期信息进行选举：

1. 如果一台服务器的当前任期号小于另一台服务器的当前任期号，则它会将其当前的任期进行更新；
2. 如果候选者或leader发现其任期号比其他服务器小，则会立即恢复为follower状态；
3. Follower会评估候选者的日志确定其是否是最新的，如果不是则拒绝投票请求；如果是，则投票给候选者；
4. 在任何时间点，任何其他服务器拥有更高的term number，它可以立即成为新任leader；

选举结果：

情况1： 选举成功（Step: receives votes from majority of servers）

如果候选节点收到来自整个集群中同一任期的大多数服务器的选票（N/2+1），则该候选节点将赢得选举，此时，它会立刻将自己的状态更新为Leader，并向所有其他服务器发送心跳消息，以建立其权威并防止新的选举。每个节点针对每个term只能投出一张票，按照先到先得的原则确保了最多保只有一个 candidate 会成为 leader。

情况2：选举失败（Step: discovers current leader or new term）

在等待投票时，候选节点可能会从另一台声称是自己是leader的服务器收到AppendEntries RPC。如果这台服务器携带的任期（包含在其RPC中）跟候选节点自身当前的任期一样大或者比他大，那么候选节点则承认对方的leader身份并认为对方是生效的，然后将自身状态切换回follower状态。这说明其它节点已经成功赢得了选举，它只需立刻跟随即可。 如果RPC中的任期小于候选节点当前的任期，则候选节点拒绝此次请求并继续保持候选状态。

情况3：选举超时（Step: times out, new election）

最后一种情况是候选人既不会赢得选举，也不会输掉选举：如果许多follower同时成为候选人，选票可能会被分散，从而没有一个候选节点可以获得多数票的支持。当这种情况发生时，每个候选节点都将超时，此时它们需要通过增加自身的任期并发起新另一轮的RequestVote RPC来开始新一轮选举。但是需要注意的是，如果此时不采取额外措施，这种分散选票选不出leader的情况可能会无限期的重复发生。

为了解决上述风险，Raft采用了一个被称为随机选举超时的机制来减少后续出现分散投票的几率。简单来说就是为了预防多次出现平票的情况，每个节点的选举定时器时间都是不一样的，会从固定时间间隔（比如150-300毫秒）中随机选择。大多数情况下，只有一台服务器将超时，赢得选举，赢得选举后会在任何其他服务器超时之前发送心跳消息树立权威。相同的机制也应用于处理分裂投票。出现分裂投票的情况下，候选节点们在选举开始时重新启动该机制，降低新选举中再次出现分裂投票的可能性。

下图展现了出现分票的情况之一：

以上就是 Raft 的选主逻辑，但还有一些细节（譬如是否给该 candidate 投票还有一些其它条件）依赖算法的其它部分基础，具体将在后续的安全属性章节介绍。

一旦 leader 被票选出来，它就需要承担起相应的职责了，开始接收客户端的请求，并将日志条目复制到其他节点上确保数据一致性。

日志复制（Log repication）

正如前面的内容提到的状态复制机，只要保证节点log的一致性，就可以保证最终的一致性。Raft赋予了leader节点更强的领导力，所有的log都必须交给leader节点处理，并由leader节点复制给其它节点。这个过程，就叫做日志复制（Log replication）

日志的结构通常如上图所示，每个日志条目都包含leader收到该条目时的任期和状态机的命令，任期号可以用于检测日志之间的不一致。每个日志条目还有一个唯一的整数索引值（log index），可以用于标识其在日志集合中的位置。此外，每条日志还会存储一个term number（日志条目方块最上方的数字，相同颜色任期号相同），该term表示leader收到这条指令时的当前任期，term相同的log是由同一个leader在其任期内发送的。

一旦Leader被选举出来，后续的接受客户端请求以及日志复制等操作主要由leader负责。客户端的每个请求都包含了需要由复制状态机执行的命令，leader会将命令作为新条目附加到其日志中，然后向其他服务器并行发出AppendEntries RPC以便它们复制该条目到相应的日志中。

• 如果follower节点宕机或者运行缓慢，再或者网络数据包丢失，leader会不断地重试AppendEntries RPC，直到follower节点最后存储了所有的日志条目。
• 一旦Leader收到超过一半follower的确认，则表明该条目已被成功复制（比如上图中的log index 7）。Leader将该条目应用（apply)到其本地状态机（被视为committed）并将执行结果返回给客户端。此事件还会提交leader日志中之前存在的条目，包括前任leader创建的条目。

Leader会持续发送心跳包给 followers，心跳包中会携带当前已经安全复制（我们称之为committed）的日志索引，以便其他服务器知晓。一旦follower得知日志条目已提交，它就会将该条目应用到其本地状态机（按日志顺序）。

Raft的日志机制（安全规则：日志匹配属性）确保了集群中所有服务器之间日志的高度一致性。日志匹配指的是说：

1. 如果不同日志中的两个条目拥有相同的term和index，则它们存储着相同的命令。原因就是因为raft要求leader在一个term内针对同一个index只能创建一条日志，并且永远不会修改，保证“持久化”；
2. 当发送AppendEntries RPC时，leader在其日志中会额外包含紧邻新条目之前的日志的index和term信息。如果followers在其日志中找不到具有相同索引和任期的日志条目，则它会拒绝新的日志条目。因此，如果不同日志中的两个条目如果拥有相同的index和term，则所有先前条目中的日志也都是相同的；

AppendEntries会执行一致性检查保留上述属性。

每当 AppendEntries 成功返回时，leader就可以知道follower的日志与自己的日志相同。正常运行时，leader和follower的日志保持一致，因此AppendEntries一致性检查不会失败，只会成功。

但是，在leader崩溃的情况下，日志可能会不一致，前任leader可能没有完全复制其日志中的所有条目。这些不一致可能会引起一系列问题引起失败，比如下图所示的内容，followers的条目与leader不完全一致，要么多了，要么缺少。

为了避免上述情况的发生，Leader通过强制follower复制自己的日志来处理不一致的问题：

1. 既然要保证follower的日志与其自己的一致，leader需要将其日志与follower日志进行比较，找到它们之间最后一次达到一致的条目，就像前面提到的日志匹配属性，因此这个条目如果一致，之前的日志也一定都是一致的。然后接下来删除follower日志中此关键条目之后的所有条目，并向follower发送该点之后自己的所有条目进行同步；
2. Leader会针对每个follower都维护一个nextindex，表示下一条需要发送给该follower的日志索引。在leader选举成功上任的时候，会将所有的nextIndex值初始化为其日志中最后一条日志的的日志索引+1；
3. 如果follower和leader的日志不一致，则下次AppendEntries RPC中的AppendEntries一致性检查将失败，Leader将递减nextIndex并重试AppendEntries RPC，直到nextIndex达到Leader和follower日志匹配的点为止；
4. 至此，AppendEntries成功，然后将删除follower日志中任何冲突的条目，并附加领导者日志中的条目（如果有）。

这样的话，leader以及follower的日志就会保持一致直到term任期结束都会保持这种状态。

图解：

注意：Leader永远不会覆盖或删除其日志中的条目，它只会追加新条目。

安全属性（Safety）

前面的部分主要描述了Raft的核心流程，也提及了个别机制比如说在给定任期内最多只能选举一名领导人。但是在分布式系统中有很多种情况可能发生，还需要更为详细的安全机制来确保每个状态机都可以以相同的顺序执行完全相同的命令。因此，我们需要针对“领导者选举”以及“日志复制”额外加上一些安全属性，来完善整个Raft算法。

选举限制

综上所述，Leader在整个Raft机制中真的充当着非常重要必不可少的角色，因此Leader的选举重中之重。

我们来试想一个场景：当leader提交了多个日志条目时，follower如果此时不可用，还没来得及复制这些日志，就被选举为新任leader了，然后这个新任leader呢，又用新的日志条目覆盖了其他节点上面上任leader committed的日志条目。那么就会导致多个不同的状态机可能执行不同的命令序列。

因此，核心问题还是在于leader选举出现了问题，对于哪些服务器有资格当选leader的限制对于Raft算法的完善十分重要，前面我们已经提过了个别的限制，下面我们再明确细化一下：

1. 日志条目仅朝一个方向流动，leader永远不会覆盖其日志中的现有条目，也不会删除其日志中的条目，只能将新条目追加到其日志中（Leader Append-Only）；
2. 在选举过程中，Candidate为了赢得选举，其日志中必须包含所有已提交的条目。为了当选，Candidate必须获得大多数服务器的投票才能当选新任leader，RequestVote RPC中包含有关Candidate日志的信息（term, index），如果其他服务器发现自己的日志比Candidate的日志新，那么将拒绝投票；

如何判定日志新旧？Raft通过比较日志中最后一个条目的index以及term来确定两个日志中哪一个更新。如果日志的最后一个条目有不同的term，那么更大的term对应的日志比较新。如果日志的term都相同，那么index大的日志更新。

Commit限制

Commit限制：通过计算副本数，仅提交leader当前term的日志条目。

为什么要增加这个限制？我们同样基于这个图进行场景模拟就知道了。

• 阶段（a）：S1是leader，收到请求后仅复制index2的日志给了S2，尚未复制给S3 ~ S5；
• 阶段（b）：S1崩溃，S5凭借 S3、S4 和自身的投票当选为term3的leader，收到请求后保存了与index2不同的条目（term3），此时尚未复制给其他节点；
• 阶段（c）：S5崩溃,S1重新启动，当选为新任leader（term4），并继续复制，将term2, index2复制给了 S3。这个时候term2,index2已经的日志条目已复制到大多数的服务器上，但是还没提交。
• 阶段（d）：如果S1如d阶段所示，又崩溃了，S5重新当选了leader（获得S2、S3、S4的选票）然后将 term3, index2的条目赋值给了所有的节点并commit。那这个时候，已经 committed 的 term2, index2被 term3, index2覆盖了。

因此，为了避免上述情况，commit需要增加一个额外的限制：仅commit leader当前term的日志条目。

举个例子，比如在c阶段，即使term4的时候S1已经把term2, index2复制给了大多数节点，但是它也不能直接将其commit，必须等待term4的日志并成功复制后一起commit。

所以除非说阶段c中term2, index2始终没有被 commit，这样S5在阶段d将其覆盖就是安全的，在要么就是像阶段e一样，term2, index2跟term4, index3一起被 commit，这样S5根本就无法当选leader，因为大多数节点的日志都比它新，也就不存在前边的问题了。

Follower 和 Candidate 崩溃

Follower和Candidate崩溃相对来说比Leader节点崩溃更好处理，如果Follower和Candidate出现了问题，那么也就意味着RequestVote和AppendEntries RPC将失败。Raft会无限期的重试，直到服务器重新启动，RPC将成功完成。如果很不凑巧，Follower和Candidate节点是在完成RPC之后但在响应之前崩溃，那么它将在重新启动后再次收到相同的 RPC。

时间安排和可用性

Raft的安全机制不能依赖于时间（如果与预期时间不符，可能会导致一系列问题），但是可用性（系统及时响应客户端的能力）必然取决于时间，比如领导者选举必须有时间限制，否则系统无法运行下去。

领导者选举是Raft机制中最关键的一个模块。只要系统满足以下时间安排，Raft就能够顺利选举初一个稳定的Leader：

broadcastTime ≪ electionTimeout ≪ MTBF

1. BroadcastTime：是服务器向集群中的每个服务器并行发送 RPC 并接收其响应所需的平均时间；
2. ElectionTimeout：是前面所描述的选举超时时间；
3. MTBF：是单个服务器的平均故障间隔时间；

在时间长短来看，广播时间是最短的，以便leader在当选后能够更可靠快速地发送心跳消息，以便阻止follower选举冲突；由于选举超时采用的是随即方法，这种方法可以降低分散选票的几率，选举超时时间比MTBF会小几个数量级。当leader节点崩溃时，系统在选举超时时间内不可用。因此，为了维持整个系统的完美可用性，选举超时时间仅占总时间的一小部分，防止影响系统运行。

BroadcastTime以及MTBF的时间具体由底层系统决定，但是ElectionTimeout时间是我们需要自行设定的。 

快照

正如前面所介绍的内容，Raft核心算法维护了日志的一致性，通过apply日志我们就可以得到一致的状态机，客户端的操作命令会被包装成日志交给 Raft 处理。但是大家有没有想过一个问题，随着客户端请求的增多，这些日志是不是会越来越长，占用越来越高的存储空间？而且，每次系统重启时都需要完整回放一遍所有日志才能得到最新的状态机。如果没有某种机制来清除日志中积累的陈旧信息，最终就会导致可用性问题影响整个系统的运行。

所以，为了避免这一情况的发生，Raft采用了最简单的日志压缩方法--快照（Snapshot）。简单来说，就是将某一时刻系统的状态 dump 下来并落地存储，这样该时刻之前的所有日志条目就都可以丢弃了（也包括先前的快照）。每个服务器独立拍摄快照，仅覆盖committed完成的日志，因为只有committed日志才是确保最终会应用到状态机的。

上图展示了服务器用新快照替换了其日志中已提交的条目（index1-index5），新快照仅存储当前状态（变量x、y）。快照中显示的last included index以及的last included term用于定位日志位置以及支持AppendEntries一致性检查。

Follower可以保持最新状态的方法就是leader通过网络向其发送最新快照。比如，当follower落后的时候，leader需要向其同步日志，但是这个时候假设leader已经做了快照，旧的日志已经被删除，leader就可以使用InstallSnapshot RPC向落后的follower发送快照，其中将包含该follower未包含的新信息。同样，当集群中有新节点加入，或者某个节点宕机太久落后了太多日志时，leader也可以直接发送快照，节约了大量日志传输和回放时间。

以上就是完整的关于Raft的介绍，在下一篇将为您介绍有关Raft在星环核心组件TDDMS中是如何发挥作用的，感兴趣的小伙伴多多点在留言支持一下吧~

预告：

星环分布式系统底层存储采用的就是Raft共识算法来进行leader选举和数据复制，与其他算法不同，不是针对整个数据集使用单个Raft组，而是在单个分片级别应用Raft复制，其中每个分片都有自己的Raft组。通过应用Raft算法，分布式存储架构实现了数据同步、容灾等能力，也辅助完成了多模态数据的统一处理、两地三中心的建设等等。那么具体Raft在整体架构中发挥了什么作用承担了什么样的角色呢？