6-1. 基于有效性检验的调度在线视频

大家好，今天我们来讲构造冲突可串行化调度的其他调度协议

这个调度协议主要有两个

一个是基于时间戳的调度协议

一个是基于有效性检查的调度协议

我们先来看一下基于时间戳的调度协议

顾名思义，基于时间戳的调度协议主要是利用事务启动的时间戳

也就是说每一个事务在启动的时候

数据库系统会赋予这个事务唯一的时间标记

这个时间标记可以是系统的时钟值或者是逻辑上的一个计数值

都可以，只要它是惟一的就行

基于时间戳的调度协议的基本原理是这样

每一个事务在开始执行的时候都给它赋予一个时间戳

那么事务的时间戳决定了它串行化的顺序

也就是说事务Ti它的时间戳小于事务Tj的时间戳

那么我们系统要产生的调度必须等价于Ti、Tj这样一种串行调度

也就是说，它实际上是依据这样一种原理

为了来进行控制的话，我们基于时间戳的调度协议有以下几个标记需要我们知道的

首先第一个时间戳，比如说一个数T，它的时间戳记为TS(T)

接下来，比如说如果事务Ti小于事务Tj的时间戳的话

就说明事务Ti比Tj开始的早

也就是说事务Ti更年老一些，事务Tj更年轻一些

W（Q），Q表示数据项，W表示write，写

W（Q）表示的就是在数据项Q上成功执行写操作的所有事务的最大时间戳

R(Q)就是在Q上执行读操作的所有事务的最大时间戳

有了这些时间戳，我们就有了一个排序协议

这个排序协议是这样子的

第一个，如果T想要执行一个读操作，比如说它在Q上执行一个读操作的话

它能不能执行呢，我们就根据下面的条件来进行判断

T的时间戳是不是与目前Q上最大的写时间戳，跟它相比较

它是不是比它更年老

也就是说，如果目前Q上最大的写时间戳比T的时间戳还要年轻的话

那么T就回退

T是一个年老的事务，但是有年轻的事务写了Q

T就不能执行了，它就要回退，否则我们就要T来读数据Q

并且把Q上最大的读时间戳进行修改

修改成T的时间戳和Q它目前的时间戳的对比那个最大

那个最年轻就赋予给R(Q)

第二个，如果T要执行写操作

也就是说，我们在Q上执行写操作的话，让T来执行写操作

那么它能不能写呢

这要看T的时间戳和Q上最大的读时间戳进行比较

如果T的时间戳比最大的读时间戳要小

T是一个更年老的事务，更年老的事务要写

更年轻的事务已经读了Q，这个时候T不能写，它必须要回退

当然也一样，如果T的时间戳比Q上最大的写时间戳还要小

也就是说，有更年轻的事务写了Q，T更年老，T也必须回退

而如果不是这两种条件的话，那我们就执行T

并且把T的时间戳作为Q上的最大写时间戳，对W(Q)进行修改

这就是排序的一个协议

被回退的事务系统给它重新赋予一个时间戳

然后再重新启动，这就是这个协议

我们可以用一个例子来说一下

比如说有三个事务，T1，T2,T3，有几个数据项A、B、C

对数据项来说，初始的读和写的时间戳都是0

比如T1的时间戳是200，T2的时间戳是150，T3的时间戳是175的话

显然T1更年轻，T2最年老，T3是中间的

如果现在T1要读这个数据B，因为B上的读时间为0

因为它初始化的时候R(B)实际上是等于0，W(B)也等于0

我们通过刚才的排序协议T1实际上是可以去读B

把B上的R(Q)变成200，也就是变成T的时间戳

同理，如果是T2要去读A，A的时间戳变成T2的时间戳，150

同理，T3读C的话，C上的时间戳变成T的时间戳，175

但是如果T1要去写B的话

这个时候写的时间戳T1就必须要和B上的读时间戳进行比较

B上的读时间戳200和T1实际上是一样的，也就是不是比它更大一些

这个时候我们把B上的写时间戳也进行修改

但是如果T1要去修改A的话

这个时候我们也根据排序协议，它也可以去进行修改

但是如果我们现在让T2去写C的话

那么我们看，T2的时间戳是150，而C的R的时间戳是175

显然T2要比C要小，也就是说

T2更年老，它必须要回退，所以它就要终止了

而T3也是一样，它要对A进行写的话也一样

T3因为比A要年老，它也要回退

这样我们通过如果要在冲突的数据上进行写的话

我们通过这样一种排序、回退

我们就把三个事务的执行顺序就给确定了

那么在这个过程当中，我们会发现一个问题

其中比如说，我们无论是T1写A和T3写A

显然我们说T1是更年轻的事务，它写的实际上是对数据库最近的更新

而T3它是更年老的事务，它也可以写A

但它写A实际上如果从实际应用的角度来说，T3的这样一种写

实际上是一种过了时的写，也就是说它写实际上是没有用的

这样的话，如果说我们把T3回退了，这样实际上相当于是一种浪费

有人就说，如果把T3回退就相当于一种浪费，实际上我就降低了并行性

所以为了提高并行性，我们可以把一些过时的写操作进行忽略

比如说像表里面的T3，实际上T3对A的写忽略它就行了

实际上数据库里面还仍然是T1的这样一种写，所以就提出来Thomas写规则

如果Ti执行写操作

那么它执行写的时候如果它比目前的写要更年老一些的话

Ti的写操作就忽略了，我们不对它进行回退

所以我们这个例子把它稍微修改一下

就是T3这个事务如果要去写A的话，虽然T3比T1年老

但这个时候我们并不对T3进行回滚，而是直接忽略它的写操作

这个事务直接向下执行，T3仍然去执行它其他的操作

这样就提高了事务的并发操作的这样一种效率