事务并发控制之时间戳排序算法

事务是一系列读写操作的集合，两个并发的事务间，必然会存在交错执行的操作，串行化调度算法使得并发事务的执行结果和无并发情况下的结果一致，就像是在串行执行一样。串行化调度算法的实现主要有两个思路，一个是以两阶段锁（2PL）为代表的有锁实现方式，这种方式相对”悲观“，因为无法预知之后是否会发生非串行化的冲突，所以”悲观“地在可能会产生冲突的数据上预先加锁；另一种则是以时间戳排序（timestamp ordering）为代表的”乐观“无锁实现方式，它只有在真的发现非串行化错误时才做处理。

本篇文章将详细介绍在单版本数据库系统和多版本（MVCC）数据库系统中的时间戳排序算法。在此之前将先介绍SG和MVSG这两种判断事务分别在单版本和多版本系统中是否是串行化的方法，它们将作为评定时间戳排序调度算法是否正确的标准。

串行化理论基础

我们用serialization graph (SG)作为分析一个事务的历史（history）是否为串行化的依据，举一个写偏斜（write knew）的例子：

H1: r1[x] r2[y] w1[y] w2[x]