# 分布式架构学习(五)-一致性算法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/)