共识算法 Raft

简介

  Raft是分布式系统中最经典且最为易理解的共识算法，共识指分布的多个参与者就值"value"达成一致。一旦参与者对某个值做出决定，这个决定将是最终的。当大多数参与者存活时，共识算法会在存活的参与者间达成值一致，这相当于全部参与者存活时达成的一致。故部分参与者达成的一致是整个系统有效的，这一特性使得分布式系统具备一定的容错能力。

算法基础

Raft算法角色

1. leader：领导者，其负责和客户端通信，接收来自客户端的命令并将其转发给follower
2. follower：跟随者，其一丝不苟的执行来自leader的命令
3. candidate：候选者，当follower长时间没收到 leader的消息就会揭竿而起成为候选者，抢夺成为leader的资格

  共识算法通常出现在复制状态机(Replicated State Machine, RSM) 上下文中，而复制状态机是构建容错系统的常规方法。一个分布式系统的复制状态机有多个复制单元组成，每个复制单元均有一个状态机，该状态机的状态保存在状态变量中，这些变量只能通过外部命令被改变。备机状态机在日志指令的驱动下，严格按照要求逐条执行日志中的指令。假定所有的状态都能按照相同的日志执行指令，则它们最终能达到相同的状态，这就能保证分布式系统状态的一致性。Raft算法明确定义复制状态机，将共识问题分为如下3个部分
4. Leader 选举 (Leader Election)：旧Leader故障时系统初始化首次需选主时，选出一个新的leader.
5. 日志复制 ( Log Replication) : Leader 接受来自客户端的命令或者操作指令，会将其转换成日志，然后复制给集群中其他服务器（即 Follower角色所在备机），通过在备机执行日志，使得备机的从副本和主Leader的主副本保持一致。日志复制依赖于复制状态机[如图]。
6. 安全措施 (Safety measures) : 通过一些措施确保系统的安全性。如确保所有状态机按照相同顺序执行相同命令，即Leader 将某个特定索引的日志条目交由主机的状态机处理，此时对于其他备机，交由备机状态机处理的日志需要具备相同索引的日志条目。

  上图讲解：①为客户端发送执行令给服务器，②为服务器通过共识模块将日志发送给每个备机的复制状态机，每个复制状态机的复制日志中指令的顺序都是相同的，③为复制状态机按序处理复制日志中的指令，④为将处理结果返回给客户端。由于复制状态机具有确定性，因此每个状态机的输入和输出都是相同的，因此能够保证一致性。

Raft算法详解

  Raft算法中要一个强Leader,在无分布式系统异常(如节点宕机的情况)，该Leader负责接受客户端的请求命令，并将请求命令作为日志通过Raft算法的日志复制功能传输给Fellower，Fellower确认日志安全后(大多数从副本将该命令写入日志中，可未完成执行操作)，Fellower将日志命令提交到本机的复制状态机执行，即上述为一个正常操作过程。但是分布式系统会存在如下问题，包括：

1. Leader故障

Leader出现故障时，需要通过集群选举产生一个新的Leader,该过程如所示：

确定Leader出现故障：依赖于心跳机制。如果Fellower节点在一定时间内未收到Leader发送的心跳信息（定期心跳信息包括不带日志的AppendEntriesRPC)，则认为Leader出现故障。所以和Leader存活有关的心跳时长，即Leader租约的长短时影响系统处理故障时长的一个因素。心跳时间不能太长(长了则不能今早的发现故障)，也不能太短（太短会频发触发选Leader的操作）从而影响效率。

Leader选举过程
Raft采用心跳机制触发Leader选举。当系统启动时，所有节点初始化为Follower状态，设置任期为0，并启动计时器，计时器超时后，Follower节点转化为Candidate节点，一旦转化为Candidate节点，立即开始做以下几件事情：

（1）增加自己的任期数
（2）启动一个新的计时器
（3）给自己投一票
（4）向所有其他节点发送RequestVote RPC请求，并等待其他节点回复。

如果在计时器超时前接收到多数节点的同意投票，则转换为Leader。如果接受到其他节点的AppendEntries心跳RPC，说明其他节点已经被选为Leader, 则转换为Follower。如果计时器超时的时候还没有接受到以上两种信息中的任何一种，则重复步骤1-4，进行新的选举。

节点在接受到多数节点的投票成为Leader后，会立即向所有节点发送AppendEntries 心跳RPC。所有Candidate收到心跳RPC后，转换为Follower，选举结束。

每个Follower在一个任期内只能投一票，采取先到先得的策略。每个Follower有一个计时器，在计时器超时时仍然没有接受到来自Leader的心跳RPC, 则转换为Candidate, 开始请求投票。也就是在当期Leader当掉后，就会有Follower开始转换为Candidate开始投票。

如果多个节点同时发起投票，每个节点都没有拿到多数票（这种情况成为Split Vote），则增加任期数，在新的任期内重新进行投票。有没有可能Split Vote反复发生，永远都选不出Leader呢？不会的。因为Raft采取随机超时时间，Raft系统有一个选举超时配置项，Follower和Candidate的计时器超时时间每次重新计算，随机选取配置时间的1倍到2倍之间。即使所有节点同时启动，由于随机超时时间的设置，各个节点一般不会同时转为Candidate，先转为Candidate的节点会先发起投票，从而获得多数票。因而在每个任期内，多个节点同时请求投票并且都只获得少数票的几率很小，连续多次发生这种情况几率更小，实际上可以认为完全不可能发生。一般情况下，基本上都在1-2个任期内选出Leader。

任期的理解
Raft把时间分为连续的任期(Term)，每个任期可以是任意时长，任期用连续的整数进行标号。每个任期首先进行Leader选举，选举时，多个Candidate竞争成为Leader,一旦某个节点成为Leader，其他节点则变回Follower，成为Leader的节点将在该任期内一直担任Leader，如果该Leader节点发生故障，其他节点会在新的任期内进行选举。任何一个任期内都不会有多个Leader。Raft系统中，任期是一个及其重要的概念，每个节点都维护着当前任期的值，每次节点间的通信都包含任期信息，每个节点在检测到自己的任期值低于其他节点，都会更新自己的任期值，设置为检测到的较高的值。当Leader和Candidate发现自己的任期低于别的节点，则立即把自己转换为Follower。

注意：任期与计时器是绑定到一起的。任何新任期的启动，必然伴随一个新计时器的启动。

Raft RPC简介
通过上面的内容我们可以得知，Raft核心部分只需要用到2个RPC：RequestVote和AppendEntries。每个Raft节点将会根据自己节点的状态数据来对这两种RPC请求进行处理。

RequestVote RPC是由Candidate发送给其他节点，请求其他节点为自己投票，如果一个Candidate获得了多数节点的投票，则该Candidate转变为Leader。

AppendEntries RPC是由Leader节点发送给其他节点，有两个作用，当其entries域为空时，该RPC作为Leader的心跳；当entries域不为空时，请求其他节点将entries域中的日志添加到自己的日志中。

Raft日志复制

1、日志复制的过程
Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行地向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

客户端的每一个请求都包含被复制状态机执行的指令。Leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让它们复制这条信息。假如这条日志被安全的复制，Leader就应用这条日志到自己的状态机中，并返回给客户端。如果Follower宕机或者运行缓慢或者丢包，Leader会不断的重试，直到所有的Follower最终都复制了所有的日志条目。

2、日志的组成
日志由有序编号（log index）的日志条目所组成。每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了,如下图所示，共有 8 条日志，提交了 7 条。提交的日志都将通过状态机持久化到磁盘中，防止宕机。

3、日志复制的详细介绍
当Leader接收到由客户端发送的请求(请求中包含可以被复制状态机执行的命令)时，Leader将会把该请求作为新的内容添加到日志中(任期号为当前Leader所处的任期号，索引号为当前Leader本地存储的日志集合中的日志的最高索引号加1)。然后将该日志通过AppendEntries RPC消息发送到网络中其他的服务器(以下简称Follower)，从而复制该日志。在网络中Follower接收到该日志消息后则会返回复制成功的回复。

在Leader接收到网络中大部分的Follower的成功复制的回复之后，Leader便认为该日志可以被提交。此时Leader将会同时做三件事：

（1）将该日志应用到Leader本地的复制状态机
（2）向所有Follower发送消息通知所有接收到该日志的Follower将该日志进行提交，然后应用到各自本地的复制状态机
（3）将执行结果通知客户端

当该日志消息成功在网络中大部分Follower本地的复制状态机执行过后，则可认为该日志已被提交。在当前日志被提交的过程中，如果Leader先前的某些日志还没有被提交，则将会一同提交。而网络中有些Follower可能由于网络状态原因反应缓慢或者崩溃，那么Leader将会无限次地尝试重复发送AppendEntries RPC消息到该Follower。直到成功为止。

4、Leader切换导致日志的不一致性

5、日志的一致性检查
如上所述，Follower在接收到AppendEntries RPC消息后则会返回复制成功的回复。实际上在接收到消息后会首先进行日志的一致性检查(正常情况下Leader与Follower的日志会保持一致，所以一致性检查不会失败)，一致性检查内容如下：

在Leader创建AppendEntries RPC消息时，消息中将会包含当前日志之前日志条目的任期号与索引号。Follower在接受到AppendEntries RPC消息后，将会检查之前日志的任期号与索引号是否匹配到。如果匹配则说明和Leader之前的日志是保持一致的，否则，如果没有匹配则会拒绝AppendEntries RPC消息。

一致性检查是一个归纳的过程。正常情况下，网络中第一条日志一定满足日志的一致性检查，然后第二条日志中包含第一条日志的任期号与索引号，所以只要Leader与Follower的第一条日志保持一致，那么第二条日志也会满足一致性检查，从而之后的每一条日志都会满足一致性检查。

从而得出了日志匹配属性:

（1）如果两个不同的日志实体具有相同的索引和任期号，那么它们存储有相同的命令。
（2）如果两个不同的日志实体具有相同的索引和任期号，则所有先前条目中的日志都相同。(由一致性检查结果得出)

Raft日志不一致的解决方案

1、日志不一致的三种情况
网络不可能一直处于正常情况，因为Leader或者某个Follower有可能会崩溃，从而导致日志不能一直保持一致，因此存在以下三种情况：

（1）Follower缺失当前Leader上存在的日志条目。
（2）Follower存在当前Leader不存在的日志条目。
（3）Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。

比如，旧的Leader仅仅将AppendEntries RPC消息发送到一部分Follower就崩溃掉，然后新当选Leader的服务器恰好是没有收到该AppendEntries RPC消息的服务器)

备注：
（1）图中最上方是日志的索引号(1-12)，每个方块代表一条日志信息，方块内数字代表该日志所处的任期号。
（2）图中当前Leader(图中最上方一行日志代表当前Leader日志)处于任期号为8的时刻。

分析说明
下面，以此图分析说明以上三种情况存在的原因：

（1）Follower a、Follower b满足以上说明的第一种情况：Follower崩溃没有接收到Leader发送的AppendEntries RPC消息。

（2）Follower c在任期为6的时刻，Follower d在任期为7的时刻为Leader，但没有完全完成日志的发送便崩溃了，满足以上说明的第二种情况：Follower存在当前Leader不存在的日志条目。

（3）Follower e在任期为4的时刻，Follower f在任期为2、3的时刻为Leader，但没有完全完成日志的发送便崩溃了，同时在其他服务器当选Leader时刻也没有接收到新的Leader发送的AppendEntries RPC消息，满足第三种情况：Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。

如上文所示，根据日志的任期数目来判断节点是否为Leader，再次印证了任期的关键作用。

2、日志不一致的解决方案
Leader通过强迫Follower的日志重复自己的日志来处理不一致之处，这意味着Follower日志中的冲突日志将被Leader日志中的条目覆盖。这个过程如下：

1. 首先，Leader找到与Follower最开始日志发生冲突的位置，然后删除掉Follower上所有与Leader发生冲突的日志，最后将自己的日志发送给Follower以解决冲突。需要注意的是：Leader不会删除或覆盖自己本地的日志条目。

2. 当发生日志冲突时，Follower将会拒绝由Leader发送的AppendEntries RPC消息，并返回一个响应消息告知Leader日志发生了冲突。

3. Leader为每一个Follower维护一个nextIndex值。该值用于确定需要发送给该Follower的下一条日志的位置索引。该值在当前服务器成功当选Leader后会重置为本地日志的最后一条索引号+1。

4. 当Leader了解到日志发生冲突之后，便递减nextIndex值，并重新发送AppendEntries RPC到该Follower，不断重复这个过程，一直到Follower接受该消息。

5. 一旦Follower接受了AppendEntries RPC消息，Leader则根据nextIndex值可以确定发生冲突的位置，从而强迫Follower的日志重复自己的日志以解决冲突问题。
   
   情况a：如上图，服务器S1在任期为2的时刻仅将日志index:2:2,term发送到了服务器S2便崩溃掉。

情况b：服务器S5在任期为3的时刻当选Leader(S5的计时器率先超时，递增任期号为3，高于服务器S3和S4，因此可以当选Leader)，但没来得及发送日志便崩溃掉。

情况c：服务器S1在任期为4的时刻再次当选Leader(S1重启时，任期仍然为2，收到新的Leader S5发送的心跳信息后更新任期为3，而在Leader S5崩溃后，服务器S1为第一个计时器超时的，因此发起投票，任期更新为4，大于网络中其他服务器任期，成功当选Leader)，同时将日志index:2:2,term发送到了服务器S2和S3，但还没有通知服务器对日志进行提交便崩溃掉。

情况d：情况(a->d)如果在任期为2时服务器S1作为Leader崩溃掉，S5在任期为3的时刻当选Leader，由于日志index:2:2,term还没有被复制到大部分服务器上，并没有被提交，所以S5可以通过自己的日志index:2:3,term覆盖掉日志index:2:2,term。

情况e：情况(a->e)如果在任期为2时服务器S1作为Leader，并将index:2:2,term发送到S2和S3，成功复制到大多数成员服务器上。S1成功提交了该日志，那么即便S1崩溃掉，S5也无法成功当选Leader，因为S5不具备网络中最新的已被提交的日志条目，S5只有term为1的日志。

Raft算法中成员变更过程解析

1、什么是成员变更？
成员变更指的是系统成员变化，即服务器节点的上下线，这和由于宕机故障导致的上下线是不同的。宕机或者重启导致的上下线，是不会影响系统的注册的成员数量的，也就不会影响到一致性判断所依据的“多数派”的生成，众所周知，“多数派”是所有一致性的基础。成员变更时，会修改注册的成员数量，比如在实际应用中，为了提高安全等级，就很可能出现需要把备机数量由三台扩充到五台，在这种情况下，就发生了成员变更。

2、直接变更存在的问题
在成员变更时，因为无法做到在同一个时刻使所有的节点从旧配置转换到新配置，那么直接从就配置向新配置切换就可能存在一个节点同时满足新旧配置的“超过半数”原则。

如下图，原集群由Server1、Server2、Server3，现在对集群做变更，增加Server4、Server5。如果采用直接从旧配置到新配置的切换，那么有一段时间存在两个不想交的“超过半数的集群”。

上图，中在中间位置Server1可以通过自身和Server2的选票成为Leader（满足旧配置下收到大多数选票的原则）；Server3可以通过自身和Server4、Server5的选票成为Leader（满足新配置线，即集群有5个节点的情况下的收到大多数选票的原则）；此时整个集群可能在同一任期中出现了两个Leader，这和协议是违背的。

3、Raft的成员变更实现方案：分阶段变更
Raft提出了通过一个中间过渡阶段，即联合共识（joint consensus），逐步把数据写入的新的集群中。其具体做法是2阶段提交式的：

第一阶段：Leader收到C-old到C-new的配置变更请求时，创建C-old-new的日志并开始复制给其他节点，此日志和普通日志复制没有区别。此时做决策的仍然是C-old集群。

第二阶段：当只有C-old-new复制到大多数节点后，Leader以这个配置做决定，这个时候处于一个共同决定的过程，因为此时做决策的是C-old-new集群。

由于两阶段变更不存在一个阶段C-old和C-new可以同时根据自己的配置做出决定，所以不会出现上文描述的情况。

备注：虽然自己是Leader，但是做决策的可不是Leader，它要根据多数派的原则进行拍板定方案，
所以归根结底，做决策的还是集群中的其他Follower成员。
1
2

参考：https://raft.github.io/