Page 181 - 《软件学报》2021年第6期

谷晓松 等:支持乱序执行的 Raft 协议 1755

\/\E b\in Ballots,i\in Instances:Phase2a(b,i)
\/\E a\in Acceptors,b\in Ballots,i\in Instances:Vote(a,b,i)
Spec==Init/\[⋅][Next]_〈〈leaderVote,ballot,vote,1amsgs,1bmsgs,2amsgs〉〉
---------------------------------------------------------------------------------------------------------
1.5 Raft协议

Raft 是一种更易于理解的分布式共识协议 [10] ,它加强了日志项之间的串行性,简化了协议的设计.Raft 中的
每个节点都维护一个递增的变量,称为任期(term).任期本质上是节点共同维护的逻辑时钟,通过任期,节点可以
发现过时的消息.具体而言,节点间发送消息时,需携带自身当前的任期.如果节点收到的消息携带的任期值小
于该节点自身当前的任期值,则拒绝该消息;否则,则更新自身的任期值.节点向日志添加新的日志项时,会将自
身当前的任期值也保存在日志项中,这成为该日志项的任期.
Raft 中的节点有 3 种角色:主节点(leader)、从节点(follower)和候选节点(candidate).初始状态下,所有的节
点都是从节点.Raft 协议主要包括两部分:选举主节点以及主节点向从节点同步日志.正常情况下,主节点通过定
时向其他节点发送心跳信号来维护自己的主节点身份.当从节点一段时间内没有收到心跳信号时,便转变为候
选节点.候选节点首先增大自身任期,然后将任期发送给所有节点,以发起选举.收到选举请求后,节点将比较自
身任期和和选举请求携带的任期.如果自身任期较大,或者自己在本任期内已为其他候选节点投过票,则拒绝此
次选举请求.收到多数派投票的候选节点将成为新的主节点.Raft 的多数派投票机制确保选举的安全性(election
safety) [10] :每个任期内,最多只有一个主节点.为了保证新任主节点的完全性(leader completeness),即它的日志应
包含所有已被提交的日志项,Raft 引入了如下规则:如果候选节点的日志比自身的日志旧 [10] ,那么节点将拒绝该
选举请求.节点间可以通过比较日志中编号最大的日志项的编号与任期(分别称为 lastIndex 和 lastTerm)判断日
志的新旧 [10] .
主节点按照日志编号顺序向从节点同步日志项,从节点需要按照编号顺序接受主节点的日志项.在收到编
号更小的日志项之前,从节点不能接受编号更大的日志项.主节点与从节点间通过确认(ack)机制维护下一个可
以接受的编号.与 Multi-Paxos 中不同实例独立发送和接受日志项不同,Raft 在所有的日志项之间通过编号建立
了全序关系.通过这样的限制,Raft 中节点的日志不会出现空洞,同时保证了节点间日志的一致性(log matching
property) [10] :如果两个节点上的日志在同一位置拥有相同的日志项,那么之前所有位置上的日志项也必定相同.
根据日志的一致性,如果某个日志项已被提交,那么日志中所有编号更小的日志项也已被提交.

2 ParallelRaft-SE 协议及精化

[7]
Raft 要求顺序提交、顺序执行用户命令,这种限制使它不适用于高并发系统 .因此,阿里巴巴公司基于 Raft
[7]
提出了 ParallelRaft,它允许乱序提交、乱序执行用户命令 .为了理清 ParallelRaft 与 Raft 之间的关系,我们提出
了 ParallelRaft-SE.ParallelRaft-SE 允许乱序提交,但仍要求顺序执行用户命令.因此,可以将 ParallelRaft-SE 视为
顺序执行版本的 ParallelRaft.为了证明 ParallelRaft-SE 的正确性,我们建立了从它到 Multi-Paxos 的精化关系.

2.1 ParallelRaft-SE协议
ParallelRaft-SE 沿用了 Raft 的角色(主节点、从节点、候选节点)、任期的概念以及选主机制.ParallelRaft-SE
协议主要包括 3 部分:主节点向从节点同步日志、主节点的选取和日志恢复.
在 ParallelRaft-SE 中,主节点可以并发地向从节点发送多个日志项.从节点收到日志项后立即接受并确认,
而无需等待编号更小的日志项.因此,ParallelRaft-SE 支持日志的乱序接受和提交.
ParallelRaft-SE 的选举机制与 Raft 基本相同,都需要保证选举的安全性.不同的是:由于 ParallelRaft-SE 不具
有 Raft 的串行性,节点的日志中可能有空洞,因此在选举过程中,ParallelRaft-SE 无法通过节点比较日志的新旧
保证新任主节点的完全性.因此,ParallelRaft-SE 加入了日志恢复阶段.
ParallelRaft-SE 的日志恢复过程的基本思想是:新任主节点收集其他节点的日志并运行 Paxos 协议,恢复那