raft 分布式共识算法

论文

Github 上有大佬们的翻译，对习惯中文的朋友会友好一些：

GitHub - maemual/raft-zh_cn: Raft一致性算法论文的中文翻译

Raft一致性算法论文的中文翻译. Contribute to maemual/raft-zh_cn development by creating an account on GitHub.

GitHubmaemual

详细的内容请参考上面仓库，下面的内容仅涉及大体流程和部分细节。

流程讲解可以参考（上面的论文可以最后看，但是在看后面的内后之前至少看看这两篇文章）：

「图解Raft」让一致性算法变得更简单

最近在刷 MIT 的 6.824 分布式课程，里面花了很多课时来讲解 Raft 一致性算法，我也花了一段时间完成了课程 lab，算是理清楚了整个算法的流程，有需要 lab 答案的可以联系我，课程要求并不允许放在网上~

ZingLixZingLix

可能有疑问的地方（Figure 8）

Raft 的 Figure 8 讲了什么问题？为什么需要 no-op 日志？

发现之前写的 Raft 文章并没有分析过 Figure 8 的问题，而这张图比较容易让人产生歧义，群里讨论过不止一次。在这里谈谈我的理解。 Figure 8 用来说明为什么 Leader 不能提交之前任期的日志，只能通过提交自己任期…

知乎专栏多颗糖.css-1cd9gw4{margin-left:.3em;}

了解 raft 的局限（也是 Paxos 等的问题）（无法完全解决拜占庭问题，无法解决出现“叛徒”的问题）：

https://zh.m.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98

如果你有兴趣可以看看一些分布式理论：

分布式之cap、base理论、flp不可能原理、一致性问题、共识算法_jy02268879的博客-CSDN博客_flp不可能原理

一、CAP理论CAP理论：在一个分布式系统中，最多只能满足C、A、P中的2个。CAP含义：C：Consistency 一致性：同一数据的多个副本是否实时相同。all nodes see the same data at the same timeA：Availability 可用性：一定时间内，系统能返回一个明确的结果 则称为该系统可用。Reads and writes always succeedP：Partition tolerance 分区容错性：分布式系统在遇到某节点或网络分区

数据格式

节点状态

所有节点的持久性状态

(在响应 RPC 请求之前，已经更新到了稳定的存储设备)

raft 的最终目标即是使集群中超过半数节点的的 log[] 相同

所有节点的易失性状态

所有服务器上的易失性状态

和状态机的关系请移步：分布式共识算法 (kicey.site)

主节点的易失性状态

(选举后已经重新初始化)

主节点需要了解其他节点的日志情况。

追加条目的 rpc 调用

由领导人调用，用于日志条目的复制，同时也被当做心跳使用

（接收者）其他节点响应内容

entrids[] 是多个日志记录，每次可以追加不知一条记录

leaderCommit 用于通知跟随节点主节点（代表集群状态）当前已经提交的状态（主节点没有一个请求单独通知跟随节点）

对于追加条目，接收者的行为遵守

接收者的实现：

1. 返回假 如果领导人的任期小于接收者的当前任期（译者注：这里的接收者是指跟随者或者候选人）
2. 返回假 如果接收者日志中没有包含这样一个条目：该条目的任期在 prevLogIndex 上能和 prevLogTerm 匹配上
   （译者注：在接收者日志中 如果能找到一个和 prevLogIndex 以及 prevLogTerm 一样的索引和任期的日志条目，则继续执行下面的步骤 否则返回假）
3. 如果一个已经存在的条目和新条目（译者注：即刚刚接收到的日志条目）发生了冲突（因为索引相同，任期不同），那么就删除这个已经存在的条目以及它之后的所有条目（发生的原因是当前节点追加了某个已经下线的 learder 的某些没有追加到超过半数的节点的日志记录，这些未提交的日志记录是无效的，需要被覆盖）
4. 追加日志中尚未存在的任何新条目（执行日志追加的请求）
5. 如果领导人的已知已提交的最高日志条目的索引大于接收者的已知已提交最高日志条目的索引（leaderCommit > commitIndex），则把接收者的已知已经提交的最高的日志条目的索引 commitIndex 重置为领导人的已知已经提交的最高的日志条目的索引 leaderCommit 或者是“上一个新条目的索引，即请求中 entries 中最后一条的索引”（取两者的最小值）（原文：
   If leaderCommit > commitIndex, set commitIndex =
   min(leaderCommit, index of last new entry)
   ）

可能会对第 5 条产生疑问：

首先要搞清楚

第 5 条是在干什么：决定哪些日志可以被应用到当前节点的状态机中。

可能存在的问题：当前节点接收了其他 leader 的未提交日志，并且这些日志的超过了本次 entries 覆盖的范围，那么 entries 之后的还是之前的错误日志，如果当前 commitIndex 超过了 entries 的索引，那么直接应用就会将错误的状态应用到状态机中，所有需要取二者中的最小值。

请求投票的 rpc 调用

由候选人负责调用用来征集选票

其他节点响应

接收者实现：

1. 如果term < currentTerm返回 false
2. 如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新（候选人的 lastLogIndex >= 当前节点的 lastLogIndex），那么就投票给他

节点遵守的规则

所有节点

• 在接收到合法追加日志，更新当前节点的状态机：
  如果commitIndex > lastApplied，则 lastApplied 递增，并将log[lastApplied]应用到状态机中
• 跟随最新的 leader：
  如果接收到的 RPC 请求或响应中，任期号T > currentTerm，则令 currentTerm = T，并切换为跟随者状态（跟随最新的主节点）

跟随者

• 响应来自候选人和领导人的请求
• 如果在超过选举超时时间的情况之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志（主节点下线），或者是给某个候选人投了票，就自己变成候选人

候选人

在转变成候选人后就立即开始选举过程

• 自增当前的任期号（currentTerm）
• 给自己投票
• 重置选举超时计时器
• 发送请求投票的 RPC 给其他所有服务器
• 如果接收到大多数服务器的选票，那么就变成领导人
• 如果接收到来自新的领导人的附加日志（AppendEntries）RPC（新的主节点已经选举得到），则转变成跟随者
• 如果选举过程超时，则再次发起一轮选举

主节点

• 一旦成为领导人：发送空的附加日志（AppendEntries）RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以防止跟随者超时而变为候选人发起选举
• 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后（此前需要复制到超过半数的跟随者上）响应客户端
• 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex[i]（lastLogIndex ≥ nextIndex[i]）（会出现这样的情况是因为之前对这个跟随者的追加日志请求失败（包括丢失等情况）），则发送从 nextIndex 开始的所有日志条目：
  * 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
  * 如果因为日志不一致而失败：则 nextIndex 递减并重试
• 假设存在 N 满足N > commitIndex，使得大多数的 matchIndex[i] ≥ N以及log[N].term == currentTerm 成立，则令 commitIndex = N （即在任期范围内，一个追加条目被大多数节点接受，那么认为该条目提交成功，便于在合法的情况下快速的更新主节点的状态）

raft 集群特性