分布式架构学习(五)-一致性算法Raft

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）了。

v2-ee29a89e4eb63468e142bb6103dbe4de_720w

Raft日志同步保证如下两点：

如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader和Followers的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。

v2-d36c587901391cae50788061f568d24f_720w

上图阐述了一些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的日志被间接提交）。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况：

v2-12a5ebab63781f9ec49e14e331775537_720w

在阶段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）。