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

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

如图 3(a)所示,每个日志项中的二元组分别记录了该日志项的提议编号(后续过程中可能更改)与生成时间.
s 1 是提议编号 1 的提议者,它向日志中添加了日志编号为 1~4 的日志项,它们的提议编号与生成时间均为 1.其
中,日志编号为 3 和 4 的日志项没有被提交.之后,s 1 失效,s 3 成为提议编号 2 的提议者.s 3 收到 s 2 的日志项,完成恢
复过程后,向日志中写入一条栅栏日志项(日志编号为 3,在图中用 B 标记),其提议编号与生成时间均为 2.s 3 首先
将栅栏日志项发送给 s 2 ,并将它提交.之后,s 3 响应用户请求,并向日志中添加了日志编号为 4~6 的日志项.其中,
日志编号为 6 的日志项被 s 2 接受(因此被提交).s 3 执行该日志项后失效.
s 2 成为提议编号 3 的提议者.如图 3(b)所示:在恢复过程中,s 2 从 s 1 的日志中找到了日志编号为 4(y←3)的日
志项并将它添加到日志中.这一项的提议编号为 3,但是它是 s 1 写入日志的,生成时间为 1.而 s 2 的日志中编号为
3 的栅栏日志项的生成时间为 2.由此,s 2 可以判断日志编号为 4 的日志项是“幽灵日志”.s 2 从日志中删除该项,
从而解决了“幽灵日志”问题.

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

(a) (b)
Fig.3 Passive way to address the “Ghost Log Entries” phenomenon
图 3 “幽灵日志”被动式解决方案

3.4 Raft的解决方案
Raft 采用了主动式的解决方案 [22] :利用选主机制中的限制条件,使得拥有“幽灵日志”的节点无法成为新的
主节点.为此,Raft 中选出的新主节点向日志中添加一条栅栏日志项.只有等栅栏日志项被提交后,新的主节点才
能响应用户的请求.根据 Raft 的选举规则,此时,没有栅栏日志项的节点将无法成为主节点(日志较旧,无法获得
多数派投票).另一方面,在日志项同步阶段,接收到栅栏日志项的节点将会删除栅栏日志项后的所有日志项,故
不存在“幽灵日志”.
如图 4(a)所示,s 1 是任期 1 的主节点,它向日志中写入了编号为 1~4 的 4 个日志项.其中,编号为 3 和 4 的日
志项还没有提交,主节点变更为 s 2 .如图 4(b)所示,s 2 成为任期 2 的主节点后,先向日志中写入一条栅栏日志项并
提交,之后 s 2 才能响应用户请求.即使 s 2 之后失效,根据 Raft 的选主规则,s 1 若想成为主节点,需要先删除多余的
日志项(编号为 3 和 4),并添加栅栏日志项.因此,编号为 3 和 4 的两个日志项不会出现在新的主节点的日志中.

1 2 3 4 1 2 3 4

(a) (b)
Fig.4 Proactive way to address the “Ghost Log Entries” phenomenon
图 4 “幽灵日志”主动式解决方案