# 分布式架构学习(五)-一致性算法Raft
[TOC]
## Raft算法
Raft 是一种为了管理复制日志的一致性算法。
Raft实现了和Paxos相同的功能,它将一致性分解为多个子问题:Leader选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等。同时,Raft算法使用了更强的假设来减少了需要考虑的状态,使之变的易于理解和实现。
### Raft中的角色
Raft将系统中的角色分为领导者(Leader)、跟从者(Follower)和候选人(Candidate):
- **Leader**:接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。
- **Follower**:接受并持久化Leader同步的日志,在Leader告之日志可以提交之后,提交日志。
- **Candidate**:Leader选举过程中的临时角色。
影响Raft中的角色变化的动作是**选举**

Raft使用心跳机制来触发选举。当server启动时,初始状态都是follower。每一个server都有一个定时器,超时时
间为election timeout(一般为150-300ms),如果某server没有超时的情况下收到来自领导者或者候选者的任何
消息,定时器重启,如果超时,它就开始一次选举,每次触发选举之后,对应的任期相应+1
动画演示Raft算法全过程:http://thesecretlivesofdata.com/raft/
### Raft算法过程
- 初始状态,各个任期都为1

- 某一时刻,其中的一个 follower 由于没有收到 leader 的 heartbeat 率先发生 election timeout 进而发起选举,此时将对应节点任期改为2

- 只要集群中超过半数的节点接受投票,candidate 节点将成为即切换 leader 状态,并将其他Follower节点任期改为2。

- 成为 leader 节点之后,leader 将定时向 follower 节点同步日志并发送 heartbeat。

### Raft运行过程中出现异常情况处理
集群中各个节点的状态随时都有可能发生变化。从实际的变化上来分类的话,节点的异常大致可以分为四种类型:
- leader不可用
- follower不可用
- 多个candidate或者多个leader
- 新节点加入集群
#### leader不可用情况处理
- 一般情况下,leader 节点定时发送 heartbeat 到 follower 节点。

- 由于某些异常导致 leader 不再发送 heartbeat ,或 follower 无法收到 heartbeat 。

- 此时当某一 follower 率先发生 election timeout 时,其状态变更为 candidate,并向其他 follower 发起投票。

- 当超过半数的 follower 接受投票后,这一节点将成为新的 leader,leader 的步进数加 1 并开始向 follower 同
步日志。

- 当一段时间之后,如果之前的 leader 再次加入集群,则两个 leader 比较彼此的任期,任期低的 leader 将切换自己的状态为 follower。

- 较早前 leader 中不一致的日志将被清除,并与现有 leader 中的日志保持一致。

#### follower 节点不可用
follower 节点不可用的情况相对容易解决。因为集群中的日志内容始终是从 leader 节点同步的,只要这一节点再次加入集群时重新从 leader 节点处复制日志即可。
- 集群中的某个 follower 节点发生异常,不再同步日志以及接收 heartbeat。

- 经过一段时间之后,原来的 follower 节点重新加入集群。

- 这一节点的日志将从当时的 leader 处同步。

#### 多个 candidate 或多个 leader
在集群中出现多个 candidate 或多个 leader 通常是由于数据传输不畅造成的。出现多个 leader 的情况相对少见,但多个 candidate 比较容易出现在集群节点启动初期尚未选出 leader 的“混沌”时期。
- 初始状态下集群中的所有节点都处于 follower 状态。

- 两个节点同时成为 candidate 发起选举。

- 两个 candidate 都只得到了少部分 follower 的接受投票,此处两个节点都是一人两票

- candidate 继续向其他的 follower 询问。

- 由于一些 follower 已经投过票了,所以均返回拒绝接受。

- candidate 也可能向一个 candidate 询问投票。

- 在步进数相同的情况下,candidate 将拒绝接受另一个 candidate 的请求。

- 由于第一次未选出 leader,candidate 将随机选择一个等待间隔(150ms ~ 300ms)再次发起投票。

- 如果得到集群中半数以上的 follower 的接受,这一 candidate 将成为 leader。

- 稍后另一个 candidate 也将再次发起投票。

- 由于集群中已经选出 leader,candidate 将收到拒绝接受的投票。

- 在被多数节点拒绝之后,并已知集群中已存在 leader 后,这一 candidate 节点将终止投票请求、切换为
follower,从 leader 节点同步日志。

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

4 个步骤:
- 客户端的每一个请求都包含被复制状态机执行的指令。
- leader把这个指令作为一条新的日志条目添加到日志中,然后并行发起 RPC 给其他的服务器,让他们复制这
条信息。
- 跟随者响应ACK,如果 follower 宕机或者运行缓慢或者丢包,leader会不断的重试,直到所有的 follower 最终
都复制了所有的日志条目。
- 通知所有的Follower提交日志,同时领导人提交这条日志到自己的状态机中,并返回给客户端。
可以看到,直到第四步骤,整个事务才会达成。中间任何一个步骤发生故障,都不会影响日志一致性。
日志由有序编号(log index)的日志条目组成。每个日志条目包含它被创建时的任期号(term),和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上,就被认为可以提交(commit)了。

Raft日志同步保证如下两点:
- 如果不同日志中的两个条目有着相同的索引和任期号,则它们所存储的命令是相同的。
- 如果不同日志中的两个条目有着相同的索引和任期号,则它们之前的所有条目都是完全一样的。
第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目,同时该条目在日志中的位置也从来不会改变。
第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时,Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志,它就会拒绝新的日志条目。
一般情况下,Leader和Followers的日志保持一致,因此 AppendEntries 一致性检查通常不会失败。然而,Leader崩溃可能会导致日志不一致:**旧的Leader可能没有完全复制完日志中的所有条目。**

上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目,也有可能包含一些Leader没有的条目,也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。
Leader通过**强制Followers复制它的日志**来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。
Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。
Leader会从后往前试,每次AppendEntries失败后尝试前一个日志条目,直到成功找到每个Follower的日志一致位点,然后向后逐条覆盖Followers在该位置之后的条目。
### Raft的安全性
Raft增加了如下两条限制以保证安全性:
- 拥有最新的已提交的log entry的Follower才有资格成为Leader。
这个保证是在RequestVote RPC中做的,Candidate在发送RequestVote RPC时,要带上自己的最后一条日志的term和log index,其他节点收到消息时,如果发现自己的日志比请求中携带的更新,则拒绝投票。日志比较的原则是,如果本地的最后一条log entry的term更大,则term大的更新,如果term一样大,则log index更大的更新。
- Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志,旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。
之所以要这样,是因为可能会出现已提交的日志又被覆盖的情况:

在阶段a,term为2,S1是Leader,且S1写入日志(term, index)为(2, 2),并且日志被同步写入了S2;
在阶段b,S1离线,触发一次新的选主,此时S5被选为新的Leader,此时系统term为3,且写入了日志(term, index)为(3, 2);
S5尚未将日志推送到Followers就离线了,进而触发了一次新的选主,而之前离线的S1经过重新上线后被选中变成Leader,此时系统term为4,此时S1会将自己的日志同步到Followers,按照上图就是将日志(2, 2)同步到了S3,而此时由于该日志已经被同步到了多数节点(S1, S2, S3),因此,此时日志(2,2)可以被提交了。;
在阶段d,S1又下线了,触发一次选主,而S5有可能被选为新的Leader(这是因为S5可以满足作为主的一切条件:1. term = 5 > 4,2. 最新的日志为(3,2),比大多数节点(如S2/S3/S4的日志都新),然后S5会将自己的日志更新到Followers,于是S2、S3中已经被提交的日志(2,2)被截断了。
增加上述限制后,即使日志(2,2)已经被大多数节点(S1、S2、S3)确认了,但是它不能被提交,因为它是来自之前term(2)的日志,直到S1在当前term(4)产生的日志(4, 4)被大多数Followers确认,S1方可提交日志(4,4)这条日志,当然,根据Raft定义,(4,4)之前的所有日志也会被提交。此时即使S1再下线,重新选主时S5不可能成为Leader,因为它没有包含大多数节点已经拥有的日志(4,4)。
### Raft与Multi-Paxos的异同
Raft与Multi-Paxos中相似的概念:

Raft与Multi-Paxos的不同:

## 参考
[Raft算法详解](https://zhuanlan.zhihu.com/p/32052223)
[动画演示Raft算法全过程](http://thesecretlivesofdata.com/raft/)
[寻找一种易于理解的一致性算法](https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md)
[The Raft Consensus Algorithm](https://raft.github.io/)
分布式架构学习(五)-一致性算法Raft