数据共享和并发编程是计算机应用中的普遍需求, 数据库的事务机制, 能帮助backend程序员编写正确的并发程序，并减轻心智负担. 因为事务具有ACID特性[1]:

1. Atomicity: 修改一组元素, 成功, 则所有元素的变更均生效; 失败, 数据库自动撤销部分元素的变更, rollback到之前状态. 用户不必采取额外的操作.
2. Consistency: 事务执行成功与否, 数据库始终处于一致状态（不是最终一致性）, 事务是将数据库从当前的一致性状态转移到下一个一致性状态的基本操作单位. 用户不必担忧约束遭到破坏.
3. Isolation: 事务并发执行以提高性能, 同时正确性能够得到保障, 用户不必担忧冲突的事务导致concurrent anomaly，不会出现脏读幻读等情况.
4. Durability: 提交的事务对数据库状态的修改具有持久性, 未完成的事务不会修改数据的状态, 即便出现升级重启, 掉电, 故障或者服务崩溃. 数据库能够恢复到正确的状态. 用户不必担忧异常事件造成数据丢失或者状态不一致.

通常单机事务的操作只涉及单机节点上的若干元素, 如果操作涉及的元素横跨多台机器, 比如Bob和Alice的账户信息分别存储在机器A和B上的MySQL服务实例中, Bob向Alice转账. 通常这样的事务称之为分布式事务(distributed transaction). 一般地, 分布式事务做为global事务, 可以分解为若干操作本地数据库的子事务; 子事务本身具有ACID特性, 但要为global事务提供ACID特性, 并非trivial problem[2]. 更一般地, NoSQL数据库提供有限的事务支持, 比如Bigtable支持单行更新事务, 跨行操作的事务也属于分布式事务的范畴[3]. 不难得出: 分布式事务是一种由若干修改本地状态的子事务组合而形成的全局事务.

本文采用Database System Concepts中的定义, 但不够合理. 在实际的应用中, 采用2PC的系统, 也可能没有将全局事务分解为子事务. 所以2PC是:

2PC是一种能够保证原子性和持久性的提交协议, 参与事务的组件有多个, 每个组件分别记录各自操作日志, 操作日志是分离式而非集中式.

2PC没有言及如何对事务做并发控制(不涉及并发控制协议), 仅仅是有别于中心化WAL日志的一种机制. 不考虑性能的情况下, 完全可以通过中心化的TM记录日志, TM通过RPC向其他事务参与者, 发起redo和undo的操作.

分布式事务, 涉及多个局部事务. 网络断开和进程崩溃等故障会导致部分局部事务提交, 部分失败. 要保证Atomicity和Durability, 需要用到提交协议, 2PC和其变种是一种广泛使用的提交协议.

单机事务: 假如采用WAL和DIRECT, STEAL/NOT-FORCE[4]. 事务开始先写<START T> 日志, 修改数据库元素之前, 先写redo日志<T elem new_val>. 如果提交事务, 则写<COMMIT T>日志, 当日志落盘后, apply日志, 更新buffer pool中相应的page, dirty page不必及时写会磁盘, 可以延迟落盘. 如果事务失败, 则写<ABORT T>日志, 不apply日志. 很显然, 未完成事务或者夭折的事务, 不会修改数据库的状态, 恢复时直接跳过. 已提交的事务, 因为dirty page延迟写回磁盘, 最近一次checkpointing的时间也可能早于dirty page落盘时间, 因此需要redo事务T日志.

分布式事务: 本地数据库有自己私有WAL日志. 难以单方面做出rollback或者redo的决定.

Two-Phase Commit Protocol(2PC)[2]

在2PC中, 由一个coordinator和多个participant对分布式事务的提交进行协调. coordinator和participant写各自WAL日志, 便于故障重启后, 对事务进行恢复. coordinator是2阶段提交的发起者. 事务T的提交过程为:

1. prepare阶段: coordinator追加<prepare T>日志记录, 向事务T所涉及的participant发送消息prepare T； 收到消息后, participant判断事务T是否可以提交(申请锁, 冲突检测). 如果可以提交, 则追加日志<ready T>, 并向coordinator发送消息ready T; 如果无法提交, 则追加日志<no T>, 向coordinator发现abort T.
2. commit阶段:

• case 1: coordinator收到全体participant的ready T: coordinator追加<commit T>日志, apply日志; 然后, coordinator向全体participant发送commit T消息, 收到消息后, participant追加<commit T>日志, apply日志修改状态.
• case 2: coordinator收到至少一个participant的abort T 或者等待超时: coordinator追加<abort T>日志, 向全体participant发送abort T消息; 收到信息后, participant追加<abort T>日志.

participant追加 <commit T> 或 <abort T>后, 向coordinator发送acknowledge T消息, coordinator收到所有participant发来的确认后, 写日志<complete T>, T结束.

事务的状态

2PC可类比投票, 投票方均拥有一票否决权, 也可以弃权(网络错误和宕机等错误导致投票超时). 只要获得全票通过, 事务才可提交(committed); 否则, 事务失败(aborted).

1. 当coordinator写下<commit T>日志后, 事务已提交(图中绿色区域);
2. 当至少有一个participant写下<no T>日志后, 事务失败(图中橙色区域).

事务的最终状态确定后, 事务尚未完成, 还有工作要做. 若事务committed, 还有继续往前滚(roll forward), 通知participant执行commit和apply; 若事务aborted, 还要往回滚(rollback), 通知participant做rollback. 如果participant使用局部锁表, 则完成本地事务之后, 需要释放锁, 容许其他事务被调度. 所以roll forward和rollback(在其他文献[2]中提到redo和undo操作)是必不可少的.

事务提交或失败后, 出现故障, 导致coordinator/participant不可用, 无法完成后续操作. 当coordinator/participant恢复可用, 对事务进行恢复时, 也要做rollback或者roll forward. 当然, 未完成的事务, 直接rollback即可.

事务进行恢复时, 如果信息有限, 无法裁决事务的最终执行状态, 则事务处于in-doubt(悬而未决)的状态(黄色区域).

容错

1. 网络错误: coordinator和participant之间出现networking partitioning, 互不可达. 普遍解决方法是: 重试+幂等+超时.
2. coordinator/participant宕机崩溃: 服务要做到high availability, 普遍采用一主多备, 在服务崩溃时, 及时地failover. 比如多个coordinator构成RSM, 如Spanner中的Paxos group[5], 其他系统也可能采用Raft group.

恢复

coordinator恢复

coordinator扫描日志:

1. 只有<prepare T>记录: 说明事务处于outstanding状态, coordinator终止事务即可, 即从图中C <abort T>做起.
2. 有<commit T>但无<complete T>: 说明事务已经提交, 但可能尚未通知participant, 则从C <commit T>做起, roll forward, 通知全体participant做commit和apply.
3. 有<abort T>但无<complete T>: 说明事务已经失败, 从C <abort T>做起, rollback, 通知全体participant做终止事务.
4. 有<complete T>记录: 事务已经完成. 无需处理.

participant恢复

participant扫描日志：

1. 如果有<no T>或<abort T>记录: 说明事务已经失败, 则可以单方面rollback.
2. 如果有<commit T>: 说明事务已经成功提交, 则做本地redo操作即可.
3. 如果只有<ready T>: coordinator无法判断事务的执行状态, 当前事务处于in-doubt状态. 见下文详细描述.

In-doubt事务的恢复:

事务的状态无非outstanding, committed, aborted, complete. 之所以处于in-doubt状态, 是因为故障导致信息缺失, 无法判断事务究竟处于三种状态outstanding, committed, aborted中的哪一种.

1. 在coordinator可用情况下, 首先询问coordinator关于事务T的状态. 如果T处于outstanding或aborted状态, 则终止事务T, rollback.
2. 在coordinator不可用情况下, 询问当前可用的其他participant关于事务T的状态. 如果事务T明确地处于committed或者aborted状态, 则选择roll forward或者rollback即可.
3. 最糟糕的一种情况: coordinator不可用, 并且当前可用的participant日志均只有<ready T>记录. 此时无法采取行动, 因为:

• 事务T可能处于committed状态: coordinator不可用, 全体participant都投票<ready T>.
• 事务T可能处于aborted状态: coordinator和全体投反对票<no T> 的participant不可用.
• 事务T可能处于outstanding状态: coordinator不可用, 在崩溃之前, 并未写下<commit T>或<abort T>.

这种情况下: 只有当coordinator恢复之后, 才能继续推进. 如果系统中有其他的coordinator, 并且该coordinator上执行的事务和in-doubt事务有冲突; 则要么自杀, 要么等待in-doubt事务恢复后, 才能推进.

in-doubt事务, 充分地说明了coordinator的高可用至关重要.

Three-Phase Commit Protocol(3PC)[2]

2PC中, 采用单一的coordinator, 难以做到高可用. 3PC提出了一种解决方法: 增加备用coordinator, 提交事务时, 不只要将<commit T>写入本地日志中, 还要将提交信息复制到至少k个coordinator上. 如果主coordinator崩溃, 备用coordinator选出新任leader, 由它负责处理后续操作. 比如总共有5个coordinator, k=2. 可以容忍两个coordinator故障.

RSM+2PC实现高可用

如下图所示, coordinator采用Paxos实现RSM, 每次写日志时, 日志被复制到Paxos group中. Log replication和Leader Election实现auto failover.

事务处理层和存储层分离

比如在Percolator[3]中, 事务处理层over Bigtable, 可以做到stateless, 通过底层可靠的分布式存储系统实现高可用.

参考文献

[1] Gray J, Reuter A. Transaction processing: concepts and techniques[M]. Elsevier, 1992.

[2] Silberschatz A, Korth H F, Sudarshan S. Database System Concepts. McGraw-Hill Education, 2011.

[3] Peng D, Dabek F. Large-scale Incremental Processing Using Distributed Transactions and Notifications[C]//OSDI. 2010, 10: 1-15.

[4] Hellerstein J M, Stonebraker M, Hamilton J. Architecture of a database system[J]. Foundations and Trends® in Databases, 2007, 1(2): 141-259.

[5] Corbett J C, Dean J, Epstein M, et al. Spanner: Google’s globally distributed database[J]. ACM Transactions on Computer Systems (TOCS), 2013, 31(3): 8.