什么是Raft

RAFT协定是一种共识算法(consensus algorithm)。什么是共识算法，说白了也就是大多数成员达成统一的算法。那对于大多数有定量吗？有，大于等于N/2+1就是大多数，也就是多余半数的成员达成统一。

共识算法的典型代表是Paxos，而因为其不仅难以了解，更难以实现，所以衍生出了很多基于Paxos的算法，Raft就是其中之一，提供了一种更易懂、且便于工程实际的算法。

Raft有什么作用

为了进步零碎的可用性，零碎设计时会引入备份（避免单点故障导致不可用）。比方零碎存储，会有一个主存储和N个备存储（多数据正本），随之产生了一个新的问题，零碎怎么保障主存储了备存储的数据统一（多正本之间数据一致性）？

一致性：一致性就是数据保持一致，在分布式系统中，能够了解为多个节点中数据的值是统一的。能够将一个具备强一致性的分布式系统当成一个整体，应用层能够疏忽底层多正本之间数据同步的问题。

Raft就是保障一致性的一种共识算法。

Raft算法介绍

Raft算法基于状态复制机(Replicated State Machine),状态机将客户端的操作命令(command) 转换成日志(log),经各状态机依照程序解决后，apply到状态机中(state )。

依据状态机的运行逻辑，要保障个节点之间的state最终统一，也就是保障个节点的日志正本统一，其余节点依照程序解决日志后，使得集群内状态统一。

Raft就是用来治理日志正本(replicated log)的算法。Raft首先会选举出一个Leader，用于治理replicated log，Leader从客户端接管申请，解决成日志(log)，并把日志同步给其余节点，而且会通知其余节点什么时候能够平安的apply 日志到状态机中。

Raft算法要保障了如下个性

  • 选举平安：在一个term（上面有介绍），最多一个Leader能够被选举（或者没有选举进去Leader）。
  • Leader 只容许日志条目减少：Leader节点永远不会笼罩或者删除本人的日志条目。只会新增新的日志条目。
  • 日志匹配：两条日志条目标term和index属性雷同，那么之前的日志条目信息也雷同。
  • Leader完整性：如果在一个term中，一个日志条目被commited，在高版本term中的Leader肯定会用用这条被commited的日志条目。也就是说commited后的日志条目在集群中不会失落。
  • 状态机平安：一个节点的某index地位applied日志条目到状态机，不会存在其余节点将对应节点不同条目标日志apply到状态机。

由此Raft算法拆分出了三个绝对独立的子问题

  • 选主 leader election，Leader不存在或者Leader宕机的状况下须要抉择出一个Leader。
  • 日志复制 log replication，Leader将本人的日志同步给集群中其余节点。
  • 安全性 Safety：次要保障状态机平安个性，前面章节会具体介绍。

选主 leader election

Raft集群中节点角色有以下三种：

  • Leader： 所有申请解决节点。申请写入本地日志后同步集群其余节点。
  • Follower：同步Leader节点日志，转发客户端申请给Leader节点。
  • Candidate：在timeout实际内没有接管到Leader节点的心跳申请，认为Leader节点宕机，转换角色状态为Candidate，开始leader election，直到选主完结。

任期 term

每当candidate触发leader election时都会减少term。term编号枯燥递增。每个节点都会保留一个以后任期term，通信时会带上这个term。

接下来咱们看下各角色之间的转换图

如何成为Follower

  • 启动时节点默认为Follower。
  • Candidate收到新Leader的RPC。
  • 所有节点，收的的申请(request)或者响应（response）中的term>currentTerm,变为Follower。

如何成为Candidate

  • Follower节点在timeout工夫内没有收到Leader节点的心跳申请且没有投票给Candidate。
  • Candidate节点在timeout周期内，没有取得大多数选票，会维持Candidate角色。

如何成为Leader

  • Candidate节点在选举周期内取得集群内大多数选票，变为Leader。

上面咱们来演示下常见的Leader election场景：选举胜利和选举失败。

Candidate节点获取其余节点的投票，通过RequestVote RPC，接口详情见下图。

投票规定：

  • 每个term，各节点能够投一票，通过votedFor属性标识是否在本term内投票过。
  • Candidate首先会给本人投一票。
  • Follower没有投票给其余节点过，投票申请中的term>=节点以后term，且投票申请中的日志index要>=以后节点最新的日志条目index，满足以上条件的投票申请 采取先到先得的形式响应对应的Candidate。

选举胜利：集群初始启动

模仿场景，集群共有5个节点S1~S5，刚开始启动时节点角色都为Follower，圈内数字标识term，刚启动时term为1，外圈灰色局部示意残余超时工夫。

S3节点超时，节点变为Candidate，开启一轮leader election。

S3的term+1变为2，S3首先投本人一票，并行的向集群中其余节点发送投票申请。

集群中的节点收到投票申请后，响应，

图片中带十字图标示意投票给申请的Candidate节点。

收到投票后果后的S3成为了Leader，选举胜利

选举失败场景：多节点同时开启leader election

S3、S2节点宕机，S5和S4节点同时超时开启新一轮的leader election。

S4、S5都投给本人一票，S1的投票依据先到先得准则投给了S4，S4失去了两票< (5/2+1=3),不满足大多数准则，S4不能胜利变更为Leader。

期待S4选举超时，开启下一轮的leader election，

因为S5的term 3 小于S4的term 4，所以S3变更为Follower，并且投票给S4

最终S4胜利取得3票入选为Leader

为了防止多个节点同时开启leader election 导致选举失败的状况，Raft采纳随机超时工夫的形式，尽量避免多节点同时开启leader election。

更多Raft集群选主场景，能够在https://raft.github.io/页面模仿各种状况进行测试。

日志复制 log replication

日志构造如下图

每个日志条目(方框标识)蕴含状态机命令(x<--3)和对应的term编号(框内上方数字)，每个条目还有一个index标识在日志中的地位（上图头部数字）。

当日志条目被集群中的大多数节点接管后，对应的日志条目就被commit。

日志同步问题次要保障Raft的日志匹配个性，日志匹配个性能够拆解为以下两点

  • 1.不同节点下，两个日志条目，领有雷同的term和index，那么对应的条目command肯定雷同。
  • 2.不同节点下，两个日志条目，领有雷同的term和index，那么该日志条目之前的条目也肯定雷同。

首先第一点，因为是Leader节点负责解决客户端申请，依照程序写入日志条目，那么term创立一个领有雷同term和index的日志条目，且日志条目不会扭转在日志的的地位，也就是index属性。

第二点是如何来保障的呢，日志同步通过AppendEntries RPC申请进行，具体参数信息请看下图

能够看到申请中蕴含了prevLogTerm和prevLogIndex,这两个参数用来做一致性查看的，收到AppendEntries RPC申请后Follower会查看前一个日志条目标term和index和申请中prevLogTerm和prevLogIndex参数是否统一，如果统一，则一致性查看通过，如果不统一，则一致性查看失败，回绝此次日志同步申请。

失常状况下Leader和Follower日志保持一致，异样状态下如网络提早或者节点宕机等状况，会呈现Follower和Leader日志不统一的状况。下图展现了一些Leader和Follower不统一的场景。

那么Raft是怎么来解决这种Leader和Follower之间日志条目不统一的状况呢？答案是Follower会从Leader中同步数据。

  1. Leader会为每个Follower保护一个nextIndex属性，用于标识下一次日志复制发送那一条日志条目给Follower。

  1. 当Leader刚入选的时候 nextIndex的初始值为Leader最初一条日志条目对应的index。
  2. 如果Follower和Leader的日志不统一，当日志条目同步AppendEntries RPC申请时，一致性查看会失败，Leader会递加nextIndex，并重试AppendEntries RPC申请，最终回到到一个nextIndex，Leader日志和Follower日志一样。
  3. Follower会删除和Leader不统一的日志条目，并且追加Leader同步过去的日志条目。最终和Leader的日志条目保持一致。

安全性 Safety

  • 选举束缚（ Election restriction），Follower会回绝投票给本人最初一条日志条目新于投票申请中的最初最初一条日志条目。
  • commit之前term的日志条目束缚：以后term的日志条目commit时，才会将之前term的日志条目一起commit。

选举束缚（ Election restriction）

Follower会回绝投票给本人最初一条日志条目新于投票申请中的最初最初一条日志条目。对于日志条目更新的比拟规定时 先比拟term，term大的更新，term一样的状况下，比拟index，index大的更新。

Leader的节点肯定蕴含所有被Commited的日志条目信息，Candidate节点要入选为Leader，必须要取得大多数节点的投票，意味着至多有一个节点领有commited的日志条目，Candidate最初最初一条日志条目要新于大多数节点，也就意味着这个入选的节点领有commited的日志条目。

commit之前term的日志条目束缚

咱们先来看一下以下场景

a) term 2 ,S1时leader 将index 2 的日志条目 复制给 S2。

b)term 3, S1宕机，S5收到S3、S4和本人的投票后入选为Leader，而后接管一个不同的日志条目到index 2。

c)term4 ，S5宕机了，S1重启后从新入选为Leader，持续复制term2、index2的日志,S3接管到term2，index2日志，term2，index2日志此时还不能commit（日志term和以后term不统一时，不能在日志同步给大多数节点后commit），起因状况接下来的场景。

d)term 5，S1宕机，S5 取得 S2、S2、S4、S5的投票后入选为Leader，同步term3 index3的日志条目给其余节点。退出过后term2 index2被提交了，那么这条提交的记录就会被笼罩掉。

e）term 4，当S1接管到新的日志条目term4 index4,并将其同步到集群中大多数节点后，term4 index4被commit，之前的term2 index2条目也能够一起被commit。

Raft不会通过计算大多数节点同步形式 commit之前term的日志条目。只有当Leader的以后term的日志条目才会通过计算大多数节点同步形式，commit日志条目。以后版本的日志条目被commit，之前term的日志条目才会被commit。

对于Raft的内容就先介绍到这，受本身教训限度，有些形容可能会呈现疏漏，残缺内容请查看官网和Raft论文。

参考：

  1. https://raft.github.io/raft.pdf