重学Java-分布式事务基础

1. CAP定理

CAP定理(CAP theorem)又称为布鲁尔定理(Brewer’s theorem)，最开始是埃里克·布鲁尔(Eric Brewer)在 2000年的计算原理研讨会(PODC) 上提出的一个猜想（《Towards Robust Towards Robust Distributed Systems Distributed Systems》）。两年后的2002年，麻省理工学院的 Seth Gilbert 和 Nancy Lynch 教授在《Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services》 一文中证明了该猜测，从此CPA定理正式诞生。

CPA 是 Consistency（一致性）, Availability（可用性） 和 Partition Tolerance（分区容错性）三个单词组成的，该定理指出在设计和部署分布式服务时，涉及一致性、可用性和分区容错性这三个核心属性，通常这三个不能同时满足，只能满足其中的两项。

• 一致性( Consistency )：
  • Every read receives the most recent write or an error.
  • 简单理解就是客户端访问每个节点，返回的都是同一份最新的数据（即最新写入的信息或错误信息）。
  • 这里的一致性是线性一致性，也被称为强一致性。
• 可用性( Availability )：
  • Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
  • 可用性保证了每次请求都能获取到数据，但不一定是最新的数据。
• 分区容错性( Partition Tolerance )
  • The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.
  • 节点之间的由于网络分区导致丢弃任意数量的消息，系统仍能继续正常运行。
  • 例如，当网络电缆被切断时，就会发生分区，节点A和节点B无法通信，此时就会导致请求到A的记录，B不清楚，反之亦然，从而出现消息丢失。

2021年，Eric Brewer 在一篇名为《CAP Twelve Years Later: How the “Rules” Have Changed》的文章中回顾了CAP定理容易产生的一些误解：

• “三选二”公式本身存在一定误导性，网络分区本身是很少发生，在未发生时，完全没有必要牺牲一致性或者可用性，这两个是可以同时满足的。当发生网络分区时，才需要从中选择一个。
• 正常运行中，虽然网络分区很少发生，但网络延迟还是存在的。在对CAP定理的经典解释中，是忽略了网络延迟的。实际上网络延迟与网络分区也是紧密联系的。当发生延迟时，放弃处理请求则相当于牺牲了可用性；如果选择继续处理请求，由于存在延迟，则相当于牺牲了一致性。

2. PACELC 定理

PACELC 定理是对 CAP 定理的扩展。由 Daniel Abadi 教授在自己的博文《Problems with CAP, and Yahoo’s little known NoSQL system》中提出，后来在其2012年的论文《Consistency Tradeoffs in Modern Distributed Database System Design》 中正式提出该定理。

PACELC 定理主要讨论的是 忽略分布式系统中的延迟影响是CAP 定理中一大主要疏忽。在系统的整个运行过程中，网络延迟是时刻存在的，但网络分区并不会一直存在。

PACELC 定理指出：

• 在分布式系统存在网络分区§的情况下，需要考虑在一致性©和可用性(A)中做出选择。
• 反之(ELSE,E)，在没有网络分区的情况下且正常运行的情况下，必须在延迟(L)和一致性©之间做出选择。

基于上面的描述可见该定理：

• 在第一部分将CPA中的 AP 和 CP,反过来写作了 PA 和 PC 。
• 在第二部分增加了新的类别 EL 和 EC 。
• 这两部分可以排列组合成多种类型。
  • 大多数系统往往属于 PA/EL 或者 PC/EC 类型。
  • 如 MYSQL CLuster 属于PC/EC类型，即在存在网络分区时优先考虑一致性，反之在系统正常运行时也优先考虑一致性。
  • 更多关于数据库 PACELC 评级可见wiki-PACELC theorem

3. BASE

BASE 理论本身是比 CAP 定理出现的要早的，第一次出现的文献暂时没找到，但从 Eric Brewer 在2012年QCon会议上的演讲《NoSQL: Past, Present, Future》的PPT中提到的一句中可知大概是在1990年代末期，最晚1997年提出来的：

Led to “ACID vs. BASE” spectrum (1997)

• Basically Available, Soft State, Eventual Consistency
• … but BASE was not well received… (ACID was sacred)

…

Developed CAP while teaching in 1998

• Appears in 1999
• PODC keynote in 2000, led to Gilbert/Lynch proof

而且 Brewer 在2000年的《Towards Robust Towards Robust Distributed Systems Distributed Systems》演讲PPT中也明确讨论了 ACID 与 BASE。所以这里采用《深入理解分布式系统》中说法，BASE 是由 Eric Brewer 及其同事提出的。

有些文章说是由 ebay 的 Dan Pritchett 提出的， 应该是参考自该作者在2008年发表的《Base: An Acid Alternative》。

由上面我们可知，BASE 是基本可用( Basically Available )、软状态( Soft State )和最终一致性( Eventual Consistency )的缩写。

• 基本可用( Basically Available )：保证各个节点读写操作尽可能可用，但不一定一致。
  • 即将当分布式系统出现故障时，将事故的影响尽可能减小，允许损失部分数据或服务。
  • 比如当前流行的微服务中，存在主链路一说，当流量过大从而可能导致系统崩溃时，我们通常会通过服务降级、流量控制等手段尽可能保证主干业务可用。比如：
    • 视频服务，优先保证播放，评论等可以暂时不可用或使用提前准备好的。
    • 商家大促活动，优先保证查看商品信息->下单->付款的主业务，评论、问答等可以滞后显示。
• 软状态( Soft State ):可以简单理解为允许系统存在中间状态，在经过一定时间后再更新为最终状态。之所以会出现该状态，是由于使用最终一致性模型，舍弃了强一致性，从而难免就会出现A从一个节点刷到的结果，B从另一个节点还没刷到的情况。
• 最终一致性( Eventual Consistency ):当客户端更新了一个数据时，可能因为网络分区或延迟，没能及时更新到所有的节点副本，系统中同时存在新旧两种数据，此时系统仍能执行读写数据，但在最终的某个时刻，系统保证这个更新操作一定会同步到所有的副本。

虽然网络分区听起来很严重，但持续时间一般不会太长，可能是几秒或几分钟，所以最终一致性是可以接收的。

就像 SQL 数据库几乎一致地兼容 ACID 一样，NoSQL 数据库也倾向于遵循 BASE 原则。MongoDB、Cassandra 和 Redis 是最流行的 NoSQL 解决方案。

4. 两阶段提交

两阶段提交( Two-Phase Commit,2PC )由两个阶段构成，准备阶段( Prepare Phase )和提交阶段( Commit Phase )，属于最经典的原子提交协议。简单来说，只执行一次请求很难知道其它节点是否成功提交，所以再增加一轮请求，先检查各节点是否能够正确执行事务，再进行事务操作。

两阶段提交包含两个角色：协调者(Coordinator)和参与者(Participants)。

• 协调者 ( Coordinator )：负责协调算法的各个阶段。
• 参与者 ( Participants )：参与到事务中执行事务操作。

4.1 准备阶段

第一个阶段为准备阶段( Prepare Phase )，也被称为投票阶段( Voting Phase)，具体执行步骤大致如下：

1. 协调者向所有参与者发送消息，询问各参与者是否可以提交事务，并等待参与者响应。
2. 参与者检查执行事务所需条件和资源(如权限验证、上锁等)，一切准备好后参与者执行事务的所有操作，并记录操作日志。
3. 参与者响应协调者发起的请求，如果参与者发现事务的所有操作都成功执行了，返回一条"是"的消息，反之资源检查失败或者事务操作执行失败则返回一条"否"的消息。

4.2 提交阶段

第二阶段为提交阶段( Commit Phase )。协调者接收到所有参与者上一阶段的响应：

• 如果所有参与者响应的都为"是":
  • 协调者向所有参与者发送提交消息，指示参与者提交本次事务，等待参与者响应
  • 参与者接收到提交消息后，正式提交事务，完成事务提交操作后，清理占用的资源(如释放锁等)，并记录操作日志。
  • 参与者终止事务后响应协调者，协调者收到所有参与者的响应后，确认事务完成。
• 只要有一个参与者响应的为"否"：
  • 协调者向所有参与者发送中止消息，指示所有参与者中止本次事务，等待参与者响应。
  • 参与者收到中止消息，利用第一阶段记录的操作日志回滚所执行的事务操作，并清理占用的资源。
  • 中止后参与者响应协调者，协调者收到所有参与者的消息后，确认事务中止。

下面是两阶段提交时序图，由于所有参与者做的事情都相同，同时为方便查看对参与者部分由多个简化为了一个。

4.3 相关故障

协调者和参与者在任何时候都可能产生故障，为了能在恢复后仍能继续推送事务，需要将事务相关信息写入持久化存储设备中(如SDD等)，以便能在重启后恢复事务的状态。和单机系统类似，通常使用 WAL 来存储事务元数据，所有修改操作完成之前都要先写如 WAL，参与者重启后可以检查 WAl 文件，恢复到事务实际执行的操作状态，根据 这个状态决定自己是回滚/继续还是维持当前现状。

两阶段提交协议针对一些故障需要保证一定的容错性：

• 参与者在回复协调者之前发生了故障，从协调者角度来看，由于一个参与者没有确认，就需要一直等待故障的参与者回复，如果该参与者无法恢复正常工作，协调者就要一直等待下去。
  • 针对该问题，协调者可以设定一个超时等待时间，等待时间超过之后参与者依旧没能返回响应，则认为该参与者投了反对票，协调者中止该事务。系统可在之后对该事务进行重试操作。
• 如果在第一阶段，协调者在向参与者发送准备请求后故障，参与者将一直阻塞，直到协调者恢复正常后才能知道本次事务是要提交还是中止。
  • 从上可知协调者存在单点故障问题，再加上协议的阻塞性，一旦协调者在特点时间宕机，参与者将一直阻塞，如果此时数据库锁定了一些事务相关的资源，导致后续事务无法访问，可能造成一些系统停顿等问题，有时可能需要人工干预来解决。
  • 两阶段提交仅满足弱终止条件，一旦协调者发生故障，参与者无法决定事务走向，所以其是一种阻塞提交算法。
• 如果在第二阶段协调者发送了一部分提交消息时发生了网络分区，导致剩下一部分参与者没有收到提交消息，如果此时其它的事务可读取到这些中间结果，会导致系统出现数据不一致的情况。
  • 极端的情况下是协调者发送消息后故障，部分参与者收到后也故障。此时选出的新协调者无法得知事务之前需要如何操作，不管是否强制提交，后续原有协调者和参与者恢复后，都会造成整个系统的数据不一致。

两阶段提交存在上述的同步阻塞问题、单点故障问题、数据不一致问题以及提交阶段不确定问题，可能会无法达到需要的安全性保证，同时导致运维工作量增加、性能降低和可用性（存在多轮数据交互）下降等问题。有些系统会选择不使用分布式事务，有些会对其做一些改进，如 CockroachDB 提出了一种m名为 Parallel Commits 的优化方案：

• 第一阶段协调者已经知道了本次事务应该提交还是中止，但可能因为网络分区或者节点故障导致数据不一致，如果此时问题节点能去所有节点查询第一次提交的状态，就能知道下一步应该做什么，然后就能在第一阶段结束后直接返回给客户端，然后异步执行第二阶段提交，减少了一轮消息的往返时间。
• Parallel Commits 将第一阶段最终的节点和结果写到全局事务日志中，这样在故障发生时就可以通过查询其它节点的结果来处理异常情况。
• Parallel Commits 需要和共识算法一起工作。

5. 三阶段提交

1982年由 Dale Skeen 提出了3PC协议【Skeen, Dale. (1982). A Quorum-Based Commit Protocol. 69-80. 】来解决2PC阻塞的问题。
在第一和第二阶段中间增加了一个预提交(Prepare to Commit,Pre-Commit)阶段，在该阶段协调者将第一阶段的投票结果发送给所有参与者，如此即使在提交阶段协调者与收到消息的参与者都发生了故障，也可以从剩下的参与者中选出一个新的协调者继续安全推进事务。

5.1 准备阶段

第一阶段仍旧是准备阶段，或者叫投票阶段。稍微不同的是参与者不会直接执行事务操作。具体如下：

1. 协调者向所有参与者并行发布准备消息，询问参与者是否准备好执行事务，等待参与者响应。
2. 参与者判断是否具备执行事务的条件。至于具体判断方式，不同否业务有不同的计算方式。此处只判断不执行事务操作。
3. 参与者响应协调者发起的请求，如果参与者确认事务可以正确执行并提交，则返回一条"是"的消息，反之返回“否”的消息。

5.2 预提交阶段( Pre-Commit Phase)

预提交阶段根据第一阶段响应情况，有如下两种情况：

• 如果所有参与者均返回“是”，则：
  • 协调者向所有参与者发送预提交信息，询问参与者是否可以执行并提交事务，等待参与者响应。
  • 参与者收到预提交消息后，检查执行事务必要条件，条件满足后执行相关事务操作，并记录操作日志。
  • 参与者响应协调者发起的请求，如果参与者发现事务的所有操作执行均成功，则返回一条“是”的消息，反之返回一条"否"的消息
• 只要有一个参与者返回“否”或者等到超时都没收到回应，那么协调者会向所有参与者发送事务中止的消息，等到所有参与者中止事务并回应后，直接中止本次事务。

5.3 提交阶段

第三阶段仍然是提交阶段，协调者收到所有参与者预提交阶段的响应

• 如果所有的参与者返回的都为“是”：
  • 协调者向所有的参与者发送消息，指示参与者提交事务，等待参与者的响应。
  • 参与者收到提交消息后，正式提交事务，完成事务所有操作后，清理占用的资源，并记录操作日志。
  • 参与者响应协调者，协调者收到所有参与者的消息，确认事务完成。
• 预提交阶段只要有一个参与者返回“否”或者超时没恢复协调者：
  • 协调者向所有参与者发送中止消息，指示参与者中止本次事务，等待参与者的响应。
  • 参与者收到中止信息后，利用其预提交时的操作日志回滚事务操作，并清理占用的资源。
  • 参与者中止事务后响应协调者，协调者收到所有参与者的消息后，确认事务中止。

与二阶段提交最大区别是三阶段提交是非阻塞的，增加了可用性，防止协调者成为一个单点故障。

5.4 缺点

但三阶段提交增加的可用性是以正确性为代价的，很容易受到网络分区的影响。如在预提交阶段收到消息和未收到消息的参与者因为网络分区刚好被一分为二，同时协调者发生故障，此时两边会各选出一个新的协调者，然后收到消息的一方继续提交事务，未收到的一方不会提交，甚至可能会因为超时中止事务，导致最终的数据不一致。

另一个明显缺点是一次事务往返次数过多，增加了事务的完成时间，从而导致较长时间的延迟。

三阶段提满足了强终止性，但受网络分区影响以及通信代价较高，所以两阶段提交仍然是第一选择。

除了上面两种实现方式，还有两种可以参考：Paxos 提交算法 和 基于 Quorum 的提交协议。这两种暂时不细谈，可以自行查阅相关资料。

• Paxos 提交算法是一种基于复制的容错提交算法，在两阶段提交的基础上引入了多个协调者(接受者)，只要有多数的接受者存在就不会产生阻塞，但与两阶段提交紧密耦合，在工程实现上具有一定难度。
• 基于 Quorum 的提交协议与三阶段提交很像，这两个都是 Dale Skeen 发明的，在该协议中，系统管理员可以动态调整事务要提交必须获得的最小票数和要中止必须获得的最小票数的值，使得该协议在网络分区下选择提交事务或者中止事务的倾向性有很大的弹性。但其也有一定的缺点：
  • 如果系统发生多个连续的、小的网络分区，可能会长时间无法做出决议。
  • 和三阶段提交一样也存在多轮消息，同样会增加事务完成的时间，不适用于对延迟敏感的业务。

3. 参考资料

这里仅放出文章中未提到过得资料，提到过的均已同时备注了查阅地址。

• 《深入理解分布式系统》