RAFT论文阅读笔记

论文下载

In Search of an Understandable Consensus Algorithm

RAFT算法

RAFT基本概念

三个状态

• raft协议中，一个节点任意时刻处于以下三个状态之一：

1. leader
2. follower
3. candidate

• leader负责与client进行交互。follower只与leader进行交互。candidate用来竞选leader。

Term （任期）

• leader选举的开始代表一个Term的开始。RAFT保证一个term最多有一个leader。当一个candidate竞选成功，它将管理这个cluster直到term的结束。
• 每一个节点都会将 current term number进行存储。在节点间的通信中，会包含current term number，当节点发现自己的term number小于其它节点的term number，它会对其进行更新。如果leader节点发现自己的term number小于其它节点，它会立刻将自己的状态变为follower。

节点间的通信

• 节点间通过RPC进行通信，包括 RequestVote RPCs，Append-Entries RPCs

Leader的选举

• leader周期性地发送heartbeat 给所有的follower。如果一段时间内一个follower没有收到来自leader的heartbeat，它会认为此刻没有有效的leader并主动发起leader的选举。流程为：

1. 将自己的 current term number + 1，并切换到candidate状态
2. 为自己投上一票，同时并行地给其它follower发送RequestVote RPC
3. 节点保持candidate状态直到出现以下情景之一：

a) 赢得选举：candidate收到半数以上节点的投票。每一个节点每个term至多能给一个candidate投票，基于的是first-come-first-served的原则（后文还介绍了其它限制）。一旦节点赢得选举，它会立刻发送heartbeat给其它节点，以终止选举流程。

b) 其它节点成为了leader：节点可能收到来自其它节点的 AppendEntries RPC （宣称自己是leader）。如果leader的term大于等于它的term，节点会认为该leader是合法的，并将自己的状态转换为follower。如果小于，节点会拒绝该RPC并保持candidate状态。

c) 一定时间过去后仍没有节点赢得选举：如果多个follower同时成为candidate，可能导致没有任何一个follower得到大多数的选票。此时各个candidate将会超时，并发起新一轮的选举流程（重复步骤1，2，3）。为了避免无限的超时重选举，RAFT将每个server的超时时间（election timeouts）随机化，使得大多数情况下一个server率先超时，在其它server超时前赢得选举。

Log replication

Log replication步骤

1. 当leader接收到client的请求，它会把请求所包含的command 添加（append）到其log中，称为一条entry。
2. 接着并行发送Append-Entries RPCs到follower使其复制该entry。
3. 当entry被大多数节点成功复制后（此时该entry被称为committed entry），leader将会将该entry应用于状态机中（执行该command），并返回执行结果给client

log entry

• 每个log entry包含command，产生该log entry的 term和log index。从下图可以看到，五个节点的日志并不完全一致，raft算法为了保证高可用，并不是强一致性，而是最终一致性。如果有follower由于跪了, 运行得很慢或者网络丢包等原因未成功存储log entry，leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。

committed entry

• leader会记录committed entry的最大index（上图中为7）。该值会被包含在与follower的AppendEntries RPCs （包括heartbeat）中。
• follower一旦发现某条log entry被committed，它会应用该entry到状态机中。

Log Matching 特性

• 如果两个节点上的某个log entry的log index相同且term相同，那么在该index之前的所有log entry应该都是相同的。

• 因为，leader在某一term的某一个index只会创建一个log entry，且log entry是append-only。另外，AppendEntries consistency check。即leader在AppendEntries RPC中包含当前log entry之前的一个log 的term和index，如果follower在对应的term index找不到log，就会拒绝这个RPC。

• 在没有异常的情况下，log matching是很容易满足的，但如果出现了node crash，情况就会变得复杂，可能的情况包括：

• 当leader发现有不一致时，它会强制follower复制自己的log。存在一个index point，它和它之前index的log是一致的。follower该index之后的log将会被leader的log覆盖。

• leader为每一个follower维护了一个nextIndex。当leader上任后，它会将该值初始化为它的最后一个index + 1 （图7中的11）。如果follower的log与leader不一致，下一个AppendEntries RPC的AppendEntries consistency check将会失败，leader会将nextIndex - 1并重试AppendEntries RPC。直到nextIndex 到达index point, AppendEntries consistency check成功。通过该流程，leader与该follower的log将变得一致。

Safty

选举安全性

• RAFT保证新选中的leader必须存储了上一个term的所有committed entry
• 如果candidate log的up-to-date程度大于等于多数的server（如果最后一个log entry的term更大，则更新；如果term相同，index更大则更新），则满足“存储了上一个term的所有committed entry”的条件。
• 在candidate的RequestVote RPC中，包含了它的log信息。如果server发现自己的log比candidate的更up-to-date，它将会拒绝投票。

Raft never commits log entries from previous terms by counting replicas.

• 某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过在提交当前任期的日志的时候把之前的日志也提交了。

Log 压缩

算法总结