CMU-15-445笔记(十五) 基于锁的协议

本次笔记来自《数据库系统概念》第七版 第18章的第一节

并发控制

为了确保书屋的隔离性，DBMS采用的是并发控制来实现的，主要有两阶段封锁(two-phase locking)和快照隔离(snapshot isolation)

基于锁的协议

可以通过以互斥的方式来访问数据项来实现隔离性，就让事务持有数据项的锁来实现这一功能。

锁

每个事务需要根据对数据项Q指定的操作申请适当的锁。事务会将锁请求发送给并发控制管理器，事务只有被并发控制管理器授予锁之后才能继续对事务进行操作。

相容函数

如果事务在已经有其他事务获取锁的数据项上再获取锁，就说明这两把锁是相容的。也就是comp(A,B)=true

封锁协议

封锁协议是一组规则，规定了事务何时可以对每个数据项进行加锁和解锁。
假设$T_i$再$Q$上持有A模式锁，后来$T_j$再$Q$上持有B模式锁，并且comp(A,B)=false，那么称作在调度$S$中，$T_i$先于$T_j$，记作$T_i\rightarrow T_j$，这种表示形式类似优先图。
如果调度$S$是一组遵守封锁协议规则的事务的一种可能的调度，那么$S$在给定的封锁协议下是合法的。如果一种封锁协议的所有合法调度都是冲突可串行化的，那么这个封锁协议就保证了冲突可串行化。

锁的授予

当事务对数据项申请的锁没有被其他事务在同一个数据项申请的锁排斥的时候，锁就可以被授予。但是申请锁有可能导致饿死，可以当一个事务申请M锁的时候，必须保证Q（数据项）上冲突的锁在其他事务上是不存在的，并且没有其他事务比当前事务更先提出加锁，这样就可以避免饿死的产生。

两阶段封锁协议

该协议分为两个阶段

• 增长阶段：一个事务可以获取锁，但是不能释放任何锁
• 缩减阶段：一个事务可以释放锁，但是不能获得任何新锁
  这个协议可以保证可串行化。但是不能保证死锁。其中事务中获取最后锁的位置叫做封锁点。

这个就是一个遵守两阶段封锁协议的事务

严格两阶段封锁协议

希望事务是冲突可串行化之外，还希望事务是无级联的，在两阶段封锁协议中，级联回滚是可能发生的

而严格两阶段封锁协议则要求事务持有的所有排他锁必须在事务提交后释放，这个要求保证未提交事务所写的任何数据都需要在事务提交前以排他模式封锁。

强两阶段封锁协议

这个协议要求事务提交前保留所有的锁。这样就可以保证事务可以按其提交的次串行化。

锁转换

当一开始使用共享锁，然后需要执行写操作时，可以使用锁升级，反之使用锁降级，这样可以提高并发度。

广泛使用的机制

这个机制自动的为事务生成封锁和解锁指令。

• 当事务$T_i$发出read(Q)指令的时候，系统会产生lock-S(Q)指令，然后再产生read(Q)
• 当事务发出write(Q)操作的时候，系统会检查是否有共享锁，如果有，升级成排斥锁，然后接着生成write(Q)操作，否则先lock-X(Q)，接着再write(Q)
• 当一个事务提交或者回滚后，该事务所有的锁都会被释放

封锁的实现

封锁是用了锁管理器来管理锁，它从事务接受消息并应答。锁管理器对封锁消息请求采用授予的信息来应答，或者采用要求事务回归的消息来应答， 对于解锁的消息只需要用于确认来回答。

锁管理器使用了hash table和链表还作为数据结构，每个数据项维护一个记录的链表，每一个请求对应链表中的一条记录，并按照请求到达的顺序进行排序。其中hash table称作锁表，对于每个数据项，链表中的每条记录都记载了哪个事务，锁的模式等信息。锁表应该还要维护一个基于事务表示的索引，来确定一个给定事务的所有锁。

基于图的协议

如果开发非两阶段的协议，需要每个事务如何存取数据库的附加信息。在数据项中规定了一种偏序$\rightarrow$ 如果数据项$d_i \rightarrow d_j$，那么任何即访问$d_i$又访问$d_j$的事务必须先访问$d_i$再访问$d_j$，这样就形成了数据库图。

书中给出了基于树形协议的简单协议，这个协议规定必须使用排他锁，并且对于每个事务

• 首次封锁可以在任何数据项上进行
• 此后，事务可以对数据项加锁的前提是该事务由该数据项父项上的锁。
• 数据项解锁可以随时进行
• 一个数据项被事务加锁并解锁后，事务不能再对该数据项加锁。
  
  
  树型协议保证冲突可串行化，并且保证不会产生死锁。
  如果要保证恢复性和无级联性，可以让事务结束前不允许释放排他锁。如果只想保证可恢复性，当$T_i$事务执行对未提交数据读操作的时候，就对该数据执行写操作的事务记录一个$T_i$的提交依赖，然后当事务$T_i$的提交依赖的所有事务完成提交之前，$T_i$不允许提交。

优缺点

优点

• 不会产生死锁，无需回滚
• 可以较早的释放锁，提高并发
  缺点
• 事务可能需要给根本不访问的数据项加锁，导致并发度降低

死锁处理

有两种主要的方法来处理死锁问题，可以使用死锁预防，也可以让系统允许进入死锁状态，然后试着用死锁检测和死锁恢复来进行回复。

死锁预防

死锁预防有两个方向，一个是给封锁请求一定顺序，或者要求事务要同时获取所有需要的数据项的锁再开始，另一个方向是每当等待有可能导致思索地时候，就执行事务回滚而不是等待锁。
第一种方法最简单的机制是事务执行前封锁它所有所需要的数据项，另一种方法是对数据项加一种次序，要求事务只能按照次序来顺序封锁数据项，树形协议就是这种方式。还有一种方式是，给所有数据项来个整体的次序，当事务封锁数据项时，不能再次封锁这个数据项之前的数据项。

第二种方式就是使用抢占和事务回滚。

• 死亡-等待(wait-die)机制是非抢占技术，当事务$T_i$时间戳小于（出现时间晚）$T_j$的时间戳的时候，如果$T_j$占有了$T_i$需要的数据项，那么$T_i$等待，如果$T_i$的时间戳大，那么$T_i$回滚

• 伤害-等待(wound-wait)，和前者类似，但是当$T_i$时间戳小于$T_j$的时候，$T_j$回滚

锁超时是另一个种简单的方式，申请锁的事务至多等待一段指定的时间，如果超时，那么事务自己回滚。

死锁检测

死锁检测可以使用等待图来描述，当事务$T_i$等待$T_j$的时候，那么就建立一条边，如果有环路，那么就说明出现了死锁

死锁恢复

死锁恢复解决方案主要是回滚一个或者多个事务，需要采取三个动作

• 选择牺牲者
• 回滚
• 饿死
  • 如果总是选择相同的事务作为牺牲者，那么有可能会产生饿死的情况，必须保证事务被选为牺牲者的次数是有限的

多粒度

多级力度封锁协议使用了树形的数据粒度的层次结构，树中的每个节点都可以单独加锁，并且会隐式的给子节点加相同的锁。

意向锁

如果有事务想要封锁整个树，就需要遍历所有的节点判断是否加的锁和某个节点的锁有冲突，这样不高效。可以给节点加上意向锁，意味着会给该节点的子节点显式加锁，这样如果要给一个节点加锁时，就可以遍历该节点的上级节点们，给他们加上对应的意向锁。
意向锁有IS IX SIX三种，IS意思是要读取某个子节点，也就是会给某个子节点加上共享锁，IX意思是要修改某个子节点，会给某个子节点加上排斥锁。对于SIX来说，意思是会读取整个子树，并修改某个节点，所以会给加上SIX的节点添加共享锁，并会在需要修改数据的子节点上加上排斥锁。

例子1：
IS和IX的兼容


例子2：
SIX和IS兼容，但是和IX不兼容

冲突图