摘要
raft 是一种比 paxos 容易理解的一致性算法, 实现起来比 paxos 简单许多. 本文前部分描述算法的细节, 后部分尝试探讨下该算法的原理.
算法描述
raft 算法之所以简单的原因之一是它将问题分解成三个子问题, 分别是:
Leader 选举
Log 复制
安全性保证
概述
raft 协议中每个 server 都要维护一些状态, 并且对外提供两个 RPC 调用分别是 RequestVote RPC 和 AppendEntries RPC 用于选举和 log 复制.
要想理解 raft, 其实就是搞明白:
leader 和 follower 需要维护哪些变量, 每个变量的含义
leader 什么时候发送 AppendEntries RPC, 携带哪些参数, follower 收到请求后做什么? leader 收到响应后做什么?
candidate 什么时候发送 RequestVote RPC, 携带哪些参数, follower 收到请求后做什么? candidate 收到响应后做什么?
状态:
RequestVote RPC
AppendEntries RPC
raft 所有的操作都是为了保证如下这些性质.
raft 保证的性质
Election Safety: at most one leader can be elected in agiven term.
- Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries.
- Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
- Leader Completeness: if a log entry is committed in agiven term, then that entry will be present in the logs of the leaders for all higher-numbered terms.
- State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.
暂时可以先不看, 需要知道的是 raft 所有的规则都是为了保证上面的这些性质, 而这些性质又是保证 raft 正确的前提.
Leader 选举
Election Safety 性质说的在某个 term 中最多只能选出一个 leader.
有如下这些规则:
raft 将时间划分为 term, 每个 term 都有一个 number, 每个 term 以选举一个 leader 开始.
每个 server 有三种状态: leader, follower, candidate.
作为 follower: 有一个称为 election timeout 的倒计时, 如果在倒计时内没有收到有效的 AppendEntries RPC, 将转换为 candidate, 增加自己的 term number, 投自己一票, 然后通过 RequestVote RPC 通知集群中的其他 server 进行投票. 当半数以上的 RequestVote RPC 返回 true 后, 这个 candidate 将转换为 leader.
某个 server 收到 RequestVote RPC 后如何确定要不要投赞同票? 同时满足以下三个条件则投赞同, RequestVote RPC 返回成功:
在当前周期内还没有投过票
candidate 中 term 不小于自己的 term
"选举限制": 想要获得投票, candidate 的 logs 必须比当前 follower 的 logs 更 up-to-date. 如何比较两个 logs 的 up-to-date 程度? 最后一个 log entry 的 term 大的更 up-to-date, 如果 term 一样, index 越大越 up-to-date.(论文 5.4.1 节)
作为 leader: 周期性的发送 AppendEntries RPC.
Log replication
Entry 格式
Logs 由 Entries 组成, 每个 Entry 包含一个 term 和命令, 格式如下:
Entry 如果已经确定可以安全 apply 到状态机的情况下, 将被标志为 commited. 看上面 state 图中, 每个 server 都维护两个变量 commitIndex 和 lastApplied. 这两个变量都是初始化为 0, 比如 Figure 6 中 leader 的 commitIndex 就是 6, 这个值会在
AppendEntries RPC 中以 leaderCommit 参数通知 followers 修改自己的 commitIndex.
commitIndex 和 lastApplied 有什么区别呢? lastApplied 总是<=commitIndex,commitIndex 表明的是到 commitIndex 为止可以被 apply,lastApplied 表明的是到 lastApplied 为止已经被 apply.
什么情况下 Entry 可以被 commit? 满足以下两个条件:
A log entry is committed once the leader that created the entry has replicated it on a majority of the servers.(leader 将该 entry 拷贝到大部分 server 中)
不能 commit term 比当前 leader 的 term 小的 Entry. 这里不是很好理解, 论文在 5.4.2 节给出了解释.
如下图:
(a):S1 是 leader(term=2),entry 2 只拷贝到了 S2 就奔溃了.
(b):S5 成为新的 leader(term=3), 并且接收了 entry 3, 但是还没进行拷贝也崩溃了.
(c):S1 重新成为 leader(只是 term=4), 并且将 entry 2 拷贝到了 S3. 如果没有条件 2 的限制, 只看条件 1,Entry 2 已经被复制到了大部分的 server 中, 就可以被 commit 了. 那么问题来了, 如果 Entry 2 被 commit 后 S1 又奔溃了, 这时 S5 重新成为 leader(根据上文给出的选举规则, S5 最后一个 Entry 的 term 是 3, 可以获得 S2, S3, S4 和自己的投票, 所以可以成为 leader), 并将 Entry 3 拷贝到其它的 server(情况(d)), 并且 commit, 这样之前 commit 的 Entry 2 就被覆盖了, 这是绝对不允许的, 已经被 commit 的 Entry 不能被覆盖. 再次回到情况(c), 这时如果 S1 不仅复制了 Entry 2 还复制了 Entry 4(term=4)(情况(e)), 这种情况下同时满足条件 1 和条件 2, 所以可以 commit Entry 2 和 Entry 4, 因为和之前不同的是, 如果 S1 现在奔溃了, S5 不可能成为 leader(S5 的最后一个 Entry 的 term=3,S1, S2, S3 都会拒绝投票, 因为它们的 logs 更 up-to-date), 也就不可能出现 commit 的 Entry 被覆盖的情况.
这个图画的有点歧义, 我总结下,(c)如果不考虑条件 2 的限制, 可能会出现 (d),(d) 是不允许出现的.(c)如果同时考虑条件 1 和条件 2, 那么可能出现 (e),(e) 是合法的, 绝不可能出现 (d) 这种情况. 所以条件 2 是必要的.
日志拷贝的过程
leader 接收客户端的 Entry, 将 Entry 添加自己的 logs 中.
leader 周期性使用 AppendEntries RPC 将新的 entry 备份到其它 server.
follower 收到 AppendEntries RPC 后做什么? 进行一致性检查. 根据参数中的 prevLogIndex, 检查自己的 log 的 prevLogIndex 处的 Entry 的 term 和参数中的 prevLogTerm 是否相同, 如果相同则将参数中的 entries 拷贝到自己的 log 中, 否则返回 false,leader 收到响应后如果发现是 false, 调整参数然后重新发送 AppendEntries RPC. 至于怎么调整参数见论文 5.3 节.
不严格的正确性解释
论文中指出 raft 正确性已经使用 TLA+ specification language 进行了证明, 顺便搜了下这个 TLA+ specification language, 由 Leslie Lamport 发明, 用来验证设计的正确性的语言, 这个 Leslie Lamport 也是 NB 的一塌糊涂, Paxos 算法也是他设计出来的. 我没有仔细研究严格的证明, 只是以一种不严格的方式试图解释下为什么 raft 可以保证一致性.
raft 中所有的 log 都是由 leader 流向 follower 的, 所以你 leaader 首先得保证拥有所有的 committed log 吧, 这就是 Leader Completeness 属性. 那么如何保证 Leader Completeness 属性呢. 我认为以下这些规则保证了该属性:
Entry 需要被大部分 server 接收才能被 commit.
leader 需要大部分 server 投赞成票才能成为 leader.
"选举限制": 想要获得投票, candidate 的 logs 必须比当前 follower 的 logs 更 up-to-date.
可以用反证法来证明:
假设 Leader Completeness 属性不成立, term T 的 leader(T) commit 了一个 Entry, 但是新的 term U 的 leader(U)没有包含该 Entry.
leader(T)已经 commit 了该 Entry, 所以该 Entry 肯定被大部分 server 接受了, leader(T)成为 leader 肯定收到了大部分 server 的投票, 那么必定存在一个 server 既接受了该这个 Entry 也投了 leader(T)一票. 显然该 server 包含的 log 比 leader(T)的要 up-to-date, 所以和规则 3 矛盾, 所以假设不成立, Leader Completeness 属性成立.
保证了源头 log 的正确性后, 拷贝过程中也要保证和 leader 的 log 一致. Log Matching 属性保证了这一点, 该属性描述的是: 如果两个 server 中 logs 中的某个 index 对应的 log entry 的 term 相同, 那么这个 index 以及之前对应的 log entry 都应该保证一样. 一致性检查规则可以保证该属性.
raft 这些性质中最重要的就是保证 State Machine Safety 属性, 该属性描述的是任何一个 server 在某个 index apply 一个 Entry, 其它 server 不会在该 index 处 apply 一个不同的 Entry.Leader Completeness + Log Matching 可以推出 State Machine Safety.
来源: https://www.cnblogs.com/gatsby123/p/10577561.html