11.3　时间戳排序协议

　　在封锁协议中，每一对冲突事务的可串行化次序是由执行时第一个两者都申请但互相冲突的锁决定的（与"按调度中事务提交的顺序做串行化"或"按调度中事务封锁点的顺序做串行化"的说法不矛盾，为什么？请大家自己思考），如图11-3-1所示：

　　在图11-3-1中，事务Ti和Tj的第一个两者都申请但相互冲突的锁是Tj的lock-S(A)和Ti的lock-X(A)，但由于事务Tj先获得锁，因此事务Tj先提交。所以这个调度中事务的可串行化次序是<Tj, Ti>。另一种决定事务可串行化次序的方法是事先选定事务的次序，其中最常用的方法就是时间戳排序机制。

　　11.3.1　时间戳

　　图11-3-1：调度中事务的可串行化次序与锁的关系

　　1、基本概念

　　⑴　对于系统中的每个事务T，把一个唯一固定的时间戳和事务T联系起来。时间戳就是一个时间标志，该时间标志是在事务T开始执行前由DBMS的并发控制管理器赋予的，记为TS(T)。

　　⑵　时间戳有大小（先后）之分：若事务Ti先于事务Tj进入系统，那么：TS(Ti) < TS(Tj)。

　　2、实现方式

　　⑴　使用系统时钟值作为时间戳：事务进入系统时的时钟值就是该事务的时间戳；

　　⑵　使用逻辑计数器：即该事务进入系统时的计数器值。每赋予一个时间戳，计数器就自动增加一次。

　　3、两个重要的时间戳

　　在时间戳机制中，每个数据项Q需要和以下两个重要的时间戳相关联：

　　⑴　W-TS(Q)：表示当前已成功执行write(Q)的所有事务的最大时间戳；

　　⑵　R-TS(Q)：表示当前已成功执行read(Q)的所有事务的最大时间戳。

　　每当有新的read(Q)或write(Q)指令成功执行，这两个时间戳就被更新。

　　事务的时间戳决定了调度中事务串行化的顺序，即，若TS(Ti)<TS(Tj)，则DBMS必须保证所产生的调度等价于Ti出现在Tj之前的某个串行调度。

备注：摘自http://www.educity.cn/zk/sjkyl/201306141634451871.htm