Raft 中的无序追加条目

Question

Raft 论文指出：

追加条目：

如果现有条目与新条目冲突（相同索引 但不同的术语），删除现有条目和所有内容 遵循它（§5.3）

从领导者的角度来看，它向跟随者发送带有条目

[1, 2]

的AppendEntries请求，然后发送另一个带有条目

[1, 2, 3]

的AppendEntries请求。

从关注者的角度来看，它最初接收到带有条目

[1, 2, 3]

的第二个AppendEntries请求，随后接收到带有条目

[1, 2]

的第一个AppendEntries请求。根据该论文，在收到带有条目

[1, 2]

的AppendEntries后，关注者必须删除日志条目

[3]

（假设

[1, 2, 3]

已成功附加）。

出现的问题是如何处理无序到达的 AppendEntries。论文似乎没有提供解决方案。 Raft 的工业实现如何处理这个问题？

Answer 1

来自同一领导者的乱序消息不会影响追随者的日志。追随者只需确认 AppendEntriesRPC 调用即可。

详情：

筏中的整体带有索引和期限（以及实际值）。让我们将 [1,2,3] 的日志替换为 [[1,1,a][2,1,b][3,1,c]] 以避免混淆术语和索引。在这些元组中，第一项是索引，第二项是术语，第三项是日志条目的值。

你原来的问题是：

• 关注者的日志是 [[1,1,a][2,1,b][3,1,c]]
• 来自领导者的迟到消息带有 [[1,1,a][2,1,b]]

在这种情况下，关注者会一一检查消息中的条目。由于 [1,1,a] 和 [2,1,b] 都已经在关注者的日志中，所以关注者什么都不做，只是确认 AppendEntriesRPC。

如果领导者发送带有[[1,1,a][2,2,d]]这样的条目的消息，就会发生冲突。收到请求后，关注者会：

• 将第一个条目与关注者日志中的现有条目进行匹配
• 检测索引 2 处的冲突条目
• 根据 raft 协议，follower 会在冲突的条目处截断其日志
• 关注者的日志将变为 [[1,1,a]] - 冲突条目和所有后续条目都将被删除
• 追随者将接受 [2,2,d] 并且追随者的日志将是 [[1,1,a][2,2,d]]

参考资料：

• https://raft.github.io/raft.pdf第4页
• 规则3：如果出现新术语，并且尚未提交的条目可能与要删除的条目发生冲突，则会发生冲突
• 规则 4：仅添加缺失的条目，如果日志中已有条目（相同的索引和术语），则不需要额外的步骤