数据库概论.陈立军.07.并发控制

并发控制

  • 并发问题
  • 资源争用
  • 关键:调度

两段锁协议

封锁的定义

  • 封锁就是一个事务对某个数据对象加锁,取得对它一定的控制,限制其它事务对该数据对象使用
  • 要访问一个数据项 \(R\),事务 \(T_i\) 必须先申请对 \(R\) 的封锁,如果 \(R\) 已经被事务 \(T_j\) 加了不相容的锁,则 \(T_i\) 需要等待,直至 \(T_j\) 释放它的封锁
  • 例子:信号灯
  • 封锁性能
    • 事务吞吐量
    • TPC-C:测数据库事务性能
      • 目前的第一:Ocean Base(阿里)
  • 一些其他的指标
    • TPC-H:测数据库的大数据分析处理能力
  • 数据库追求的目标:在避免冲突的前提下,提高事务吞吐量(提高并发度)

锁持有期

  • 长锁:保持到事务结束时才释放的锁
  • 短锁:在事务中途就可以释放的锁
  • 例子
    • read uncommitted:不申请锁
    • read committed:短 S 锁
    • repeatable read:长 S 锁

两段锁协议

  • Two-Phase Locking Protocol
  • 事务加锁和解锁过程是严格分开的
  • 增长阶段(Growing Phase)
    • 事务可以获得锁,但不能释放锁
  • 缩减阶段(Shrinking Phase)
    • 事务可以释放锁,但不能获得锁
  • 图示

  • 哪个事务隔离性级别不满足 2PL(两段锁协议)
    • read committed

两阶段封锁协议的作用

  • 若一组事务均服从两阶段封锁协议,则它们的调度一定是可串行化
  • 封锁点:事务获得其最后封锁的时间
    • 获得最后一个锁的时间
  • 事务调度等价于和其封锁点顺序一致的串行调度
  • 例子
    • 如下图,t1, t2, t3 满足 2PL 则等价的串行顺序是 t1, t3, t2

为什么两阶段封锁协议保证可串行化?

  • \(\{T_0,T_1,\cdots,T_n\}\) 是参与调度 \(S\) 的事务集
  • 如果 \(T_i\) 对数据项 \(R\)\(A\) 型锁,\(T_j\) 对数据项 \(R\)\(B\) 型锁,且 \(\mathrm{comp(A,B)=false}\)(不相容的锁),若 \(T_i\) 先获得锁,则 \(T_i\) 先于 \(T_j\),记作 \(T_i\to T_j\),得到一个优先图
  • \(t_i\)\(T_i\) 的封锁点,若 \(T_i\to T_j\),则必然有 \(t_i<t_j\)
    • 事务 \(T_j\) 需要等待 \(T_i\) 释放不相容的锁之后,才能获得锁,不妨设这个时间为 \(t_m\)
    • \(t_i<t_m\le t_j\)
  • \(\{T_0,T_1,\cdots,T_n\}\) 不可串行化,则在优先图中存在环,不妨设为 \(T_0\to T_1\to\cdots\to T_n\to T_0\),则 \(t_0<t_1<\cdots<t_n<t_0\),时间不可能成环,矛盾

封锁类型

  • 基本锁类型:X 锁、S 锁、U 锁
  • 意向锁:IS、IX、IU、SIX
  • 码范围锁:RangeS_S、RangeI_N…
  • 其他锁:模式锁、闩锁、BU锁

基本锁类型(排他锁、共享锁、更新锁)

排他锁与共享锁

  • 排它锁(X 锁,eXclusive lock)
    • lock-X(R):又称写锁,持有 X 锁可以读写数据项
    • 事务 T 对数据对象 R 加上 X 锁,则其它事务对 R 的任何封锁请求都不能成功,直至 T 释放 R 上的 X 锁
  • 共享锁(S 锁,Share lock)
    • lock-S(R):又称读锁,持有 S 锁只能读取数据项
    • 事务 T 对数据对象 R 加上 S 锁,则其它事务对 R 的 X 锁请求不能成功,而对 R 的 S 锁请求可以成功
  • 封锁的相容矩阵 \(\mathrm{comp(A,B)}\)
请求锁模式A  现有锁模式B S X
S \(\checkmark\) \(\times\)
X \(\times\) \(\times\)

先读后写场合中的锁转换

  • 两个事务 T1, T2
    • T1: read(a1); read(a2); ...; read(an); write(a1)
    • T2: read(a1); ...
  • T1 需要对 a1 加 X 锁(因为后面要写)
    • 这样的方案是不好的,因为 T2 无法执行
  • 更好的并发方式
    • T1 在 read(a1) 上加 S 锁,在执行 write(a1) 之前升级锁(upgrade)为 X 锁
    • 升级的时候要求没有事务在 a1 上持有锁
  • 如下左图等价于串行调度 T1,T2,右图等价于串行调度 T2,T1

带有锁转换的两段锁协议

  • 增长阶段
    • 可获得 lock-S
    • 可获得 lock-X
    • 可将 lock-S 升级为 lock-X(upgrade)
  • 缩减阶段
    • 可释放 lock-S
    • 可释放 lock-X
    • 可将 lock-X 降级为 lock-S(downgrade)

锁升级与重新申请锁

  • 升级锁和重新申请锁的区别
    • 申请锁是维护一个队列的
      • 重新申请锁则会排在队列的最后
      • 升级锁则会排在队列的前面,可能更早考虑
  • 在那个隔离性级别下会出现锁升级
    • repeatable read
    • read committed 不会,因为是短 S 锁

锁转化带来的问题

  • 死锁
  • 两个事务都是先读后写
  • 如下例子
    • repeatable read 情况下(read 为长 S 锁)
      • T1 在 write(a1) 时需要锁升级,但是如果此时 T2 已经执行到了 read(a1) 之后,此时 T1 等待
      • 同样的道理 T2 也等待,导致死锁

怎么避免锁转换导致的死锁

  • 引入更新锁(U 锁)

更新锁

  • U 锁,Update lock
    • 只有读权限
  • 当一个事务查询数据以便将来要进行修改时,可以对数据项施加更新锁
    • 先读后写的操作申请 U 锁
    • 只读则申请 S 锁
  • 如果事务修改资源,需将更新锁转换为排它锁(X 锁)
  • 一次只有一个事务可以获得资源上的更新锁
更新锁的相容矩阵
请求锁模式A  现有锁模式B S X U
S \(\checkmark\) \(\times\) \(\checkmark\)
X \(\times\) \(\times\) \(\times\)
U \(\checkmark\) \(\times\) \(\times\)

封锁粒度

  • 封锁对象
    • 属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库、物理页、块
  • 不同封锁粒度
    • 封锁粒度大,则并发度低,开销小
    • 封锁粒度小,则并发度高,开销高
  • 一个锁在数据库中大概占据 100 来个字节
  • 事务的完整性相关域:
    • 只封锁与操作有关的的数据对象

封锁粒度与查询性能

  • 一份早期的数据,数据表五道口技工学院中性别为女的记录非常少
  • 满足条件的数据非常少时,最佳粒度为行锁
1
2
3
select *
from 五道口技工学院
where 性别='女'
  • 满足条件的数据非常多时,最佳粒度为表锁
1
2
3
select *
from 五道口技工学院
where 性别='男'
  • 系统必须支持多粒度锁,根据查询范围选择最佳粒度

多粒度封锁中的隐含冲突

  • 事务 T1(表锁)
1
2
3
select *
from 五道口技工学院
where 性别='男'
  • 事务 T2(表锁)
1
2
/* 修改表的属性 */
alter table 五道口技工学院
  • 事务 T3
1
2
3
select *
from 五道口技工学院
where 性别='女'
  • T1 和 T2 的冲突是能够检测出来的
    • 锁表中有表的 id
  • 事务 T2 和 T3 的冲突无法检测
    • 锁表中只有行 id 和表 id,无法检测
  • 冲突无法检测的原因:大集合中包含小集合,存在包含冲突
    • 在分层封锁中,封锁了上层节点就意味着封锁了所有内层节点
    • 如果有事务 T3 对某元组加了 S 锁,而事务 T2 对该元组所在的关系加了 X 锁,因而隐含地 X 封锁了该元组,从而造成矛盾

  • 在对某个粒度加锁的同时,在其父节点贴上告示条,表示被占用
    • 告示条和告示条之间不冲突
    • 告示条告诉别人不能直接加锁
    • 告示条只起到提示作用
  • 引入意向锁(起到告示条的作用)

意向锁

意向锁 I(Intend)

  • 引入意向锁 I(Intend)
  • 当为某节点加上 I 锁,表明其某些内层节点已发生事实上的封锁,防止其它事务再去显式封锁该节点
  • I 锁的实施是从封锁层次的根开始,依次占据路径上的所有节点,直至要真正进行显式封锁的节点的父节点为止
意向锁 I 的相容性
请求锁模式A  现有锁模式B S X I
S \(\checkmark\) \(\times\) \({\color{red}\times}\)
X \(\times\) \(\times\) \(\times\)
I \({\color{red}\times}\) \(\times\) \({\color{red}\checkmark}\)
意向锁 I 的不足之处
  • 能够防范读写冲突

  • 让读读操作变成了不相容

  • 降低了并发度
  • 根本原因:I 锁没有告诉我们内层加的锁的类型
  • 引入意向锁 IS 锁,IX 锁

更为精细化的意向锁(IS 锁,IX 锁)

  • IS 锁:如果对一个数据对象加 IS 锁,表示它的后裔节点拟(意向)加 S 锁
  • IX 锁:如果对一个数据对象加 IX 锁,表示它的后裔节点拟(意向)加 X 锁
  • 本质还是意向锁,起到告示条的作用
意向锁 IS/IX 的相容性
请求锁模式A  现有锁模式B S X IS IX
S \(\checkmark\) \(\times\) \({\color{red}\checkmark}\) \({\color{red}\times}\)
X \(\times\) \(\times\) \(\times\) \({\color{red}\times}\)
IS \({\color{red}\checkmark}\) \(\times\) \({\color{red}\checkmark}\) \({\color{red}\checkmark}\)
IX \({\color{red}\times}\) \({\color{red}\times}\) \({\color{red}\checkmark}\) \({\color{red}\checkmark}\)
实际例子
  • 能够防范读写冲突

  • 读读操作还是相容的
    • 解决了简单的意向锁 I 降低了并发度的问题

共享与意向排他锁 SIX

  • 共享意向排他
    • S + IX
  • 解决如下事务的加锁问题
    • 在表的级别应该加什么锁呢?
    • IX 和 S 单独都不能支持这个操作
    • X 锁并发性很低
1
2
3
4
5
6
set transaction isolation level repeatable read
begin tran 'audit'
select * from bigtable
update bigtable
set col = 0
where keycolumn = 100
  • 在表上加 SIX 锁,则表示该事务要读整个表(S 锁),同时会更新个别元组(IX 锁)
  • SIX 锁只和 IS 锁相容
    • 找同时与 S 锁和 IX 锁相容的锁
相容矩阵
请求锁模式A  现有锁模式B S X U IS IX SIX
S \(\checkmark\) \(\times\) \(\checkmark\) \({\color{red}\checkmark}\) \({\color{red}\times}\) \(\times\)
X \(\times\) \(\times\) \(\times\) \(\times\) \({\color{red}\times}\) \(\times\)
U \(\checkmark\) \(\times\) \(\times\) \(\checkmark\) \(\times\) \(\times\)
IS \({\color{red}\checkmark}\) \(\times\) \(\checkmark\) \({\color{red}\checkmark}\) \({\color{red}\checkmark}\) \({\color{red}\checkmark}\)
IX \({\color{red}\times}\) \({\color{red}\times}\) \(\times\) \({\color{red}\checkmark}\) \({\color{red}\checkmark}\) \(\times\)
SIX \(\times\) \(\times\) \(\times\) \({\color{red}\checkmark}\) \(\times\) \(\times\)

SQL Server 的锁模式

模式修改锁(Sch-M锁)

  • 执行表的 DDL 操作时使用模式修改锁
  • Sch-M 锁与所有锁模式都不相容

模式稳定锁(Sch-S锁)

  • 当编译查询时,使用模式稳定锁
  • Sch-S 锁与除了 Sch-M 锁之外所有其它锁模式相容
  • 此时其它事务都能继续运行,但不能对表执行 DDL 操作

SQL Server中的大容量更新锁

  • BU 锁,Bulk update lock
  • 当使用 bulk insert 命令或 bcp 工具将数据大容量复制到表,且指定了 TABLOCK 提示或者使用 sp_tableoption 设置了 table lock on bulk 表选项时,将使用大容量更新锁
  • 大容量更新锁允许多个进程将数据并行地大容量复制到同一表,同时防止其它不进行大容量复制数据的进程访问该表

SQL Server 码范围锁

  • 如何避免幻象的产生
  • 只封锁现有数据是无效的
  • 查询例子
1
select * from R where A>=10 and A<=20
  • 应该防止其他事务往区间 \([10,20]\) 插入数据
    • 如何防止?
  • 如何找到这样一个区间?
  • 表本身是无序的集合,只能用整个表覆盖这个区间,也即需要申请表级锁,并发度极低
  • 数据库中什么对象是有序的?
    • 索引是有序的
  • 如果在 A 上存在索引,则可以找到一个紧凑区间

码范围锁:范围扫描查询

  • 码范围锁定原理解决了幻像并发问题
  • 码范围锁通过覆盖索引行和索引行之间的范围来工作,因为第二个事务在该范围内进行任何行插入、更新或删除操作时均需要修改索引,而码范围锁覆盖了索引项,所以在第一个事务完成之前会阻塞第二个事务的进行
  • 要求(同时满足)
    • 必须在查询项上存在索引
    • 隔离性级别为 serializable

码范围锁模式

  • 码范围锁包括范围组件行组件
    • 前者表示保护两个连续索引项之间范围的锁模式(RangeT)
    • 后者表示保护索引项的锁模式(K),这两部分用下划线连接,如 RangeT_K
范围 模式 描述
RangeS S RangeS_S 共享范围,共享资源锁;可串行范围扫描
RangeS U RangeS_U 共享范围,更新资源锁;可串行更新扫描
RangeI NULL RangeI_N 插入范围,空资源锁;用于在索引中插入新码之前测试范围
RangeX X RangeX_X 排它范围,排它资源锁;用于更新范围中的码

码范围锁的相容矩阵

请求模式 S U X RangeS_S RangeS_U RangeI_N RangeX_X
共享(S) \(\checkmark\) \(\checkmark\) \(\times\) \(\checkmark\) \(\checkmark\) \(\checkmark\) \(\times\)
更新(U) \(\checkmark\) \(\times\) \(\times\) \(\checkmark\) \(\times\) \(\checkmark\) \(\times\)
排它(X) \(\times\) \(\times\) \(\times\) \(\times\) \(\times\) \(\checkmark\) \(\times\)
RangeS_S \(\checkmark\) \(\checkmark\) \(\times\) \(\checkmark\) \(\checkmark\) \(\times\) \(\times\)
RangeS_U \(\checkmark\) \(\times\) \(\times\) \(\checkmark\) \(\times\) \(\times\) \(\times\)
RangeI_N \({\color{red}\checkmark}\) \(\checkmark\) \({\color{red}\checkmark}\) \({\color{red}\times}\) \(\times\) \(\checkmark\) \(\times\)
RangeX_X \(\times\) \(\times\) \(\times\) \(\times\) \(\times\) \(\times\) \(\times\)

一个例子

  • employees 表上存在 last_name 上的索引

  • 在 serializable 隔离性级别上执行如下查询
1
2
3
select *
from employees
where last_name between 'Delaney' and 'DuLaney'
  • 在索引上找到一个覆盖上面范围的最小区间 \(\mathrm{(Dallas,Duluth)}\)
  • 如果 Dallas, Donovan 和 Duluth 是叶级的顺序索引码,前两个码将获得码范围锁 RangeS_S
    • 码范围锁防止任何向以这两个码结束的区间插入数据
      • 锁住了 Dallas 和 Donovan 后面的区间
    • 没有大于 Dallas 且小于等于 Donovan 的行可以插入,也没有大于 Donovan 且小于等于 Duluth 的行可以插入
  • 能否插入 Dashagua?
    • 不能插入,虽然是在查询范围之外,但是在最小覆盖的索引范围内部

SQL Server 锁

MySQL 中的行锁模式

  • MySQL 的 innode 引擎,在建表的时候,默认会有一个隐含的自增字段,缺省的会在这个字段上建立聚簇索引
  • 缺省的 MySQL 就是有序的表
  • MySQL 中的行锁模式
    • lock_rec_not_gap:只锁记录
    • lock_gap:间隙锁,锁两个记录之间的gap,防止记录插入
    • lock_ordinary:也称为Next-KeyLock,锁一条记录及其之前的间隙
    • lock_insert_intension:插入意向gap锁,插入记录时使用,是lock_gap的一种特例
  • 图示

  • 相容性
RECORD GAP NEXT-KEY II GAP
RECORD \(\checkmark\) \(\checkmark\)
GAP \(\checkmark\) \(\checkmark\) \(\checkmark\) \(\checkmark\)
NEXT-KEY \(\checkmark\) \(\checkmark\)
II GAP \(\checkmark\) \(\checkmark\)

闩锁

  • lock:保护逻辑对象
  • latch:保护内存页
  • 以下显示不对内存页加保护的结果
    • 页头的写入需要做保护

  • 为什么不直接使用排他锁实现?
    • 太慢了,需要向锁管理器申请,锁表的处理慢
  • 闩锁是自旋锁(spinlock)
  • 使用序列号锁聚簇索引码的问题
    • 由于自增 id,最新的页面会被很多进程同时写,闩锁竞争激烈

MySQL 的自增器

1
2
3
4
5
6
7
/* SQL1 */
/* 已知条数 */
insert into t1 values (1),(2)

/* SQL2 */
/* 未知条数 */
insert into t2 select * from t1
  • 已知行数用闩锁(mutex),未知行数使用自增锁(auto-inc locking)
  • 为了保证同一个事务插入的数据,自增 id 是连续的