《深入浅出Greenplum内核》系列直播已经进行到第七场。错过活动的小伙伴可以前往Greenplum中文社区B站频道观看相关视频，相关PPT均已上传Greenplum中文社区网站的下载页面，欢迎获取！现在让我们通过这篇万字长文来回顾一下第七场活动《Greenplum分布式事务》精华内容。
事务处理是数据库系统的核心能力之一，在Greenplum等分布式数据库上实现更为复杂。本文将从四大块内容来为大家讲解Greenplum分布式事务：
- 事务实现原理和Write Ahead Logging（WAL）
- 分布式事务和两阶段提交的原理
- Greenplum两阶段提交协议的实现
- Greenplum两阶段提交协议的优化
一、事务实现原理和Write Ahead Logging（WAL）
事务处理是数据库管理系统的核心功能。数据库管理系统自诞生到现在已经发展了几十年，它能够在各行各业得到如此广泛的应用，一个非常重要的原因就是它提供了对事务的支持。事务是指对是数据库管理系统中的数据对象进行的一系列操作，通常是以begin transaction开始，以end transaction结束，中间包含了对数据对象的一些增删改查等操作。
事务的属性：ACID
那么事务有4个属性，通常被统称为ACID，在下面的表格里，中间栏分别列出了这4个属性的含义。右边栏列举了从数据库系统实现的角度来看，支持这4个属性常用的技术、方法或协议。
Jim Gray于1981年VLDB描述了事务的原子性、一致性和持久性，在此基础上，Haerder和Reuter在1983年中提出了事务的隔离性并提出术语“ACID”，自此，事务的ACID四个性质成为业内标准术语。
下图是一个典型的disk-oriented database的架构。这张图片来自数据库教科书《数据库系统实现》。还有一种数据库叫main-memory database，也就是主存数据库。
Disk-Oriented Database包括一些重要的模块或者子系统。
其中索引、文件、记录管理器也称为资源管理器，它的任务是管理各种数据库资源；缓冲区管理器主要负责管理缓冲区。需要注意一下的是，这里存在两个独立的缓冲区，分别是数据页的buffer pool和log文件的buffer。
存储管理器会负责从存储里面去获取数据页。事务的实现需要多个组件协同工作，事务管理器就负责协调调度、跟踪事务的各个执行阶段和状态；通过资源管理器以及日志和恢复模块，保证实物的原子性和持久性两个属性。并发控制模块会通过锁管理器等模块来保证事物的隔离性。
事存储介质的类型
接着我们再来了解一下数据库存储介质的类型，主要分为三大类。
- 第一类是易失性存储器，包括CPU的寄存器，cache以及主存等。这些存储器的特点是当断电之后，上面的数据就丢失了。
- 第二类存储器是非易失性存储器，包括Disk、SSD、NVM等。这类存储器的特点是如果断电了，对数据不会产生影响。
- 还有一种是稳定存储器，理论上来讲是不可能被保证的，因为只要是物理存储介质都有被损坏的可能性，所以它只是一个概念上的存在。
下图描述了这些不同的存储介质的特点。我们可以看到，越靠近CPU，存储速度越快，容量越小，单位成本越高；越远离CPU在存储访问越慢，容量越大，单位成本越低。
不同硬件的特点会导致访问数据耗时的不均衡性。因此数据库的数据会尽量缓冲在一个buffer pool里进行操作，而不会直接去操作磁盘上的数据文件。
缓冲区Buffer Pool
我们再来了解一下缓冲区(buffer pool)。数据文件以一个个block/page组成，每个页面的大小为32K、64K字节，页面里存放着用户的数据，数据库启动时，buffer pool在内存中开辟一大块空间，按page组织和管理。
- Input（page）： 从磁盘里读page到buffer中去进行操作。
- Output（page）： page更新完毕，把buffer的page写回到磁盘中
- Pin（page）： 如果page被pin住，这个page将不被允许写回磁盘，pin是防止正在修改的数据页被刷到磁盘，加共享锁或者排他锁是为了并发控制。
- Unpin（page）： 操作和Pin相反
缓冲区管理策略
有了buffer pool，就会有相应的管理策略。从两个维度来看，可以分成4类管理策略。
- Force / No-Force
- Force: 事务提交时，所修改的页面必须强制刷回到持久存储中
- No-Force: 事务提交时，所修改的页面不需要强制刷回到持久存储中
- Steal / No-Steal
- Steal: 允许Buffer Pool里未提交事务所修改的脏页刷回到持久存储
- No-steal: 不允许Buffer Pool里未提交事务所修改的脏页刷到持久存储中
不同的缓冲区的管理策略会有不同的问题。
1. Force策略的问题
Force策略中，提交事务需要把buffer pool里的脏页刷回到磁盘里，就会对持久存储器进行频繁的随机写操作，导致性能下降。
2. No-Steal策略的问题
如果不允许未提交事务的脏页换出，系统的并发量会不高，这是为什么呢？假如说有一些事务修改了很多数据，几乎把整个buffer pool里的page全部占满，但一直没有提交。此时如果其他事务就无法申请空闲页来取数据。
因此，Force和No-Steal对于一个面向磁盘的数据库来讲，是基本上不可用的。通常，我们都会采用No-Force和Steal这种组合方式来完成数据库缓冲区的管理，虽然这种策略有很好的性能，但如何保证事物的原子性和持久性呢？
No-Force这种策略下，事故提交后，所修改的数据页没有刷回至持久存储，若此时发生断电了或者系统崩溃了，就会违背事务的原子性和持久性。
而Steal这种策略下，如果Buffer Pool中未提交的事务所修改的脏页允许刷回到持久存储里，如果此时发生断电或者系统崩溃，事务并没有提交，但是修改的脏页已经上回到持久存储了，覆盖了原来正确的数据，就会违背事务的原子性。
解决方案：日志
虽然No-Force和Steal这两种策略组合起来有更好的性能，但不能保证事务的原子性和持久性。数据库是怎样解决的呢？这里就会引入一个非常经典的一个机制——通过日志的方式来保证事务的原子性和持久性。
1. No-Force → Redo Log
事务提交时，数据页不需要刷回持久存储，为了保证持久性，先把Redo Log写入日志文件。Redo log记录修改数据对象的新值(After Image, AFIM)
2. Steal → Undo Log
允许Buffer Pool未提交事务所修改的脏页刷回到持久存储，为了保证原子性，先把Undo Log写入日志文件。Undo Log记录修改数据对象的旧值(Before Image, BFIM)
缓存区管理策略和事务恢复的关系
Force和No-force，Steal和No-steal组合起来可以得到四种事务恢复类型。在最右上角的这种方式，是数据库里非常常见Steal+No-Force的，这种方式的性能是最佳的，但是因为它既需要做undo log，也需要做redo log，恢复较慢。
左下角的这种方式，既没有undo log，也没有redo log，因此性能是最差的。它的优点是恢复很快。这种没有redo log也没有undo log的方式，也有一种对应的技术：Shadow Paging。IBM早期的数据库System R采用的就是这种技术，如今大部分数据库都不再采用这种技术，唯一一个例外就是LMDB，它仍在使用这种方式来做恢复。
不同的Buffer Pool的管理策略和更新方式决定了数据库的恢复策略。接下来，我们来通过一个例子来说明。
下图的日志中，左面这一栏是undo log，一开始有A、B、C三条数据，T1修改了A，T2修改了B和C。那么它的日志大概就是这样一个形式，记录数据对象的旧值。如果此时发生崩溃，恢复时是从后往前，对未提交的事务的日志做undo操作。这样就可以撤销那些未提交事务的修改，保证数据恢复到原来的值。
redo log只记录新值，假如事务提交后发生系统崩溃，恢复时对日志进行从前往后扫描，对已提交的事务的日志做redo操作，这样就可以把事务恢复回来。
undo log和redo log的结合，既需要记录旧值，也需要记录新值。恢复时通常是三个阶段，第一个阶段是分析阶段，第二个阶段是redo操作，从前往后把所有已经提交的事务做redo操作。第三个阶段是undo操作，即从后往前对未提交的事务做undo操作。
Buffer Pool和Log Buffer的关系
通过日志机制，可以把对数据库文件的随机的写操作变成顺序写操作。对日志的操作采用的是append的方式，如果buffer满了或是需要commit事务时，才将log buffer刷回到日志文件里，这个过程是一个顺序的操作，从而极大的提高了数据库的性能。实际上，这也是由当时的硬件特点来决定的。
Write Ahead Logging
我们再来看一下Write Ahead Logging（WAL）协议。上文提到过，在任何被修改的page被刷进硬盘之前，必须保证log先写入磁盘。在确保事务对数据的修改的logo写入磁盘之后，这个事务才能提交。分别对应了下面的两点：
- Steal policy。更新non-volatile storage中的页面时，必须记录undo log。保证事务的原子性。
- No-Force policy。提交事务时，必须记录redo log。保证事务的持久性。
WAL协议提出后，细节还不够清晰，数据库系统本身处理很复杂，需要考虑并发控制、checkpoint性能、恢复时又发生系统崩溃的情况、怎样缩短恢复时间、加锁等等。当时业内并没有一篇论文能讲述实际的成功案例，把这些复杂的因素从上到下串联起来，直到IBM DB2的研究者提出了ARIES的恢复算法，对其他数据库系统产生巨大的影响，很多数据库的恢复机制都借鉴了ARIES的实现。
Greenplum采用的策略
在介绍完理论知识后，我们来看看Greenplum和PostgreSQL采用了什么策略。上文中提到，Steal+No-Force的性能最好。因此，毫无疑问，Greenplum的master节点、segment节点和PostgreSQL都采用了这种方式。大家可能会有一个问题：Greenplum和PostgreSQL有redo log，没有undo Log，事务回滚不需要做undo操作，这是为什么呢？
这是因为Greenplum和PostgreSQL采用的是MVCC并发控制技术，更新元组操作不是in-place update，而是重新创建tuple。也就是说，更新一条tuple时，并不在原来的tuple上进行修改，而是在相同的存储空间里另外创建一个新的tuple，把新值写到tuple里。在heap表的存储空间里，已经有元组的旧值，不需要额外通过undo log记录旧值。当事务的扫描到一个tuple时，可以通过可见性的判断来决定这个tuple是否对当前的事务可见。因此Greenplum和PostgreSQL并没有undo log，事务回滚时也不需要undo操作。
现在让我们来思考两个问题：
问题1. MySQL同样采用MVCC，事务恢复的时候为什么需要undo log？
这是因为版本的存储方式（Version Storage）不同。Greenplum和PostgreSQL上，任何对tuple的修改都在主表上创建一个新的tuple进行修改，再通过一个指针指向新的tuple。MySQL和Oracle的Version Storage的实现是另一种机制：Delta Storage。把的差异变化记录到Delta Storage里，形成一个链，这种差异的存储被称为rollback segment，即回滚段。如果对Version Storage感兴趣，可以去阅读论文 《Yingjun Wu, An Empirical Evaluation of In-Memory Multi-Version Concurrency Control, VLDB 2017》
问题2. 出现新硬件（NVRAM）并不断得到广泛应用，WAL是否适合新硬件特点？
通过日志的方式，把对数据库文件的随机写操作变成了顺序写操作，一定程度上讲，这也是由硬件特点决定的。如今产生了很多新硬件，比如NVRAM。NVRAM的特点是，它是一种非易失性的随机访问存储器，有内存的访问速度和特点，并切具有持久性，断电不会丢数据，随机写和顺序写性能差别并不大。
在这种情况下，当今数据库架构以及WAL机制是否适合新硬件的特点？能否发挥新硬件的特性？业内有很多研究者已经进行了这方面的探索，比如说CMU在VLDB2016 提出了在NVRAM基础上实现的数据库恢复的协议——Write-Behind Logging，如果有兴趣可以阅读这篇论文。
二、分布式事务和两阶段提交的原理
讲完在单机版数据库事务A和D两个性质的实现，我们再来看分布式事务的事务实现。
分布式事务
分布式事务是指分布式环境下的事务，是一个典型的嵌套式事务，一个事务由多个工作节点的子事务组成。同样必须保证参与分布式事务的各个场地（节点）的事务，要么全部提交，要么全部rollback，不能出现部分提交的情况。
两阶段提交协议
通过下图，我们可以看到，一阶段提交并不能保证分布式的原则性。用户通过A发起查询请求并提交，这个查询所涉及到的操作包括在B节点更新X，在C节点更新Y。设想这样一种情况，A向B、C发送提交请求，在B节点，更新数据X并提交成功，在C节点，更新数据Y，但是并没有将Y的修改写入稳定存储器，此时C节点数据库发生系统崩溃，系统需要进行恢复操作，该事务并没有提交成功，所以对数据Y的更新丢失了。这个分布式事务，B提交成功而C提交失败，使得数据库处于不一致状态，违背了事务的原子性。
于是，Jim Gray等研究者在1978年提出了两阶段提交协议，用于保证分布式事务提交的原子性，这是一个非常经典的分布式提交协议。两阶段协议可以用于单机集中式系统，由事务管理器协调多个资源管理器；也可以用于分布式系统，由一个全局的事务管理器协调各个子系统的局部事务管理器完成两阶段提交。
这个协议有两个角色，如图所示，A节点是事务的协调者，B和C是事务的参与者。事务的提交分成两个阶段，第一个阶段是投票阶段，也被称做prepare阶段；第二个阶段是决定阶段。在第一个阶段，假设有一个事务已经完成操作，决定提交。首先需要发一个prepare消息给B和C节点这两个参与者，B和C收到消息后，根据自己的实际情况，如果可以处理提交，就会回复一个ready，来告知已经准备好提交。当A节点收到B和C参与者所有的确认消息后，才会发送commit消息，让B和C进行提交。如果，有节点回复无法提交，则整个事务提交不能执行，A节点会发送abort命令给所有参与者。
接下来我们来结合两阶段协议和日志操作来看一下它是怎样实现的。
在阶段1，A的事务管理器将<prepare, T>加入日志中，并强制将日志写入稳定存储器，然后将prepare T的消息发到所有参与这个事务的节点，在本例中就是节点B和C，B和C系统的事务管理器在接到prepare消息后，来决定是否提交T中属于它的那部分操作，如果不能提交（比如出现任何错误），事务管理器就在日志中加一个<not prepared, T>记录，并且向A发送abort T作为响应，如果能提交，事务管理器就在日志中加一个<ready, T>记录（或者prepared记录）并且将所有与T相关的日志记录强制写入稳定存储器中，然后向A回复一条ready T作为响应。
在阶段2，当A收到所有对prepare消息回答后，就可以确定T是提交还是中止。如果A收到所有参与者的ready应答消息后，该事务可以提交，否则该事务必须撤销。提交事务T时，将<commit T>（或者<abort T>，如果中止事务）日志记录写入日志，并且强制将日志写入稳定存储器中，并且将commit消息（或者abort消息，如果中止事务）发到所有参与者，其他节点收到commit消息后，将<commit T>写入日志。
在一些2PC的实现里，第二阶段的最后，参与者向协调者发送确认消息。A收到所有参与者的确认消息后，把记录<complete T>加入日志文件中。
需要注意的是，参与者收到协调者发送来的prepare消息，在应答ready之前，必须保证该事务所有操作的日志记录已经被刷入稳定存储器。
两阶段协议也可以用于单机集中式系统。如果各个资源管理器有独立的日志缓冲区和日志文件，则需要2PC协议保证提交的原子性。
需要处理的故障
两阶段的过程中，可能出现各种各样的故障，下面是两种常见的故障：
1. 参与者故障
参与者恢复后，根据日志记录来决定重做或者撤销事务T，是否有<Ready T>记录？是否有<Commit T>或者<Rollback T>，如果没有，可以询问参与者。
2. 协调者故障
如果协调者发生故障，参与者必须决定提交或者撤销事务，在某些情况下，参与者并不知道是否提交事务，所以必须等协调者从失败中恢复。
这就是两阶段提交存在的问题。协调者回复的时间不确定，有可能需要很长时间，而参与者需要持有事务T的资源，等待协调者的消息，这就造成了阻塞的问题，事务T的执行阻塞在协调者的恢复。或者另一种情况，由于网络故障，协调者的提交或者撤销消息迟迟不能发送到参与者，同样会造成各个子事务阻塞在各个参与者，每个参与者事务所占用的系统资源也不能释放，降低了系统的可靠性和可用性，这也是两阶段提交协议最突出的问题。图片出自Philip A. Bernstein著作Principles of Transaction Process
针对协调者发生崩溃或者协调者堵塞的问题，业内提出一些优化，以及新的协议，比如说三阶段提交，三阶段提交在两阶段基础上再增加了一个阶段，目的是保证事务不被阻塞。但是三阶段的实现代价太高，因此三阶段提交协议目前只是理论上的存在，还未被使用到商业数据库系统里。两阶段协议虽然存在一些问题，但数据库实现者可以通过一些方法进行规避。
三、Greenplum的两阶段提交
在讲述Greenplum两阶段提交前，我们先来看一下PostgreSQL的两阶段提交，Greenplum是基于PostgreSQL的基础上实现了分布式事务和两阶段提交，有一些逻辑非常相似。
PostgreSQL的两阶段提交
PostgreSQL是一个集中式数据库，没有实现分布式事务管理器。PostgreSQL实现了对两阶段提交协议的支持，实际上是作为分布式事务的参与者，也就是说，PostgreSQL数据库可以作为分布式数据库的一个场地，完成协调者对其发起的两阶段提交。
PostgreSQL主要通过PREPARE TRANSACTION相关SQL命令实现对两阶段提交协议的支持。然后通过PREPARE TRANSACTION、COMMIT PREPARED、ROLLBACK PREPARED命令实现了对两阶段提交协议参与者的支持。PREPARE TRANSACTION对应两阶段提交协议的第一个阶段，协调者向参与者发送PREPARE命令。COMMIT/ROLLBACK PREPARED命令对应第二阶段，协调者再收集到所有参与者的PREPARE响应消息后，向参与者发送COMMIT或者ROLLBACK命令。
我们考虑两个问题
问题 1：协调者向参与者发prepare之后，参与者完成prepare相应操作，在发送ready之前，会把日志落盘。那参与者申请的锁会不会释放？
参与者prepare时，会将日志落盘，释放一些资源，但不会释放申请的锁。
在PostgreSQL里，执行完PREPARE语句之后，此时把数据库停掉（或者杀掉所有数据库进程）再启动起来，会发现pg_locks里，prepared事务所申请的还在pg_lock表里。大家可能会有这样一个问题：
问题2: 既然pg_locks是一个内存的数据结构，记录各个backend进程申请的锁，那数据库重启后，为什么已经prepared事务申请的锁仍在pg_lock表呢？
这个操作涉及到prepare事务的恢复过程，它是这样完成的：
当执行prepare时候，PG会把该事务的lock信息当做prepare日志记录的一部分记录在日志文件（xlog）里。当数据库重新启动，会读这个日志文件（xlog）这条日志记录，把锁“还原”到pg_lock表里。
- StartupXlog函数发现XLOG_XACT_PREPARE日志记录进行redo，调用函数recreateTwoPhaseFile将该日志记录中的信息放到pg_twophase目录下的文件里，每一个prepared事务对应一个文件。
- StartupXlog函数调用recoverPreparedTransaction函数读取pg_twophase目录下的文件并进行相关操作，为该事务重新获取锁。
- 恢复成功后，删掉pg_twophase目录下的文件。
如果分布式数据库系统的某一个节点发生故障而进行恢复，如果在日志文件里发现一个事务，有<ready T>日志记录，而没有<commit T>或者<abort T>记录，也就是说该事务完成了两阶段提交的第一个阶段，恢复算法就需要和协调者进行联系以确定该事务是否提交，我们将这种事务称为疑问事务（in-doubt transaction）。其他正常的事务必须等到疑问事务提交或者回滚之后才能开始进行，因为有可能产生写写冲突，而这一过程可能需要很长一段时间，为了规避这个问题，在进行第一阶段提交时，会同时记载该事务的封锁信息，也就是说，参与者所记录的日志记录不是<ready T>，而是<ready T, L>，L是所持有写锁的列表。在这个数据库节点进行恢复时，对于疑问事务的<ready T, L>记录，会重新为该疑问事务申请锁。这样为疑问事务重新申请锁之后，其他事务就不需要等待疑问事务的提交或者回滚，可以继续运行，根据操作申请读锁或者写锁，如果写锁和疑问事务的写锁有冲突，则需要等待疑问事务完成两阶段提交并释放写锁。这种实现的理论依据可以参考《数据库系统概念》19.4.1.3。
通过这个实验，我们可以看到参与者需要有能力恢复prepare事务，恢复后，只要协调者发来commit或者rollback就能继续完成这个事务。在Greenplum数据库里如果QE在prepare之后发生崩溃，QD会在函数doNotifyingCommitPrepared里重试，QE恢复prepare事务的逻辑与上述PostgreSQL的步骤类似。
Greenplum实现分布式事务与并发控制
我们再看一下Greenplum是如何实现分布式事务的并发控制。上图中，左边这一栏是Greenplum复用的PostgresSQL的实现，包括本地事务的创建，提交状态迁移等。
右边是Greenplum在这个基础上独立实现的功能，包括分布式事务的创建、状态迁移、QD向QE发起两阶段提交等，分布式死锁检测，全局分布式快照创建与同步。
分布式事务信息在QD和QE之间的同步
我们再来看一下，在Greenplum中，分布式事务的信息怎样在QE和QD之间同步。
这里需要提到一个TMGXACT分布式事务结构体，当创建一个新的事务时，需要在这个结构体里指定。
- 分布式事务id
- 分布式事务管理器启动的时间戳
- 活跃分布式事务中最小的事务id
- session id
这些分布式事务信息，包括分布式快照信息，再通过这种序列化的方式，把它序列化到一个查询计划里，然后再用dispatch的方式发送到segment上。Segment节点作为分布式事务的参与者，需要把这些信息进行反序列化，读到自己的内存里，从而完成一个QD到QE之间的信息的共享。
下图列举了两阶段协议实现的一些主要函数，以及大概的逻辑，方便大家快速找到对应的一些步骤。
Greenplum两阶段提交协议的优化
我们再来看一下Greenplum两阶段提交协议的优化。Greenplum为了提高TP的性能，做了很多优化，比如降低一些锁的竞争等。
关于两阶段提交，这里介绍一个优化，即一阶段提交。因为两阶段协议往往有多个参与者，因此需要进行协调。但在某些情况下，参与者只有一个，它自己就可以决定整个事务是否提交成功，如果它提交成功，则整个事务就提交成功了。此时，两阶段就可以简化为一阶段提交。
这种优化在Bernstein的著作里称为协调权的转移，是指协调者认为可以做这种一阶段提交时，把决定权交给参与者，由参与者决定是否提交。
Greenplum所做的优化和这个类似，但也有不一样的地方。QD在执行提交前，会检查事务是否满足一阶段提交的条件：
- 有写操作，参与者只有一个
- 只读事务
若满足这两个条件中的一个，QD就会调用函数doNotifyingOnePhaseCommit向参与者发送DTX_PROTOCOL_COMMAND_COMMIT_ONEPHASE命令，QE完成提交。
