并发控制

发表于 分类于

事务的基本特性是隔离性，然而当数据库中由多个事务并发执行时，事务的隔离性不一定能保持。为保持事务的隔离性，系统必须对并发事务之间的相互作用加以控制，这种控制通过并发控制机制来实现。

之前我们了解到视图串行化并不存在有效验证方法，那么还需要有一种方式来确保在不提前知道所有调度的情况下所有执行调度仍然是正确的，因此引入锁机制。

之前的调度序列在引入锁机制后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 T1                      T2
BEGIN
LOCK(A)
R(A)
                       BEGIN
                       LOCK(A)
W(A)
R(A)
UNLOCK(A)
                       R(A)
                       W(A)                       
COMMIT
                       UNLOCK(A)
                       COMMIT

在T2申请对A锁的时候，T1已经取得了对A的锁，在T1释放对A锁之后，T2才可得到对A的锁。

锁的基本类型有两种

  • S-LOCK: 共享读锁
  • X-LOCK: 排他写锁

对于给定的一个锁类型集合,令A与B代表任意的锁类型，假设事务Ti请求对数据项加A类型锁，而事务Tj当前在数据库Q上拥有B类型锁，而事务Ti可立即获得数据项Q上的锁，那么A类型锁和B类型锁是相容的。

S-LOCK和X-LOCK的相容性矩阵如下

S X
S true false
X false false

关于锁的流程为

  1. 事务申请锁(或者更新)

  2. 锁管理器授予锁或者拒绝请求

  3. 事务释放锁

  4. 锁管理器释放内部的锁表

    锁表中存储持有锁的事务信息和等待锁的事务信息

在系统中每一个事物遵从称为封锁协议的一组规则，这些规则规定事务何时对数据项进行加锁、解锁，封锁协议限制了可能的调度数目。

两阶段封锁协议

确保串行性的一个协议是两阶段封锁协议，该协议要求每个事务分两个阶段提出加锁和释放锁申请。

  1. 增长阶段：事务可以获得锁，但是不能释放锁

    锁管理器允许/拒绝请求

  2. 缩减阶段：事务可以释放锁，但是不能释放锁

    在增长阶段后不允许申请/升级锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
 T1                      T2
BEGIN
X-LOCK(A)
R(A)
W(A)
                       BEGIN
                       X-LOCK(A)
R(A)
UNLOCK(A)
                       W(A)                       
COMMIT
                       UNLOCK(A)
                       COMMIT

两阶段封锁协议可保证冲突可串行化，产生无环的依赖图。

在两阶段封锁协议中，可能存在级联回滚现象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 T1                      T2
BEGIN
X-LOCK(A)
X-LOCK(B)
R(A)
W(A)
UNLOCK(A)
                       BEGIN
                       X-LOCK(A)
                       R(A)
                       W(A)
R(B)                    .
W(B)                    .
ABORT                   .

在事务T1的W(B)后发生故障，从而导致T2级联回滚，从而导致无效的操作。同时存在可能的可串行化调度，但是不被两阶段封锁协议允许。

可通过严格两阶段封锁协议或者强两阶段封锁协议解决。

强两阶段封锁协议

除了要求封锁是两阶段以外，还要求事务持有的所有锁必须在事务提交后方可释放。

  • 仅仅允许可冲突可串行化调度
  • 不存在级联回滚现象
  • 一个事务写入的值在该事务结束前不可被其余事务读入或者写入
  • 可能存在死锁现象

死锁处理

死锁检测

系统创建等待图，节点为事务，若事务Ti等待事务Tj释放锁，那么添加从Ti到Tj的边。系统定期检查等待图中是否出现环路，再决定如何破坏循环。

  • 当系统检测到死锁，系统将会选择一个回滚的事务来破坏环路

  • 取决于应用处理方式，选择的事务将重启或者终止

  • 有多种事务属性可作为选择替代的根据，不存在哪个优于其余选择

    按照时间(最早或者最晚)

    按照进程(最少/最多执行的查询)

    按照已经锁住的条目个数

    按照回滚事务的个数

    按照事务过去重启的次数

  • 在选择事务后，系统还需决定回滚的长度，要么整个事务的操作均撤销，要么撤销操作数目达到死锁解除的要求即可。

死锁预防

当一个事务请求已经被其他事务持有的锁，此时执行死锁预防算法。

基于时间给定优先级，例如，时间越久意味着优先级越高。如此可确保不存在死锁，因为只有一个方向的等待。当一个事务重启，它将继承之前的优先级。

  • wait-die:若T1优先级高于T2,T1等待T2，否则T1终止
  • wound-wait:若T1优先级高于T2，T2终止，否则T1等待

多粒度

之前提到的例子均将一个个数据项作为同步执行的单元，如果一个事务想更新一百万个元组，那么该事务将请求一百万个条目。为了避免多余的开销，系统将通过层次化锁来允许一个事务粗粒度加锁。例如，该事务将为一百个元组申请一个锁，而不是为每个元组申请一个锁。当一个事务请求层次化结构中的某个节点，该事务隐式地为其后代加锁。

若事务Ti希望封锁整个数据库，而Tj持有其中某个节点的锁，那么系统如何判定根节点是否可以加锁呢？

一种可能的方法是遍历整棵树，显然违背了多粒度锁机制的初衷。通过引入意向锁来允许高层次节点在无需检查后代节点即可加共享锁或者排他锁。如果一个节点加上了意向锁，那么意味着在树的更低层进行显式加锁，即以更小的粒度加锁。在一个节点显示加锁之前，其所有祖先节点均加上了意向锁。因此，事务不必遍历整棵树即可判定能否成功地给一个节点加锁。

  • 共享型意向锁(IS) 将在树的较低层进行显式封锁，但是只能加共享锁
  • 排他型意向锁(IX) 在树的较低层进行显式封锁，可以是共享锁或排他锁
  • 共享排他型意向锁(SIX) 以该节点为根的子树显式地加上共享锁，在树的更低层显示地加上排他锁

这些锁的相容矩阵为

多粒度封锁协议根据以下规则对数据项Q加锁：

  • 事务Ti必须首先封锁树的根节点，并可以加任意类型的锁
  • 仅当Ti当前对Q的父节点具有IX或IS锁时，Ti可以对节点Q可加S锁或者IS锁、
  • 仅当Ti当前对Q的父节点具有IX或SIX锁时，Ti可以对节点Q加X、SIX或IX锁

加锁按照从上到下的顺序，而锁的释放则按照从下到上的顺序。

在低层次的锁申请过多时，为了更高粒度的并行，可以升级锁。

时间戳排序协议