CMU15-445笔记(十六)

并发控制

基于时间戳的协议

时间戳

对于系统中的每个事务$T_i$，赋予它一个时间戳，记为$TS(T_i)$。如果$TS(T_i) < TS(T_j)$，说明$T_j$比较新。
可以使用

• 系统时钟
• 逻辑计数器 来实现时间戳。
  除了$TS(T_i)$之外，还需要两个与数据库项$Q$相关的时间戳
• W-timestamp(Q)表示成功执行write(Q)的任意事务的最大时间戳
• R-timestamp(Q)表示成功执行read(Q)的人一十五的最大时间戳

时间戳排序协议

时间戳排序协议保证任何有冲突的read和write操作按照时间戳的次序执行。

• 假设事务$T_i$执行read(Q)
  • 如果$TS(T_i) < W-timestamp(Q)$，那么$T_i$需要读取的值就被覆盖了，read操作会被拒绝执行，并且执行回滚
  • 如果$TS(T_i) \geq W-timestamp(Q)$那么可以执行read操作，并且$R-timestamp(Q)$会被设置成$R-timestamp(Q)$和$TS(T_i)$的最大值
• 如果事务$T_i$执行write(Q)
  • 如果$TS(T_i) < R-timestamp(Q)$ 那么说明$T_i$的Q值是之前需要的，并且系统会认为这个值不会再出现了，所以拒绝执行，回滚
  • 如果$TS(T_i) \geq R-timestamp(Q)$，那么执行，并将$W-timestamp(Q)$设置为$TS(T_i)$

时间戳排序协议保证没有死锁，因为事务不会出现等待锁的情况。但是有可能会出现饿死的情况。时间戳协议也可能会出现不可恢复的调度。可以采取以下策略来保证可恢复

• 再事务末尾一起执行所有的写操作，并且要求再执行这些写操作的时候，任何事务都不能访问已经写过的任何数据项，否则就有可能不可恢复。这种策略是保证无级联和可恢复的
• 对未提交的数据项的读操作推迟到更新该数据项的事务提交之后也可以保证无级联和可恢复
• 使用提交依赖

Thomas写规则

当$TS(T_i) < W-timestamp(Q)$的时候，这个write会直接忽略，而不是回滚。这个会形成view serializable，不是冲突 serializable。

基于有效性检查的协议

有效性检查时用来监控哪些事务会陷入冲突中的监控机制。它要求事务$T_i$按照两个或者三个阶段来执行。这个协议也叫乐观的并发控制(optimistic concurrency-control)

• 读阶段
  • 在这个阶段中，事务$T_i$读取数据项的值并保存在局部变量中，$T_i$的所有write操作都是针对局部变量的
• 有效性检查阶段
  • 对事务$T_i$进行有效性检查测试，决定事务是否可以继续执行，还是终止
• 写阶段
  • 如果通过了检查，$T_i$将write的操作的局部变量写入数据库

有效性检查

为了执行有效性检查，需要以下三个时间戳

• $StartTS(T_i)$ 事务开始执行的时间
• $ValidationTS(T_i)$ 事务完成读阶段并开始检查的时间
• $FinishTS(T_I)$ 事务完成写阶段的时间

该协议利用$ValidationTS(T_i)$时间戳的值来通过时间戳排序协议决定串行化的顺序。所以$TS(T_i)=ValidationTS(T_i)$，并且如果$TS(T_j) < TS(T_k)$，那么有效性检查协议必须等价于事务$T_j$出现在$T_k$之前的一个串行调度。

有效性检查需要满足以下两个条件之一

• $FinshTS(T_k) < StartTS(T_i)$，这样的话，$T_k$不会影响到$T_i$
• $T_k$写的数据项和$T_i$读的数据项没有交集，并且在$T_i$开始有效性检查阶段前，$T_k$就完成了写阶段，这就保证了两个事务的写不会重叠，导致覆盖的顺序错误。这样就保证了串行化
  

有效性检查还保证了无级联，因为写操作事务提交后实际上的写到数据库的操作才开始。

为什么要用$ValidationTS(T_i)$来作为$TS(T_i)$，而不是$StartTS(T_i)$，还是假设$TS(T_i) > TS(T_k)$这样有可能导致$T_i$比$T_k$更早的进入有效性检查阶段，从而导致$T_i$需要等待$T_k$

多版本控制

multiversion concurrency control在每次write(Q)时都会创建Q的新版本，当事务执行read(Q)操作的时候，并发控制管理器会选择Q的一个合适的版本进行读取，必须能保证可串行化。
多版本控制主要解决的时以上协议想要读取旧版本时导致的回滚或者等待问题。

多版本时间戳排序

这个是时间戳排序协议的拓展版本，对于每一个数据项Q，都有多个版本Q1 Q2…Qk，每个版本都对应着三个数据字段

• Content Qk版本的值
• W-timestamp(Q) 创建Qk版本的事务的时间戳
• R-timestamp(Q) 所有成功读取Qk事务的最大时间戳

假设$Q_k$小于或等于$TS(T_i)$的最大写时间戳

• 如果$T_i$执行read(Q)，那么直接返回$Q_k$的值
• 如果事务$T_i$执行write(Q)，如果$TS(T_i) < R-timestamp(Q_k)$，那么系统回滚$T_i$，如果$TS(T_i)=W-timestamp(Q_k)$，系统会覆盖Q_k的内容，如果$TS(T_i) > R-timestamp(Q_k)$，系统给Q创建新的版本

对于Q，有一个有效区间的概念，如果Qi是Q的最新版本，那么Qi的有效区间就是$[W-timestapm(Q_i), \infty]$，如果不是最新的，那么就是$[W-timestamp(Q_i), W-timestamp(Q_{i+1})]$。有效区间就是事务在这个区间内会读取到这个Q版本的数据

多版本时间戳是不保证可恢复和无级联的，可以按照原版时间戳的方式进行扩展。

多版本两阶段封锁

多版本两阶段封锁会对只读事务和更新事务分别有不同的处理
更新事务会执行强两阶段封锁，事务会只有全部的锁直到事务结束，所以可以实现按照事务提交的次序来进行串行化，每个事务都会有以逻辑计数器呈现的时间戳，叫ts-counter
当只读事务开始前，数据库会赋予它时间戳，只读事务执行读操作是和多版本时间戳是一样的。
当更新事务读取一个数据项的时候，会先获取数据项上的共享锁并且读取数据项的最新版本。当更新事务写数据的时候，要获取排他锁，然后创建一个该数据项的新版本，并设置新版本的时间戳为$\infty$
当更新事务$T_i$完成操作的时候，会进入提交过程。同一时间只能有一个更新事务进行提交。$T_i$会将它创建的每个版本的时间戳设置为ts-counter + 1, 然后ts-counter + 1，最后提交。
只读事务会看到ts-counter的旧值直到$T_i$提交陈工，所以$T_i$提交前，启动的只读事务只能看到$T_i$更新前的就值，而提交后的只读事务能看到新值。
只读事务在任何情况下都不用加锁。

多版本两阶段封锁是可恢复且无级联的（因为强两阶段封锁）

多版本控制删除版本

如果有多个W-timnestamp小于当前所有事务中最老的事务，那么就删除这些版本除了最新的版本之外的所有版本。

快照隔离

快照隔离是一种特殊的并发控制机制。在事务开始执行时给它一份数据库的快照，然后事务在快照上以其他并发事务完全隔离的形式进行操作。快照中的数据值仅包含已经提交的事务所写的值。
在快照隔离中，更新事务会存在可能的冲突，所以在允许事务提交前，需要进行有效性检查，这里的有效性检查和前面的方式不同。直到检查通过，事务进行的更改才会进入数据库中。

快照隔离中的多版本

事务有两个时间戳，$StartTS(T_i)$和$CommitTS(T_i)$，分别是事务$T_i$开始的时间和事务请求有效性检查的时间。在版本中，只有一个写时间戳，表明版本创建的时间，事务$T_i$创建的版本的时间戳设定为$CommitTS(T_i)$
当事务$T_i$读取一个数据项的时候，具有时间戳$\leq$ 的数据项的最新版本会返回给事务。所以事务$T_i$不会看到比事务新的数据，这样就完成了快照隔离

更新事务的有效性检查步骤

如果有两个更新事务都要进行提交，有可能会出现更新丢失的情况，快照隔离有两种方式来防止更新丢失

• 先提交者胜 first committer wins
• 先更新者胜 first updater wins
  这两种都是基于检查事物的并发事务

并发事务

如果：
$StratTS(T_j) \leq StartTS(T_i) \leq CommitTS(T_j)$
$StratTS(T_i) \leq StartTS(T_j) \leq CommitTS(T_i)$
两个任意一个成立，那么这两个事务就是并发的

先提交者胜 first committer wins

• 检查是否存在某个事务在当前事务将数据写到数据库前就将更新提交到了数据库中，也就是可以检查数据项d中是否有一个版本的时间戳介于$StratTS(T_i)$ $CommitTS(T_i)$之间
• 如果有，那么$T_i$就终止
• 如果没有就提交

先更新者胜 first updater wins

当事务想要更新数据项的时候，先获取该数据项的写锁，如果能获取，那么获取后

• 如果这个数据项已经被任何并发事务更新，那么$T_i$终止，否则可以继续执行
  如果写锁已经被另一个并发事务获取了，
• $T_i$等待直到获取锁的事务中止或者提交
  • 如果获取锁的事务终止了，那么$T_i$获取锁，然后执行上面的有效性检查
  • 如果获取锁额事务提交了，那么$T_i$中止

快照隔离存在的问题

快照隔离第一个问题是主键约束和外键约束不能再快照