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

Posted on Edited on In Views:
并发控制、两段锁协议、基本锁类型（排他锁、共享锁、更新锁）、意向锁（I、IS、IX）、SQL Server 的锁模式（码范围锁）、MySQL 的行锁

并发控制

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

两段锁协议

封锁的定义

  • 封锁就是一个事务对某个数据对象加锁，取得对它一定的控制，限制其它事务对该数据对象使用
  • 要访问一个数据项 \(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 是连续的