Paxos 协议：多状态机的一致性解决方案

文章目录

• 问题背景
• 中心化架构带来的单点失败问题
• 复制数据
• 数据一致性如何解决
• • 简化问题为多份状态机
• 如何确保副本收到相同顺序的相同指令
• 如何应对主结点宕机
• • 草稿方案
  • 问题
  • 灵感：半数以上结点的两个分区必有重合
• Paxos： 视图变化算法
• Paxos 概览
• Paxos 详解
• • Paxos 第一阶段（Phase 1）
  • Paxos 第二阶段（Phase 2）
  • Paxos 第三阶段 ( Phase 3)
  • Paxos 通信超时应对方案
  • Paxos 图解（一图胜千言）
  • Paxos 几个待思考的问题
  • • 多个 Leader 出现的情形
    • 协议执行过程中发生结点宕机
• 总结

问题背景

在 正确理解二阶段提交（Two-Phase Commit） 的文章中， 笔者解析了二阶段提交协议是如何满足一个分布式原子性提交协议应该具有的性质。

二阶段提交协议（Two-Phase Commit）出现的本质原因是， 分布式系统中不同的结点有不同的功能， 不同功能背后对应的数据集不同， 不同功能又需要一定的协同性。

二阶段协议中， 一个比较严重的问题是， 如果遇到结点宕机， 必须等到所有结点恢复以后， 协议才能继续。 于是这里就引出了如何提高分布式系统可用性的问题。

中心化架构带来的单点失败问题

以 正确理解二阶段提交（Two-Phase Commit） 中提到的跨行转账场景为例。 银行A， 银行B ， 事务协调者 TC 都拥有并维护着各自的唯一的， 权威的账目数据集。 任何一个结点停止工作都会导致其他结点也无法继续工作。

所以我们希望提高分布式系统的可用性。

复制数据

很自然的方案时将核心数据复制多份，由多个结点维护， 万一有部分结点失效， 我们希望其他结点还能正常工作

数据一致性如何解决

只要存在多份数据，就一定会面临如何解决数据一致性的问题。 当客户通过请求修改了其中一份数据以后， 其他的数据该如何保持一致？

简化问题为多份状态机

任意的服务器结点本质上都是一个状态机。

• 磁盘， 内存, CPU 缓存中的数据都属于状态
• 通过指令， 状态机的状态发生变化
• 用户可以通过请求触发状态机执行特定的指令，从而进一步触发状态转化

通过复制产生了多个位于不同结点的状态机

• 每一个状态机副本必须接受到顺序相同的指令集
• 如果每一个指令所导致的状态是确定的（非随机）， 副本状态机在执行了相同的指令以后， 最终会达到相同的状态。

如何确保副本收到相同顺序的相同指令

首先可以指定一个特殊的副本结点作为主结点

将其他的结点作为这个主结点的备份

客户统一将请求都发送给当前的主结点

主结点负责：

• 为接受到的客户指令确定唯一排序
• 把具有唯一顺序的指令集发送给它的备份结点
• 响应客户

如何应对主结点宕机

显而易见： 选出新的主结点

草稿方案

为每一个结点标注一个编号， 当主结点宕机时， 现存结点中编号最小的成为主结点

在主结点宕机后， 剩余结点需要相互通信， 判断哪些结点还存活

问题

• 通信不可靠， 相互之间发送的数据可能发生丢失
  • 后果： 可能产生多个主结点
• 通信可能存在时延
  • 后果： 可能产生多个主结点
• 网络分区（部分结点相互可通信， 另外一部分结点相互可通信）
  • 后果： 可能产生多个主结点

灵感：半数以上结点的两个分区必有重合

要求： 至少要有超过半数以上的结点同意才能选出新的主结点

好处：多数结点所在的分区只能有一个， 如果存在两个以上的分区选出了两个主结点， 那么多个分区中， 一定存在重合的结点， 重合的结点可以发现选出了多个主结点，进而“拉响警报”

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！