Back

Concurrency control of the database

Fri, May 13 20163 min read
Nathaniel

并发控制的主要技术

  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\T2SXISIXSIX
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$
​ 申请封锁时应该按自上而下的次序进行
​ 释放封锁时则应该按自下而上的次序进行

Comments(0)

Continue with
to comment