分布式一致性协议之Raft（一）

  Raft算法解决的核心问题是在分布式环境下如何保持集群状态的一致性，简而言之就是一组服务，给定一组操作，最后得到一致的结果。
  Raft算法通过选举领导人（leader），由领导人复制日志（log）到跟随者（follower），跟随者执行日志指令来达到最后集群状态的一致，整个算法也分成了两部分，领导人如何选举和跟随者如何安全的执行日志指令。

领导人选举

  Raft算法中一个节点在任意时刻只能处在领导人（leader），候选人（candidate），跟随者（follower），同时强调强领导来简化整个流程，所以他的日志数据流只能从领导人复制到跟随者，跟随者之间也不能传递日志。

通常情况下，系统中只有一个领导人并且其他节点全部都是跟随者，跟随者都是被动的，他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求

  下面是三个状态的状态转换图；
图片描述
  节点启动的时候，都是跟随者状态，在一段时间没有收到来自领导者的心跳，就从跟随者转变为候选人，发起选举；如果收到含自己的多数选票则转换到领导者；如果发现其他节点比自己更新，则切换到跟随者状态。为了确定其他节点比自己更新，Raft又引入了任期（term）的概念。

  算法起始，任期是0，当有节点当选领导者时，任期号为1，新领导人选出后，任期在之前的任期号加1。当节点从跟随者转化为候选人的时候，任期号也要增加1。

任期起到逻辑时钟的作用

选举流程

  当一个跟随者节点长时间没有收到领导者心跳包，猜测领导者节点可能挂了，发起新领导者节点选举。

• 增加自己当前的任期，转换状态到`候选人；
• 投自己一票，并且给其他节点发送请求给自己投票的请求；

• 等待其他节点回复，在等待过程中又可能发生下面的情况

  1. 赢得选举，成为领导者；
  2. 被告知其他节点当选领导者，自己退回跟随者状态；
  3. 超时时间没有收到足够多的选票，则重复整个选举过程；

下面的这个gif就展示了这个过程；(吐槽不支持git，博客连接http://qyuan.top/2019/07/14/r...

日志复制

  当选出了领导人系统就可以对外提供服务，客户端把请求发送给集群，如果是跟随者收到则转发给领导者，由领导者统一处理，领导人会调度这些请求，顺序告知所有跟随者，保证所有节点的状态一致。
  Raft是基于复制状态机实现的，其核心思想就是相同的初始状态 + 相同的输入 = 一致的最终状态，领导者将客户端请求打包到一个个log entry，将这些log entries发送到所有跟随者节点，然后大家按相同顺序应用log entry中的命令，则状态肯定是一致的。

复制流程

• 领导者接收请求打包到log entry；
• 领导者并行发送log entry到集群所有节点；
• 领导者收到大多数跟随者收到log entry的回复；
• 领导者应用log entry里面的命令到自己的状态机中，也就是执行命令；
• 领导者回复跟随者，并且让他们也执行log entry中命令，达到和自己一致的状态机；

  每个log entry中，除了需要执行的命令之外还有领导者节点的任期号，用于处理异常情况；同时我们也可以看到，当日志被复制到大多数节点，即可向客户端返回成功的消息，一旦返回了结果，就必须保证系统在任何异常情况都不会发送回滚。
  Raft通过第一个阶段的commited和第二个阶段的apply，保证了状态机的一致性。

  当然还有各种异常情况，我们下篇再讲，讨论细节(╹▽╹)

欢迎关注我的博客（qyuan.top），不定期分享一些区块链底层技术文章，博客排版好一点（ㄟ( ▔, ▔ )ㄏ）。