将 paxos 和 raft 统一到一个协议下: abstract-paxos - OpenACID Blog

[giscus[bot]]

将 paxos 和 raft 统一到一个协议下: abstract-paxos - OpenACID Blog

从古至今, 武林中有两招绝学, paxos 和 raft, 三十天了, 我用了整整三十天的时间, 将两招绝学并成了一整招, 看好了: abstract-paxos

https://blog.openacid.com/algo/abstract-paxos/

[Veeupup]

xp哥，写得太好了😭，问下最后 Raft 的第二个优化感觉和 pipeline 复制 有些相似，可以理解为这里是聚合成 batch 发吗？

[drmingdrmer]

@Veeupup 跟 pipeline 应该没有关系, 它只是在leader 刚选出来时可能可以提前确认第一个commit的时间. 后面就用不到了.

[TCeason]

粉了

[xxchan]

右边的目录 overflow 了🤔

[drmingdrmer]

换...显示器?... 😭

[caicancai]

博主的文章是我看过Paxos和Raft讲的最细了

[Phoenix500526]

博主的文章写的非常精彩！！我在”成员变更约束-2“（后面简称 Sec-2）那里有些地方不太明白，想要请教一下。在 Sec-2 中提到的:

writer 中断, 另一个 writer 看到 cᵢ₊₁ 时, 它不知道 cᵢ₊₁ 处于变更中间, 也就是说新的 writer 不知道现在的 commit 应该使用 [cᵢ, cᵢ₊₁], 它只使用 [cᵢ₊₁].
问题一、W2 在 W1 中断后，Propose 的也是 Config Change 吗？这个问题是特指 W1、W2 并发 Propose Config Change 时才发生的？还是在 W1 执行 Propose Config Change 中断后，W2 Propose 任何提案都会发生的（不局限在 Config Change 上）？

所以对 config 日志向 joint config 的 commit 分为两步:

1. 先在旧配置上拒绝更小的 State 的提交, 再 propose 新配置. 根据 成员变更Lemma-1, 即, 至少将一个与 w.commit_index 相同的 State commit 到 cᵢ 上.
2. 再 propose cᵢ₊₁, 从日志 cᵢ₊₁ 之后的日志开始, 都只需 commit 到 cᵢ₊₁ 上.
   问题二，1 中的旧配置，指的是 Joint Config[cᵢ, cᵢ₊₁,], 还是 cᵢ ？ 我理解应该是前者，但符号上看的有些混乱。
   问题三，W1 应该会先在 cᵢ 上提交自己的 State（该 State 的最后一条日志是 [ cᵢ, cᵢ₊₁,]）。当这个 State 提交成功后，W1 需要在 [ cᵢ, cᵢ₊₁,] 提交自己当前的 State。 在 [ cᵢ, cᵢ₊₁] 上提交当前 State 的行为是自发进行的吗？还是需要像 Raft 一样，提交一条 no-op log 呢？（感觉 no-op 似乎不必要，Raft 单节点变更的弊端使得 no-op 是必要的，联合共识的变更应该不需要这样的补丁。）如果不必要，那 abstract paxos 的 Config Change 应该是两条日志（[ cᵢ, cᵢ₊₁] 和 cᵢ₊₁ 两条），三次提交（第一次在 cᵢ 上提交 [cᵢ, cᵢ₊₁] 日志，第二次在 [ cᵢ, cᵢ₊₁] 上提交自己 State，第三次在 [ cᵢ, cᵢ₊₁] 上提交 cᵢ₊₁）
   问题四，我其实不太明白为什么把 "Config 向 Joint Config 的 commit"拆成两次 commit 以后就能够解决问题。如果第二次 commit 失败，那不就又回到原点了吗？第二次 commit 失败，W1 的 State 并没有在 [cᵢ, cᵢ₊₁] 上被提交，那 W2 拿着 cᵢ₊₁ 发起 Propose 也可能把错误的 State 写入到 cᵢ₊₁ 的 Quorum 中吗？
   最后再次感谢博主的精彩文章，从中学习到了很多知识

[drmingdrmer]

问题一、W2 在 W1 中断后，Propose 的也是 Config Change 吗？这个问题是特指 W1、W2 并发 Propose Config Change 时才发生的？还是在 W1 执行 Propose Config Change 中断后，W2 Propose 任何提案都会发生的（不局限在 Config Change 上）？

这里讨论的W2 propose的内容不特指config change,也可以是业务的数据, 就这段话来说, 它是说,
w1 propose config change 到[cᵢ₊₁], 这时w1知道后面的commit必须commit到 [cᵢ, cᵢ₊₁];
但是如果w1挂了, 新来的w2不知道要commit到[cᵢ, cᵢ₊₁], w2只会commit到cᵢ₊₁; 这样就会脑裂;

问题二，1 中的旧配置，指的是 Joint Config[cᵢ, cᵢ₊₁,], 还是 cᵢ ？ 我理解应该是前者，但符号上看的有些混乱。

这里指的是cᵢ

问题三，W1 应该会先在 cᵢ 上提交自己的 State（该 State 的最后一条日志是 [ cᵢ, cᵢ₊₁,]）。当这个 State 提交成功后，W1 需要在 [ cᵢ, cᵢ₊₁,] 提交自己当前的 State。 在 [ cᵢ, cᵢ₊₁] 上提交当前 State 的行为是自发进行的吗？

是的, 就像raft的commit标准一样.

还是需要像 Raft 一样，提交一条 no-op log 呢？（感觉 no-op 似乎不必要，Raft 单节点变更的弊端使得 no-op 是必要的，联合共识的变更应该不需要这样的补丁。）

no-op是新leader要确保自己term里的log被commit加入的. 对一个leader来说, 加多少个config change log, 后面都不需要特别的追加no-op;

如果不必要，那 abstract paxos 的 Config Change 应该是两条日志（[ cᵢ, cᵢ₊₁] 和 cᵢ₊₁ 两条），三次提交（第一次在 cᵢ 上提交 [cᵢ, cᵢ₊₁] 日志，第二次在 [ cᵢ, cᵢ₊₁] 上提交自己 State，第三次在 [ cᵢ, cᵢ₊₁] 上提交 cᵢ₊₁）

是的.

问题四，我其实不太明白为什么把 "Config 向 Joint Config 的 commit"拆成两次 commit 以后就能够解决问题。如果第二次 commit 失败，那不就又回到原点了吗？第二次 commit 失败，W1 的 State 并没有在 [cᵢ, cᵢ₊₁] 上被提交，那 W2 拿着 cᵢ₊₁ 发起 Propose 也可能把错误的 State 写入到 cᵢ₊₁ 的 Quorum 中吗？

这个问题我没太明白, 不太清楚你说的第二次指的是commit哪个数据🤔

[Phoenix500526]

感谢博主回答，这里的第二次 commit 指的是 W1 在 [cᵢ, cᵢ₊₁] 上 commit 自己当前的 State。如果这里的失败了，W2 拿着 cᵢ₊₁ 的配置发起 Propose，不也一样会出现脑裂吗？

[drmingdrmer]

首先这里讨论的前提是 cᵢ ~ cᵢ₊₁, 就是说相邻2个config 中的任意一对quorum都是有交集的;

然后, 对你的问题: 第二次commit 后, 如果w1挂了, 那么w2只可能使用cᵢ₊₁ 或 cᵢ , 但他俩有交集, 所以选举时会互斥, 不会有w2 和w2'同时都是可写的;

如果没有第二次 commit, 那么可能出现这种情况:
cᵢ = {xyz}; 即xyz 三个节点的集群
cᵢ₊₁ = [{xyz}, {uvw}], 即xyz, uvw的joint config
c'ᵢ₊₁ = [{xyz}, {pqr}], 也是一个joint config

然后 w1 把cᵢ₊₁ 写到 {z, u, v} 后挂了;
然后另一个w1'通过xy完成第一阶段, 把 c'ᵢ₊₁ 写到{q,r,x} 后挂了;

这时, w2可以通过uvw中的2个节点在cᵢ₊₁上完成第一阶段;
w2'可以通过pqr中的2个节点在c'ᵢ₊₁上完成第一阶段;
这样就出现了2个可写的w2 和w2'.

但有了第二次commit后, 上面的流程变成了:

• w1 把cᵢ₊₁ 写到 {z, u, v} 后挂了;
• 另一个w1'通过xy完成第一阶段, 先commit了一个随便的数据; 然后 把 c'ᵢ₊₁ 写到{q,r,x} 后挂了;
• 这时, w2 如果要用 cᵢ₊₁ 来完成第一阶段, 它一定会看到w1' 最后commit的数据, 这样就发现了cᵢ₊₁ 不是最大的. 所以就阻止了脑裂.

[Phoenix500526]

好的，感谢博主，过后我又仔细地看了一遍文章，现在基本上是弄懂了。

[Phoenix500526]

博主，你好！又是我😃。在看完了前面的 《可靠分布式系统-paxos的直观解释》和这篇 blog 之后，我把 Paxos 和 Fast Paxos 的 Paper 都找来阅读了一遍，但发现它们当中都没有提到成员变更。我在想，abstract paxos 的这套成员变更，能够被应用到 Fast Paxos 上吗？我感觉应该是可以的。主要有两点：

1. 不要使用 fast round，只用 classic round 进行 Joint Consensus 成员变更，这个应该和 abstract paxos 不会有太大区别
2. 联合共识变更过程实际上要求的是在相邻的两个合法配置之间分别达成共识（即在 cᵢ 上提交 {cᵢ, cᵢ₊₁} entry，在 {cᵢ, cᵢ₊₁} 上提交 cᵢ₊₁ entry），似乎并不关心这个共识是由 fast round 得来的还是 classic round 得来的。

那么，关于在 Fast Paxos 上，使用 classic round 执行 joint consensus 和在 abstract Paxos 上执行 joint consensus 没有太大区别这个想法是否正确呢？其次，能够使用 fast round 执行 joint consensus 吗？感谢

[drmingdrmer]

理论上是可以的，但是我不是很确定怎么让 fast round 呈现在那个 joint consensus 上面。因为 joint consensus 实际上不是一个单纯由数量决定的一个 quorum，但是 fast round 它需要 3/4 以上节点或者其他配置。

如果你想写 paper 的话，感觉 Fast Paxos 和 joint consensus 的结合不太容易。因为 Fast Paxos 的 paper 上说，fast round 只在 round 0 使用。

而且，在一个 single leader consensus 算法上面使用 fast round 不是很划算。

一般来说，FAST Paxos 会运用在 Master Leader 的一些算法里。