Nathaniel's blog
Back to posts
DevOps

Concurrency control of the database

Nathaniel LinMay 13, 20163 min read5 views
Concurrency control of the database

并发控制的主要技术

  1. 封锁(Locking)

  2. 时间戳(Timestamp)

  3. 乐观控制法

锁的类型

  • 排他锁 X锁

写锁

  • 共享锁S锁读锁

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

并发操作带来的数据不一致性
丢失更新
两个事务同时读写一个数据

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

导致事务1的结果失效
不可重复读
三类不可重复读

  1. T1读两次数据得到不同的值，因为T2修改了该数据

  2. T1再读的时候数据消失，因为T2删除了该数据

  3. T1同条件读时多了一些数据，因为T2插入了一些数据

读“脏”数据
事务2读到了事务1进行中的数据

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

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

<u>不一致性是由并发操作引起的</u>

主要原因是<u>并发操作破坏了事务的隔离性</u>

封锁协议

  1. 一级封锁协议

     修改前加X锁，结束才释放

 读数据时不加锁，可能 [重复读](#不可重复读) 和 [读“脏数据”](#读“脏”数据)

 可以解决丢失更新

  1. 二级封锁协议

     在一级封锁协议之上 读数据前加 [S锁](#锁的类型) 读完之后释放 S锁

 可以避免 读“脏数据”

  1. 三级封锁协议

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

活锁

定义

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

如何解决：

	采用先来先服务策略

死锁

定义

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

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

解决方法：

预防死锁

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

		问题：扩大了封锁的范围，降低了并发度
顺序封锁法：
		事先规定一个封锁顺序，所有事务都按这个顺序封锁

		问题：维护成本高，难以实现
事务重试法：
		使用抢占机制和事务回滚

		即后申请的事务可能能够抢占已有锁的事务的锁
结论：
		操作系统中的预防死锁的策略 <u>不很适合</u> 数据库的特点

		DBMS在解决死锁的问题上 采用的是 <u>诊断并解除死锁</u> 的方法

死锁的检测与恢复

即允许死锁先发生

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

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

被撤销的事务回滚
超时法
	如果一个事务等待时间超过了限制，就认为发生了死锁

	优点：实现简单	缺点：可能误判 或 发现死锁不及时
事务等待图法
	用事务等待图动态反映所有事务的等待情况

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

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

	周期性检查图中是否有回路 有回路即出现了死锁
恢复
	解除死锁的方法是回滚一个或多个相关事务

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

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

两阶段封锁协议

	是最常用的一种封锁协议

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

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

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

	**是保证并发调度可串行性的封锁协议**
含义
	事务分为两个阶段

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

	第二阶段是释放封锁，也称为收缩阶段
充分条件而不是必要条件
	**所有遵守两阶段封锁协议的事务，其并行执行的结果一定是正确的**

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

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

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

锁表

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

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

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

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

多粒度封锁

封锁粒度

定义
封锁对象的大小称为封锁粒度

封锁对象可以是逻辑单元（属性至数据库）

也可以是物理单元（数据页）

多粒度封锁

定义
在一个系统中同时支持多种封锁粒度供不同的事务选择
原则
选择封锁粒度考虑封锁机构和并发度两个因素

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

| 封锁的粒度

| 大

$\uparrow$

| 小 $\downarrow$ | | ---------------- | ---------------- | --------------- | | 系统被封锁的对象 | 少

$\downarrow$ | 多 $\uparrow$

| | 并发度

| 低

$\downarrow$ | 高 $\uparrow$

| | 系统开销

| 小

$\downarrow$ | 大 $\uparrow$

|

<u>多个关系</u>的<u>大量元组</u>的用户事务

$\to$

以数据库为封锁单位

需要处理<u>大量元组</u>的用户事务

$\to$

以关系为封锁单元

只处理<u>少量元组</u>的用户事务

$\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$

|

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

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

Share this post

TwitterRedditTelegram

Reactions