知识卡片
Paxos最终值取决于Promise应答是否已包含批准值而非谁先获批
内容
[[Paxos的准备批准两阶段协议与三种节点角色]]里最反直觉的一点,是通过一个 五节点并发提案的例子才能看清楚:S1提议值X、S5提议值Y并发竞争。如果S1的 提案已经拿到多数派批准,S5发起Prepare请求时只要收到的多数应答里有任意 一个节点(哪怕只有一个)曾经批准过X,S5就必须放弃Y、无条件把自己的提案 改成X——最终”取值为X”这个结果,并不需要X本身被多数派共同批准,只取决于 S5的Prepare请求收到的应答里是否已经包含了批准过X的那个节点。这意味着 即使X只被一个决策节点批准过,只要后续提案节点的Prepare请求恰好触达了 这个节点,X依然会被”传递”下去、最终一致地被整个系统接受。但如果S5的 Prepare请求触达的三个节点都还没批准过任何值,这三个节点就会转而批准Y, 最终系统会对Y达成一致。这个机制解释了Paxos为什么能在”网络不可靠、请求 可并发”的双重压力下依然保证结果确定:决定最终值的不是”谁先完成”这种 时间竞速,而是”多数派交集”这个数学性质——任意两个多数派集合必然至少 共享一个节点,已批准的值必然会通过这个交集节点被下一轮提案”继承”下去。
参考来源
- 位置:《凤凰架构:构建可靠的大型分布式系统》第6章"分布式共识"6.1.3节
"工作实例"(源文件:_epub-src对应OEBPS/Text/chapter80.xhtml)
- 结论依据:原文用S1提X、S5提Y的并发场景说明,X最终被选定并非因为它
最先获得多数派批准,而是取决于S5的Promise应答中是否已包含批准过X的
决策节点,直接支撑本卡片结论。
- 原始内容:事实上,对于情况一,X被选定为最终值是必然结果,但从图6-2
中可以看出,X被选定为最终值并不是必须得到多数派的共同批准,而是只
取决于S5提案时Promise应答中是否已包含了批准过X的决策节点。