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

1764 Journal of Software 软件学报 Vol.32, No.6, June 2021

3.5 乱序执行下的挑战
将 Multi-Paoxs 对“幽灵日志”的解决方案直接应用在 ParallelRaft-SE 上,并不能保证 ParallelRaft-SE(或
ParallelRaft)在乱序执行下的正确性.换句话说,在乱序执行下,“幽灵日志”现象并非导致状态不一致的必要条
件.比如,主节点 i 的日志中包含未提交的日志项.当主节点发生变更后,i 乱序地收到了新主节点的日志项.i 并不
知道日志中未提交的日志项已经过时,从而误以为不存在冲突,导致不一致的行为.
另一方面,Raft 利用它的串行性在选举过程中消除了“幽灵日志”.然而,ParallelRaft-SE 支持乱序提交,日志
中可能存在“空洞”.这使得 ParallelRaft-SE 也不能直接应用 Raft 的解决方案.

4 ParallelRaft-CE 协议与规约

为了解决乱序执行下的“幽灵日志”问题,我们基于 ParallelRaft-SE 提出了 ParallelRaft-CE 协议.ParallelRaft-
CE 通过限制 ParallelRaft-SE 在乱序提交阶段的并行度,避免了“幽灵日志”问题,保证乱序执行下的状态机的一
致性.ParallelRaft-CE 主要包括 3 个部分:日志同步机制、选主机制及其日志恢复机制.
我们先给出 ParallelRaft-CE 的几条关键性质,其中,“同步号”与“主节点候选者”的概念将在接下来的协议描
述中介绍.下一节将简要证明这些关键性质以及 ParallelRaft-CE 的正确性.
(1) 节点的任期与同步号单调递增;
(2) 选举的安全性:每个任期最多选出一个主节点;
(3) 设主节点候选者的任期为 t,同步号为 s,则 s<t 且系统内不存在任期大于 s 的日志项;
(4) 主节点完全性:若主节点的任期为 t,那么它的日志中包括所有任期小于 t 且被提交的日志项;
(5) 一致性:对任意两个节点,如果它们的同步号都大于某个任期值 t,则它们的日志中包含相同的任期为 t
的日志项.

4.1 日志同步机制
在 ParallelRaft-CE 中,日志项的发送与接受是部分乱序的:任期相同的日志项可以并发地发送与接受,任期
不同的日志项则需按序发送与接受.为此,每个节点维护一个同步号(sync),表示目前节点仅接受任期等于同步
号的日志项.当从节点收到主节点的日志项时,会检查该日志项的任期.如果日志项的任期与从节点的同步号相
同,则从节点接受该日志项,并回复确认消息;否则,从节点拒绝该日志项,并将自己的同步号发送给主节点.主节
点额外维护每个从节点的同步号.当收到从节点的同步号时,主节点升级自己记录的从节点同步号.当从节点对
当前任期的每一条日志项都完成确认后,主节点通知从节点将同步号设置为下一任期.这种日志同步机制限制
了提交阶段的并行度.

4.2 选主机制
ParallelRaft-CE 的选主机制与 Raft 相似.不同的是,ParallelRaft-CE 通过同步号判断日志的新旧:节点的同步
号越大,它的日志就越新.候选节点发起选举时,将自己的同步号也发送给其他节点.只有当接收节点的同步号
不大于候选节点的同步号时,才同意该选举请求.

4.3 日志恢复机制
在 ParallelRaft-CE 中,任期相同的日志项可以并发发送与接受.因此,日志中可能存在“空洞”,新的主节点需
要对上一任期的日志项进行恢复.恢复的目标是使得主节点的同步号升级为它的任期,此时,系统便已对所有任
期小于主节点任期的日志项达成了共识.我们将尚未完成日志恢复的主节点称为主节点候选者(leader
candidate).恢复过程完成后,所有任期小于主节点任期的日志项的状态是确定的:已经被提交(或执行)的日志项
仍在新主节点的日志中;之前未提交的日志项要么被提交,要么被丢弃且之后不会再被提交.
假设主节点候选者 l 的任期为 t,同步号为 s(根据性质 3,s<t).根据性质 5 系统已对任期小于 s 的日志项达成
共识.再根据性质 3,系统中不存在任期超过 s 的日志项.因此,l 仅需要恢复任期等于 s 的日志项.恢复日志项的方