知识卡片
Paxos两阶段
Paxos为一个consensus instance选择单一值;少数节点故障时,协议只有在能联系到多数派时才可能推进。Phase 1中,Proposer选择唯一且足够大的提案编号n并向Acceptor发送Prepare。Acceptor若尚未对更大编号的Prepare作出承诺,就承诺今后不接受编号小于n的提案,并返回自己已接受的最高编号提案(若有);这些状态需要持久化以跨故障保留。
Proposer收到多数派应答后不能任意使用自己的值:若应答包含已接受提案,必须选择其中编号最高者的值;只有全部为空时才能提出自己的值。Phase 2发送Accept(n, v),Acceptor只要没有承诺过更高编号即可接受。多数派接受后,值v被选定。
安全性保证是同一instance不会选定两个不同值。更高编号的提案可以后来被接受甚至被多数派接受,但必须延续已经选定的值;因此不能写成“最终只有一个ProposalID能完成”。提案编号的生成方式是实现细节,时间戳加机器标识只是可能方案之一。
结构图:
sequenceDiagram
participant P as Proposer
participant A as Acceptor(多数派)
Note over P: 阶段一:Prepare
P->>A: Prepare(n)
Note over A: 若n大于已应答Prepare编号<br/>承诺不再接受编号<n的提案
A-->>P: Promise + 本机最高已接受(nᵢ, vᵢ)(若有)
alt 多数派应答包含已接受提案
Note over P: v = 其中编号最高者的值
else 多数派均未接受过提案
Note over P: v = Proposer自己的值
end
Note over P: 阶段二:Accept
P->>A: Accept(n, v)
Note over A: 未承诺更高编号才接受
A-->>P: Accepted(n, v)
Note over P,A: 多数派接受后值v被选定<br/>更高编号仍只能延续已选定值
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《高可用架构(第1卷)》第2章《高可用架构原理与分布式实践》"2.10 架构师需要了解的Paxos原理、历程及实战"节,"2.10.2 Paxos协议简单回顾"(源文件:_epub-src/OEBPS/Text/Chapter2_10_3.xhtml)
- 结论依据:原文逐条列出Prepare与Accept阶段行为;正文和结构图按Lamport原文补全“继承多数派应答中最高编号已接受值”这一安全性关键条件,并把结果表述为单值安全而非ProposalID唯一。
- 外部核验:[Lamport《Paxos Made Simple》](https://lamport.azurewebsites.net/pubs/paxos-simple.pdf)规定Phase 2采用多数派应答中最高编号已接受提案的值,并把安全目标表述为只选择一个值。
- 原始内容:Acceptor收到PrepareRequest后,做出"2个承诺,1个应答"……第1,不再应答ProposalID小于等于……当前请求的PrepareRequest。第2,不再应答ProposalID小于……当前请求的AcceptRequest……最后Proposer收集到多数派应答的AcceptResponse后,形成决议。