分布式一致性-2PC、3PC和PAXOS算法

2PC

2PC（Two-Phase Commit），即二阶段提交。其将事务提交过程分为两个阶段来进行处理，执行流程如下。

阶段一：提交事务请求

  1. 事务询问

    协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。

  2. 执行事务

    各参与者节点执行事务操作，并将Undo和Redo信息记入事务日志中。

  3. 各参与者向协调者反馈事务询问的响应

    如果参与者成功执行了事务操作，那么就反馈给协调者Yes响应，表示事务可以执行；如果参与者没有成功执行事务，那么就反馈给协调者No响应，表示事务不可以执行。

1

阶段二：执行事务提交

在阶段二中，协调者会根据各参与者的反馈情况来决定最终是否可以进行事务提交操作，正常情况下，包含以下两种情况。

执行事务提交

协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务提交。

  1. 发送提交请求

    协调者向所有参与者节点发出Commit请求。

  2. 事务提交

    参与者接收到Commit请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。

  3. 反馈事务提交结果

    参与者在完成事务提交之后，向协调者发送Ack消息。

  4. 完成事务

    协调者接收到所有参与者反馈的Ack消息后，完成事务。

中断事务

假如任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无发接收到所有参与者的反馈响应，那么就会中断事务。

  1. 发送回滚请求

    协调者向所有参与者节点发出Rollback请求。

  2. 事务回滚

    参与者接收到Rollback请求后，会利用其在阶段一种记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。

  3. 反馈事务回滚结果

    参与者在完成事务回滚之后，向协调者发送Ack消息。

  4. 中断事务

    协调者接收到所有参与者反馈的Ack消息后，完成事务中断。

2

问题

  1. 同步阻塞

    无论是在一阶段还是在二阶段，所有参与者资源和协调者资源都是被锁定的，所有参与事务操作的逻辑都处于阻塞状态。

  2. 单点问题

    由于协调者的重要性，一旦协调者发生故障，参与者会一直阻塞下去。尤其是在第二阶段，所有的参与者都处于锁定事务资源的状态中，无法继续完成事务操作。

3PC

3PC（Three-Phase Commit），即三阶段提交，是2PC的改进版。其将二阶段提交协议的 执行事务提交过程一分为二，形成了由CanCommit、PreCommit和do Commit三个阶段组成的事务处理协议。除此之外，3PC支持参与者超时机制（在2PC中只有协调者拥有超时机制）。

阶段一：CanCommit

  1. 事务询问
  2. 各参与者向协调者反馈事务询问的响应

阶段二：PreCommit

在阶段二中，协调者会根据各参与者反馈进行事务的预提交操作。根据参与者的反馈有两种可能。

执行事务预提交

如果协调者获得所有参与者的反馈都为Yes，就会执行事务预提交。

  1. 发送预提交请求
  2. 事务预提交
  3. 各参与者向协调者反馈事务执行的响应

中断事务

任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。

  1. 发送中断请求
  2. 中断事务

阶段三：doCommit

和2PC的阶段二相似。

相较于2PC，3PC支持参与者的超时机制，降低了参与者的阻塞范围。另外，通过CanCommit、PreCommit、DoCommit三个阶段的设计，相较于2PC而言，多设置了一个缓冲阶段保证了在最后提交阶段之前各参与节点的状态是一致的。

PAXOS

原文地址：http://www.duanle.net/upload/2021/01/paxos-simple-cd8f248edfcb4ab99d804a04a72c9c74.pdf

在paxos算法中，有三个角色：

  • Proposer
  • Acceptor
  • Learner

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。

还有一个重要的概念叫提案（Proposal）。最终要达成一致的value就在提案里。

3

问题描述

假设有一组可以提出value（value在提案中）的进程集合。一个一致性算法需要保证提出的多个value中只有一个被选定。如果没有value被提出，就不该有value被选定。如果一个value被选定，那么所有进程都应该能学习（learn）到这个被选定的value。对于一致性算法，安全性要求如下：

  1. 只有被提出的value才能被选定；
  2. 只有一个value选定；
  3. 如果某个进程任务某个value被选定了，那么这个value必须是真的被选定的那个。

Paxos的目标：保证最终有一个value会被选定，当value被选定后，进程最终也能获取到被选定的value。

推导过程

最简单的方案-只有一个Acceptor

假设只有一个Acceptor，只要Acceptor接受它收到的第一个提案，则该提案被选定，该提案里的value就是被选定的value。这样就保证只有一个value被选定。但是，如果这个唯一的Acceptor出现问题，那么整个系统就无法工作了。因此，需要多个Acceptor。

4

那么，如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢？

下面开始寻找解决方案。

如果我们希望即使只有一个Proposer提出了一个value，该value也最终被选定。那么，就得到下面的约束：

P1：一个Acceptor必须接受它收到的第一个提案。

但是这又会引出一个新的问题：如果每个Proposer分别提出不同的value到不同的Acceptor。根据P1，Acceptor分别接受自己收到的value，就会导致不同的value被选定，出现不一致。

5

刚刚是因为**一个提案只要被一个Acceptor接受，则该提案的value就被选定了**才导致了出现上面不一致的问题。因此，我们需要加一个规定：

一个提案需要被半数以上的Acceptor接受。

这个规定又暗示了：**一个Acceptor必须能够接受不止一个提案！**不然可能导致最终没有value被选定。比如上图的情况。value1、value2、value3都没有被选定，因为它们都只被一个Acceptor的接受。

这时，我们的**提案=value的方案需要重新设计，需要给每个提案加上一个提案编号，表示提案被提出的顺序。与时提案=[编号，value]**。

虽然我们允许多个提案被选定，但是必须保证所有选中的提案value相同，否则又会出现不一致。所以结合提案编号，可以给出如下约定：

P2：如果某个value=v的提案被选中了，那么所有编号更高的被选中的提案value也必须是v。

一个提案只有被Acceptor接受才可能被选定，因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。

P2a：如果某个value=v的提案被选中了，那么所有编号更高的被Acceptor接受的提案value也必须是v。

但是由于通信是异步的，一个提案可能会在其中某个Acceptor还没有接收到提案时就被选定了。

6

如上图所示，在Acceptor1没有收到任何提案的情况下，其他4个Acceptor已经接受了来自Proposer 2的提案[M1,V1]，而此时，Proposer1产生了一个具有其他value值并且编号更高的提案[M2,V2]，并发送给了Acceptor1。根据P1约定（一个Acceptor必须接受它收到的第一个提案），就需要Acceptor1接受提案，但是这与P2a矛盾，因此如果要同时满足P1和P2a，需要对P2a进行如下强化：

P2b：如果某个提案被选定了，那么之后任何Proposer提出的编号更高的提案的value必须也是v。

因为一个提案必须在被Proposer提出后才能被Acceptor批准，因此P2b包含了P2a，进而包含了P2。

那么，如何确保在某个value为v的提案被选定后，Proposer提出的编号更高的提案的value都是v呢？（具体请看《从PAXOS到zookeeper分布式一致性原理与实践》中的数学归纳法证明。）

只要满足P2c即可：

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

  • S中每个Acceptor都没有接受过编号小于M的提案。
  • S中Acceptor接受过的最大编号的提案的value为v。

Proposer 生成提案

为了满足P2c，这里有个比较重要的思想：Proposer生产提案之前，应该先去学习已经被选定或者可能被选定的value，然后以该value作为自己提出的提案的value。如果没有value被选定，Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个Prepare请求实现的。

于是我们得到了如下的提案生成算法：

  1. Proposer选择一个新的提案编号M，然后向某个Acceptor集合（半数以上）发送请求，要求该集合中的每个Acceptor做出如下响应：

    1. 向此Proposer承诺不在接受任何编号小于M的提案。
    2. 如果Acceptor已经接受过提案，那么就向Proposer响应已经接受过的编号小于M的最大编号的提案。

    我们将该请求称为编号为M的提案的Prepare请求。

  2. 如果Proposer收到了来自半数以上的Acceptor响应结果，那么它就可以生成编号为M，value为V的提案[M, V]。这里的V是所有的响应中编号最大的提案的value，如果所有的响应中都没有提案，那么此时V可以有Proposer自己选择。

    生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。我们称改请求为Accept请求。

Acceptor接受提案

一个Acceptor可能会受到来自Proposer的两种请求，分别是Prepare请求和Accept请求，对这两类请求做出响应的条件分别如下。

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

因此，对Acceptor逻辑处理的约束条件，可以定义如下：

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

如果Acceptor收到一个编号为M的Prepare请求，在此之前它已经响应过编号大于M的Prepare请求。根据P1a，该Acceptor不能接受编号为M的提案。因此，该Acceptor可以忽略编号为M的Prepare请求。当前，也可以回复一个error，让Proposer尽早知道自己的提案不会被接受。

因此，一个Acceptor只需要记住：

  1. 已接受的编号最大的提案。
  2. 已响应的请求的最大编号。

7

算法陈述

结合Proposer和Acceptor对提案的处理逻辑，得到如下两个阶段：

阶段一：

  1. Proposer选择一个提案编号M，然后向半数以上的Acceptor发送编号为N的Prepare请求。
  2. 如果一个Acceptor收到一个编号为M的Prepare请求，且M大于该Acceptor已经响应过的所有Prepare请求编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于M的提案。

阶段二：

  1. 如果Proposer收到半数以上Acceptor对其发出的编号为M的Prepare请求的响应，那么它就会发送一个Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
  2. 如果Acceptor收到一个针对编号为M的提案的Accept请求，只要该Acceptor尚未对编号大于M的Prepare请求做出响应，它就可以通过这个提案。

8

Learner获取提案

9

通过选取主Proposer保证算法的活性

10

为了保证算法的活性，避免上述死循环，必须选择一个主Proposer，并规定只有主Proposer才能提出议案。这样一来，只要主Proposer和过半的Acceptor能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准。

参考资料