数据库的并发控制

仅做笔记

Posted by Nathaniel on 2016-05-13

并发控制

并发控制的主要技术

  1. 封锁(Locking)
  2. 时间戳(Timestamp)
  3. 乐观控制法

锁的类型

  • 排他锁 X锁 写锁
    • 共享锁S锁读锁

并发事务运行存在的异常问题

​ 并发操作带来的数据不一致性

丢失更新

​ 两个事务同时读写一个数据

​ 事务2的写影响(覆盖)了事务1的写

​ 导致事务1的结果失效

不可重复读

​ 三类不可重复读

  1. T1读两次数据得到不同的值,因为T2修改了该数据
  2. T1再读的时候数据消失,因为T2删除了该数据
  3. T1同条件读时多了一些数据,因为T2插入了一些数据
读“脏”数据

​ 事务2读到了事务1进行中的数据

​ 事务1后来因为某种原因被撤销

​ 事务2读到的数据就是不正确的数据

不一致性是由并发操作引起的

​ 主要原因是并发操作破坏了事务的隔离性

封锁协议

1. 一级封锁协议

​ 修改前加X锁,结束才释放

​ 读数据时不加锁,可能 重复读读“脏数据”

​ 可以解决丢失更新

2. 二级封锁协议

​ 在一级封锁协议之上 读数据前加 S锁 读完之后释放 S锁

​ 可以避免 读“脏数据”

3. 三级封锁协议

​ 在二级封锁协议之上 事务结束之后才释放 S锁

活锁

定义

​ 某个事务由于请求封锁,总也得不到锁而长时间处于等待状态

如何解决:

​ 采用先来先服务策略

死锁

定义

​ 同时处于等待状态的2个或多个事务互相封锁了对方请求的资源

​ 使得没有任何事务能够有足够资源运行完毕

​ 解决方法:

预防死锁

一次封锁法:

​ 将事务在执行过程中可能要封锁的数据对象全部加锁

​ 问题:扩大了封锁的范围,降低了并发度

顺序封锁法:

​ 事先规定一个封锁顺序,所有事务都按这个顺序封锁

​ 问题:维护成本高,难以实现

事务重试法:

​ 使用抢占机制和事务回滚

​ 即后申请的事务可能能够抢占已有锁的事务的锁

结论:

​ 操作系统中的预防死锁的策略 不很适合 数据库的特点

​ DBMS在解决死锁的问题上 采用的是 诊断并解除死锁 的方法

死锁的检测与恢复

​ 即允许死锁先发生

​ 由DBMS的并发控制子系统定期检测系统中是否存在死锁

​ 检测到死锁,选择一个处理死锁代价最小的事务,将其撤消,使其它事务能继续运行。

​ 被撤销的事务回滚

超时法

​ 如果一个事务等待时间超过了限制,就认为发生了死锁

​ 优点:实现简单 缺点:可能误判 或 发现死锁不及时

事务等待图法

​ 用事务等待图动态反映所有事务的等待情况

​ 事务等待图是一个有向图 $G=(V,U) $

​ 若$V1$等待$V2$,则$V1$,$V2$之间画一条有向边,从$V1$指向$V2$

​ 周期性检查图中是否有回路 有回路即出现了死锁

恢复

​ 解除死锁的方法是回滚一个或多个相关事务

​ 即选择一个处理死锁代价最小的事务,将其撤消

​ 释放此事务持有的所有的锁,使其它事务能继续运行下去

两阶段封锁协议

​ 是最常用的一种封锁协议

​ 协议指所有事务必须分两个阶段对数据项加锁和解锁

​ 在对数据进行任何读写操作之前要先获得对该数据的封锁

​ 在释放一个封锁之后,事务不再获得任何其他封锁

是保证并发调度可串行性的封锁协议

含义

​ 事务分为两个阶段

​ 第一阶段是获得封锁,也称为扩展阶段

​ 第二阶段是释放封锁,也称为收缩阶段

充分条件而不是必要条件

所有遵守两阶段封锁协议的事务,其并行执行的结果一定是正确的

​ 事务遵守两段锁协议是可串行化调度的充分条件,而不是必要条件

​ 可串行化的调度中,不一定所有事务都必须符合两阶段封锁协议

​ 遵守两阶段封锁协议的事务也可能发生死锁

锁表

定义

​ 锁的请求、授予和解除是由数据库系统的锁管理器(Lock Manager) 完成

​ 锁管理器为目前已加锁的数据项维护一个记录链表

​ 每个锁请求为一个记录,按请求的到达顺序排序这个表称为锁表

​ 锁表将数据库元素和封锁信息联系在一起

多粒度封锁

封锁粒度

定义

​ 封锁对象的大小称为封锁粒度

​ 封锁对象可以是逻辑单元(属性至数据库)

​ 也可以是物理单元(数据页)

多粒度封锁

定义

​ 在一个系统中同时支持多种封锁粒度供不同的事务选择

原则

​ 选择封锁粒度考虑封锁机构和并发度两个因素

​ 对系统开销与并发度进行权衡

封锁的粒度 大 $\uparrow$ 小 $\downarrow$
系统被封锁的对象 少 $\downarrow$ 多 $\uparrow$
并发度 低 $\downarrow$ 高 $\uparrow$
系统开销 小 $\downarrow$ 大 $\uparrow$

多个关系大量元组的用户事务 $\to$ 以数据库为封锁单位

​ 需要处理大量元组的用户事务 $\to$ 以关系为封锁单元

​ 只处理少量元组的用户事务 $\to$ 以元组为封锁单位

多粒度树

​ 以树形结构来表示多级封锁粒度

​ 根节点是整个数据库,表示最大的数据粒度

​ 叶结点表示最小的数据粒度

多粒度封锁协议
  • 允许多粒度树中的每个结点被独立地加锁

  • 对一个结点加锁意味着

    这个结点的所有后裔结点也被加以同样类型的锁

  • 在多粒度封锁中一个数据对象可能以两种方式封锁,封锁的效果是一样的

    ​显式封锁:直接加到数据对象上的封锁

    ​隐式封锁:由于其上级结点加锁而使该数据对象加上了锁

    ​检查封锁冲突:

意向锁

目的

​ 提高对某个数据对象加锁时系统的检查效率

定义

​ 对任一结点加基本锁,必须先对它的上层结点加意向锁

常用意向锁

意向共享锁 IS锁

​ 表示它的后裔结点拟(意向)加S锁

意向排它锁 IX锁

​ 表示它的后裔结点拟(意向)加X锁

共享意向排它锁 SIX锁

​ 表示对它加S锁,再加IX锁

意向锁的相容矩阵

T1\T2 S X IS IX SIX
S $\surd$ $\mathsf{X}$ $\surd$ $\mathsf{X}$ $\mathsf{X}$ $\surd$
X $\mathsf{X}$ $\mathsf{X}$ $\mathsf{X}$ $\mathsf{X}$ $\mathsf{X}$ $\surd$
IS $\surd$ $\mathsf{X}$ $\surd$ $\surd$ $\surd$ $\surd$
IX $\mathsf{X}$ $\mathsf{X}$ $\surd$ $\surd$ $\mathsf{X}$ $\surd$
SIX $\mathsf{X}$ $\mathsf{X}$ $\surd$ $\mathsf{X}$ $\mathsf{X}$ $\surd$
$\surd$ $\surd$ $\surd$ $\surd$ $\surd$ $\surd$
锁的强度

​ 锁的强度是指它对其他锁的排斥程度

​ 一个事务在申请封锁时以强锁代替弱锁是安全的,反之则不然

​ 偏序关系 $X \succ SIX \succ S \parallel IX \succ IS \succ 空$

事务的隔离级别

定义

​ 事务准备接受不一致数据的级别称为隔离级别

​ 隔离级别是一个事务必须与其它事务进行隔离的程度

隔离级别 低 $\downarrow$ 高 $\uparrow$
并发 增加 $\uparrow$ 降低 $\downarrow$
数据正确性 降低 $\downarrow$ 保证 $\uparrow$

​ 申请封锁时应该按自上而下的次序进行

​ 释放封锁时则应该按自下而上的次序进行