数据库系统概念 - 事务与并发控制

本节内容

1. 事务
2. 并发控制

事务

事务：访问并可能更新各种数据项的一个程序执行单元。

事务的ACID特性：

• 原子性（Atomicity）：事务的所有操作在数据库中要么全部正确地反映出来，要么完全不反应。
• 一致性（Consistency）：隔离执行事务时（在没有其他事务并发执行的情况下）保证数据库的一致性。
• 隔离性（Isolation）：尽管多个事务可能并发执行，但系统保证，对任何一对事务Ti和Tj，对Ti看来，Tj或在Ti开始之前已经执行，或在Ti完成之后开始执行。因此，每个事务都感觉不到系统中有其他事务在并发地执行。
• 持续性（Durability ）：一个事务成功完成后，对数据库的改变必须是永久的，即使出现系统故障。

抽象事务模型：

调度：指令在系统中执行的时间顺序。

串行调度：属于同一事务的指令在调度中紧挨在一起。

可串行化调度：等价于一个串行调度的调度。

指令冲突：分别属于两个事务的两条指令至少有一个是write指令。

冲突等价：在调度S中，含有分别属于事务Ti和Tj的两条连续指令Ii和Ij，且Ii和Ij引用了相同的数据项Q。只考虑read和write指令，若调度S可以经过一系列非冲突的指令转换为另一调度S’，则称S与S’是冲突等价的。

调度的优先图：调度S中包含事务T1，T2，……，Tn。将事务Ti作为图的顶点，若Ti和Tj有冲突且Ti比Tj优先访问资源，则图中存在一条从Ti到Tj的有向边。

一个调度S是冲突可串行化的 当且仅当 S的优先图中不存在环路；当且仅当 存在一个串行调度S’，S与S’冲突等价。

可恢复调度：对任何一对事务Ti和Tj，若Tj读取了之前由Ti所写的数据项，Ti应先于Tj提交。

级联回滚：因单个事务故障导致的一系列事务回滚的现象。

无级联调度：对任何一对事务Ti和Tj，若Tj读取了之前由Ti所写的数据项，Ti应在Tj这一读操作前提交。

并发控制

并发导致的不一致性

一对矛盾：数据共享（并发性质）、数据一致性

• 丢失修改（Lost Update）两个事务T1和T2读入同一数据并修改，T2的提交结果破坏了T1提交的结果，导致T1的修改被丢失。
• 不可重复读（Non-repeatable Read）：不可重复读是指事务T1读取数据后，事务T2执行更新（更删改）操作，使T1无法再现前一次读取结果。
• 读“脏”数据（Dirty Read）：事务T1修改某一数据，并将其写回磁盘；事务T2读取同一数据后，T1由于某种原因被撤销，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致。T2读到的数据就为“脏”数据，即不正确的数据。

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

并发控制的主要技术：有封锁(Locking)、时间戳(Timestamp)、乐观控制法

封锁

封锁：事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁。

共享锁（读锁，S锁）：可读不可写的锁，再加X锁需要等待释放。

排他锁（写锁，X锁）：可读可写的锁，再加S锁、X锁要等待释放。

活锁和死锁

活锁：事务T2在一数据对象加锁，事务T1加锁的请求处于等待状态，可能存在一个事务序列，其中每个事务申请对该数据加锁，每个事务在授权加锁后的一小段时间内释放锁，而事务T1对一数据的加锁请求一直处于等待状态，可能永远得不到进展。

解决办法：先来先服务原则

死锁【重点】：两个或多个事务都封锁了一些数据对象，然后又请求对已为其他事务封锁的数据对象加锁，从而出现死等待。
存在一个等待事务集{T0，T1，…，Tn}，其中T0正等待被T1锁住的数据项，T1正等待被T2锁住的数据项，Tn-1正等待被Tn锁住的数据项，且Tn正等待被T0锁住的数据项。

例：事务T1对数据A加锁，事务T2对数据B加锁，之后事务T1又请求对数据B加锁，出现等待，事务T2又请求对数据A加锁，也出现等待。

解决：

1. 预防死锁（DBMS不常用，常用于操作系统）
2. 一次性封锁（一次性把要使用的数据全部加锁，否则不能继续执行）——降低系统的并发度，难于事先精确确定封锁对象
3. 顺序封锁法（预先对数据对象规定封锁顺序，所有事务都按照这一顺序封锁数据）——很难确定一个事务要封锁哪些对象
4. 诊断并解除死锁（DBMS采用）
5. 超时法（一个事务等待时间超过规定的时限，就认为发生了死锁）——实现简单，但有可能误判死锁，时限定的太长无法及时发现死锁
6. 事务等待图法（动态反应所有事务的等待情况），系统周期性地（间隔数秒）建图，判断图中是否包含回路，解除死锁即选择一个处理死锁代价最小的事务，将其撤销，释放其占有的锁

事务等待图是一个有向图 G=(T, U) ，T结点集合，每个结点为正在运行的事务；U为有向边的集合，若T1等待事务T2，则存在一条从T1到T2的有向边。

并发调度的可串行性

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

可串行性：是并发事务正确调度的准则。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。

可串行化调度的充分条件：一个调度是冲突可串行化调度，一定是可串行化调度。

v冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度。

冲突可串行化调度：一个调度S在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度S’，如果S’是可串行化的，称调度S是冲突可串行化的调度。

冲突操作：分别属于两个事务的两条指令至少有一个write指令。

---

［例］ 今有调度 Sc1=r1(A) w1(A) r2(A) w2(A) r1(B) w1(B) r2(B) w2(B)

• 把w2(A)与r1(B)w1(B)交换，得到： r1(A) w1(A) r2(A) r1(B) w1(B) w2(A) r2(B) w2(B)
• 再把r2(A)与r1(B)w1(B)交换： Sc2＝r1(A) w1(A) r1(B) w1(B) r2(A) w2(A) r2(B) w2(B)
• Sc2等价于一个串行调度T1，T2，Sc1冲突可串行化的调度

［例］ 有3个事务 T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)

• 调度L1=W1(Y) W1(X) W2(Y) W2(X) W3(X)是一个串行调度。
• 调度L2=W1(Y) W2(Y) W2(X) W1(X) W3(X)不满足冲突可串行化。但是调度L2是可串行化的，因为L2执行的结果与调度L1相同，Y的值都等于T2的值，X的值都等于T3的值

---

两段锁协议 Two-Phase Locking，2PL

保证可串行性的一个协议，对数据对象封锁约定一些规则。所有事务必须分两个阶段对数据项加锁和解锁。

• 扩展阶段：（申请封锁）在任何数据读写之前，事务首先要获得对该数据项的封锁，但不能释放锁。
• 收缩阶段：（释放封锁）事务只能释放锁，但不能申请和获得新的锁。

可串行化调度的充分条件：遵守2PL的调度一定是可串行化的调度。

若并发事务都遵守2PL，则对这些事务的任何并发调度都是可串行化的。

一次封锁法 vs 2PL：一次性封锁法要求每个事务必须一次性把所有数据全加锁，否则不能继续执行，是遵守2PL的，但2PL不要求一次性全部加锁，故遵守2PL的调度有可能发生死锁。

封锁粒度

封锁粒度：封锁对象的大小

封锁的对象：逻辑单元（属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库），物理单元（页/block、物理记录）

封锁粒度越大，数据库能封锁的数据单元越少，并发度越小，系统开销也越小；封锁粒度越小，并发度较高，但系统开销也就越大（因为授权锁时检查的内容也就更多）。

多粒度封锁：在一个系统中同时支持多种封锁共不同事务选择。

选择封锁粒度需考虑的因素：封锁开销和并发度。

多颗粒树

允许各种大小的数据项并定于数据粒度的层次结构，小粒度的数据项嵌套在大粒度数据项中。

允许多颗粒树中的每个结点被独立抵加锁，对一个结点加锁意味着这个结点的所有孩子结点都加了同类型的锁。

一个数据对象可能以两种方式封锁：隐式封锁（由于上级结点加锁导致结点加锁）、显式封锁。两种封锁的效果是一样的。

系统检查封锁冲突时，要检查显式封锁和隐式加锁：该数据对象，所有上级结点，所有下级结点。

意向锁 intention lock

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

如果对一个结点加意向锁，说明该结点的下层结点正在被加锁；对任意结点加基本锁，必须对上层结点加意向锁。

即任何结点如果要加锁，则其上层结点要加相应意向锁。

• 意向共享锁（IS锁）：（下层结点将要被读取）后继结点拟（意向）加S锁。
• 意向排它锁（IX锁）：（下层结点将要被更新）后继结点拟（意向）加X锁。
• 共享意向排它锁（SIX锁）：（该数据项正在被读取，其下层结点个别数据即将更新）该数据对象加S锁，再加IX锁。SIX=S+IX （如：读整个表，更新个别元组）

意向锁的相容性矩阵（Y-相容，N-不相容）：

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

锁的强度：X>SIX>S=IX>IS

具有意向锁的多粒度封锁方法：申请时自上而下，释放锁时自下而上

---

例如：事务T1对关系R1加S锁。

首先，对数据库加IS锁，检查数据库和R1是否加了不兼容的锁（X、IX）

（优点）不在需要搜索和检查R1中的元组是否加了不相容的锁（X）。

---

提供意向锁可以避免检查其子节点是否存在不相容的锁，减少了加锁的开销，提高了解锁和加锁的开销。