分布式事务

发表于 更新于 分类于
本文字数： 12k 阅读时长 ≈ 11 分钟
简单整理了分布式事务相关知识，内容包括：ACID到CAP/BASE，2PC二阶段提交，3PC三阶段提交，Paxos算法等。

分布式事务

一. 从ACID到CAP/BASE

1.1 ACID

数据库事务和ACID可以参看：《高性能MySQL》（一）架构和历史 中事务章节。

1.2 什么是分布式事务

分布式数据库中，数据分散在不同的机器上，分布式事务中事务的参与者、支持事务的服务器、资源服务器以及事务管理器可能分别位于不同的节点上。

思考如何实现分布式的事务处理？

首先我们要把分布式事务看作一组分布式的操作序列，即一组子事务，所以分布式事务也具有ACID的事务特性。

实现分布式事务，保证数据的严格一致性时必然要牺牲掉部分系统可用性。

1.3 CAP

CAP理论：一个分布式系统不可能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance），最多同时满足其中两项。

  • 一致性：分布式中指数据在多个副本间能否保持一致。对一个数据更新且执行成功后，所有用户都要能读到最新的值。
  • 可用性：系统服务必须一直处于可用的状态，用户的每个操作请求总是能在有限的时间内返回结果。系统存在一个合理的响应时间，否则就会使用户对系统失望。
  • 分区容错性：分布式系统在遇到任何网络分区故障时，仍要保证对外提供满足一致性和可用性的服务。

对于分布式系统来说，分区容错性是一个最基本的要求，因为分布式必然要把组件部署到不同的节点，网络问题必定会出现，所以架构设计师往往需要把精力花在如何根据业务特点在一致性和可用性之间寻求平衡。

1.4 BASE理论

BASE 是 Basically Available（基本可用），Soft state（软状态）和 Eventually consistent（最终一致性），是对CAP中一致性和可用性权衡的结果，核心思想是即使无法做到强一致性（Strong consistency），每个应用都可以根据自身业务特点采用适当的方式来使系统最终一致性（Eventual consistency）。

基本可用，指分布式系统在出现不可预知的故障时，允许损失部分可用性，但这不等价于系统不可用：

  • 响应时间上的损失：如正常情况下，搜索引擎要在0.5秒内返回给用户查询结果，但由于故障导致响应时间增加到1到2秒。
  • 功能上的损失：如正常情况下，消费者能在商城平台顺利完成每一笔订单，但在一些节日购物高峰为了保证系统稳定，部分消费者可能被引导到一个降级页面。

弱状态：也叫软状态，指允许系统中的数据存在中间状态，并认为该中间状态的存在不影响系统整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程出现延时。

最终一致性：系统中所有的数据副本，经过一段时间的同步后，最终能够达到一个一致的状态。最终一致性的5种变种：

  • 因果一致性（Causial consistency）：进程A在更新完某个数据后通知了进程B，进程B能读取到A更新后的最新值，如果B要对数据进行更新要基于此最新值，即不能发生丢失更新的情况；而与此无关的进程C无此限制。
  • 读己之所写（Read your writes）：进程A更新一个数据后，自己总能访问更新后的最新值，是一种特殊的因果一致性。
  • 会话一致性（Session consistency）：系统保证在同一个有效的会话中实现读己之所写的一致性。
  • 单调读一致性（Monotonic read consistency）：如果一个进程从系统中读出一个数据后，系统对于该进程后续的任何数据访问都不应该返回更旧的值。
  • 单调写一致性（Monotonic write consistency）：系统保证来自同一个进程的写操作被顺序的执行。

现代的关系型数据库中，往往会采用同步和一步的方式来实现主备数据复制技术：

  • 同步方式：数据的复制过程通常是更新事务的一部分，因此在事务完成后，主备数据库的数据就会达到一致。
  • 异步方式：备库的更新往往存在延时，取决于事务日志在主备数据库之间传输的时间长短，如果时间过久或传输中出现异常导致无法及时将事务应用到备库，就会导致数据不一致。

BASE理论不同于传统事务ACID的强一致性模型，提出牺牲强一致性来获得可用性，允许数据在一段时间内不一致，但最终达到一致性状态。

二. 一致性协议

有很多的经典的一致性协议和算法来解决分布式一致性问题，最著名的有二阶段提交协议、三阶段提交协议和Paxos算法。

2.1 二阶段提交-2PC

2PC，即二阶段提交，Two-Phase Commit 的缩写，为了使分布式系统下所有的节点在进行事务处理过程中能保持原子性和一致性而设计的算法。目前大部分关系型数据库都采用2PC来完成分布式事务处理。

执行流程：

  • 阶段一：提交事务请求（也叫投票阶段）
    1. 事务询问：协调者向所有参与者发送事务内容，询问是否可以执行事务提交操作，等待各参与者响应。
    2. 执行事务：各参与者执行事务操作，并将 Undo 和 Redo 信息记入事务日志。
    3. 各参与者向协调者反馈事务询问的响应：参与者成功执行了事务操作，反馈给协调者Yes响应，表示事务可以执行；若未执行成功，反馈No。
  • 阶段二：执行事务提交（所有参与者都反馈Yes，进行阶段二）
    1. 发送提交请求：协调者向所有参与者节点发出 Commit 请求。
    2. 事务提交：参与者收到 Commit 请求，正式执行事务提交操作，在完成提交后释放事务资源。
    3. 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送 Ack 消息。
    4. 完成事务：协调者收到所有参与者的 Ack 消息后，完成事务。
  • 中断事务：当某个参与者反馈了No响应、或等待接收所有参与者反馈超时之后，执行中断事务
    1. 发送回滚请求：协调者向所有参与者节点发出 Rollback 请求。
    2. 事务回滚：参与者接收到 Rollback 请求后，利用其在阶段一中记录的 Undo 信息来执行事务回滚操作，并释放事务占用资源。
    3. 反馈事务回滚结果：参与者完成回滚后，向协调者发送 Ack 消息。
    4. 中断事务：协调者收到所有参与者反馈的 Ack 消息后，完成事务中断。

2PC的核心是每个事务都采用先尝试后提交的处理方式，可以看作一个强一致性算法。

优缺点：

  • 优点：原理简单，实现方便。
  • 缺点：同步阻塞、单点问题、脑裂、太过保守
    • 同步阻塞：在二阶段的提交过程，所有参与该事务操作的逻辑都处于阻塞状态，各个参与者在等待其他参与者响应的过程无法进行其他操作。
    • 单点问题：协调者太过重要，一旦出现问题整个流程就无法运作，如果是在阶段二出现问题，更会导致参与者都处于锁定事务资源的状态。
    • 数据不一致：在阶段二执行事务提交时，当协调者向所有参与者发生Commit请求后，发生局部网络异常或是协调者自身未发送完即崩溃，导致只有部分参与者收到了Commit请求。收到的提交事务，未收到的无法提交，出现数据不一致现象。
    • 太过保守：参与者出现故障而导致协调者始终无法获取到所有响应，此时只能依靠协调者自身的超时机制来判断是否需要中断事务，显得过于保守，没有完善的容错机制，导致一个节点的失败导致整个事务失败。

2.2 三阶段提交-3PC

3PC，即三阶段提交，Three-Phase Commit的缩写，针对2PC的缺陷进行了优化，将2PC的提交事务请求过程一分为2。

执行阶段：

  • 阶段一：CanCommit
    1. 事务询问：协调者向所有参与者发送一个包含事务内容的 canCommit 请求，询问是否可以执行事务提交操作，并开始等待各参与者响应。
    2. 各参与者向协调者反馈事务询问的响应：参与者接收到 canCommit 请求后，若判断自己可以顺利执行事务则反馈Yes响应，并进入预备状态，否则反馈No响应。
  • 阶段二：PreCommit
    • 执行事务预提交：协调者收到所有Yes反馈
      1. 发送预提交请求：协调者向所有参与者发送一个包含事务内容的 preCommit 请求，并进入 Prepared 阶段。
      2. 事务预提交：参与者接收到 preCommit 请求后，执行事务操作，并将 Undo 和 Redo 信息记入事务日志。
      3. 各参与者向协调者反馈事务执行的响应：参与者成功执行了事务操作，反馈给协调者 Ack 响应，同时等待最终指令（commit或abort）。
    • 中断事务：任意一个参与者反馈了No响应、或等待超时后仍未收到所有参与者的反馈响应
      1. 发送中断请求：协调者向所有参与者发送 abort 请求。
      2. 中断事务：无论是收到协调者的 abort 请求，或是等待协调者请求超时，参与者都会中断事务。
  • 阶段三：doCommit
    • 执行提交：协调者处于正常状态，且收到了所有参与者的 Ack 响应
      1. 发送提交请求：协调者将从预提交状态转换为提交状态，并向所有参与者发送 doCommit 请求。
      2. 事务提交：参与者收到 doCommit 请求，正式执行事务提交操作，完成提交后释放事务资源。
      3. 反馈事务提交结果：参与者完成事务提交后，向协调者发送 Ack 消息。
      4. 完成事务：协调者收到所有参与者的 Ack 消息后，完成事务。
    • 中断事务：协调者处于正常状态，且有任一的参与者反馈了No响应，或者等待超时后仍未收到所有参与者响应
      1. 发送中断请求：协调者向所有参与者发送 abort 请求。
      2. 事务回滚：参与者接收到 abort 请求后，利用其在阶段二中记录的 Undo 信息来执行事务回滚操作，并释放事务占用资源。
      3. 反馈事务回滚结果：参与者完成回滚后，向协调者发送 Ack 消息。
      4. 中断事务：协调者收到所有参与者反馈的 Ack 消息后，完成事务中断。

进入阶段三后可能会出现两种故障：

  • 协调者出现问题
  • 协调者和参与者之间网络出现故障

最终都会导致参与者无法及时收到 doCommit 请求或 abort 请求，这时参与者会在等待超时后继续进行事务提交。

优缺点：

  • 优点：相较2PC降低了参与者的阻塞范围，能够在出现单点故障后达成一致。
  • 缺点：3PC在去除阻塞的同时也带来了新问题，就是在参与者收到 preCommit 请求后，如果网络出现分区，这时协调者所在的节点和参与者无法进行正常的网络通信，这个参与者仍会进行事务的提交，导致了数据不一致性。

2.3 Paxos 算法

2.3.1 什么是 Paxos ？

  • Paxos 算法由 Leslie Lamport 于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题的最有效算法之一。
  • Paxos 算法解决了分布式系统中发生任何的机器宕机或网络异常，都不会破坏整个系统的一致性。
  • Paxos算法支持分布式节点角色之间的轮换，避免了分布式单点的出现，既解决了无限期等待问题，也解决了脑裂问题。

集群环境下，常常会有一个中心（Leader），如ZK的Leader节点或ES的Master节点。当网络通信故障导致选举出多个Leader时，就是所称的大脑分裂现象。

ZK采用过半原则，达到了要么没有Leader要么只有一个Leader来避免脑裂现象。集群节点数是奇数。

1
古希腊有一个叫 Paxos 的小岛，岛上采用议会的形式来通过法令，议员间通过信使进行消息的传递，议员或信使都是兼职的，随时可能离开议会厅，信使可能会重复的传递消息，也可能一去不回。议会协议要保证在这种情况下仍能正确的产生法令，并且不出现冲突。

Paxos算法的核心是一个一致性算法，即 Lamport 的论文 The Part-Time Parliament 中提到的 synod 算法。

Paxos与Raft的关系？

raft是落地的分布式一致性算法，Paxos是理论。raft核心算法可以看作是multi paxos的一个应用。

2.3.2 拜占庭将军问题

1
2
3
拜占庭将军问题：

	拜占庭帝国有多支军队，不同军队的将军之间需要制定一个统一的行动计划，从而做出进攻或撤退的决定，各个将军在地理上被分割开，只能依靠通讯员进行联络。通讯员中可能存在叛徒，可以任意的篡改消息。

理论上来说，在异步系统和不可靠通道上来达到一致性状态是不可能的，因此往往假设信道是可靠的。现实中，大部分系统都部署在同一个局域网，消息被篡改的情况比较罕见；硬件或网络原因导致的消息不完整问题，只需一套简单的校验算法即可避免。因此实际工程实践中，可以假设不存在拜占庭将军问题，我们需要什么样的算法来保证一致性？

2.3.3 背景

Paxos的任务是协同一堆机器达成一致性，比如一个机器接收了一个文件，其余机器也要复制过去。

分布式系统一致性问题最终都是分布式存储一致性，集群的高可靠性都要建立在不太可靠的硬件上：

  • 磁盘：4%年损坏率
  • 服务器宕机时间：0.1%或更久
  • IDC间丢包率：5%~30%

分布式存储一致必须用冗余的方式来在廉价的硬件基础上实现高可靠。冗余依赖多副本策略，副本之间通过Paxos来保证一致性。

多副本的数据丢失风险：

  • 1副本：~ 0.63%
  • 2副本：~ 0.00395%
  • 3副本：< 0.000001%
  • n副本：~ x^^^n (x = 单副本损坏率)

2.3.4 不完美的复制策略

不太完美的复制策略：

  • 主从异步复制：

    • 应用：MySQL的binlog复制

      1. Master接收到写请求。
      2. Master写入磁盘。
      3. Master应答OK。
      4. Master复制数据到从库。

    • 优点：最简单。

    • 缺点：不可靠。客户端收到一个数据同步信息，与数据真正复制到全部机器在时间上有空隙。如果这段时间Master机器宕机或磁盘损坏，会导致数据丢失。

  • 主从同步复制：

    • 流程：
      1. Master接收到写请求。
      2. Master复制日志到从库。
      3. 从库此时可能阻塞。
      4. 客户端一直等待应答OK，直到所有从库返回。
    • 优点：完整可靠。
    • 缺点：系统中若有任一机器宕机，就会导致写入无法继续，可用性非常糟糕。

  • 主从半同步复制：

    • 流程：
      1. Master接收到写请求。
      2. Master复制日志到从库。
      3. 从库此时可能阻塞。
      4. 当1<=x<=n个从库返回OK，则返回客户端。
    • 优点：兼容前两个，高可靠和高可用。1台机器宕机不会导致整个系统无法写入。
    • 缺点：从库可能不完整。如数据a复制到从库1，数据b复制到从库2，此时Master挂掉，需要从某个从库恢复数据，但任一从库都不能保证数据完整。

  • 多数派写（读）：每条数据必须写入到半数以上的机器上，每次读取数据都必须检查半数以上的机器是否有该数据。

    • 客户端写入 W >= N/2+1 个节点，不需要Master。
    • W + R > N; R >= N/2+1。
    • 容忍最多(N-1)/2个节点损坏。
    • 仍不完美，节点1和2都写入了a=x，下次更新时节点2和3写入了a=y，此时一个要进行读取a的客户端联系到了节点1和2会看到不同的数据。所以还要为每次写入增加一个全局递增的时间戳，忽略小时间戳的数据从而避免歧义。

即使加了时间戳后，此方案仍还有问题。

1
2
3
4
5
# 节点1和2写入
a=x，1
# 节点3写入成功，客户端挂掉
a=y 2
# 此时另一个客户端读取，仍有两种值

Paxos通过2次不严谨的多数派读写实现了严谨的强一致性算法。

2.3.5 多数派到Paxos

假想的存储服务：

  • 一个有3个存储节点的集群。
  • 使用多数派读写的策略。
  • 只存储1个变量i。
  • i的每次更新对应多个版本：i1、i2、i3
  • 支持三个命令：
    1. get：读取最新的i。
    2. set n：设置下个版本的i值。
    3. inc n：对i加n，也生成一个新版本。

set命令是一个多数派写。inc是最简单的事务操作：

  1. 通过多数派读，读取到最新的i。
  2. i2 = i1 + n
  3. set i2

如果有两个客户端同时并发做inc操作，多数派读写实现中必然会产生一个Y客户端覆盖X客户端的问题。

图片来自《可靠分布式系统-paxos的直观解释》

为了解决问题，需要新加一个功能，系统会记录最后一个做写前读取的操作，只允许其可以进行后续写入。这样Y做完写前读取操作后，系统会阻止过期的X的写入。

总结，Paxos的特点：

  • 基于多数派读写。
  • 每个Paxos实例用来存储一个值。
  • 用两轮RPC来确定一个值。
  • 值确定后不能被修改。确定指被多数派接受写入。
  • 保证强一致性。
  • 核心是解决网络延迟/乱序的问题，而不是存储不可靠和消息错误，后者是数据校验层面的事情。

优化：

  • Classic Paxos：1个实例确定一个值，写入需要两轮RPC。
  • Multi Paxos：约为1轮RPC，确定一个值（第一次RPC做了合并）。
  • Fast Paxos：
    • 没冲突：1轮RPC确定一个值。
    • 有冲突：2轮RPC确定一个值。

2.3.6 Paxos算法描述

对于一个一致性算法来说要保证几点：

  • 在这些被提出的提案中，只有一个会被选定。
  • 如果没有提案被提出，就不会有被选定的提案。
  • 当一个提案被选定后，进程应该可以获取被选定的提案信息。

一致性的安全性需求：（Paxos的目标就是保证最终有一个提案被选定）

  • 只有被提出的提案才能被选定。
  • 只能有一个值被选定。
  • 如果某个进程认为某个提案被选定了，这个提案必须是真的被选定的那个。

在该一致性算法中，有三种参与角色：

  • Proposer（提议人），可以理解为客户端，发起Paxos的进程。
  • Acceptor（接收人），可以理解为存储节点，接收、处理和存储消息。
    • last_rnd：是Acceptor存储最后一次进行写前读取的Proposer。
    • v：最后被写入的值。
    • vrnd：与v是一对，记录了v被写入的Round。
  • Learner，Acceptor会发送Phase-3到所有该角色，通知一个值被确定了。通常Proposer就是Learner。

Quorum指多数派，即半数以上的Acceptor。Round标识一次算法实例，每个Round是2次多数派读写，每个Proposer都必须生成全局单调递增的Round，从而区分开先后和Proposer。

v和vrnd用来恢复一次未完成的Paxos，通过vrnd决定哪些值是最后写入的。

Phase-1：第一次多数派读写，写前读取过程在Acceptor上写入一个标识，表示后面要写入，并读出是否有未完成的Paxos还在运行。若有则尝试恢复。

1
2
3
4
5
6
request:
	rnd: int
response:
	lat_rnd: int
	v: "xxx",
	vrnd: int
  • 如果请求的rnd小于last_rnd，拒绝请求。
  • 将请求的rnd保存到本地的last_rnd。此后这个Acceptor只接受带有这个rnd的Phase-2请求。
  • 返回应答，带上之前的last_rnd和已经接受的v。

Proposer收到X的Quorum多数派应答，认为可以继续进行，否则会阻塞。

  • 如果应答中的last_rnd大于发出的rnd，退出。

  • 如果应答不够多数派，退出。

  • 所有应答的v都为空，可以写入自己的v。表示系统之前是空，此时Proposer继续将要写入的值在Phase-2中真正写入到半数的Acceptor中。

  • 某个应答包含被写入的v和vrnd，Proposer认为有其他Proposer正在运行。虽然X不知道对方是否已经结束，但已经不能再修改。X将看到的最大vrnd对应的v作为X的Phase-2将要写入的值。

Phase-2：第二次多数派读写，Proposer将它选定的值写入到Acceptor中，这个值可能是Proposer自己要写入的值，也可能是它从某个Acceptor上读到的v。

1
2
3
4
5
6
# Proposer发送
request:
	v: "xxx",
	rnd: int
response:
	ok: bool
  • 在收到P1应答，发送P2请求的这段时间，可能有其他Proposer又完成了一个rnd更大的P1，所以此时X不一定能成功完成P2。
  • Acceptor通过比较P2请求中的rnd和自己本地的rnd来决定是否有权写入。
    • 拒绝rnd不等于Acceptor的last_rnd的请求。
    • 将P2请求中的v写入本地。
    • last_rnd==rnd保证了此过程没有其他Proposer写入。

2.3.7 Paxos运行案例

第一种，无冲突时：

第二种，X和Y同时运行，Y导致X中断：

  • X成功完成了写前读取，将rnd=1写入了左边2个Acceptor。
  • Y用更大的rnd=2覆盖，并写入到右边的2个Acceptor。
  • X以为自己还能继续P2，但只有左边第一个成功运行，中间的拒绝了X。
  • Y则对右边两个Acceptor成功运行了P2，成功写入内容。

X因为P2没有执行成功，需要重新再尝试一遍，它将rnd更新为3：

  • X成功在左边两个Acceptor上读取到写入的值为两个：v=x, vrnd=1 和 v=y, vrnd=2。此时X不能再修改已存在的值，只能尝试修复操作。
  • X选择多数派的值v=y, 并使用rnd=3继续运行，最终把v=y, vrnd=3写入到所有Acceptor。

多个Proposer并发对一个值进行写入时，可能会互相覆盖对方的rnd，不断提升自己的rnd，导致死循环。

2.3.8 Paxos优化

  • Multi-Paxos：Paxos每写入一个值就需要两轮的RPC，所以第一个优化是用一次RPC为多个Paxos实例运行Phase-1。每个Paxos只须单独运行Phase-2。
  • Fast-Paxos：通过增加Quorum的数量来达到一次RPC就能达成一致性的效果。如果一次未达成则会退化到Classic-Paxos。
    • Proposer直接发送Phase-2.
    • rnd为0，保证一定小于任何Classic-Paxos的rnd，从而在出现冲突时，安全的回退。
    • Acceptor只在v为空时才接收Fast Paxos请求的P2请求。
    • 当发生冲突，回退到Classic-Paxos，用标准的rnd>0重新运行。

Fast-Paxos需要扩大Quorum的值，否则会在回退到Classic阶段选择错误的值。比如5个节点，Quorum为3。X的Fast写入成功导致Y写入中断，此时Y无法得知X0和Y0哪个是被确定的，两者rnd相同。

所以需要让未确定的值不占据多数派，即Fast的多数派需要 > n * 3/4，即被 3/4n + 1个Acceptor接受。 3/4的由来是在最差情况下，达到Fast-Quorum的Acceptor在Classic-Quorum中必须大于半数，才不会导致修复进程选择一个与Fast-Round不同的值。

Fast-Paxos需要更多的Acceptor工作，会导致可用性降低。

2.3.9 算法推导

（1）提案的选定
  • 选定一个唯一提案，最简单的方案是只允许一个 Acceptor 存在，Proposer 只能发送提案给它，Acceptor 选择它接收到的第一个提案，这种方案存在单点故障。
  • 存在多个 Acceptor ：Proposer 向一个 Acceptor 集合发送提案，集合中每个 Acceptor 都可能会批准该提案，当有足够多的 Acceptor 批准这个提案时，就可以认为它被选定了（多数派）。
（2）推导过程

需求：在没有失败和消息丢失的情况下，即使只有一个提案被提出，也要选出一个提案。这就意味着P1：一个 Acceptor 必须批准它收到的第一个提案。这可能会导致每个 Acceptor 都批准了第一个提案，但没有一个提案是多数人批准的。

一个提案需要由半数以上的 Acceptor 批准的需求暗示着一个 Acceptor 必须能够批准不止一个提案。

Paxos 使用一个全局编号来唯一标识每一个被 Acceptor 批准的提案，当一个具有某 Value 值的提案被半数以上的 Acceptor 批准后，即该 Value 被选定了和该提案被选定了。提案变成了一个由编号和 Value 组成的组合体 “【编号, Value】”。

P2：如果编号为M0、Value值为V0的提案被选定了，那么所有比编号M0更高的，且被选定的（被 Acceptor 批准的）提案，其Value值必须也是V0

通信是异步的，一个提案可能会在某个 Acceptor 还未收到任何提案时就被选定了，所以仍需要P1来保证提案会被选定。

P2b：如果一个提案[M0, V0]被选定后，那么之后任何 Proposer 产生的编号更高的提案，其Value值必须也是V0

因为一个提案必须在被 Proposer 提出后才能被 Acceptor 批准，所以P2b包含P2。

（3）数学归纳法证明

需要证明结论：假设某个提案[M0, V0]被选定了，证明任何编号Mn>M0的提案，其Value值都是V0。

我们可以通过对Mn进行第二数学归纳法进行证明，即证明：假设编号在M0到Mn-1之间的提案，其Value值都是V0，证明编号为Mn的提案的Value值也为V0。

因为M0的提案已被选定，意味着肯定存在一个由半数以上的 Acceptor 组成的集合C，都批准了提案。C中的每个 Acceptor 都批准了在M0到Mn-1范围内的提案，并且每个编号在M0到Mn-1之间的被批准的提案，其Value值都是V0。

因为任何包含半数以上的 Acceptor 组成的集合都至少包含一个C的成员，所以如果保持下面P2c的不变性，可以认为编号为Mn的提案的Value值也为V0。

P2c：对于任意的Mn和Vn，如果提案[Mn, Vn]被提出，那么肯定存在一个由半数以上的 Acceptor 组出的集合S，满足以下两个两个条件中的任意一个：

  • 要么，S中不存在任何批准过编号小于Mn的提案的 Acceptor。
  • 要么，选取S中所有 Acceptor 批准的编号小于 Mn 的提案，其中编号最大的哪个提案其 Value 值是 Vn 。

P2c=>P2b=>P2，通过P2和P1保证一致性。

假设提案[M0, V0]被选定了，需要证明在P2c的前提下，对于所有的[Mn, Vn]，存在 Vn = V0 ：（第二数学归纳法）

  1. 当 Mn = M0 + 1 时，因为[M0, V0]被选定了，一定会存在一个 Acceptor 的子集S，S中的 Acceptor 已批准了小于 Mn 的提案，因此 Vn 只能是S中编号小于 Mn 但为最大编号的提案。因为 Mn = M0 + 1 ，所以提案是 [M0, V0] ；同时由于S和通过[M0, V0]的集合都是多数集，所以二者一定存在交集，这样 Proposer 在确定 Vn 取值时一定会选择 V0 。
  2. 编号在 M0 + 1 到 Mn - 1 之间的Value值都为 V0 ，要证明编号为 Mn 的提案的Value值也为 V0 。根据P1c，一定会存在一个 Acceptor 的子集S，S中的 Acceptor 已批准了小于 Mn 的提案，那么编号为 Mn 的提案的Value值只能是S中编号小于 Mn 但为最大编号的提案的值。只要编号落在 M0 + 1 到 Mn - 1 之间，那么Value值就是 V0 ；如果不落在区间内，那肯定是 M0 ，因为S肯定会和批准[M0, V0]的集合有交集，如果编号为 M0 ，那么其Value值也为 V0 。
（4）Proposer 生成提案

对于 Proposer 来说，获取已经被通过的提案远比预测未来可能被通过的提案简单。因此 Proposer 在产生一个编号为 Mn 的提案时，必须要知道当前一个将要或已经被半数以上 Acceptor 批准的编号小于 Mn 的最大提案编号。并且 Proposer 会要求所有 Acceptor 不再批准任何编号小于 Mn 的提案。

提案生成算法：

  1. Proposer 选择一个新的提案编号 Mn ，然后向某个 Acceptor 集合的成员发送请求（即编号为 Mn 的提案的 Prepare 请求），要求该集合中的 Acceptor 做出如下回应。
    • 向 Proposer 承诺，保证不再批准任何编号小于 Mn 的提案。
    • 如果 Acceptor 已经批准过任何提案，那么其就向 Proposer 反馈当前该 Acceptor 已经批准的编号小于 Mn 但为最大编号的那个提案的值。
  2. 如果 Proposer 收到了来自半数以上的 Acceptor 的响应结果，那么它可以产生编号为 Mn 、Value值为 Vn 的提案，Vn 是所有响应中编号最大的提案的 Value 值。还有一种情况，即半数以上都未批准过任何提案，也即响应中不包含任何提案，此时 Vn 值可以由 Proposer 任意选择。

Proposer 发送给 Acceptor 选定的提案期望获得批准的请求叫Accept请求。接受请求的 Acceptor 集合不一定是之前响应Prepare请求的那一个。

（5）Acceptor 批准提案

一个 Acceptor 可能接收到两种来自 Proposer 的请求：

  • Prepare请求：Acceptor 可以在任何时候响应。
  • Accept请求：在不违背Accept现有承诺的前提下，任意响应Accept请求。

P1a：一个 Acceptor 只要尚未响应过任何编号大于 Mn 的Prepare请求，它就可以接受这个编号为 Mn 的提案。

（6）算法优化

假设一个 Acceptor 收到了一个编号为 Mn 的Prepare请求，但此时它已经对大于 Mn 的Prepare请求做出了响应，因此它肯定不会再批准编号 Mn 的提案，所以 Acceptor 没有必要对此请求做出响应，可以选择忽略这种Prepare请求。同理还可以忽略已经批准过的提案的Prepare请求。

这样 Acceptor 只需记住它已经批准的提案的最大编号和它已经做出Prepare请求响应的提案的最大编号，以便再出现故障或节点重启时也能保证P2c的不变性。

对于 Proposer 来说，只要保证不会产生相同编号的提案，可以丢弃任意提案和运行时状态信息。

（7）算法陈述

综上所述，可以得到一个类似二阶段提交的算法执行过程：

  • 阶段一
    1. Proposer 选择一个提案编号 Mn ，然后向 Acceptor 的某个超过半数的子集成员发送编号为 Mn 的Prepare请求。
    2. 如果一个 Acceptor 收到一个编号为 Mn 的Prepare请求，且编号 Mn 大于它已经响应的所有Prepare请求的编号，那么它会将它已经批准过的最大编号的提案作为响应反馈给 Proposer ，同时承诺不会再批准小于编号 Mn 的任何提案。
  • 阶段二
    1. 如果 Proposer 收到来自半数以上的 Acceptor 对于其发出的编号为 Mn 的Prepare请求的响应，它就会发送一个针对[Mn, Vn]提案的 Accept 请求给 Acceptor （ Vn 为收到的响应中编号最大的提案的值，若响应中不包含提案，它可以是任意值）。
    2. 如果 Acceptor 收到此 Accept 请求，只要该 Acceptor 尚未对编号大于 Mn 的Prepare请求做出响应，它就可以通过这个提案。
（8）提案的获取

Learner 获取提案的几种方案：

  1. Learner 获取提案的前提是此提案已被半数以上的 Acceptor 批准。因此最简单的做法是一旦 Acceptor 批准了提案，就把其发送给所有的 Learner 。这种做法会让每个 Acceptor 与所有的 Learner 通信，通信次数至少为二者个数的乘积。
  2. 让所有的 Acceptor 对提案的批准情况统一发送给一个主Learner，主Learner 被通知一个提案已被选定后会负责通知其他 Learner 。此方案通过多加一个步骤，大大减少了通信次数，但带来了主Learner可能发生故障这个隐患。
  3. 针对方案二，将主Learner扩大为特定的Learner集合，从而提高可靠性。
（9）通过选取主Proposer保证算法的活性

Paxos算法可能会出现多个Proposer相互导致对方提案请求被忽略的死循环：

解决方案：选定一个主Proposer，并规定只有主Proposer才能提出议案。

参考：

🔗 《从Paxos到Zookeeper-分布式一致性原理与实践》

🔗 《可靠分布式系统-paxos的直观解释》