1.什么是时间戳？

不用锁，能否进行并发控制？

时间戳(TIMESTAMP)

• 一种基于时间的标志，将某一时刻转换成的一个数值。
• 时间戳具有唯一性和递增性。

事务的时间戳

• 事务T启动时，系统将该时刻赋予T，为T的时间戳
• 时间戳可以表征一系列事务执行的先后次序：时间戳小的事务先执行，时间戳大的事务后执行。
• 利用时间戳，可以不用锁，来进行并发控制

2.基于时间戳的并发控制

借助于时间戳，强制使一组并发事务的交叉执行，等价于一个特定顺序的串行执行。

• 特定顺序：时间戳由小到大。
• 如何强制：执行时判断冲突，
  如无冲突，予以执行；
  如有冲突，则撤销事务，并重启该事务；
  此时该事务获得了一个更大的时间戳；
  表明是后执行的事务。
• 有哪些冲突：
  读-读无冲突；
  读-写或写-读冲突；（先执行的事务后操作，后执行的事务先操作就有可能冲突）
  写-写冲突。

一种简单的调度规则

• 对DB中的每个数据元素x，系统保留其上的最大时间戳
  RT(x): 即R-timestamp(x)
  读过该数据事务中最大的时间戳， 即最后读x的事务的时间戳。

• WT(x): 即W-timestamp(x)
  写过该数据事务中最大的时间戳， 即最后写x的事务的时间戳。

• 事务的时间戳
  TS(T): 即TimeStamp

• 读-写并发：(读-写、写-读)
  （1）若T事务读x，则将T的时间戳TS与WT(x)比较:
  若TS大(T后进行)，则允许T操作，并且更改RT(x)为max{RT(x),TS}；
  否则，有冲突，撤回T，重启T。
  （2）若T事务写x，则将T的时间戳TS与RT(x)比较：
  若TS大(T后进行)，则允许T操作，并且更改WT(x)为max{WT(x),TS}；
  否则，有冲突，撤回T重做。

• 写-写并发
  （1）若T事务写x，则将T的时间戳TS与WT(x)比较：
  若TS大，则允许T写，并且更改WT(x)为T的时间戳；
  否则有冲突，T撤回重做。
  

基于时间戳的简单调度规则可以避免：T过晚的读决T过晚的写的冲突问题

3.基于时间戳的另一种调度规则

需要解决的问题是：

• 脏读数据如何避免？此时T读取了脏数据
  

如何放行一些事实上可实现的冲突?

• 托马斯写规则
  过时的写操作可直接被忽略，而无需撤销过时的事务
  

托马斯规需注意的问题如下：

• 按照托马斯规则，T可被忽略，但是U终止了，T又不能被忽略了，怎么办？
  

所以，有了基于时间戳的另一种调度规则
对DB中的每个数据元素x，系统保留其上的最大时间戳

• RT(x): 即R-timestamp(x)
  读过该数据事务中最大的时间戳， 即最后读x的事务的时间戳。

• WT(x): 即W-timestamp(x)
  写过该数据事务中最大的时间戳， 即最后写x的事务的时间戳。

• C(x): x的提交位。
  该位为真，当且仅当最近写x的事务已经提交。
  C(x)的目的是避免出现事务读另一事务U所写数据然后U终止这样的情况

• 事务的时间戳
  TS(T): 即TimeStamp

调度规则
对来自事务T的读写请求，调度器可以：

• 同意请求
• 撤销/终止T，并重启具有新时间戳的T(终止+重启，被称回滚)
• 推迟T，并在以后决定是终止T还是同意请求(如果请求是读，且此读可能是脏的)

调度规则
假设调度器收到请求$r_T(X)$

• (1)如果TS(T)>=WT(x), 此读是事实上可实现的
  如C(x)为真，同意请求。如果TS(T)>RT(x), 置RT(x):=TS(T); 否则不改变RT(x).
  如C(x)为假，推迟Ｔ直到C(x)为真或写x的事务终止。
  

• (2)如果TS(T)<WT(x), 此读是事实上不可实现的
  回滚T(终止并重启T)；(过晚的读)
  

假设调度器收到请求$w_T(X)$

• (1)如果TS(T)>=RT(x), 且TS(T)>=WT(x), 此写是事实上是可实现的（后启动的事务先写）
  为x写入新值；置WT(x):=TS(T)；置C(x):=false.

• (2)如果TS(T)>=RT(x),但是TS(T)<WT(x)，此写是事实上可实现的。（新启动的事务后写）
  但x已经有一个更晚的值
  如果C(x)为真，那么前一个x的写已提交；则忽略T的写；继续进行。(托马斯写规则)
  如果C(x)为假，则我们需推迟T，直到C(x)为真或写x的事务终止。
  

• (3)如果TS(T)<RT(x), 此写是事实上不可实现的（先启动的事务后写）
  T必须回滚。（过晚的写）
  

假设调度器收到提交T的请求。

• 它必须找到T所写的所有数据库元素x, 并置C(x):=true。
• 如果有任何等待x被提交的事务，这些事务就被允许继续进行。

假设调度器收到终止T的请求

• 像前述步骤一样确定回滚T。那么任何等待T所写元素x的事务必须重新尝试读或写，看这一动作现在T的写被终止后是否合法
  

4.基于有效性确认的并发控制方法

能否进行批量性的冲突检测？

什么是有效性确认？
基于时间戳的并发控制的思想

• 事务在启动时刻被赋予唯一的时间戳，以示其启动顺序。
• 为每一数据库元素保存读时间戳和写时间戳，以记录读或写该数据元素的最后的事务。
• 通过在事务读写数据时判断是否存在冲突(读写冲突、写读冲突、写写冲突)来强制事务以可串行化的方式执行。（有冲突，就撤销、重启）

基于有效性确认的并发控制的思想

• 事务在启动时刻被赋予唯一的时间戳，以示其启动顺序。
• 为每一活跃事务保存其读写数据的集合， RS(T)：事务T读数据的集合；WS(T)：事务T写数据的集合。
• 通过对多个事务的读写集合，判断是否有冲突(存在事实上不可实现的行为)，即有效性确认，来完成事务的提交与回滚， 强制事务以可串行化的方式执行。

基于有效性确认的调度器

• 事务在启动时刻被赋予唯一的时间戳，以示其启动顺序。
• 每一事务读写数据的集合，RS(T)：事务T读数据的集合；WS(T)：事务T写数据的集合。
• 事务分三个阶段进行
  （1）读阶段。事务从数据库中读取读集合中的所有元素。
  事务还在其局部地址空间计算它将要写的所有值；
  （2）有效性确认阶段。
  调度器通过比较该事务与其它事务的读写集合来确认该事务的有效性。
  （3）写阶段。
  事务往数据库中写入其写集合中元素的值。
• 每个成功确认的事务是在其有效性确认的瞬间执行的。
• 并发事务串行的顺序，即事务有效性确认的顺序

调度器维护三个集合

• START集合。
  已经开始但尚未完成有效性确认的事务集合。
  对此集合中的事务，调度器维护START(T)，即事务T开始的时间。
• VAL集合。
  已经确认有效性但尚未完成第3阶段写的事务。对此集合中的事务，调度器维护START(T)和VAL(T)，即T确认的时间。
• FIN集合。已经完成第3阶段的事务。
  对这样的事务T, 调度器记录START(T), VAL(T)和FIN(T)，即T完成的时间

有效性确认规则

• 冲突1
  假设存在事务U 和 T满足：
  (1)U 在VAL或FIN中, 即U已经过有效性确认。
  (2)FIN(U)>START(T), 即U在T开始前没有完成。
  (3)RS(T)∩WS(U)非空（T的读集合，U的写集合）， 特别地，设其均包含数据库元素为x。
  则T和U的执行存在冲突，T不应 进行有效性确认
  如果一个较早的事务U现在正在写入T应该读过的某些对象，则T的有效性不能确认

• 冲突2
  假设存在事务U 和T 满足：
  (1)U 在VAL, 即U有效性已经成功确认。
  (2)FIN(U)>VAL(T), 即U在T进入其有效性确认阶段以前没有完成。
  (3)WS(T)∩WS(U)非空, 特别地，设其均包含数据库元素x。
  则T和U的执行存在冲突，T不应 进行有效性确认
  
  如果T在有效性确认后可能比一个较早的事务先写某个对象，则T的有效性不能确认

有效性确认规则

• (1)对于所有已经过有效性确认, 且在T开始前没有完成的U，即对于满足
  FIN(U)>START(T)的U，检测：RS(T) ∩WS(U)是否为空。
  若为空，则确认。否则，不予确认。
• (2)对于所有已经过有效性确认，且在T有效性确认前没有完成的U，即对于
  满足FIN(U)>VAL(T)的U， 检测：WS(T) ∩WS(U)是否为空。
  若为空，则确认。否则，不予确认
• eg：
  

5.小结