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

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

Multi-Paxos 中,提议者通过运行 Paxos 选出提议值后,向接受者同步;
• HandleRequestSync 对应于 Vote.在 ParallelRaft-SE 中,从节点收到同步请求后更新自己的日志.在
Multi-Paxos 中,接受者收到提议者的提议后,接受提议并记录在本地;
• ClientRequest 对应于 Propose.在 ParallelRaft-SE 中,主节点收到用户命令,将其作为日志项添加到日志
的末尾.在 Multi-Paxos 中,若对于某个编号,提议者没有收到提议值,可以提出任意合法的值.因此可以
向日志末尾追加合法的日志项.
ParallelRaft-SE 规约给出了 ParallelRaft-SE 和 Multi-Paxos 在常量、变量之间的精化映射:
----------------------------------------------------------------------------------------------------
Acceptors==Server
Ballots==Term
Instances==Index
ballot==currentTerm
leaderVote==[i\in Ballots6[j\in Index6〈〈leaderLog[i][j][1],leaderLog[i][j][2]〉〉]]
1amsgs=={〈〈m[1]〉〉:m\in r1amsgs}
1bmsgs=={〈〈m[1],{〈〈e[1],〈〈e[2][1],e[2][2]〉〉〉〉:e\in m[2]},m[3]〉〉:m\in r1bmsgs}
2amsgs=={〈〈m[1],m[2],〈〈m[3][1],m[3][2]〉〉〉〉:m\in r2amsgs}

Spec==Init/\[⋅][Next]_vars

MP==INSTANCE MultiPaxos

THEOREM Refinement==Spec⇒MP!Spec
--------------------------------------------------------------------------------------------------------------

3 乱序执行模型与“幽灵日志”问题

相对于 Raft 而言,ParallelRaft-SE 支持乱序提交.但是,它仍然要求顺序执行用户命令,不适合于高并发系统.
在 PolarFS 文件系统应用场景中,ParallelRaft 需要支持乱序执行,也就是允许状态机先执行编号较大的已提交日
[7]
志项,而不必等待编号较小的日志项被提交或被执行 .为了在乱序执行情况下仍能满足状态一致性,需要保证
被乱序执行的命令是无冲突的.因此,本节先介绍 ParallelRaft 所采用的乱序执行模型.在分析 ParallelRaft 协议的
正确性时我们发现,文献[7]中关于 ParallelRaft 的描述忽略了可能会违反状态一致性的“幽灵日志”问题.本节将
分析该问题给乱序执行机制带来的挑战.
3.1 乱序执行的模型
[7]
ParallelRaft 的乱序执行模型给出了用户命令之间的冲突判断规则 .在 PolarFS 文件系统应用场景中,每个
用户命令都包含该命令所访问数据的逻辑区块地址(logic block address,简称 LBA).LBA 不重叠的命令不存在
冲突,可以乱序执行;相反,LBA 有重叠的命令需要按日志编号顺序执行.
在该模型下,每个命令在被执行前,首先检查该命令是否与编号更小的命令存在冲突.由于日志项是乱序接
受(可能尚未被提交)的,日志中可能存在“空洞”.为了在存在空洞的情况下仍能判断当前命令是否可被执行,
ParallelRaft 要求每个日志项记录它之前的 K(是待定参数)个日志项的 LBA,称为“向后看缓冲区”(look behind
buffer,简称 LBF).因此,只要日志中不存在长度超过 K 的“空洞”,就可以判断任意两个日志项/命令之间是否存在
冲突;否则,“空洞”之后的日志项都需要等待.