分布式事务

目录

1. 简介
2. 单一分布式事务与嵌套分布式事务
3. 原子提交协议
   • 两阶段提交协议
   • 嵌套事务的两阶段提交协议
4. 分布式事务的并发控制
   • 加锁
   • 时间戳并发
   • 乐观并发控制
5. 分布式死锁
6. 事务恢复
   • 日志
   • 影子版本
   • 为何恢复文件需要事务状态和意图列表
   • 两阶段提交协议的恢复

本文介绍分布式事务，即涉及多个服务器的事务。分布式事务可以是普通的单个事务也可以是嵌套事务。
原子提交协议是参与一个事务的多个服务器之间使用的协作方案。该协议能够让多个服务器共同参与决策，来确定是提交事务还是回滚事务。本文将降解最常用的原子提交协议----两阶段提交协议。
分布式事务的并发控制小结中将会讨论如何扩展单库事务中的加锁逻辑、时间戳排序和乐观并发控制，以让其支持分布式事务。
使用加锁机制可能会造成分布式死锁，因此本文也会提到几种分布式死锁的检测算法。
每个支持事务的服务器都肯定包含一个恢复管理器。当服务器发生故障并被修复后（修复故障服务器或直接用新服务器取代故障服务器），恢复管理器负责将故障前的事务状态进行恢复。恢复管理器会将对象、意图列表（别慌，后面讲到）和每个事务的状态信息记录在持久性的存储器中。

一、简介

如果一个事务所要访问的对象位于多个服务器上，则该事务为分布式事务。

分布式事务也具有原子性，当一个分布式事务结束时所有参与该事务的服务器必须全部提交或者全部放弃（回滚）该事务。为了实现这一点，其中一个服务器需要扮演协调者的角色，由它来协调其他参与该事务的服务器，以保证分布式事务的原子性。协调者如何展开工作取决于它采用何种协议。两阶段提交协议是最常见的原子提交协议，该协议规定了一系列的服务器之间相互通信的操作，以便共同决定是提交事务还是放弃事务。

运行在单个服务器上的事务通过加锁、时间戳排序和乐观并发控制等方法来保证事务的串行化（不懂的请移步Innodb事务实现原理）。分布式事务还需要保证全局串行化，因此需要在单服务器事务的基础上进行扩展。有时候因为不同服务器之间存在互相依赖循环，可能会造成分布式死锁。

事务恢复用于保证分布式系统的状态只受到已提交事务的影响而不受到未提交事务的影响。

二、单一分布式事务与嵌套分布式事务

有两种构建分布式事务的方式，按平面事务（单个事务）构造和按嵌套式事务（层次事务）构造。

图1 分布式事务的两种构建方式

如上图1a中，事务T是一个平面事务，它用到了服务器X、Y、Z上的对象。平面事务必须顺序执行每个请求，完成一个请求之后才能发起下一个请求。当服务器使用加锁机制时，平面事务一次只能请求一个锁。

嵌套事务则可以看成是是一组协作的小事务协作组成的事务，如图1b。在嵌套事务中，顶层事务可以创建子事务。事务T创建了两个子事务T1和T2，它们分别访问服务器X、Y上的对象。T1和T2又创建了子事务T11、T12、T21、T22，这四个子事务由分别访问服务器M、N和P上的对象。在嵌套事务中，同一层次的事务可以并发执行，T1、T2是并发执行的，而且它们访问的是不同的服务器，因此是并行执行的。

现在考虑这样一个分布式事务：客户从A账户转账10元到C账户，再从B账户转账10元到D账户。账户A、B分别在服务器X、Y上，账户C、D都在服务器Z上。如果将该事务组织成一个嵌套事务，那么四个请求（两个存款操作两个扣款操作）可以并发执行，因此整体执行性能优于4个操作被顺序执行的简单事务。

图2 嵌套的银行事务

分布式事务的协调者

执行分布式事务的服务器之间需要相互通信，以确保能够协调它们之间的动作。客户在启动一个事务时，向任意一台服务器上的协调器发出openTransaction请求，协调器处理完openTransaction请求后会将事务标识符TID返回给客户端。应当注意，分布式系统的事务标识符在整个分布式系统中必须是唯一的。构造TID的一种简单的方法是将TID分成两部分：创建该事务标识符的服务器标识符（例如IP地址）和对应该服务器来说是唯一的数字（例如时间戳）。

创建分布式事务TID的协调者就是该分布式事务的协调者，它在分布式事务结束时负责全局把控事务行为（提交还是回滚）。分布式事务所访问到的服务器称为该分布式事务的参与者，每个参与者需要提供一个参与者对象。参与者一方面负责跟踪和管理事务访问到的对象，另一方面还要配合协调者共同执行提交协议。

在事务执行过程中，协调者会创建一个列表来保存所有参与者的引用，每个参与者也要保存协调者的引用。

协调者接口Coordinator提供了一个join方法，它用于将新的参与者加入到当前事务：

interface Coordinator{
    join(long trans, Participant participant)
}

图3显示了一个这样的事务：客户端发起了一次银行转账事务T，先从账户A转账4块钱到账户C，再从账户B转账3块钱到账户D。涉及到服务器X、Y、Z，其中账户C、D都在服务器Z上。客户端发起openTransaction请求给协调者，当提交事务时再发送closeTransaction给协调者。协调者对象可以位于该事务涉及的任意一个服务器上。并且，每个服务器都有一个参与者对象，它们通过调用协调者的join方法来加入事务。客户端访问服务器上的一个对象时，例如访问服务器Y上的B对象，该对象会告诉参与者对象自己属于事务T。如果在这之前没有通知过协调者，则参与者对象调用join方法通知协调者。因此，在客户端调用closeTransaction之前，协调者就有了对所有参与者的引用。

图3 一个分布式银行事务

三、原子提交协议

事务的原子性要求事务在结束时它的所有操作要么全部执行要么全部放弃。客户端请求提交或者放弃事务时，事务结束。对于分布式事务，以原子方式完成事务的一个简单的方法就是让协调者不断地向所有参与者发送提交或者放弃请求，直到所有参与者确认已经执行完成相应的操作。这是一个单阶段原子提交协议的例子。

但是，这种单阶段原子提交协议显然是不够用的。因为它要求所有参与者必须执行协调者发来的指示（提交或者放弃事务），而不允许任何服务器单方面放弃事务。但是很多因素会导致服务器不得不单方面放弃事务，例如为了解除死锁需要放弃事务，或者服务器已经崩溃了。

为了克服单阶段原子提交协议的不足之处，聪明的科学家们设计出了两阶段原子提交协议。它允许任何一个参与者单方面放弃自己那部分事务。当部分事务被放弃时，整个事务也必须被放弃，这样才能满足事务的原子性要求。

两阶段提交协议

在两阶段提交协议的第一阶段，协调者询问参与者是否可以提交各自负责的那部分事务；在第二阶段，协调者通知它们提交（或放弃）事务。

参与者必须保证自己能够旅行自己做出的决定。当参与者通知协调者自己已经准备好提交时，参与者应保证在任何情况下都可以提交，例如遇到服务器崩溃重启等事故，参与者服务器也能够保证已经“准备好提交”的事务也可以正确提交。这就需要参与者事先将需要提交的事务写入到持久性存储器中，以确保任何情况下都不会丢失这部分数据和操作。

为了实现两阶段提交协议，协调者和参与者会使用以下代码块所示的命令进行通讯，其中canCommit、doCommit、doAbort是参与者提供给协调者的方法，haveCommited、getDecision是协调者提供给参与者的方法。

// 协调者调用该方法询问参与者是否能够提交事务，参与者将回复它的投票结果
canCommit(trans) ? -> Yes / No

// 协调者调用该方法告诉参与者提交它那部分事务
doCommit(trans)

// 协调者调用该方法告诉参与者放弃它那部分事务
doAbort(trans)

// 参与者调用该方法告诉协调者自己已经提交了事务
haveCommited(trans, participant)

// 参与者调用该方法询问协调者最终的投票结果（参与者投票后在一段时间内未收到协调者应答时调用该方法询问结果，可能因为协调者服务器出现了异常或者消息延迟）
getDecision(tans) -> Yes / No

两阶段提交协议之所以称为两阶段就是因为它相较于但阶段提交协议增加了“投票阶段”。两阶段提交协议由投票阶段和完成阶段组成。在投票阶段，协调者询问所有参与者是否能够提交事务，收到参与者的回复后，协调者根据投票结果来确定事务是提交还是放弃。在完成阶段，如果协调者收到的投票全部为Yes，则协调者通知参与者提交事务，否则通知参与者放弃事务。具体步骤见下图：

图5 两阶段提交协议

协调者和参与者之间的信息交换会由于服务器的崩溃或消息丢失而失败。采用超时机制可以防止进程无限期阻塞。当进程检测到超时后就会采取适当的措施来处理可能的错误或者重试。协议的每一个阻塞操作都被设计了超时机制，这不光是因为超时机制可以避免死等问题而且还考虑到在异步系统中超时并不意味着服务器出现故障，有时候只是消息丢失。

两阶段提交协议的超时动作

在两阶段提交协议的不同阶段，协调者或参与者都可能需要等待接收某个消息才能决定自己下一步该怎么做。

考虑这样一个场景：某个参与者投Yes票并等待协调者回复决定。这时，参与者在收到协调者的回复之前无法确定下一步的操作，而且该事务所使用的对象不能释放以用于其他事务。如果等待时间过长，则参与者会主动向协调者发起 getDecision 请求来尝试获取投票结果。如果协调者发生了故障，那么参与者将无法获取决定，这可能导致参与者长时间处于不确定状态。

如果某些参与者得到过协调者的回复，则没有得到协调者回复的参与者可以询问得到过回复的参与者，来获取投票结果。当协调者发生故障时，这种办法通常能够解决问题。但是如果所有的参与者都没有得到过协调者的回复，那就只能等协调者恢复工作后再继续事务了。

另一种可能导致参与者延迟的情况是，参与者已经完成了事务中所有客户请求，但一直没收到协调者 canCommit 请求。当等待时间过长以至于超时后，参与者自能单方面放弃该事务。相对应的，协调者会因为向该参与者发送 canCommit 请求长时间未得到回复，而认为参与者出现了故障，默认该参与者没有能力完成事务。因此协调者决定放弃整个事务，并通知所有投Yes的参与者放弃该事务。

当协调者由于没有收到某些参与者的投票而决定放弃整个事务后，可能因为网络延迟原因，又收到了某些参与者的Yes票。但是，这些Yes票会被直接忽略掉，协调者不会给予任何回复。延迟发送这些Yes票的参与者由于不能收到协调者回复而进入不确定状态，超时后将自动放弃它所负责的那部分事务。

两阶段提交协议的性能

假设一切都正常运行，即协调者和参与者都不出现崩溃并且通信也正常，有N个参与者的两阶段协议需要传递N个canCommit？的消息和应答，然后再有N个doCommit消息。这样，消息开销就与3N成正比，时间开销就是3次消息往返的时间。（为什么haveCommited消息被忽略计算了？因为即使没有它，事务也能正常运行。haveCommited消息只是用于提示服务器删除过时的协调者）

但是，两阶段提交协议的执行过程中可能会遇到任意多次服务器故障或者通信故障。虽然协议不能保证在限定时间内完成完成事务，但它有能力连续解决故障直到最终完成。

嵌套事务的两阶段提交协议

四、分布式事务的并发控制

每个服务器都要管理很多对象，它必须保证多个事务并发访问这些对象时，这些对象任然能保持一致性。因此，每个服务器需要对自己管理的对象应用并发控制机制。而且，对于分布式事务，所有涉及到的服务器需要协作来保证事务以串行方式执行。也就是说，如果在某个服务器上事务T在事务U之前，那么在分布式事务涉及到的所有服务器上，事务T都要在事务U之前。

加锁

单个服务器上的锁管理器只能保证单服务器上运行的事务串行执行并在死锁时进行检测和消除。不过在分布式事务的运行过程中，单服务器上的锁管理器将无法检测死锁。如下图所示就是两个分布式事务产生了死锁：

分布式死锁

在服务器X上，事务T在事务U之前，但在服务器Y上事务U在事务T之前。这种不同的事务次序导致事务之间的循环依赖，从而引发分布式锁。一旦发生死锁，那么必须放弃一个事务来解除死锁，后面会讲到分布式死锁的检测和解除方法。

时间戳并发控制

对于单个服务器上的事务，在事务开始运行时，协调者会为其分配一个唯一的时间戳。多个事务并发访问一个对象时，按照时间戳的先后次序决定对象版本的提交次序，这样就保证了事务之间的串行性。在分布式事务中，协调者需要为每个事务分配一个全局唯一的时间戳。这个全局唯一的时间戳由事务访问的第一个协调者创建并返回给客户端。如果客户端向另外一个服务器发起了事务中的某个操作，则该时间戳也会被传递给服务器的协调者（注意：传递给服务器的协调者而不是参与者）。

分布式事务所涉及到的所有服务器共同协作来保证分布式事务的串行等价性。例如在某个服务器上事务T先于事务U提交，则在其他服务器上也要保证T先于U提交。也就是说，事务T对对象产生的作用必须先于事务U发生。为了保证所有服务器上都有相同的次序，协调者必须就时间戳的排序方式达成一致。时间戳是一个二元组<本地时间戳，服务器id>。在比较时，先比较本地时间戳，如果时间戳相同则在根据服务器的优先级进行排序。可以看出，即便每个服务器上的时钟有偏差，但也任然能保证时间戳有序。但为了保证事务之间的公平性，最好还是将所有服务器上的时间调成一致。（假设某台机器的时间慢10分钟，则该机器上发起的事务将会优先于前面十分钟内在其他机器上发起的事务，这显然不太公平。）

乐观并发控制

五、分布式死锁

六、事务恢复