【Zookeeper学习】2.一致性协议

上一章，我们了解了分布式事务的定义及相关的理论，从理论上来看，可以对分布式事务分为两类：

• 刚性事务

  对于满足CP模型的事务，遵循ACID，对数据要求强一致性。
  实现方案：基于XA协议的2PC，3PC；Java事务规范的JTA、JTS。

• 柔性事务

  对于满足AP模型的事务，遵循BASE，允许一定时间内不同节点的数据不一致，但要求最终一致。
  实现方案：补偿协议：TCC，SAGA；基于最终一致性的本地消息表，可靠消息，最大努力通知等。

1 分布式协议

为了解决分布式一致性问题，涌现了一大批经典的一致性协议和算法，最有名的有二阶段提交协议（2PC）、三阶段提交协议（3PC）和Paxos算法。

1.1 XA协议

当一个事务操作需要跨越多个分布式节点时，为了保持事务处理的ACID特性，就需要引入一个“协调者”的组件来统一调度所有分布式节点的执行，这些被调度的分布式节点则称为“参与者”，协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务真正提交。

XA 协议是由 X/Open 组织提出的分布式事务处理规范，主要定义了事务管理器TM和 本地（或局部）资源管理器 RM之间的接口。

目前主流的数据库，比如 oracle、DB2 都是支持 XA 协议的。MySQL 从 5.0 版本开始，innoDB 存储引擎已经支持 XA 协议。

在这个协议里，有三个角色：

• AP（Application）：应用系统（服务）
• TM（Transaction Manager）：事务管理器（全局事务管理）
• RM（Resource Manager）：资源管理器（数据库）

基于这种思想，衍生出了二阶段和三阶段提交协议。

1.1.1 2PC

两阶段提交协议2PC是Two-Phase Commit的缩写，目前绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理的。

顾名思义，二阶段提交协议是将事务的提交过程分成两个阶段来进行处理

• 阶段一：提交事务请求

  阶段一也被称为“投票阶段”。即各参与者投票表明是否需要继续执行接下去的事务提交操作。

• 阶段二：执行事务提交

  在阶段二中，协调者会根据各参与者反馈的情况来决定最终是否进行事务提交。

2PC

优点：

• 原理简单，实现方便

缺点：

• 同步阻塞

  各参与者都需要等待其他参与者的响应，期间什么都做不了。

• 单点问题

  协调者有明显的单点问题。

• 数据不一致

  协调者发送部分节点commit指令后挂了，数据出现不一致。

注意：

2PC只适用两个数据库（数据库实现了XA协议）之间；
2PC有诸多问题和不便，在实践中一般很少使用。

1.1.2 3PC

2PC在运行中存在同步阻塞、协调者单点问题、数据不一致的问题，因此在其基础上进行了改进，提出了三阶段协议。

3PC，是Three-Phase Commit的缩写，是2PC的改进版，其将2PC阶段一再分为两个阶段：询问、预提交。

• 阶段一：CanCommit

  • 事务询问：协调者向所有参与者发送包含事务内容的canCommit的请求，询问是否可以执行事务提交，并等待应答；

  • 各参与者反馈事务询问：正常情况下，如果参与者认为可以顺利执行事务，则返回Yes，否则返回No。

• 阶段二：PreCommit

  在本阶段，协调者会根据上一阶段的反馈情况来决定是否可以执行事务的PreCommit操作。两种结果：

  • 执行事务提交

    • 发送预提交请求。协调者向所有节点发出PreCommit请求，并进入prepared阶段；

    • 事务预提交。参与者收到PreCommit请求后，会执行事务操作，并将Undo和Redo日志写入本机事务日志；

    • 各参与者成功执行事务操作，同时将反馈以Ack响应形式发送给协调者，同事等待最终的Commit或Abort指令。

  • 中断事务

    • 加入任意一个参与者向协调者发送No响应，或者等待超时，协调者在没有得到所有参与者响应时，即可以中断事务；

    • 发送中断请求。协调者向所有参与者发送Abort请求；

    • 中断事务。无论是收到协调者的Abort请求，还是等待协调者请求过程中出现超时，参与者都会中断事务。

• 阶段三：doCommit

  两种结果：

  • 执行提交

    • 发送提交请求。假如协调者收到了所有参与者的Ack响应，那么将从预提交转换到提交状态，并向所有参与者，发送doCommit请求；

    • 事务提交。参与者收到doCommit请求后，会正式执行事务提交操作，并在完成提交操作后释放占用资源；

    • 反馈事务提交结果。参与者将在完成事务提交后，向协调者发送Ack消息；

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

  • 中断事务

    • 在该阶段，假设正常状态的协调者接收到任一个参与者发送的No响应，或在超时时间内，仍旧没收到反馈消息，就会中断事务；

    • 发送中断请求。协调者向所有的参与者发送abort请求；

    • 事务回滚。参与者收到abort请求后，会利用阶段二中的Undo消息执行事务回滚，并在完成回滚后释放占用资源；

    • 反馈事务回滚结果。参与者在完成回滚后向协调者发送Ack消息；

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

3PC

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

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

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

优点：

• 利用超时机制解决了2PC的同步阻塞问题

缺点：

• 仍然存在一致性问题

  因为网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况

2PC和3PC后，两者都无法彻底解决分布式一致性问题。

1.2 Java事务规范

XA协议是一种通用的规范，但对于JAVA来说，其规范就是JTA、JTS.

1.2.1 JTA

Java事务API（Java Transaction API）是一个Java企业版的应用程序接口，在Java环境中，允许完成跨越多个XA资源的分布式事务。

1.2.2 JTS

Java事务服务（Java Transaction Service）是J2EE平台提供了分布式事务服务的具体实现规范，j2ee服务器提供商根据JTS规范实现事务并提供JTA接口。

1.3 补偿协议

1.3.1 TCC

TCC（Try-Confirm-Cancel）又被称补偿事务。

• 一种服务层面上的2PC
  • 2PC是在数据库层面，TCC是在应用层面
  • 锁粒度更小
• 缺点
  • 对应用的侵入性非常强
  • 业务紧耦合
  • 实现难度也比较大

TCC

1.3.2 Saga

业务流程中每个参与者都提交本地事务，当出现某一个参与者失败则补偿前面已经成功的参与者。

如下内容主要来源于这里，然后由flyingww翻译整理在知乎。

Saga的实现有很多种方式，其中最流行的两种方式是：

• 基于事件的方式。这种方式没有协调中心，整个模式的工作方式就像舞蹈一样，各个舞蹈演员按照预先编排的动作和走位各自表演，最终形成一只舞蹈。处于当前Saga下的各个服务，会产生某类事件，或者监听其它服务产生的事件并决定是否需要针对监听到的事件做出响应。

• 基于命令的方式。这种方式的工作形式就像一只乐队，由一个指挥家（协调中心）来协调大家的工作。协调中心来告诉Saga的参与方应该执行哪一个本地事务。

我们继续以订单流程为例，说明一下该模式。

假设一个完整的订单流程包含了如下几个服务：

• Order Service：订单服务
• Payment Service：支付服务
• Stock Service：库存服务
• Delivery Service：物流服务

a very high-level design a saga pattern implementation

1.3.2.1 基于事件的方式

在基于事件的方式中，第一个服务执行完本地事务之后，会产生一个事件。其它服务会监听这个事件，触发该服务本地事务的执行，并产生新的事件。

采用基于事件的saga模式的订单处理流程如下：

基于事件的saga模式的订单处理

• 订单服务创建一笔新订单，将订单状态设置为”待处理”，产生事件ORDER_CREATED_EVENT。
• 支付服务监听ORDER_CREATED_EVENT，完成扣款并产生事件BILLED_ORDER_EVENT。
• 库存服务监听BILLED_ORDER_EVENT，完成库存扣减和备货，产生事件ORDER_PREPARED_EVENT。
• 物流服务监听ORDER_PREPARED_EVENT，完成商品配送，产生事件ORDER_DELIVERED_EVENT。
• 订单服务监听ORDER_DELIVERED_EVENT，将订单状态更新为”完成”。

在这个流程中，订单服务很可能还会监听BILLED_ORDER_EVENT，ORDER_PREPARED_EVENT来完成订单状态的实时更新。将订单状态分别更新为"已经支付"和"已经出库"等状态来及时反映订单的最新状态。

该模式下分布式事务的回滚

为了在异常情况下回滚整个分布式事务，我们需要为相关服务提供补偿操作接口。

假设库存服务由于库存不足没能正确完成备货，我们可以按照下面的流程来回滚整个Saga事务：

• 库存服务产生事件PRODUCT_OUT_OF_STOCK_EVENT。

• 订单服务和支付服务都会监听该事件并做出响应：

  • 支付服务完成退款。
  • 订单服务将订单状态设置为"失败"。

基于事件方式的优缺点

优点：简单且容易理解。各参与方相互之间无直接沟通，完全解耦。这种方式比较适合整个分布式事务只有2-4个步骤的情形。

缺点：这种方式如果涉及比较多的业务参与方，则比较容易失控。各业务参与方可随意监听对方的消息，以至于最后没人知道到底有哪些系统在监听哪些消息。更悲催的是，这个模式还可能产生环形监听，也就是两个业务方相互监听对方所产生的事件。

接下来，我们将介绍如何使用命令的方式来克服上面提到的缺点。

1.3.2.2 基于命令的方式

在基于命令的方式中，我们会定义一个新的服务，这个服务扮演的角色就和一支交响乐乐队的指挥一样，告诉各个业务参与方，在什么时候做什么事情。我们管这个新服务叫做协调中心。协调中心通过命令/回复的方式来和Saga中其它服务进行交互。

我们继续以之前的订单流程来举例。下图中的Order Saga Orchestrator就是新引入的协调中心。

基于命令的saga模式的订单处理

• 订单服务创建一笔新订单，将订单状态设置为"待处理"，然后让Order Saga Orchestrator（OSO）开启创建订单事务。
• OSO发送一个"支付命令"给支付服务，支付服务完成扣款并回复"支付完成"消息。
• OSO发送一个"备货命令"给库存服务，库存服务完成库存扣减和备货，并回复"出库"消息。
• OSO发送一个"配送命令"给物流服务，物流服务完成配送，并回复”配送完成”消息。

在上述情况下，Order Saga Orchestrator 知道执行“创建订单”事务所需的流程是什么。如果有任何失败，它还负责通过向每个参与者发送命令来协调回滚以撤消上一个操作。

对 Saga 业务流程协调程序进行建模的标准方法是状态机(Sate Machine)，其中每个转换对应于一个命令或消息。状态机是构建定义良好的行为的绝佳模式，因为它们易于实现，特别适合测试。

该模式下分布式事务的回滚

事务的回滚

该模式下的回滚流程如下：

• 库存服务回复OSO一个"库存不足"消息。
• OSO意识到该分布式事务失败了，触发回滚流程；
• OSO发送"退款命令"给支付服务，支付服务完成退款并回复"退款成功"消息。
• OSO向订单服务发送"将订单状态改为失败命令"，订单服务将订单状态更新为"失败"。

基于命令方式的优缺点

优点：

• 避免了业务方之间的循环依赖。
• 将分布式事务的管理交由协调中心管理，协调中心对整个逻辑非常清楚。
• 减少了业务参与方的复杂度。这些业务参与方不再需要监听不同的消息，只是需要响应命令并回复消息。
• 测试更容易（分布式事务逻辑存在于协调中心，而不是分散在各业务方）。
• 回滚也更容易。

缺点：

• 一个可能的缺点就是需要维护协调中心，而这个协调中心并不属于任何业务方。

1.3.2.3 Saga模式建议

• 给每一个分布式事务创建一个唯一的Tx id。这个唯一的Tx id可以用来在各个业务参与方沟通时精确定位哪一笔分布式事务。
• 对于基于命令的方式，在命令中携带回复地址。这种方式可以让服务同时响应多个协调中心请求。
• 幂等性。幂等性能够增加系统的容错性，让各个业务参与方服务提供幂等性操作，能够在遇到异常情况下进行重试。
• 尽量在命令或者消息中携带下游处理需要的业务数据，避免下游处理时需要调用消息产生方接口获取更多数据。减少系统之间的相互依赖。

1.4 最终一致性协议

1.4.1 本地消息表

本地消息表的方案最初是由 eBay 提出，核心思路是将分布式事务拆分成本地事务进行处理。此章节来源于CSDN博主不才陈某这里.

1.4.2 可靠消息

当事务发起方执行完成本地事务后并发出一条消息，事务参与方(消息消费者)一定能 够接收消息并处理事务成功，此方案强调的是只要消息发给事务参与方最终事务要达到一致。

基于 MQ 的分布式事务方案其实是对本地消息表的封装，将本地消息表基于 MQ 内部，其他方面的协议基本与本地消息表一致。

• 正常情况：事务主动方发消息

  
  正常情况

• 异常情况：事务主动方消息恢复

  
  异常情况

优点：
相比本地消息表方案，MQ 事务方案优点是：

• 消息数据独立存储 ，降低业务系统与消息系统之间的耦合。
• 吞吐量大于使用本地消息表方案。

缺点：

• 一次消息发送需要两次网络请求(half 消息 + commit/rollback 消息) 。
• 业务处理服务需要实现消息状态回查接口。

1.4.3 最大努力通知

最大努力通知也称为定期校对，是对MQ事务方案的进一步优化。它在事务主动方增加了消息校对的接口，如果事务被动方没有接收到消息，此时可以调用事务主动方提供的消息校对的接口主动获取。

最大努力通知的整体流程如下图：

最大努力通知整体流程

1.4.3.1 特点

• 用到的服务模式：可查询操作、幂等（idempotent）操作

• 适用于对业务最终一致性的时间敏感度低的系统

  分布式事务中对一致性要求最低的一种,

• 适合跨企业的系统间的操作，或者企业内部比较独立的系统间的操作，比如银行通知、商户通知等

• 不可靠消息：业务活动主动方，在完成业务处理之后，向业务活动的被动方发送消息，直到通知N次后不再通知，允许消息丢失(不可靠消息)

• 定期校对：业务活动的被动方，根据定时策略，向业务活动主动方查询(主动方提供查询接口)，恢复丢失的业务消息。

1.4.3.2 适用场景

典型的使用场景：银行通知、支付结果通知等。

1.4.3.3 核心功能点

• 消息重复通知机制
• 消息校对机制

2 Paxos算法

There is only one consensus protocol, and that’s Paxos. All other approaches are just broken versions of Paxos.
– Mike Burrows(Google Chubby的作者)

Paxos 算法是分布式技术大师莱斯利·兰伯特 Leslie Lamport 于1990年提出的一种基于消息传递且具有高度容错特性的共识算法[^1] (PS: 网上有很多文章写成一致性算法，咱要尊重作者老爷子的思想，个人拙见，共识是手段，少数服从多数；一致性是目标和结果)，是目前公认的解决分布式一致性问题最有效的算法之一。其解决的问题是

如何在一个可能发生宕机或网络异常等情况下的分布式系统中，快速且正确地在集群内部就某个数据的值达成一致，并且保证不论发生上述任何一种异常，都不会破坏整个系统的一致性。

在此之前，Lamport提出过这样一个经典问题：

拜占庭帝国有许多支军队，不同军队的将军之间必须制订一个统一的行动计划，从而做出进攻或者撤退的决定，同时，各个将军在地理上都是被分隔开来的，只能依靠军队的通讯员来进行通讯。然而，在所有的通讯员中可能会存在叛徒，这些叛徒可以任意篡改消息，从而达到欺骗将军的目的。

这就是拜占庭将军问题[^2]。从理论上说，在分布式计算领域，试图在异步系统和不可靠的通道上来达到一致性状态是不可能的。因此在对一致性的研究过程中，往往假设信道是可靠的。事实上，大多数系统都是部署在同一个局域网中的，因此消息被篡改的情况非常罕见；另一方面，由于硬件和网络原因而造成的消息不完整问题，只需一套简单的校验算法即可避免——因此，在实际工程实践中，可以假设不存在拜占庭问题，即假设所有消息都是完整的，没有被篡改的。

Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传递的消息是不会被篡改的。

Lamport鉴于之前成功地运用故事类比，把拜占庭将军问题阐述地简单清晰明了，因而在提出Paxos算法时，同样给出了一个场景：

在古布腊有一个叫做Paxos 的小岛，岛上来用议会的形式来通过法令，议会中的议员通过信使进行消息的传递。值得注意的是，议员和信使都是兼职的，他们随时有可能会离开议会厅，并且信使可能会重复的传递消息，也可能一去不复返。因此，议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。

这个算法也是因此而得名.

2.1 主要角色

• Proposer（提案者/提议者）：提议一个值，用于被投票决议。
• Acceptor（附议者/接受者）：对每个提议进行投票。
• Learner（学习者/告知者）：被告知投票的结果，不参与投票过程。

引用@pdai大神的说法：

可以理解为人大代表(Proposer)在人大向其它代表(Acceptors)提案，通过后让老百姓(Learner)落实。

2.2 三阶段

• 第一阶段: Prepare阶段
  Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。

  • Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。
  • Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。
    • 承诺1: 不再接受Proposal ID小于等于(注意: 这里是<= )当前请求的Prepare请求;
    • 承诺2: 不再接受Proposal ID小于(注意: 这里是< )当前请求的Propose请求;
    • 应答: 不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

• 第二阶段: Accept阶段
  Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

  • Propose: Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。
  • Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。

• 第三阶段: Learn阶段
  Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

参阅漫谈分布式系统(11) – 达成共识就是一致
大话分布式理论之二——共识算法与一致性的区别

伪代码:

2.3 Paxos算法推导

参阅理解Paxos算法的推导过程

2.4 Paxos算法拓展

Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。后续文章会讲讲ZAB，RAFT，敬请期待。

• Multi-Paxos
  由于Paxos每次流程只能支持一个提案的达成，效率较低，于是又出现了Multi-Paxos，支持一次协调达成一揽子的提案。
• Raft
  Raft是对Muti-Paxos的精简，强调易理解、易实现。
• Multi-Raft
  当下很多分布式数据库存在分片，不同分片之间的数据/信息应该是隔离的，于是需要多个Raft来支持分片，每个Raft对应一个分片，这就是Multi-Raft。
• ZAB
  ZAB也是对Multi-Paxos算法的改进，是Zookeeper中的选主机制，比Raft协议出现的更早。

2.5 Paxos 算法的一致性

Paxos 算法的一致性主要体现在以下几点：

• 每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N， 即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案。
• 每个表决者在 accept 某提案后，会将该提案的编号 N 记录在本地，这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。
• 在众多提案中最终只能有一个提案被选定。
• 一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。
• 没有提案提出则不会有提案被选定。

参考文献

• Lamport, Leslie. “The part-time parliament.” ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.
• Lamport, Leslie. “Paxos made simple.” ACM Sigact News 32.4 (2001): 18-25.

[^1]:第一篇论文;第二篇论文;Nancy Lynch
[^2]:Byzantine Generals Problem