《大规模分布式计算深入解析》4.1 Basic Paxos:prepare 与 accept

用单 slot 时序解释 prepare 承诺、最高已接受值继承和选择条件。

两阶段恢复一个 slot

ballot 可由本地递增计数和 proposer ID 排序组成。acceptor 把已承诺的最高 ballot 与最近一次接受的 ballot/value 持久化。Prepare 成功收齐多数派后,proposer 从所有回复中取最高已接受 ballot 的值,只有回复都没有已接受值,才可选自己的值。此前某值已被少数派接受,proposer 也可能必须继承它。

sequenceDiagram
    participant P as proposer ballot b
    participant Q as acceptor quorum
    participant L as learner
    P->>Q: Prepare(b)
    alt 未承诺更高 ballot
        Q->>Q: 持久化 promise
        Q-->>P: Promise,附最高 accepted ballot/value
        P->>P: 继承最高已接受值,否则用新值
        P->>Q: Accept(b,v)
        alt 多数派接受并持久化
            Q-->>P: Accepted(b,v)
            P->>L: 通知已选定的 v
        else 被更高 ballot 抢占
            Q-->>P: 拒绝,等待退避或新 leader
        end
    else 已承诺更高 ballot
        Q-->>P: 拒绝或告知新 ballot
    end

Phase 2 的 acceptor 若尚未承诺更高 ballot,可以接受并持久化。某个值被多数派接受即被选定,学习者随后获知。阶段一 quorum 与已选值对应的阶段二 quorum 相交,继承规则防止更高 ballot 选择冲突值。同一 ballot、slot 内的 proposer 应坚持一个值。

若两阶段各 10 ms,理想串行网络部分 20 ms。前提是收到足够响应、无重试、暂不计磁盘和应用。消息数要先注明是否含本地以及是否按全部 fan-out 计。

验证

从卷七实验包 解包,在纸面将 A 接受的旧值放入 prepare 应答,检验高 ballot 的 proposer 必须取哪个值。

一手资料

卷七目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图