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

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

串行化理论基础

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

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

SG(H1)为：

图中的箭头表示的是依赖关系，有的又称为冲突关系，总共分为三种冲突，读写（rw），写读（wr），写写（ww），这些冲突可以体现事务之前的顺序，拿写读冲突举例，如果T2读到了T1的写，则表示T2发生在T1后，T1<T2，而如果有别的冲突使得T2<T1，则顺序混乱，所以当SG中的依赖关系没有成环时，则历史是串行化的。

recoverability

SG不成环只能保证事务的隔离性，数据库系统还需要保证事务的可恢复性，即committed的事务不会被未提交的事务的失败影响，举一个不可恢复事务的例子

H2: w1[x] r2[x] c2 a1 

T2读到了T1的写，并且提交了，T1再回滚，T1的写将对T2造成不可恢复的影响。那是不是T2读到T1的写之后等T1成功提交后再提交就行了？可以，但是这会导致联级回滚（cascading abort），在T1失败时，所有和T1有依赖链的未提交事务都要回滚。为了避免这种现象索性禁止事务读取未提交的写，这也是为什么ANSI在Read Committed隔离级别下就禁止了脏读。

Timestamp Ordering

用时间戳排序调度算法时，事务管理器给每个事务一个时间戳，管理器根据时间戳进行冲突的安排。

• TO规则：数据管理器将按照时间戳的大小，依次执行冲突的操作。

结合SG分析一下这个规则如何保证正确性，其实很好理解，TO用时间戳规定了事务发生的顺序，也就是说时间戳小的操作永远不可能发生在时间戳大的操作后面，这个约束使SG永远不会成环。

TO现实方式

时间戳排序的基本实现（Basic TO）：每个事务有一个的时间戳，事务管理器在每个数据上维护一个结构体max-q-scheduled[x]记录发生在这个数据上冲突的大时间戳，如果有比这个时间戳小的冲突，则拒绝。严格的实现（strict TO）则在此的基础上为了保证recoverability，禁止了脏读。

MVCC

上面讲的都是基于单版本系统的，多版本并发控制算法允许每个写操作产生一个新的版本数据，读操作可以选择读取过去的版本数据，其好处在于事务管理器不用再拒绝那些”过时的读“（arrive too late）。比如说，在但版本的系统中，一个读操作在执行之前一旦有别的写操作先执行了，读操作想要读的数据就被覆盖了，它只能被拒绝，而多版本系统允许了它读历史数据。而正是这个特性带来了新的串行化问题。

H3: w0[x0] w0[y0] c0 r1[x0] r1[y0] w1[x1] w2[x2] c1 r1[x1] r2[y1] c1 r2[x0] r2[y1] c2

SG(H3)为

SG并没有成环，但是稍微仔细分析就可以发现H并不是串行化历史，通过w1[x0]…w1[x1]...r2[x0]，我们不仅能得出T0<T2，还可以得出T2<T1，因为T2并没有读到T1写的x1。

MVSG和SG相比结合了对版本顺序（version ordering ）和冲突的关系，串行化事务MVSG是无环的。虽然内部实现是多版本，但是MV系统对外表现是和单版本系统一样的，MV串行化事务历史是一定可以等价为单版本串行化事务历史的，具体证明参考《concurrency control and recovery in database systems》chapter4

MVTO

MVTO调度器为每个事务都有一个的时间戳，表示为ts(Ti)。每个操作都有其对应事务的时间戳。每个版本都由写它的事务的时间戳来标示，MVTO也采取先到先服务的原则，使得对数据的操作看起来像单版本系统一样，与单版本Basic TO不同的是，MVTO允许”迟到“的读操作去读历史版本，但是MVTO同样不允许“迟到”的写，比如这种情况，w0[x0]在t0写后， r2[x0]用t2时间戳读，如果此时有w1[x1]想用t1去写x1（t0<t1<t2），则会被拒绝。因为读操作读的是小于ts(Ti)的大时间戳版本数据，一个写操作的“迟到”会使已经处理的读。

另外，MVTO还应该考虑数据可恢复性，推迟对有脏读事务的提交。综上，其算法可总结为：