4.1 Introduction

之前说的2PL是一种实现Recoverable和Serializable的方法，这里介绍两种新的方法，时间戳(TO)和序列图检测(SGT)。和2pl一样，这两种方法也有激进/保守、单机/分布式的区别。

4.2 TO

方法描述起来很简单。每一个transaction，都是被赋予一个独一无二的timestamp。如果两个操作冲突了，调度器就会保证时间戳更早的transaction对应的操作先执行

如果$p_i[x]，q_j[x]$冲突，当且仅当$ts(T_i) < ts(T_j)$，Data Manager先执行p。

满足上述条件的执行一定是可序列化的执行。证明也很简单，就是两个操作如果冲突，一定会按照时间戳的顺序执行。这样SG中就不会有环了。

基本的时间戳算法

基本的TO算法，是一个激进的算法。TM收到任何操作，都立刻转发给DM；如果发现有冲突操作来得太迟，即$p_i[x]$与$q_j[x]$冲突，且$ts(T_i) < ts(T_j)$，q先执行。所以只能abort掉$T_i$。

abort掉之后，需要重发，重发的transaction必须有一个新的时间戳，而且这个时间戳必须造成自己abort的那个要晚，不然会出现一直abort的现象。

具体实现方法是：对于每个object，有一个 queue，作为被pending的任务；一个w-in-transits，一个r-in-transits，表明正在被下层DM执行的读写任务数量（当然，w-in-transits只能是0或者1，这个有点像读写锁）。还有一个max-w-schedued / max-r-schedued，表面已经完成的最大的读写的transaction的TO。

那么，在一个任务到了TM的时候，比如是read，需要判断max-w-schedued 是否比自己大，比自己大直接丢掉；如果比自己小，进一步判断，w-in-transits是否为0，是0可以直接操作，不是0需要等一会，即进入到queue里面。

strict TO

basic TO 只能保证serializability，不能保证recoverability.这个很好理解，因为一个transaction完全可以读另外一个事务的值，然后先commit了，basic TO对此并没有限制。

实现的目标很简单：就是让一个write所在的transaction，在abort/commit之前，别人不能读或者写。因此实现起来也比较简单，在basic TO中，当一个写完成的时候，立刻更新 w-in-transits （减1），现在改为 abort/commit 之后在更新，即写操作会阻塞之后所有的读操作或者写操作。

这个看起来更像是读写锁了，但是跟2PL还是有点不太一样，那就是对读。对于（strict）2PL，如果读一旦上锁，那么直到该transaction结束，才会释放这个锁；但是对于strict TO 不一样，读结束之后可以立刻进行下一个写。

timestamp management

从上面介绍的方法来看，TO一个比较突出的问题就是太占空间。一个object需要有好几个参数。所以最后很有可能timestamp比数据库本身还大。

实际上，对于一个TM来说，收到的transaction请求往往是一个时间窗口内的，不会差距太大。因此可以设置一个$ts_{min}$，所有低于这个timestamp的都可以删了，然后默认每个object上的最小值都是这个值。如果真的有transaction低于这个值，直接杀掉。这样误杀率也会很低。

distributed TO

Distributed TO 非常简单，因为每个机器只用关心自己存储的object的timestamp信息，彼此之间没有任何交互，只需要有一个中心化的timestamp生成器就可以了。这个跟2PL不一样，2PL还需要全局交互检查死锁。

conservative TO

保守策略只有一点不同，就是在收到请求之后等一小会，等一会带着更小的timestamp的请求过来，这样会减少abort的几率。此处又有一个trade-off。

还有一种极端保守的策略，固定好Transaction Manager的数量，保证在queue里面有来自所有TM的operation，且给他们排好序。这样确保每次执行的都是ts最小的，没有任何transaction会被abort。如果一个TM没有任何操作可做，可以发NULL。

但其实这种极端保守等价于串行执行了。没有任何意义。有一种改进的策略，是指定 transaction class，每个class 有一个readset和一个writeset，每个transaction一定属于一个（或多个）transaction class，即他的readset/writeset是该transaction class的子集。因此，只有一个class内的会有冲突。于是上文说的，queue只用保证一个会有冲突的transaction class对应的TM都有操作（一个transaction class对应一个TM）即可。这样可以提高并行度，但需要知道所有transaction的readset、writeset。

Serialization Graph Testing

Basic SGT

这个方法是从本质上解决非串行化的问题，可以说是一个比较紧的界。具体来说，每当有新的操作产生，（可能）会有新的conflict，即不同transaction之间的依赖关系产生。也就是说，这个图会不断地增长。如果一旦发现环，就说明已经不是serializable了，需要终止掉当前的这个事务，使得依赖图依然是一个无环图。

实现起来比较麻烦，首先需要维护每个transaction的readset和writeset；其次需要加入新操作之后能够迅速地找到conflict（书中没有说怎么找，个人猜测每个 object 本身有一个transaction list）

还有一个难点是如何把确定没有用的transaction从图中移走。即使一个transaction已经commit了，也不能从图中移走；原因是因为他依然可能构成环。事实上，一个transaction commit之后，不会再有新的入边（它不会读新的东西了，因此也不会再去依赖别人），如果它完全没有入边，那么可以确定永远不会构成环。所以只把没有入边的节点给剔除掉。

conservative SGT

同样的，还有一种保守的SGT方法，即让transaction延迟一下，等到条件达到才进行操作。这里也需要transaction 预先知道自己的readset和writeset。每当一个transaction开始的时候，就往 SSG里面添加若干条边。因为每次都加的是入边，所以永远不会有环。但是需要保证的是，operations执行的顺序也是按照SSG里面的顺序来的。

具体操作是，当$T_i$的一个操作p排在queue的头部时，需要等

  1. 所有发送给DM的与p冲突的操作，已经完成（ack）
  2. 所以在SSG中，在$T_i$的直接前继节点，所有与p冲突的操作都已经完成。（或者没有与p冲突的操作）

Recoverability

但是同样的，SGT和conservative SGT都不保证Recoverability。因为并不能保证后面的transaction后commit。也可以用和strict TO的方法，使得transaction可以达到strict：等到transaction commit/abort的时候，才把对应的 write 置为 ack，即把上面第一个条件阻塞住。

也可以用来实现更若的recoverability。比如为了实现ADA，（只读已经commit的），需要区分read/write。跟上面的区别在于，write不会阻塞write。有一个方法是，对于任何一个$r_i[x]$， 在SSG中所有 w-scheduled 中含有x的transaction，会形成一条链，那么在$T_i$最前面的一个为 $T_j$。 只有 $T_j$ commit之后， $r_i$ 才会被执行。

如果仅仅为了实现Recoverable，（冲突操作的顺序和commit的顺序一样），跟上面的区别在于，只需要堵塞住 $T_i$ 的commit即可。当然，因为这个不能避免 cascading abort；当一个transaction abort的时候，所有依赖它的也会被abort掉。

Distributed SGT

因为SSG分布在不同机器上，所有检查 cycle非常麻烦，需要多个图合并；同时，跟死锁不一样，死锁的时候大家都会等着；而SGT中，如果没发现cycle，会立刻往下执行，就导致错误。所以每有一个新的transaction，需要同步一次SSG，这个开销非常大。所以SSG不太适合在分布式系统中。（当然，系统规模比较小，可以考虑用一个机器单独处理SSG）

Space-efficient SGT

跳过。

certifier (乐观控制)

之前说的，所有的操作到达了Scheduler的时候，都会被检查，执行、回滚或者delay。另外一种方式，是直接操作，最后commit的时候再检查。2PL、TO、SGT都有对应的乐观的版本。

2PL certifier

每次收到read/write 请求，直接执行；收到commit请求，判断当前transaction 是否跟 任何 active的transaction conflict；如果有就abort。
需要的数据结构有：transaction nodes；每个transaction 有readset[$T_i$]和writeset[$T_i$]。证明：

  1. 假设H为任意一个上述协议产生的history，$T_j \rightarrow T_i$ 是SG(H)中一条边，因此会有两个操作 $p_i[x]$ 和 $q_j[x]$ 为冲突操作，且 $p_j[x] < p_i[x]$.
  2. 假设$T_i$是先调用 commit (certifier)的，那么此时, $p_j[x]$肯定是被执行完的，否则不会$p_j[x]$ < $p_i[x]$。那么在 $T_i$ 进行检查的时候，肯定会被abort掉。因此，$T_j$ 先被 certified。
  3. 如果SG(H)中有一个环，$T_j, T_i, …, T_k, T_j$，$T_j$ 在自己之前被certified，显然不可能。

为什么称之为 2PL 呢（实际上并没有用到任何lock）？因为每次一个operation被执行时，相当于加上了一把锁；任何两个冲突的事务，先提交的会被abort。

为了保证recoverability，需要额外加一个，如果一个transaction $T_i$ 被 abort掉了，那么读它的transaction $T_j$ 也必须要abort。但是怎么做呢：选取 readset[$T_j$] 和 writeset[$T_i$] 交集不为空。但这样会误杀，因为可能 $T_i$执行在后。但是上述的方法没法判断两个操作的先后顺序关系。因此只能误杀了。

（如此看来，如果不引入延迟，certifier没办法达到 ADA?)

最后从性能分析上来说，2PL certifier比原生的2PL性能要差；因为两个冲突的事务，会执行到结束之后才发现要abort，这样会浪费执行的资源。因此，当conflict程度大的时候，乐观控制性能总是会下降地特别快。

SGT certifier

SGT本质上和 certifier很像；所以改起来很容易。在Scheduler收到请求的时候，直接发送到DM。只在收到commit请求的时候，才会去判断是否有环；如果有环，则需要abort掉当前的事务。Recoverability是一样的，当一个事务被abort掉，所有(可能)依赖于它的事务。

TO certifier

和 Basic TO没啥区别，就是在commit的时候检查有没有按照 timestamp order 执行的；没有的话abort掉自己。所以这里用乐观控制没啥用。性能反而低了，因为有大量的浪费。

distributed certifier

和之前distributed SGT一样，local的certifier不准，必须要有全局的certifier。

组合的策略

之前讨论的策略主要是三种，2PL，TO，SGT，悲观和乐观的都有。这一节主要讨论的是如何将多种方法组合起来使用。回到冲突本身，有rw-conflict和ww-conflict，如果对这两种冲突使用同一种策略叫 pure scheduler，如果使用不同策略叫 mixed scheduler。之前我们讨论的都是 pure。

rw serialization graph (rw SG) 也可以分成两个，每个图里面的边，都是由某一种冲突构成的（rw-conflict/ww-conflict)。记作 $SG_{rw}(H)$ 或者 $SG_{ww}(H)$。只要两个图的并集，是一个无环图，那么history也是SR的。

Thomas’ Write Rule (TWR)

在TO中，如果收到了一个比较早的写，$w_i[x]$，但是之前已经执行过 $w_j[x]$, 且 i < j。按照Basic TO，这个transaction应该回滚的。但是如果我们只关心ww-conflict，其实这里没必要回滚。因为我们可以“假装” $w_i[x]$ 已经执行过了，效果是一样的（会被 $w_j[x]$覆盖）。这个现象称之为 TWR。再加一个rw synchronizer，就可以完美处理所有的冲突了。下面会介绍两种基于TWR的设计。

Pure integrated scheduler

就是Basic TO (rw-conflict) + TWR (ww-conflict)。Basic TO只关心读写冲突。所以会对每个 object，记所有的tx的timestamp。

A mixed integrated scheduler

这里是 strict 2PL + TWR。需要保证下面的条件；

  1. 如果在 $SG_{rw}(H)$ 中，$T_i \rightarrow T_j$, 则 ts($T_i$) < ts($T_j$)。

先看下，如果$SG_{rw}(H)$满足这个条件，同时又因为 $SG_{ww}(H)$ 中，也一定满足这个条件，所以两个图的并集也一定是无环的（证明和TO的证明是一样的）。所以就能保证它是SR的。后面就展开如何保证这个条件。

进一步推导，如果$SG_{rw}(H)$中 $T_i < T_j$。说明 $T_i$先拿到锁，又因为是strict 2PL，直到commit才会释放锁。所以$T_i$会先commit。

  1. 如果 $T_i$ 先发出commit请求，则 ts($T_i$) < ts($T_j)。
    如果2满足，则1一定满足。（三段论）。

实现中，如果按照basic TO，先给每个transaction赋一个ts，则不能保证条件2，因为谁先拿到锁谁会先试图commit。即使Scheduler上再套一层，按照顺序一个一个接受commit，也不行，因为只有ts小的有可能会被大的锁阻塞住（类似死锁）。所以只能说在commit的时候才给每个transaction赋ts，同时阻塞所有的写（因为只有ts TWR才能工作），假装已经完成，但实际上并没有操作。

这种设计一是挺反直觉；第二个问题在于，read没法读自己的。解决方法是：如果在read请求，试图拿读锁的时候，发现写锁已经被自己拿住了，那么直接读自己的即可；否则的话，要么被其他人的写锁阻塞住，要么成功拿到读锁，直接执行读就可以了。不可能存在在ts比自己小的写，且这个被Scheduler阻塞住，因为这些写的ts肯定比自己大。