09-并发

• 多用户数据库系统：多个用户同时使用

• 多事务执行方式

  • 串行

  • 交叉并发：单处理器，本质上是串行执行

  • 并行并发：多处理器，多个事务同时执行

• 并发控制

  • 调度并发操作

  • 保证事务的隔离性

  • 保证数据库的一致性

• 数据不一致性：并发操作破坏了事务的隔离性

  • 丢失修改：写后写，导致第一次写的修改被覆盖

  • 不可重复读：读后写后读，当读进程再次读取时数据不一致（可能为增/改/删）

  • 读脏数据：读后写，当写的数据被撤销时，读进程读取了撤销前的数据，产生错误

封锁

• 封锁：对数据项的访问加锁，防止其他事务访问

种类

类型	别称	上锁者权限	他人权限	作用
X锁	排他锁/写锁	独占，可读可写	无	写者为避免他人读取错误数据
S锁	共享锁/读锁	可读	可读（只能上 S 锁，不能上 X 锁）	读者为避免他人修改数据

T1\T2	X	S	-
X	N	N	Y
S	N	Y	Y
-	Y	Y	Y

常用符号

• Ri(X)：事务Ti对数据项X的读操作

• Wi(X)：事务Ti对数据项X的写操作

• Slock X：对数据项X加 S 锁

• Xlock X：对数据项X加 X 锁

• Unlock X：对数据项X解锁

封锁协议

类型	写	读	丢失修改	读脏数据	不可重复读
一级封锁协议	上 X 锁，事务结束释放	不上锁	Y	N	N
二级封锁协议	上 X 锁，事务结束释放	上 S 锁，读取后释放	Y	Y	N
三级封锁协议	上 X 锁，事务结束释放	上 S 锁，事务结束释放	Y	Y	Y

• X 锁的释放时机为事务结束，包含了 COMMIT 和 ROLLBACK

上锁带来的问题

• 活锁：系统先满足后来事务的请求，先来的事务一直在等待锁，无法继续执行

  • 采用先来先服务的方式

• 死锁：两个或多个事务互相等待对方释放锁，导致无法继续执行

• 解除死锁：撤销处理代价最小的事务并释放锁，使其他事务继续执行

检测死锁

OS 中预防死锁的方式不适合数据库的特点

• 一次封锁法：事务将所需的数据一次性上锁

  • 牺牲并发度

• 顺序封锁法：定义上锁顺序，所有事务的上锁顺序一致

  • 实现复杂

• 超时法：事务等待锁的时间超过一定阈值则放弃

  • 实现简单

  • 可能误判

• 等待图法：间歇性生成事务等待图，如果存在回路则死锁

  • 节点：事务

  • 边：事务之间的等待关系

调度

• 可串行化调度：多事务并发后的结果和事务按某一顺序串行执行的结果一致

  • 并发调度当且仅当其为可串行化时才是正确调度

事务T1：读B；A=B+1；写回A 事务T2：读A；B=A+1；写回B A,B 初始值均为 2 并行调度后，若(A,B)=(3,4) 或 (4,3)，则都是正确的调度结果

冲突可串行化

• 目标：判定调度是否可串行化

• 冲突操作：两个事务对同一数据项的操作互相影响

  • Ri(X) 和 Wj(X) 冲突

  • Wi(X) 和 Wj(X) 冲突

• 不能交换的操作：

  • 同一事务的两个操作

  • 不同事务的冲突操作

• 若调度Sc在保证冲突操作次序不变的情况下，交换事务不冲突操作的次序，得到串行的调度Sc'，则Sc 是冲突可串行化的

• 冲突可串行化 -> 可串行化（仅为充分条件）

  • 不满足冲突可串行化的调度不一定不可串行化

T1=W1(Y)W1(X) T2=W2(Y)W2(X) T3=W3(X) L1 = T1 T2 T3 = W1(Y)W1(X)W2(Y)W2(X)W3(X) 是串行调度 L2 = W1(Y)W2(Y)W2(X)W1(X)W3(X) 虽然不是冲突可串行化的调度，但是结果和L1一致，是可串行化的调度

两段锁协议

• 目标：实现调度的可串行性

• 实现步骤

  1. 扩展阶段：在需要用数据前，先上锁

  2. 收缩阶段：释放锁，开始释放锁后不能再上锁

• 两段锁协议 -> 可串行化（仅为充分条件）

  • 不满足两段锁协议的调度不一定不可串行化

• 和一次封锁法的差别：

  • 一次封锁法必须一次性对所有所需数据上锁

  • 两端锁协议更宽松，可上锁后对数据进行操作，随后继续上锁，只需保证上锁和释放过程不交叉

  • 因此两段锁协议的事务可能会发生死锁

封锁粒度

• 封锁力度：上锁对象的大小

  • 逻辑单元：属性值、属性值的集合、元组、关系、索引项、整个索引、整个数据库

  • 物理单元：页（数据页/索引页）、物理记录

• Tradeoff：并发度 vs 封锁开销

  • 粒度越小，封锁开销越大，并发度越高

  • 粒度越大，封锁开销越小，并发度越低

多粒度封锁

• 多粒度封锁：根据事务所需数据的粒度，动态调整封锁粒度

• 多粒度树：以树表示多级封锁粒度

  • 根节点为整个数据库

  • 子节点为最小的数据粒度

  • 当父节点上锁时（显式上锁），子节点自动上锁（隐式上锁）

• 实现：系统检查封锁冲突时需同时检查上锁节点的父节点、上锁节点本身和上锁节点的子节点

意向锁

• 目的：提高加锁时系统的检查效率

• 意向锁：当子节点加基本锁时，须对所有父节点加意向锁

  • IS（意向共享锁）：子节点上 S 锁时，父节点上 IS 锁

  • IX（意向排他锁）：子节点上 X 锁时，父节点上 IX 锁

  • SIX（共享意向排他锁）：同时对对象上 S 锁和 IX 锁

T1\T2	S	X	IS	IX	SIX	-
S	Y	N	Y	N	N	Y
X	N	N	N	N	N	Y
IS	Y	N	Y	Y	Y	Y
IX	N	N	Y	Y	N	Y
SIX	N	N	Y	N	N	Y
-	Y	Y	Y	Y	Y	Y

• 若父节点只读，则子节点只能上 S 锁

• 若父节点上 X 锁，则子节点不能上任何锁

• 若有子节点上 X 锁（正在被改动），父节点不能上 S 锁

• 锁的强度：X > SIX > (S, IX) > IS > 无锁

  • 对其他锁的排斥程度

  • 以强锁代替弱锁是安全的

• 具有意向锁的多粒度封锁方法

  • 申请封锁：从上向下对数据库加意向锁，检查是否存在不相容的锁

  • 释放封锁：从下向上

  • 好处：无需检查对象的子对象的锁状态，减少开销