Paxos 所谓的日志空洞, 在讨论 Paxos 和 Raft 对比时出现的频率非常高, 非常显眼. Paxos 的日志空洞是什么? "日志空洞"对线性一致性有什么影响? 我认为大多数人都对 Paxos 日志空洞有误解, 包括我之前也是.
很多人认为 Multi Paxos 可以允许空洞, 但是 Paxos 论文提到:
To guarantee that all servers execute the same sequence of state machine commands, we implement a sequence of separate instances of the Paxos consensus algorithm, the value chosen by the ith instance being the ith state machine command in the sequence.
状态机必须严格按顺序执行(apply)命令, 所以, Multi Paxos 并不允许 apply 时出现所谓的日志空洞. 虽然会乱序 chosen(也即所谓的空洞), 但是, apply 一定是严格按顺序进行的. Apply 的时候, 如果不是严格按顺序的, 就不是日志复制状态机.
但是, 因为必须严格按顺序执行日志序列, 所以, 即使 Multi Paxos 乱序 chosen 日志, 也不会影响外部一致性.
考虑这样的场景:
外部请求 req-1, 被 chosen 为 log-6, 此时 log-5 是空洞. 因为有空洞, 所以 log-6, 也即 req-1 不会被执行, 外部无法看到状态机的结果. 这时, 外部并发地请求 req-2, 注意, 因为 req-2 并不知道 req-1 的结果, 所以两个请求是并发的. req-2 被 chosen 为 log-5, 然后, 状态机按顺序先执行 req-2, 再执行 req-1.
这是一个非常容易迷惑和造成误解的场景. 很多人认为, 这里不符合"线性一致性", 因为他们觉得 req-2 在 req-1 之后发起, 却在 req-1 之前被状态机执行(apply). 造成这种误解的原因, 是因为他们无法理解"并发"的含义:
For defining concurrency, exact time doesn’t matter: we simply call two operations concurrent if they are both unaware of each other, regardless of the physical time at which they occurred. - Martin Kleppmann
req-1 和 req-2 是并发的, 因为它们不知道对方的结果, 而不管它们谁先开始谁后开始. 因此, 它们的执行顺序有两种可能性, 任何一种都不会违反线性一致性, 只要多副本一致即可.
注: 外部一致性这个词可能会更适当一些.
什么是日志复制状态机?
- 日志序列
- 将日志复制到多节点
- 严格按顺序 apply(无空洞)
什么是乱序确认, 乱序提交?
有一些错误的观念, 以为 Paxos 可以乱序确认或者乱序提交, 并且把这两个东西称为"日志空洞". 前面已经提到了, 无论什么是乱序确认或者乱序提交, 根据日志复制状态机的定义, 都必须严格按顺序 apply, 没有空洞, 有空洞就不是日志复制状态机, 也不要叫这个名字.
还有些人错误地认为 Paxos 一条日志在确认/提交之后, 就可以返回响应给客户端, 以及这样就可以减少 RT. 这种做法只是特殊场景的特殊优化, 不具备通用性, 通用的方案是日志复制状态机, 也就是必须 apply 之后才能将结果返回给客户端. 这不是废话吗? 不 apply, 你哪来的结果? 凭空捏造吗? Incr 命令不 apply, 你怎么知道结果等于几?
动不动就说 Paxos 乱序提交好, 日志空洞好, Raft 串行化不好, 真是蠢人多作怪.
什么是乱序 Apply
是日志复制状态机就不能乱序 apply, 乱序 apply 就不是日志复制状态机! 能不能乱序 apply, 由应用层决定, 和共识模块(Paxos/Raft)无关. 虽然 Raft 按顺序将日志交给你 apply, 你也可以并发(异步)多线程 apply, 别人顺序交给你, 不代表你必须顺序执行呀! 胡扯什么 Raft 不能乱序 apply?
Raft 的日志序列有什么特点?
Raft 的日志序列, 本质是一种节点带前向指针的链表. 这个链表还有一个核心的特点是, 所有节点按顺序赋予了连续整数编号, 编号和前向指针(prevTerm)共同组成了节点的唯一摘要(digest). 因此, 如果两条链表在相同位置的节点是相同的(也即摘要相等), 那么各自从链表的头节点到此位置节点组成的两个前缀链表也是完全相同的.
这种链表结构也出现在区块链技术中(见 - Raft 协议和区块链).
这种链表有个好处, 就是可以一次 commit 多条日志. 例如, commit index=100, 等同于把之前 99 条日志也都 commit 了. 如果按纯朴的 Paxos 的做法, 必须 commit 100 次. 1 比 100 少, 所以"Raft 比 Paxos 好 100 倍!". 我们是不是要据此捧 Raft 踩 Paxos?
总结
由于对"并发"的定义有误解, 导致了许多人对 Multi Paxos 日志空洞也产生了错误的理解, 并推导出了很多错误的推论. 另外, 许多人拿基于特殊场景的特殊优化方案与普适通用的方案进行不恰当的对比, 从而不断地强化自己的错误观念.
Loading ...