Skip to content

Latest commit

 

History

History
executable file
·
307 lines (186 loc) · 12.1 KB

concurrency.md

File metadata and controls

executable file
·
307 lines (186 loc) · 12.1 KB

并发控制

概述

多用户数据库系统指的是允许多个用户同时使用的数据库系统，此系统设计并行控制

多事务的执行方式：

  1. 串行执行
  2. 交叉并发方式：时间片轮转

由于事务是并发可能告知的基本单位，所以并发控制机制的主要任务有：

  • 对并发操作进行正确调度
  • 保证事务的隔离性
  • 保证数据库的一致性

封锁

封锁指的是当事务在对某个数据对象操作之前，先向系统发出请求，对其进行加锁

加锁后该事务就对该数据有了一定控制，在事务释放锁之前，其他的事务不能更新此数据对象

封锁是实现并发控制的一个重要技术

基本封锁类型

事务对数据对象加锁后拥有的控制权限由锁的类型来决定

锁的类型：

  • 排他锁 Exclusive locks：又称为 X 锁、写锁，给该数据加上排他锁的事务可以读与修改数据；其他事务不允许加锁、读取、修改
  • 共享锁 Share locks：又称为 S 锁、读锁，给数据加上共享锁的事务只能读取该事务，不能修改；其他事务允许对该数据加 S 锁，但不允许加 X 锁

锁的相容矩阵

加 X 锁 加 S 锁
加 X 锁 不允许 不允许
加 S 锁 不允许 允许

封锁协议

封锁协议 Locking protocal 指的是运用 X 锁与 S 锁对数据对象加锁时，需要遵守的规则（比如上述的相同矩阵）

本章节主要介绍三级封锁协议

一级封锁协议

一级封锁协议指的是事务在修改数据之前必须先对其加上 X 锁直到事务结束释放

事务结束释放包括：正常结束 commit、非正常解释 rollback

一级封锁协议的作用：

  • 可以防止数据 “丢失修改”，保证事务可以恢复
  • 在一级封锁协议中，如果仅需要读数据是不需要加锁的，所以它不能保证可重复读与不读脏数据

二级封锁协议

二级封锁协议是在一级的基础上加上事务读取数据之前必须先对其加上 S 锁直到读完后释放

二级封锁协议作用：

  • 可以防止数据“丢失修改”以及读脏数据
  • 在二级中由于读完数据后就可以释放 S 锁，所以不能保证可重复读

三级封锁协议

三级封锁协议是在一级的基础上加上事务读取数据之前必须先对其加上 S 锁直到事务结束后释放

三级封锁协议作用：

  • 防止丢失修改、读脏数据，保证可重复读

总结

X 锁 S 锁 一致性保证
一级封锁协议 事务结束释放 没有 不丢失修改
二级封锁协议 事务结束释放 操作封锁协议 不丢失修改、不读脏数据
三级封锁协议 事务结束释放 事务结束释放 不丢失修改、不读脏数据、可重复读

活锁与死锁

活锁

活锁的一个例子：

  1. 首先有一个事务 A 申请封锁数据 D
  2. 事务 B 在封锁期间请求数据 D，发现上锁了，所以 pending
  3. 事务 C 在事务 B 之后请求数据 D，并且在等待过程中事务 A 结束且释放了数据 D 的锁，此时系统把相应了事务 C 的请求把数据 D 上锁并将权限交给事务 C
  4. 此时事务 B 仍然在等待中
  5. 再来了一个事务 D 做了跟事务 C 一样的操作……
  6. 事务 B 持续 pending……形成活锁

活锁的意思是：虽然锁住了，但是事务还有可能获得请求的数据

避免活锁的方式：先来先服务原则

死锁

死锁的一个例子：

  1. 假设事务 A 需要数据 X 和数据 Y；事务 B 也需要数据 X 和数据 Y
  2. 事务 A 优先请求了数据 X，并对其加了锁
  3. 事务 B 优先请求了数据 Y，并对其加了锁
  4. 此时事务 A 想请求数据 Y 时因为发现加锁了，所以 pending
  5. 事务 B 想请求数据 X时因为发现加锁了，所以也 pending
  6. 互相 pending……两个事务永远拿不到所有数据，形成死锁

死锁的意思是：两个事务互相竞争资源，导致互相等待，永远拿不到所需资源

避免死锁的方式：

  • 预防死锁：事先破坏死锁形成条件（效率低）
    • 一次封锁法：每个事务必须一次将所有需要数据全部加锁；缺点是会降低系统并发度，且难以事先确定封锁对象
    • 顺序封锁法：对数据对象规定一个封锁顺序，事务按照数据对象顺序来进行封锁；缺点是维护成本高，难以实现（需要对每一个新插入的数据都给一个顺序）
  • 死锁诊断与解除：事后处理死锁
    • 超时法：如果事务等待时间超过规定时间，就认为是死锁
      • 优点：实现简单
      • 缺点：如果规定时间太短可能误判死锁；如果太长可能不能及时发现
    • 等待图法：并发控制子系统周期性画有向图，点表示事务，边表示事务等待情况，如果有向图产生回路了，表示死锁产生；解除死锁的方法是选择一个处理死锁代价最小的事务撤销，并释放其控制的所有锁

并发调度的可串行性

可串行化调度：多个事务并发执行是正确的，当且仅当起结果与按某一次串行执行这些事务时结果相同

可串行性：并发事务正确调度的准则，如果按照这个准则进行的并发调度只有时可串行化的才是正确的

冲突的操作

不同事务对同一数据的特定操作会让并行调度产生冲突

  • 读写操作：事务 A 在读数据 X 的同时事务 B 在写数据 X
  • 写写操作：事务 A 在写数据 X 的同时事务 B 在写数据 X

冲突可串行化调度：指的是将一个调度在保证事务冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序能得到另一个可串行调度的过程

如果调度是冲突可串行化调度，那么这个调度一定是可串行化调度；反之则不一定

两段锁协议 2PL

DBMS 普遍采用两段锁协议来实现并发的可串行性，从而保证调度的正确性

两段锁协议定义：所有事务都必须分两个阶段对数据加锁、解锁；在对任何数据进行读、写之前，事务必须要先申请对数据的封锁；在释放一个封锁后，事务不再申请获得任何封锁

两个阶段

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

这个阶段事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁

第二个阶段是：释放封锁，也称为收缩阶段

这个阶段事务可以释放任何数据项的任何类型的锁，但是不能再申请任何锁

简单来说，就是事务可以在执行中不断给数据加锁，但是只要开始解锁了，就只能解锁不能加锁了


遵守了两段锁协议的事务一定是可串行化的；反之则不一定

两段锁协议并不要求事务必须一次性把所需数据全部加锁，所以遵守两段锁协议的事务可能发生死锁

封锁的粒度

封锁对象的大小被称为封锁的粒度 Granularity

封锁的对象一般分为两个部分：

  • 逻辑单元：属性值、属性值的集合、元组、关系、索引项、整个索引、整个数据库
  • 物理单元：页（数据页或索引页）、物理记录

说明：

  • 封锁力度与系统的并发度和并发控制的开销密切相关
  • 颗粒度越大，数据库能封锁的数据单元越少、并发度越小、系统开销越小
  • 颗粒度越小，数据库能封锁的数据单元越多、并发度越大、系统开销越大

多粒度封锁

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

选择粒度的原则：系统开销 + 并发度

  • 如果是多个关系的大量元组的用户事务：以数据库为单位
  • 如果是大量元组的用户事务：以关系为封锁单元
  • 如果只处理少量元组的用户事务：以元组为封锁单位

多粒度树

多粒度树是以树形结构来表示多级封锁粒度，根节点是整个数据库，表示最大的数据粒度，叶子结点表示最小的数据粒度

db-6

多粒度封锁协议

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

对一个节点加锁意味着该节点所有后裔节点页会被加上同样类型的锁

加锁有两种方式：

  • 显式封锁：直接加到数据对象上的封锁
  • 隐式封锁：对该对象的上级节点加锁导致该对象也被封锁

两种加锁方式的效果是一样的，DBMS 在检查封锁冲突时需要两种一起检查

意向锁

意向锁时为了提高对某个数据对象加锁时的系统检查效率

意向锁的含义：如果对一个数据节点加了意向锁，则说明该节点的下层节点正在被加锁；如果对任一结点加基本锁，则必须在其上级节点加上意向锁

常用的意向锁：

  • 意向共享锁 Intent Share Lock, IS 锁：IS 锁的后裔节点有 S 锁
  • 意向排他锁 Intent Exclusive Lock, IX 锁：IX 锁的后裔对象有 X 锁
  • 共享意向排他锁 Share Intent Exclusive Lock, SIX 锁：表示要对该节点加 S 锁与 IX 锁

锁的相容情况：

S X IS IX SIX
S Y X Y N N
X N N N N N
IS Y N Y Y Y
IX N N Y Y N
SIX N N Y N N

具有意向锁的锁粒度封锁原则：

任何事物要对数据对象加锁时，申请封锁需要自上而下；申请解锁时需要自下而上

其他并发控制机制

时间戳方法

给事务盖上一个时间戳，标识事务开始的时间

机制：

  • 由于每个事务都有一个时间戳，所以我们可以按照时间戳来解决冲突
  • 如果遇到冲突则优先回滚时间戳较早的事务
  • 对于回滚的事务赋予一个较新的时间戳从头开始执行

乐观控制法

不对事务进行任何管制

机制：

  • 只在事务提交前进行准确性检查
  • 如果事务出现冲突并影响可串行性，则拒绝提交并回滚

多版本并发控制 MVCC

在 DB 中维护数据库对象多个版本信息来实现高效并发控制

版本类似与数据对象的一个快照，记录了数据对象在某个时刻的状态

多版本并发控制协议

每个写操作都会创建一个新的版本 Q，最终会形成一个版本序列

每个版本 Q 都包含三个数据：

  • 版本值
  • 创建事务 Q 的时间戳
  • 记录所有版本中最大的时间戳（最后一次的时间戳）

协议内容如下：

  1. 如果当前版本 Q 有小于事务 T 的最大时间戳
  2. 如果事务 T 发出读操作，则直接返回最新版本 Q 的内容
  3. 如果事务 T 发出写操作，则
    1. 如果版本最后读取的时间比事务 T 的时间要后，则需要回滚 T（否则读数据会不一致）
    2. 如果事务 T 的时间跟版本 Q 最后写的时间一致，则覆盖版本 Q 的内容
    3. 否则，创建 Q 的新版本
  4. 如果最后有两个 Q 版本，这两个本本都比系统中最老的时间戳小，则我们可以删掉两个本本中比较旧的那个版本

说明：

  • MVCC 与封锁机制相比，消除了数据库中数据对象读写操作的冲突，能提高系统性能呢个
  • MVCC 会产生大量无效版本，且在结束事务时其影响的元组有效性不能马上确定

改进的多版本并发控制

改进点：将事务分为只读事务与更新事务（ＭV2PL 协议 ）、加上了验证锁（C 锁）

  • 只读事务发生冲突的可能性很小，采用多版本的时间戳
  • 更新事务采用较为保守的两段锁协议

MV2PL 相容矩阵

R lock W lock C lock
R lock Y Y N
W lock Y N N
C lock N N N

说明：

  • 写锁与读锁相融了，写成新的版本，读旧的版本
  • 事务提交时，需要先获得验证锁（获得条件是数据没有任何其他锁），获得验证锁之后就可以丢掉旧的值了
  • MV2PL 的好处是读写锁不冲突，可以提高系统并发性