《数据库实现》-- 第七章 并发控制

Posted on In , Views: Symbols count in article: 2.3k Reading time ≈ 8 mins.
《数据库实现》-- 第七章 并发控制

第七章， 并发控制


image.png
调度器保证并发执行事务能保持一致性， 当调度器接受到事务请求时，并不是立即执行，而是稍等一下， 有的时候是因为缓冲区的缘故， 有的时候是因为lock的缘故， 甚至有的时候会中止提交的请求。 
调度器关注3样元素， 锁， 时间戳和有效性确认。 

串行调度和可串行化调度

串行调度

调度的粒度是完整执行一个事务， 这个事务内包含大量动作， 事务和事务之间是串行化。 


串行化调度可保持数据库的一致性， 如果一个调度，他执行并不是串行化，但得到的结果和串行化是一致的，则可以称这个调度为可串行化

冲突可串行化

冲突： 如果将顺序改变， 涉及的事务至少一个行为有改变

  1. Ri(X), Rj(Y) 不会冲突
  2. Ri(X), Wj(Y) 不会冲突， 只要X!=Y, 
  3. Wi(X), Rj(Y) 不会冲突
  4. Wi(X), Wj(Y) 不会冲突


冲突
  1. 同一个事务的2个动作永远都是冲突的
  2. 不同事务对同一元素的写冲突
  3. 不同事务对同一元素的读写也冲突。


无冲突的动作是可以交换， 进行任意非冲突的交换， 将该调度转换为一个串行调度。 

优先图及冲突可串行化判断

image.png
对于A, r2(A) 在w3(A)前，w2（A）在w3（A）/r3(A) 前   –》 因此就A 而言， T2 优先T3
对于B, r1(B) 在w2（b）前， w1（b）在r2（b）/W2(B)之前， 因此 就B 而言， T1 优先T2
 
我们可以构造S的优先图， 如果没有构成环， 则表示冲突可串行化。 就可以通过相邻动作的合法交换，改变调度中动作的顺序， 直到调度称为一个串行调度
基于原来的T1 < T2 < T3
可以修改调度为
image.png


可串行化的调度， 是一个迭代的过程， 
找到一个事物Ti， 这个事物没有依赖， 将这个事物移到调度的最前， 然后迭代事物序列，找到剩余的事物中，依赖除了Ti 之外的事物。 




不过有的时候， 冲突可串行化不重要。

  1. 比如， 当T1 修改a， T2 也修改a， 但最后的T3 修改a， 因此T1 和T2 的顺序不重要， 因为最终都是T3 的修改是最终值。

 

基于锁的可串行化实现

事物获得他所访问元素上的锁， 防止其他事物在同一时间访问这些元素并因而引入非可串行化的可能。 
image.png
用一张锁表来帮助调度器做一些决策， 事物在读写数据库元素以外必须申请和释放锁。 
因此对，之前的case
image.png
image.png


现在带锁的操作如下
image.png
仅仅带锁还不能解决问题，还是不能保证可串行化。 
image.png

2阶段锁

2阶段锁可以保证一致事务的合法调度， 就是冲突的可串行化。 
原则：

  1. 在一个事务中， 所有的lock 操作先于所有的解锁操作
  2. 2阶段（2 Phase lock）， 获得锁的第一阶段， 释放锁的第二阶段


image.png


但这个存在死锁的可能性， 假设T2 先修改B， 然后再修改A, 则会出现死锁


如何对2阶段锁，进行串行调度


假设有n 个事务T1, T2, T3, …., Tn,  其中Ti 是第一个有解锁的动作， ui(x).  将Ti的动作不经过任何有冲突的读或写向前移动到调度最开始。 


读写锁

用sli(x) 读锁
用xli(x)写锁


事务的2阶段锁， 所有的lock必须在解锁前。 
一个调度过程
image.png


因此产生的效果，可能如图
image.png
冲突等价的串行顺序是T2 T1. 

更新锁

传统的读写锁，其中当持有读锁时， 当更新时，不能升级为写锁。 但更新锁可以。 
image.png
当有读锁时， 允许再申请更新锁，
但当有更新锁时， 他就和写锁没有区别

增量锁

对一个元素进行增加或减少的锁， 这种锁背后的动作其实时可以交换的， 比如对一个元素进行增加
增量锁会与读锁或写锁冲突，但增量锁和增量锁不冲突


基于锁的简单调度

有个前提：

  1. 事务自身不申请锁或释放锁， 都是由调度器来插入或释放锁。


逻辑比较简单

  1. 接收事务产生的请求流， 在所有的操作前后，加入合适的锁动作
  2. 执行请求流
    1. 事务T 申请的锁出现冲突， 推迟这个动作， 并加入事务T 执行的动作列表
    2. 如果没有冲突， 修改锁表， 将刚授予的锁写进去， 并执行动作
  3. 当 T 提交或中止时， 释放等待或持有的锁。 
  4. 如果其他事务释放了锁， 则执行步骤2

锁表

image.png
在释放锁的时候， 重新调度等待锁的时候， 有一些调度算法

  1. 先来先服务
  2. 共享锁优先
  3. 升级优先

警示锁

image.png
image.png


警示锁在普通锁（读写锁/更新锁）前加前缀， 

  1. 锁从根开始向下扫描
  2. 如果就是要锁当前节点， 就对当前节点直接上锁并结束遍历。
  3. 如果锁的对象是当前节点的子元素， 则当前节点进行警示锁， 对子元素进行锁。

 


image.png


幻象记录
在执行一个事务的过程中， 并行插入了一条新的记录， 这条新的记录就像幻象一样存在。 
解决的办法，
首先这2个事务不是串行化事务， 
当第一个事务， 对全表进行扫描的时候， 他会获得全表的警示读锁， 
当第二个事务执行时， 对表进行插入， 他需要获取全表的警示写锁， 这个时候， 就会发生冲突， 需要事务t2 进行等待

树协议

在b+ 树中， 对任何一个节点进行访问，都需要对根节点进行警示锁， 这个非常容易发生冲突。

  1. 事务的第一个锁可以在树的任何节点
  2. 事务只有获得父节点的锁后， 才能获得后续的锁
  3. 事务不能对一个已经释放的锁再进行上锁， 即使拥有父节点的锁
  4. 任何时刻可以unlock

image.png
树协议生成的调度关系，基本上都是串行化。 

  1. 如果2个事务都对几个元素进行锁， 则这些元素的锁顺序必须相同

时间戳

  1. 为每个事务分配一个时间戳， 事务的时间戳确保调度等价于实际事务的调度。
  2. 有效确认。 当提交一个事务的时候， 检查事务和数据库元素的时间戳， 这一过程称为有效性确认。

 


时间戳需要解决2个问题

  1. 过晚的读， 当读一个数据元素时， 发现读取元素的更新时间戳比自己时间戳还要新， 意味着读一个未来的值。 
  2. 过晚的写， 当理论上应该读取事务t 写入的值，但却读取了别的事务的值。

 


基于时间戳的调度

  1. 当接受到一个读事务时
    1. 如果ts(T) < wt(X), 则读非法， 中止事务T, 用一个更大的ts 来执行读
    2. 如果ts(T) >= wt(X), 可执行
      1. 如果是已经提交的值， 同意请求， 当ts(T) > rt(X), 设置rt(X) = ts(T)
      2. 如果还没有提交的值（脏读）， 推迟T 或中止
  2. 当接受一个写事务时
    1. TS(T) < RT(X), 当前写的时间比读上来的时间早， 回滚
    2. TS(T) >= PT(X) && TS(t) >= wt(x), 执行写， 置wt（x） = ts（t）， 置脏位
    3. 如果TS(T) >= RT(X) && TS(T) < WT(X), 可以写入，但后面有个更新的写， 如果是已经提交的写， 当前写必须丢弃， 如果是脏写还没有提交， 可以推迟当前写。
  3. 如果调度器执行提交的t的请求，则需要设置所有修改元素提交位， 所有等待事务可以继续