paxos算法步骤（Paxos扩展偏序rnd）

Paxos^[1]phase-1 要求 Proposer 生产一个整数n 来作为rnd. 实际上rnd的定义从整数推广到任意的 偏序关系^[2]的值, 也同样能满足 Paxos 的正确性, 因为 Paxos 中主要只用到了rnd的大小关系的性质.

使用偏序 rnd的 Paxos, 可以选择强制的冲突互斥(类似2PC^[3]) 或是非强制的冲突互斥(类似Paxos的活锁)来实现一致性协议的安全性要求.

例如选择 整除的偏序关系实现 Paxos, 定义rnd为正整数, 大小关系定义:为如果 a 整除 b, 那么 a 才小于 b: 这时有:1 < 2 < 6,1 < 3 < 6, 但是2 ≮ 3. 如下例子中, Proposer P2 完成 phase-1 后, P3 无法完成 phase-1, 因为Acceptor A2 上3 ≯ 2, 于是放弃 P3, 使用 P6 完成 phase-1, 进而再完成 phase-2, 完成一次commit.

在应用上, 偏序的rnd给 Paxos 等一致性算法提供了非常大的扩展空间, 它将一维的先后关系扩展到多维度的先后关系(类似多维的时间).

例如对一个存储系统可以设置 2 组 rnd: 一组 Proposer 只选择 2ⁿ 的rnd, 希望执行事务A; 一组 Proposer 只选择 3ⁿ 的rnd, 希望执行事务B; 于是这两组 Proposer 之间互斥, 保证了最多只有一个事务成功(不会产生 Paxos 中的活锁). 而组内多个 Proposer 之间又可以形成高可用的互备(不存在 2PC 中 Coordinator 宕机的问题).

所以, 偏序 Paxos 可以提供 2PC 的事务互斥性, 也提供了 Paxos 的故障容忍, 可以将分布式DB(例如spanner) 中的 2PC Paxos 的两层架构简化成一层.

[1]Paxos: https://en.wikipedia.org/wiki/Paxos_(computer_science)[2]偏序关系: https://en.wikipedia.org/wiki/Partially_ordered_set[3]2PC: https://en.wikipedia.org/wiki/Two-phase_commit_protocol

• vivo大数据日志采集Agent设计实践

• 直播混沌工程之故障演练实践总结 | 助力S12全球总决赛

• 字节跳动 kube-apiserver 高可用方案 KubeGateway

• AI绘画火了！一文看懂背后技术原理

• B站直播的自研P2P实践 | 助力S12英雄联盟总决赛

本文由高可用架构转载。技术原创及架构实践文章，欢迎通过公众号菜单「联系我们」进行投稿