Raft共识算法

一、简介

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

更多细节可以阅读Raft官网文档：https://raft.github.io/

在讲解Raft算法的选举和故障转移过程之前，我们先引入Raft算法中的一些基本概念：

Follower

Follower是请求的被动更新者，主要职责是从Leader接收更新请求，再将日志写入本地文件中。
Candidate

Leader选举中的候选者。如果Follower在一定的时间内，没有收到Leader的心跳，则判断Leader可能已经发生故障，此时启动Leader Election过程，本节点切换为Candidate参与Leader的竞选，直到选举结束。
Leader

所有请求的处理者，接收客户端发起的操作请求，写入本地日志后，同步至其他Follower节点。
Term

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域中的日志添加到自己的日志中。

二、Leader选举和Failover过程

1、Leader的选举过程

Raft采用心跳机制来触发Leader的选举。当系统启动时，所有的节点转化为Follower状态，设置任期（term）为0，并启动计时器（election timeout，即选举的超时时间），在超时时间内如果没有收到Leader节点的心跳，就会发起新一轮的选举，此时节点会从Follower转换为Candidate，而一旦转变为Candidate节点，就会做以下几件事情：

增加自己的term任期数
启动一个新的election timeout计时器
给自己投一票
向集群中的每一个节点发送RequestVote RPC请求，并等待其他节点回复

如果在新的计时器超时前收到多数节点（集群节点个数的一半）的同意投票，则转换为Leader。如果接收到的是其他节点的AppendEntries心跳RPC，说明其他节点早先与自己被选为Leader，则转换为Follower，同时将自己的任期更新为检测到的最高值。如果计时器超时的时候还没有接收到以上两种信息中的任何一种，则重复1-4步骤，进行新的选举。

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

每个Follower在一个任期内只能投一票，采取先到先得的策略。每个Follower有一个计时器，在计时器超时时仍然没有接受到来自Leader的心跳RPC，那说明Leader可能宕机或者是其他原因，则转换为Candidate，开始请求投票。

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

这里我们再细讲一下Leader的投票规则：

投票是一个first-come-first-serve的机制，即谁先找我我就给谁投票。我们想确保新的Leader在赢得选举的时候有所有已经提交（commit）的entry，因为这样就不需要向新Leader同步它不知道的已经同步信息。这就意味着所有entry只会向一个方向传递：从Leader到Follower。并且Leader也不会重写log里面已经存在的entry。
因此，当Candidate的log包含了所有已经提交的entry时，它才能赢得选举。为实现这点，Candidate需要获得集群中的大多数（超过集群server个数的一半）server的确认，当Candidate的log至少是“最新的”（up-to-date）时，则说明它的log中有所有的已经提交的entry。
因此，当投票者发现自己的log比Candidate的都新时，就会拒绝给该Candidate投票。
“最新的”（up-to-date）定义：当Candidate发起RequestVote的RPC时，会包括上个log entry的index和term信息。投票者比较自己和Candidate的index和term，当term不同时，term越高则为越新；当term相同时，index越高则为越新。（lastTerm_v > lastTerm_c) || (lastTerm_v > lastTerm_c) && (lastIndex_v > lastIndex_c)

2、Leader的Failover故障转移

Leader出现故障时，需要通过集群选举产生一个新的Leader。那怎么知道Leader是否出现了故障呢？这个我们其实在上面讲过了，Raft核心部分只需要用到2个RPC：RequestVote和AppendEntries。每个Raft节点将会根据自己节点的状态数据来对这两种RPC请求进行处理。当Candidate选举成Leader后，他会通过发送AppendEntries RPC请求，向其他节点推送持续的心跳。

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

三、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将会同时做三件事：

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

当该日志消息成功在网络中大部分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的第一条日志保持一致，那么第二条日志也会满足一致性检查，从而之后的每一条日志都会满足一致性检查。

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

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

6、Raft日志不一致的解决方案

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

Follower缺失当前Leader上存在的日志条目。
Follower存在当前Leader不存在的日志条目。
Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。

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

备注：

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

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

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

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

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

首先，Leader找到与Follower最开始日志发生冲突的位置，然后删除掉Follower上所有与Leader发生冲突的日志，最后将自己的日志发送给Follower以解决冲突。需要注意的是：Leader不会删除或覆盖自己本地的日志条目。
当发生日志冲突时，Follower将会拒绝由Leader发送的AppendEntries RPC消息，并返回一个响应消息告知Leader日志发生了冲突。
Leader为每一个Follower维护一个nextIndex值。该值用于确定需要发送给该Follower的下一条日志的位置索引。该值在当前服务器成功当选Leader后会重置为本地日志的最后一条索引号+1。
当Leader了解到日志发生冲突之后，便递减nextIndex值，并重新发送AppendEntries RPC到该Follower，不断重复这个过程，一直到Follower接受该消息。
一旦Follower接受了AppendEntries RPC消息，Leader则根据nextIndex值可以确定发生冲突的位置，从而强迫Follower的日志重复自己的日志以解决冲突问题。

情况a：如上图，服务器S1在任期为2的时刻仅将日志index:2:2,term发送到了服务器S2便崩溃掉。

情况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，这和协议是违背的。