Raft

参考资料：

Raft论文 In search of an understandable consensus algorithm.

Consensus: bridging theory and practice

Raft协议详解

深入架构原理与实践:成员变更问题

浅谈Raft配置变更(成员变更)策略

一、Raft基础

• Raft集群包含若干个服务器节点都处于这三个状态之一：领导人(Leader)、跟随者(Follower)、候选人(Candidate)。
  1. Leader：所有请求的处理者，其实就是整个Raft集群和外部进行沟通的接口。Leader接收client的更新请求，本地处理后再同步至多个其他副本；
  2. Follower：请求的被动更新者，从Leader接收更新请求，然后写入本地日志文件；
  3. Candidate：如果Follower副本在一段时间内没有收到Leader的心跳，则判断Leader可能已经发生故障，此时启动Leader election，Follower副本会变成Candidate状态，直至选主结束。

• 时间被划分成一个个的任期，每个任期开始都是一次选举。在选举成功后， 领导人会管理整个集群直到任期结束。有时候选举会失败，那么这个任期就会以没有领导人而结束。任期之间的切换可以在不同的服务器上观察到。Raft保证了在一个给定的任期内，最多只有一个领导者。
• Raft算法中server节点之间通信使用远程过程调用(RPCs)，并且基本的一致性算法只需要两种类型的RPCs。请求投票RequestVote RPCs由候选人在选举期间发起，然后附件条目AppendEntries RPCs由领导人发起，用来复制日志和提供一种心跳机制。后面为了在server之间传输snapshot增加了第三种RPC。

二、领导人选举

2.1 触发选举

• Raft使用一种心跳机制来触发领导人选举。
• 当服务器程序启动时，他们都是Follower角色。一个server节点继续保持着Follower状态只要它从Leader或者Candidate处接收到有效的RPCs。Leader周期性的向所有Follower发送心跳包(其实就是不包含日志项内容的AppendEntries RPCs)来维持自己的领导权威。
• 如果一个Follower在一段时间内没有接收到任何消息，也就是发生了timeout，那么他就会认为系统中没有Leader，因此自己就会进入Candidate状态，并发起选举以选出新的Leader。

2.2 选举过程

• 要开始一次选举过程，Follower先要增加自己的current_term_id并转换到Candidate状态。然后它会并行的向集群中的其他服务器节点发送RequestVote RPC来给自己投票。Candidate会继续保持当前状态直到以下三种情况出现：

1. 自己赢得选举

• 当收到了大多数节点(majority)的选票后，角色状态会转换为Leader，之后会定期给其它所有server发心跳信息（不带log entry的AppendEntries RPC），用来告诉对方自己是当前term（RequestVote RPC附带的current_term_id）的Leader。
• 每个term最多只有一个Leader，term id作为logical clock，在每个RPC消息中都会带上，用于检测过期的消息。当一个server收到的RPC消息中的rpc_term_id比本地的current_term_id更大时，就更新current_term_id为rpc_term_id，并且如果当前节点的角色状态为Leader或者Candidate时，也会将自己的状态切换为Follower。如果rpc_term_id比接收节点本地的current_term_id更小，那么RPC消息就被会拒绝。

2. 别人赢得选举

• 当Candidate在等待投票的过程中，收到了rpc_term_id大于或者等于本地的current_term_id的AppendEntries RPC消息时，并且这个RPC消息声明自己是这个任期内的Leader。那么收到消息的节点将自己的角色状态转换为Follower，并且更新本地的current_term_id。

3. 无人赢得选举

• 第三种可能的结果是Candidate既没有赢得选举也没有输，本轮选举没有选出Leader，这说明投票被瓜分了。没有任何一个Candidate收到了majority的投票时，Leader就无法被选出。这种情况下，每个Candidate等待的投票的过程就出现timeout，随后Candidates都会将本地的current_term_id自增“1”，再次发起RequestVote RPC进行新一轮的leader election。

2.3 投票策略

• 每个节点只会对每个term_id中的一个RequestVote RPC进行相应，对每个投票请求是否进行投票需要根据日志长度比较来决定，和后续的Safety有关，除此之外就是对先来的请求投票。
• 当投票被瓜分后，所有的Candidate同时超时，然后有可能进入新一轮的票数被瓜分，为了避免这个问题，Raft采用一种很简单的方法：每个Candidate的election timeout从150ms-300ms之间随机取，那么第一个超时的Candidate就可以发起新一轮的leader election，带着最大的term_id给其它所有server发送RequestVote RPC消息，从而自己成为Leader。

三、日志复制

3.1 正常日志复制

• 当Leader被选出来后，就可以接受客户端发来的请求了，每个请求包含一条需要被replicated state machines执行的命令。Leader会把它作为一个log entry追加到日志中，然后给其它的server发AppendEntries RPC请求。
• 当Leader确定一个log entry被safely replicated了（即大多数节点已经将该命令写入日志），就apply这条log entry到状态机中然后返回结果给客户端。如果某个Follower宕机了或者运行的很慢，或者网络丢包了，则会一直给这个Follower发AppendEntries RPC直到日志一致。
• 当一条日志是commited时，Leader才可以将它应用到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的节点执行。

3.2 日志恢复

• 当一个新的Leader被选出来时，它的日志和其它的Follower的日志可能不一样，这个时候，就需要一个机制来保证日志的一致性。
• 新Leader产生后，就以Leader上的log为准（当然这里保证了新Leader包含了所有已经提交的日志，这是通过Safety保证的）。对于其他的Follower，缺失数据、多无效日志、即缺失有多无效日志都是可能的。我们需要一定的机制让所有的Follower的日志和Leader保持一致。
• Leader会为每个Follower维护一个nextIndex，表示Leader给各个Follower发送的下一条log entry在log中的index，初始化为Leader的最后一条log entry的下一个位置。Leader给Follower发送AppendEntries RPC消息，附带(term_id, nextIndex-1)，表明这个AppendEntries RPC中的log是哪个位置的日志。
• Follower接收到AppendEntries RPC后，会和自己的日志中对应位置的日志进行对比。如果不存在这样的log entry或者不相等，就给Leader回复拒绝消息，然后Leader则将nextIndex减“1”，再重复直到AppendEntries RPC消息被接收。

四、安全性

4.1 选举限制

• 为了达到选择出的Leader节点必须拥有所有已经提交的日志项的目的，Raft给出的方案是比较日志。如果Candidate的日志至少跟过半的服务器节点一样新，那么它就一定包含了所有已经提交的日志条目，一旦有Follower发现自己的日志比Candidate的还新，那么就会拒绝该投票请求，该Candidate也就不会赢得选举。这里对日志的“新”做一个定义:

  • 如果两份日志最后条目的任期号不同，那么任期号大的日志更新。
  • 如果两份日志最后条目的任期号相同，那么谁的日志更长，谁就更新。

• 通过比较日志的“新”选出的Leader一定拥有着一个大多数集群中最新的日志。一个日志只有被 成功添加到了大多数节点中才有可能被提交，而选举的限制保证了所选出的Leader拥有一个大多数集群中最新的日志，因此Leader一定包含了已提交的日志。尽管非大多数的节点也有可能拥有比Leader还“新”的日志，但是这部分日志是没有被提交过的，被删除掉并不会影响正确性。

4.2 日志提交限制

4.2.1 提交日志

• 关于日志提交的问题，我们通常认为只要某一条日志已经被集群的大多数节点所复制了，那就可以提交了。这里的提交包含两层意思：第一层是可以将提交的结果返回给上层应用；第二层是将提交的信息发送给Follower。
• 作者在设计Raft时为了尽可能使协议足够简单易懂，将很多消息发送都进行了合并和简化。所以Commit的消息只需要附带到下一次的AppendEntries RPCs（心跳包）就可以了，这避免了消息的冗余。
• 但是“大多数节点复制的日志就可以提交。” 的结论是存在漏洞的，冲突来源于Leader节点切换时对前面任期的日志进行提交的处理上。

4.2.2 经典问题分析

• Raft原文中给出了一个经典例子，将会以此为例分析Raft关于提交之前任期内的日志条目的解决方案：

• 在图(a)中，Leader节点为S1，任期为2。在 log index = 2 的日志还没有被添加到大多数节点日志中时开始了新一轮的任期。
• 在图(b)中，S5获得了S3和S4的投票当选Leader，任期为3。这时对于S5来说，其 log index = 2 的位置并没有日志项，所以其新添加的日志会被放着这个位置。但是因为一些意外S5只完成了对自己日志的更新便又开始了新一轮的任期。
• 在图(c)中，S1获得了S2和S3的投票当选Leader，任期为4。然后S1将复制它之前在任期2中放在log index = 2的日志项到其余的Follower中。这时那条日志已经被复制到过半的节点中了。
• 情况一：在图(d)中，由于S5最后的日志项的任期号大于S2、S3、S4，因此S5可以被成功选举为Leader，任期为5。S5在当选之后会将自己在log index = 2的日志项同步到Follower节点，如果在上一个任期中，S1将log index = 2的日志项提交了，就会造成已提交日志丢失的问题
• 情况二：在图(e)中，在任期4时，如果S1节点在自己的任期内复制了日志项到大多数机器上。那么到下一个任期S5就不可能成为Leader了，这种情况下通过提交任期4的日志，根据日志匹配特性也可以保证同时提交之前任期的日志。

4.2.3 日志提交方案

• 所以Raft关于前任期内的日志条目的提交方法已经呼之欲出了，Raft永远不会通过计算副本数目的方式来提交之前任期内的日志条目。
• 只有Leader当期内的日志条目才通过计算副本数目的方式来提交。一旦当前任期内的某个日志条目以这种方式被提交，那么由于日志匹配特性，之前的所有日志条目也会被间接地提交。

五、拓扑变更

5.1 问题分析

• 在实际场景中，我们会遇到很多改变集群节点数的情况，例如服务器故障需要移除副本、集群扩容增加副本等等。为了让所有成员在同一时刻都能获取到更新后的集群配置，选择集群停机后再更新配置是最简单的方案，但在一个致力于解决分布式可用性的容错系统中，用影响可用性的方式解决成员变更问题显然不可接受。
• 集群配置的变更本质上也是将一个消息同步到所有节点上，自然可以把配置当成 raft 中的日志，成员动态变更的需求就演化成了配置日志一致性问题。
• 但成员变更存在一个特殊性，集群成员的动态变更导致多数派的数量也随之变化。如果处理方式不当，可能会导致两个多数派（变更前的多数派 $C_{old}$（旧配置）和变更的多数派$C_{new}$（新配置））之间不存在相交的成员，这样就产生两个Leader在各自认为的“多数派”中工作的问题。

• 配置的变更显然是无法原子完成的，而变更配置需要一个过程。如上图所示，3 个节点的集群扩展到 5 个节点，在某个时刻只有3个节点变更配置完成，另外2个节点还处于原配置状态。这会造成 Server1 和 Server2 构成老成员配置的多数派，Server3、Server4 和 Server5 构成新成员配置的多数派。因为这两个多数派不存在相交的成员，所以有可能在一个日志索引上会提交两个不同的日志项，从而导致协议冲突，影响 Raft 的安全性。

• 原论文中提出了一种两阶段的成员变更方法 Joint Consensus（联合共识）。大致是维护一个变更中的状态，在这个状态中开展新的选举，已经获得新配置的节点需要同时获得 $C_{old}$和$C_{new}$中的大多数投票才能当选，中间状态完成后再转变成$C_{new}$的最终配置。这种方式实现起来很复杂。

• 后来提出一种更简单的方案 Single Server Changes（单成员变更），单成员变更的思路是既然同时提交多个会存在问题，那每次就提交一个成员变更，这样旧配置的“多数派”和新配置的多数派就始终会有一个节点重叠，这样就不存在不相交的问题了，如果有要添加多个成员，那就执行多次单成员变更。

5.2 联合共识

5.2.1 基本流程

• 配置变更为两阶段实现，第一阶段集群先从旧成员配置$C_{old}$切换到一个过渡成员配置$C_{old} \cup C_{new}$，这个中间状态被称为联合共识；第二阶段集群再从过渡成员配置切换到新成员配置$C_{new}$。Raft协议的两阶段成员变更过程如下：
  1. Leader收到成员变更请求从$C_{old}$切换成$C_{new}$；
  2. Leader在本地节点生成一个新的log entry，内容为$C_{old} \cup C_{new}$，代表当前时刻新旧拓扑配置共存，写入本地日志，同时将该log entry推送至其他Follower节点。在此之后新的日志同步需要保证得到$C_{old}$和$C_{new}$两个多数派的确认；
  3. Follower节点收到log entry后更新本地日志，并且此时就以该配置作为自己认知的全局拓扑结构；
  4. 如果$C_{old}$和$C_{new}$中的两个majority的Follower节点确认了$C_{old} \cup C_{new}$这条日志的时候，Leader就提交这条log entry；（注意这里要求的是两个大多数集合都确认收到日志，这里应该是保证不会出现两个Leader的关键）
  5. 随后Leader会生成一条新的log entry，内容是全新的成员配置$C_{new}$，同样将这条log entry写入本地节点日志，并同时推送到其他Follower节点上；
  6. Follower收到新的配置日志$C_{new}$后，将其写入日志，并且从当前时刻起，将$C_{new}$作为系统成员拓扑结构，并且如果发现自己不在$C_{new}$这个配置中会自动退出；
  7. Leader收到majority的Follower节点的确认消息后，给客户端发起命令执行成功的消息。后续的日志只要得到$C_{new}$多数派的确认即可。

5.2.2 安全性分析

• 首先需要明确，集群的配置更新过程会出现问题的核心是会在某一时刻存在两个majority，因此如果这时候发生选举，可能造成出现两个Leader的情况，会严重影响分布式集群的安全性。

为什么会出现两个合法的majority？

• 集群在变更过程中节点存在两种配置状态，即一部分节点为$C_{old}$状态，另一部分的节点为$C_{new}$。只要$C_{old}$中的少部分节点完成变更，并与新添加的节点可以构成$C_{new}$的majority，那么就可以同时存在两个合法的大多数集合了。
• 这里有两个破局点，一个是不让部分配置变更完成的节点能够成为合法的majority，方案就是添加联合共识的中间的态，对中间态节点达成共识添加更多的限制；还有一个是让新增节点不能与$C_{old}$中的少部分节点构成$C_{new}$​的majority，其实只要控制每次变更的节点数量就可以了，即下一节的单成员变更方案。

联合共识的中间的态是什么？

• 中间态或者过渡态即为$C_{old} \cup C_{new}$，处于这种配置的节点在选举或者提交数据时需要同时获得$C_{old}$和$C_{new}$两个majority的认可。先说选举上的问题，无论是$C_{old}$还是$C_{old} \cup C_{new}$配置的节点，想要成功当选Leader都是需要得到$C_{old}$的majority的投票，所以便避免出现两个leader了。
• 第二步是将$C_{old} \cup C_{new}$配置同步到Follower的日志中，并且得到大多数节点的回复后提交这条消息，然后开启下一阶段对$C_{new}$配置的同步。这里有一个细节，因为Leader节点必然是$C_{old} \cup C_{new}$配置，所以想要提交这个配置需要等待$C_{old}$和$C_{new}$两个majority的认可。这意味着提交$C_{old} \cup C_{new}$时，原$C_{old}$中的大多数节点必然已经进入中间态了，那么这时$C_{old}$配置的节点必然不可能当选新Leader了。
• 我们来考虑一下如果没有这条提交消息的限制会怎样。有[server1, server2, server3]三个原节点，然后添加两个新节点[server4, server5]。然后[server3, server4, server5]进入$C_{old} \cup C_{new}$配置，并且完成提交。这时候开始同步$C_{new}$配置，并且[server3, server4, server5]进入$C_{new}$，但是[server1, server2]依然保持在$C_{old}$，这是就可能出现$C_{old}$和$C_{new}$​两个majority形成的两个Leader节点了。

5.2.3 异常处理

追赶日志

• 新的服务器节点在初始化时没有存储任何的日志条目。当这些服务器节点以这种状态加入集群中，那么这些新加入的节点需要一定的时间来追赶日志，这段时间内还无法接收新的日志条目。
• 为了避免这种可用性的间隔时间，Raft在成员变更的时候使用了一种额外的阶段，在这个阶段，新的服务器节点以没有投票权的身份加入到集群中(Leader会复制日志给他们，但是不考虑他们是大多数)。一旦新的服务器节点追赶上了集群中的其他机器，就可以按照上面描述的做成员配置变更。

删除Leader节点

• 集群的Leader不是$C_{new}$中的一员。在这种情况下，Leader会在提交了$C_{new}$日志之后退出，回到Follower状态。因此会有一段时间Leader管理着集群，但是并不在集群成员范围内。Leader复制日志但是不把他自己算作大多数之一。当$C_{new}$被提交之后，会发生Leader过渡，因为$C_{new}$提交之后，最新的集群成员配置就可以正常独立工作了，此时会在$C_{new}$范围内选出新的Leader。在此之前，Leader都是从$C_{new}$范围内选举Leader。

5.3 单成员变更

5.3.1 安全分析

• 配置变更的思路是相同的，通过日志提交的方式利用自身的共识机制实现配置的变更。但单成员的变更就不需要添加额外的限制了，上图给出了奇偶节点数新增和减少一个节点时候的四种情况，可以发现必然是存在交集的。
• 这里一定要注意新增或者被删除的那个节点是知道变更之后的配置情况的（不存在形成两个$C_{old}$的majority的情况），因此要同时形成$C_{old}$和$C_{new}$​两个majority的节点数量一定会超过集群节点总数，所以单节点的变更是绝对安全的。

5.3.2 连续变更

连续增加

• 如果对于一个节点数量为3的集群，我们想要新增两个节点，第一步按照要求进行配置变更日志的共识和提交，此时集群可能会变为[server1, server2, server4]进入$C_{new}$，[server3]保持$C_{old}$；第二步是继续新增节点，而时机上只要上一条变更配置的日志被提交就可以立刻开始下一条配置变更的共识。
• 此时新进入的[server5]是具有最新配置的，那么可以组成大多数集[server1, server2, server5]。此时剩余的[server3, server4]前者停留在3节点，后者停留在4节点，因为[server4]是已经提交第一轮配置变更的节点，因而他一定能在两者的选举中胜出。此时的[server3, server4]则不可能可以形成majority。

连续删除

• 连续删除是类似的道理，对于原来节点数量为5的集群[server1, server2, server3, server4, server5]，我们希望删除两个节点[server1, server2]，第一步是[server3, server4, server5]三个节点达成共识，要删除[server1]，此时的[server1]因为暂时丢失没有被真正删除。
• 然后开始继续删除[server2]，如果[server4, server5]完成了删除操作，那么接下来发生选举时这两个节点自己就能形成majority。剩下的[server1, server2, server3]分别认为集群中还存在5，5，4个节点，那么剩下的这三个节点就能形成大多数集吗？
• 要注意[server3]是有第一次的删除记录的，所以首先他会有选举的优先权，而他是知道[server1]在第一轮被删除过的，所以即使这里有三个节点，依然是不能形成majority的。

增删混合

• 当想要替换某个节点的时候可能会发生这种场景，考虑3节点的集群替换其中的一个节点。如果是先删除后新增，场景分析和连续删除非常相似；如果是先新增后删除，场景分析和连续新增非常相似。
• 个人理解，单节点变更的方法其实就是利用将配置变更拆成多次进行提交，而这些中间的提交状态其实就是多节点变更的联合共识状态，只不过实现起来简单了很多。