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

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

3.2 “幽灵日志”问题
经过日志恢复后,ParallelRaft 中主节点的日志不存在“空洞”,因此它可以为每个日志项计算 LBF.之后,主节
点可以将 LBF 随日志项一起发送给从节点.正确的冲突判断要求每个日志项的 LBF 都准确地记录了它之前 K
个日志项的 LBA.然而,“幽灵日志”现象可能会导致主节点计算出的 LBF 与实际不符.图 2 描述了“幽灵日志”现
象,它包含 3 个阶段(图中每个方格表示一个日志项,它记录了该日志项的任期以及所携带的用户命令.日志项从
1 开始编号).
(1) 如图 2(a)所示,第 1 阶段中,s 1 是主节点.s 1 向日志中添加了编号为 1~4 的 4 个日志项.其中,编号为 1 和
2 的日志项被 s 2 和 s 3 接受,这两个日志项被提交;编号为 3 和 4 的日志项还没有被 s 2 和 s 3 接受.s 1 失效;
(2) 第 2 阶段中,s 3 成为主节点.s 3 的主节点在恢复过程中没有收到 s 1 未提交的项(注意,s 3 只需要从多数派
节点收集日志项).因此完成恢复完成后,s 3 的日志中不包含 s 1 未提交的日志项.如图 2(a),之后,s 3 向日
志中添加了编号为 3~6 的新的日志项,并将编号为 6 的日志项发送给了 s 2 ,该项被提交.由于这一项是
对 y 的修改(y←2),与之前的日志项无冲突,因此 s 3 执行 y←2(乱序执行).之后,s 3 也失效,系统选出新的
主节点 s 2 ;
(3) 如图 2(b)所示,第 3 阶段中,s 3 在恢复过程中的收到了 s 1 (此时 s 1 恢复正常)未提交的日志项(编号为 4),
并将它发送给 s 3 .这一项被提交后,s 3 需要执行.它也是对变量 y 的修改(y←3),根据乱序执行的规则,应
该先执行.但是 s 3 已经执行 y←2,因此导致了执行顺序的不一致.

1 2 3 4 5 6 1 2 3 4 5 6

(a) (b)
Fig.2 The “Ghost Log Entries” phenonmenon violates consistency
图 2 “幽灵日志”破坏状态一致性
s 1 在第 1 阶段未提交的日志项不在第 2 阶段的主节点 s 3 的日志中,但是之后又出现在了第 3 阶段的主节点
s 2 的日志中.我们称这种现象为“幽灵日志”.这使得 s 3 计算出的 LBF 与实际不符,可能会导致错误的冲突判断,
进而影响 ParallelRaft-SE(ParallelRaft)在乱序执行下的正确性.避免出现“幽灵日志”的关键在于,在日志恢复的
过程中,第 2 阶段的主节点 s 3 需要明确 s 1 中未提交的日志项的状态:要么将它们重新提交,要么将它们删除并保
证之后不会被新的主节点提交.“幽灵日志”现象在顺序执行(如 Multi-Paxos 与 Raft)下也可能出现,但不会影响
协议的正确性 [22] .在顺序执行下,“幽灵日志”问题很容易解决.接下来我们考虑将 Multi-Paxos 的解决方案应用
到 ParallelRaft-SE 上,并简要论述 Raft 对“幽灵日志”的解决方法.我们将说明这些方案无法解决乱序执行下的
“幽灵日志”问题.
3.3 Multi-Paxos的解决方案
Multi-Paxos 采用了被动式的解决方案.提议者在添加日志项时保存它的生成时间(即生成该日志项的提议
者的提议编号).节点可以通过日志项的生成时间检测出“幽灵日志”,并忽略它们.为此,新的提议者完成恢复过
程后,向日志中写入一条特殊的空操作日志项,称为栅栏(barrier).只有等栅栏日志项被提交后,提议者才能向日
志中添加新的日志项.因此,栅栏日志项标记了日志恢复的终点以及新的提议者添加日志项的起点.如果之后某
个日志项的生成时间小于栅栏日志项的生成时间,则可断定它为“幽灵日志”.