分布式系统一致性及Paxos详解

YXiao's Blog

2022-08-05

前言

在分布式系统中，为了保证数据的高可用，通常，我们会将数据保留多个副本(replica)，这些副本会放置在不同的物理机器上。为了对用户提供正确的CRUD等语义，我们需要保证这些放置在不同物理机器上的副本是一致的。

为了解决这种分布式一致性问题，前人在性能和数据一致性的反反复复权衡过程中总结了许多典型的协议和算法。其中比较著名的有二阶提交协议（Two Phase Commitment Protocol）、三阶提交协议（Three Phase Commitment Protocol）和Paxos算法。

分布式事务

在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。由于存在事务机制，可以保证每个独立节点上的数据操作可以满足ACID。但是，相互独立的节点之间无法准确的知道其他节点中的事务执行情况。所以从理论上讲，两台机器理论上无法达到一致的状态。如果想让分布式部署的多台机器中的数据保持一致性，那么就要保证在所有节点的数据写操作，要不全部都执行，要么全部的都不执行。但是，一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果。所以他也就不知道本次事务到底应该commit还是 rollback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。

2PC

两阶段提交主要保证了分布式事务的原子性：即所有结点要么全做要么全不做。所谓的两个阶段是指：第一阶段：准备阶段(投票阶段)和第二阶段：提交阶段（执行阶段）。

二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

准备阶段

事务协调者(事务管理器)给每个参与者(资源管理器)发送Prepare消息，每个参与者要么直接返回失败(如权限验证失败)，要么在本地执行事务，写本地的redo和undo日志，但不提交，到达一种“万事俱备，只欠东风”的状态。

可以进一步将准备阶段分为以下三个步骤：

协调者节点向所有参与者节点询问是否可以执行提交操作(vote)，并开始等待各参与者节点的响应。
参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。（注意：若成功这里其实每个参与者已经执行了事务操作）
各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个“同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个“中止”消息。

提交阶段

如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)

接下来分两种情况分别讨论提交阶段的过程。

当协调者节点从所有参与者节点获得的相应消息都为“同意”时:

2PC_success

协调者节点向所有参与者节点发出“正式提交(commit)”的请求。
参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
参与者节点向协调者节点发送“完成”消息。
协调者节点受到所有参与者节点反馈的“完成”消息后，完成事务。

如果任一参与者节点在第一阶段返回的响应消息为“中止”，或者协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：

2PC_fail

协调者节点向所有参与者节点发出“回滚操作(rollback)”的请求。
参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
参与者节点向协调者节点发送“回滚完成”消息。
协调者节点受到所有参与者节点反馈的“回滚完成”消息后，取消事务。

不管最后结果如何，第二阶段都会结束当前事务。

2PC缺点

二阶段提交看起来确实能够提供原子性的操作，但是不幸的是，二阶段提交还是有几个缺点的：

同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）。
数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

由于二阶段提交存在着诸如同步阻塞、单点问题、脑裂等缺陷，所以，研究者们在二阶段提交的基础上做了改进，提出了三阶段提交。

3PC

三阶段提交（Three-phase commit），也叫三阶段提交协议（Three-phase commit protocol），是二阶段提交（2PC）的改进版本。

3PC

与两阶段提交不同的是，三阶段提交有两个改动点:

引入超时机制。同时在协调者和参与者中都引入超时机制。
在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。

也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。

CanCommit阶段

3PC的CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

PreCommit阶段

协调者根据参与者的反应情况来决定是否可以记性事务的PreCommit操作。根据响应情况，有以下两种可能。

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

发送预提交请求。协调者向参与者发送PreCommit请求，并进入Prepared阶段。
事务预提交。参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
响应反馈。如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

发送中断请求。协调者向所有参与者发送abort请求。
中断事务。参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

DoCommit阶段

该阶段进行真正的事务提交，也可以分为以下两种情况。

执行提交

发送提交请求。协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
事务提交。参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
响应反馈。事务提交完之后，向协调者发送ack响应。
完成事务。协调者接收到所有参与者的ack响应之后，完成事务。

中断事务

协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。

发送中断请求。协调者向所有参与者发送abort请求。
事务回滚。参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
反馈结果。参与者完成事务回滚之后，向协调者发送ACK消息。
中断事务。协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。）

Paxos的提出

为分布式系统设计一个正确的一致性协议是很困难的，了解了2PC和3PC之后，我们可以发现，无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。Google Chubby的作者Mike Burrows说过， *”There is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.* 意即世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整版。

Paxos的理解困境

Paxos究竟在解决什么问题？

这个问题等同于：Paxos如何确定一个不可变变量的取值。取值可以是任意二进制数据，并且一旦确定将不再更改，并且可以被获取到（不可变性、可读取性）。

Paxos如何在分布式存储系统中应用？

我们知道在分布式系统中数据是可变的，用户可以任意的进行增删改查，分布式存储系统为了保证数据的可靠存储，一般会采用多副本的方式进行存储。如果对多个副本执行的操作序列[ $op_1$ , $op_2$ , …, $op_n$ ]不进行任何控制，那网络延迟、超时等各种故障都会导致各个副本之间的更新操作是不同的，这样很难保证副本间的一致性。所以为了保证分布式存储系统数据的一致性，我们希望在各个副本之间的更新操作序列是相同的、不变的，即每个副本执行[ $op_1$ , $op_2$ , …, $op_n$ ]顺序是相同的。我们通过Paxos算法依次来确定不可变变量 $op_i$ 的取值，即第i个操作是什么。每次确定完 $op_i$ 之后，可以让各个副本来执行 $op_i$ ，依次类推。

抽象问题

本文介绍Paxos过程中，希望抽象为这样一个实际问题：即设计一个系统，来存储名称为var的变量。系统内部由多个acceptor组成，负责存储和管理var变量；外部有多个proposal机器，可以任意并发的调用系统api，向系统提交不同的var取值；系统对外的api接口为：propose(var, V) => <ok, f> or <error>，其中f为系统内部已经确定下来的var的取值。

系统需要保证var的取值满足一致性，即var的取值初始为null，而一旦var的取值被确定，则不可以被更改，并且可以一直获取到这个值。

除了一致性以外，系统还需要满足容错性，即可以容忍任意proposal机器出现故障，也可以容忍少数（半数以下）acceptor出现故障。

暂不考虑网络分化、acceptor故障会丢失var信息等其他问题。

系统难点

设计这样一个系统有什么难点呢？

如何管理控制多个proposal的并发执行；
如何保证var变量的不可变性；
如何容忍任意proposal机器故障；
如何容忍半数以下acceptor故障。

确定不可变变量取值 —— 方案一

在方案一中我们先考虑整个系统由单个acceptor组成，通过类似互斥锁的机制，来管理并发的proposal运行。Proposal首先向acceptor申请互斥访问权，然后才能请求acceptor接受自己的取值。而acceptor给proposal发放互斥访问权，谁申请到互斥访问权，就接受谁提交的取值。

这样通过互斥访问权机制，我们可以让proposal按照获取互斥访问权的顺序来依次访问acceptor，一旦acceptor接受了某个proposal的取值，则认为var值被确定，其他的proposal不能再更改。

实现

以下是基于互斥访问权的acceptor实现：

Acceptor保存：
  变量var
  一个互斥锁lock

Acceptor.prepare():
  加互斥锁，给予var的互斥访问权，并返回var的当前取值f。
Acceptor.release():
  释放互斥锁，收回var的互斥访问权。
Acceptor.accept(var, V):
  如果已经加锁，并且var没有取值，则设置var为V，并且释放锁。

propose(var, V)的两阶段实现：

第一阶段：通过Acceptor.prepare()获取互斥访问权和当前var取值，如果无法获取，返回<error>（锁被别人占用）。
第二阶段：根据当前var的取值f，选择执行：
- 如果f为null（以前没有proposal设置过var的值），则通过Acceptor.accept(var, V)提交数据；
- 如果f不为null（接受某个proposal设置过var的值f），则通过Acceptor.release()释放访问权，返回<ok, f>。

方案一总结

所以总结来说方案一是通过Acceptor互斥访问权，能够让Proposal按照获取互斥访问权的顺序序列运行，而不再是并行运行，这样可以简单实现var取值的一致性。

但不足的是，Proposal在获取到互斥访问权后，并且还没有释放互斥访问权之前发生了故障，则会导致其他所有Proposal无法获取互斥访问权进入第二阶段运行，此时会导致系统陷入“死锁”的状态。即，方案一无法容忍任意Proposal机器出现故障。

引入抢占式访问权 —— 方案二

我们提出方案二，引入抢占式访问权的方式来解决死锁问题，即Acceptor可以让某个Proposal获取到的访问权失效，不再接受它的访问。之后，可以将访问权发放给其他的Proposal，让其他Proposal访问Acceptor。从而避免“死锁”带来的影响。

对Proposal来说，Proposal向Acceptor申请访问权时会指定编号epoch（越大的epoch越新）。获取到访问权以后，才能向Acceptor提交取值。

对Acceptor来说，采用“喜新厌旧”的原则。即一旦收到更大的新epoch的申请，马上让旧epoch的访问权失效，不再接受他们提交的取值，然后给新的epoch发放访问权限，只接受新的epoch提交的取值。

在这种原则下，新的epoch可以抢占旧epoch，让旧epoch访问权失效。为了保证一致性，不同epoch的Proposal之间采用“后者认同前者”的原则，即在肯定旧epoch无法生成确定性取值时，新的epoch会提交自己的value，不会冲突；一旦旧epoch形成确定性取值，新的epoch肯定可以获取到此取值，并且认同此取值，不会破坏。

实现

基于抢占式访问权的acceptor实现：

Acceptor保存：
  当前var的取值<accepted_epoch, accepted_value>
  最新发放访问权的epoch latest_prepared_epoch
  
Acceptor.prepare(epoch)：
  只接受比latest_prepared_epoch更大的epoch，并给予访问权；
  记录latest_prepared_epoch = epoch，返回当前var值。
Acceptor.accept(var, prepared_epoch, V)：
  验证latest_prepared_epoch == prepared_epoch，若不等，说明有一个更大的epoch抢占了访问权，prepared_epoch已失效；
  并设置var的取值<accepted_epoch, accepted_value> = <prepared_epoch, V>

propose(var, V)的两阶段实现：

第一阶段：获取epoch轮次的访问权和当前var的取值，我们可以简单获取当前时间戳为epoch：
- 通过Acceptor.prepare(epoch)，获取epoch轮次的访问权和当前var的取值；
- 如果不能获取，返回<error>。
第二阶段：采用“后者认同前者”的原则执行。
- 如果var取值为null，则肯定旧epoch无法生成确定性取值，则通过Acceptor.accept(var, prepared_epoch, V)提交数据V。
  - 成功后返回<ok, V>；
  - 若accept失败，则说明被更新的epoch抢占或Acceptor故障，返回<error>。
- 如果var取值存在，则此取值肯定是确定性取值，此时认同它不再更改，直接返回<ok, accepted_value>。

qiangzhanshi

方案二总结

基于抢占式访问权的核心思想是让Proposal按照epoch递增的顺序抢占式的依次运行，后者会认同前者。在这种机制下，可以避免Proposal机器故障带来的“死锁”问题，并且仍可以保证var取值的一致性。

但方案二中只有一个Acceptor，单机模块的Acceptor故障时会导致整个系统宕机，无法提供服务，所以我们仍需要引入多个Acceptor。

Paxos解决方案

前面铺垫了这么多，总算来到了paxos的解决方案！

Paxos是在方案二的基础上引入多个Acceptor，在paxos方案里面，Acceptor的实现保持不变，仍然采用“喜新厌旧”的原则运行。由于引进多个Acceptor，所以采用“少数服从多数”的思路。一旦某个epoch的取值f被半数以上Acceptor接受，我们就认为这个var的取值被确定为f，不再更改。

实现

Acceptor同方案二，但加入多个Acceptor。

Proposal同方案二，仍旧采用两阶段方式运行propose(var, V)：

第一阶段：选定epoch，获取epoch访问权和对应的var取值，在paxos中需要获取半数以上Acceptor的访问权和对应一组var取值。
第二阶段：采用“后者认同前者”的原则执行。
- 如果获取的var取值都为null，则旧的epoch无法形成确定性取值，此时努力使<epoch, V>成为确定性取值：
  - 向epoch对应的所有Acceptor提交取值<epoch, V>；
  - 如果收到半数以上成功，则返回<ok, V>；
  - 否则返回<error>（被新的epoch抢占或Acceptor故障）。
- 如果var的取值存在，认同最大的accepted_epoch对应的取值f，努力使<epoch, f>成为确定性取值。
  - 如果f出现半数以上，则说明f已经是确定性取值，直接返回ok, f<>；
  - 否则，向epoch对应的所有Acceptor提交取值<epoch, f>。

paxos_run

Paxos总结

Paxos算法核心思想：

在抢占式访问权基础上引入多个Acceptor；
保证一个epoch，只有一个Proposal运行，Proposal按照epoch递增的顺序依次运行；
新epoch的Proposal采用“后者认同前者”的思路运行：
- 在肯定旧的epoch无法生成确定性取值时，新的epoch会提交自己的取值，不会冲突；
- 一旦旧的epoch行程确定性取值，新的epoch肯定可以获取到此取值，并且会认同此取值，不会破坏。

Paxos算法可以满足容错要求，即半数以下Acceptor出现故障时，存活的Acceptor仍然可以生成var的确定性取值；一旦var值被确定，即使出现半数一下Acceptor故障，此取值可以被获取，并且将不再被更改。