关于算法:Raft算法

什么是 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。

2. 当 Leader 刚入选的时候 nextIndex 的初始值为 Leader 最初一条日志条目对应的 index。
3. 如果 Follower 和 Leader 的日志不统一，当日志条目同步 AppendEntries RPC 申请时，一致性查看会失败，Leader 会递加 nextIndex，并重试 AppendEntries RPC 申请，最终回到到一个 nextIndex，Leader 日志和 Follower 日志一样。
4. 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