知识卡片

结构图卡 · 1769.j

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后,形成决议。