事务

事务(transaction)在数据库中执行一个或多个操作构成的序列用于完成数据库系统的先进功能。

SQL事务语句

1. 事务启动(start):BEGIN;

2. 事务提交(commit):COMMIT;
   将事务对数据库的修改写入数据库

3. 事务中止(abort):ROLLBACK;

• 撤销所有修改数据库的事务(undo)，就像事务从未执行过一样

• 事务可以中止自己，也可以暂停自己DBMS中止

事务的ACID性质(The ACID Properties)

原子性(Atomicity): “all or nothing”

1. 事务的操作要么全部执行，要么一个不执行

2. 事务的执行只有两个结局

• 所有操作完成后，提交不损坏原子性
• 执行了部分操作后中止?破坏原子性

1. DBMS保证事务的原子性

中止事务(abortedtxn)执行的操作必须撤销(undo)

一致性(Consistency): “it looks correct to me”

如果事务程序正确，数据库在事务开始时处于一致状态(consistent state)，数据库在事务结束时仍处于一致状态

• 用户(user)保证事务的一致性(不要写错程序)

隔离性(Isolation):“as if alone”

一个事务的执行不受其他事务的干扰

执行多个事务有两种方式

• 串行执行(serial execution) ? 不破坏隔离

• 交叉执行(interleaving execution) ? 隔离可能被破坏

DBMS保证事务的隔离

• 并发控制(concurrency control):确定多个事务的正确交叉执行顺序

持久性(Durability):“survive failures”

1. 一旦事务提交，其对数据库的修改必须长期写入数据库

2. 故障(failure)修改数据库有四个结果

• 提交事务的修改已全部持久存储 ?不破坏耐久性
• 提交事务的修改仅部分持久存储 ?破坏持久性
• 部分暂停事务的修改已经持续存储 ?破坏持久性
• 暂停事务的修改没有持续存储 ?不破坏耐久性

1. DBMS保证事务的持久性

• 重做(redo)提交事务对数据库的修改
• 撤销(undo)停止对数据库的修改

并发控制

基本概念

1. 数据库(database):固定数据对象集合

• 数据对象可以是属性值、元组、页面、关系或数据库
• 数据对象又称数据库元素(database element)
• 我们不考虑数据的插入和删除

1. 事务(transaction):数据库对象的读写操作序列

• 事务可以在数据库作很多事务，但是DBMS只关心数据对象的读写操作

调度(Schedules)

调度(schedule)是一个或多个事务重要操作序列。

串行调度(Serial Schedules)

调度中不同事务的操作没有交叉(interleave)，调度是串行调度(serial schedule)。

非串行调度(Nonserial Schedules)

非串行调度的调度称为非串行调度(nonserial schedule)。

调度的正确性(Correctness of Schedules)

孤立执行每一项事务(executedinisolation)，将数据库从一致性状态(consistent state)变成另一种一致性状态。

任何串行调度都可以保持数据库的一致性

非串行调度可能会破坏数据库的一致性

异常(Anomalies)

非串行调度会导致事务异常行为(anomaly behavior)，从而破坏数据库的一致性

脏写(Dirty Writes)

T1提交之前，T已被写入的值T2覆盖。

脏读(Dirty Reads)

不可重复读(Unrepeatable Reads)

• T2更改了已被T1读A的值，T2提交。

• 如果T再次尝试读取值A，T即使得到不同的结果，同的结果TA值未修改。

幻读(Phantoms)

等价调度(Equivalent Schedules)

如果两个调度在任何数据库实例中都有相同的效果，则等价(equivalent)。

可串行调度(Serializable Schedules)

如果调度等同于串行调度，则该调度为串行调度(serializableschedule)

优点

缺点

1. 可串行调度并发度低

2. 在某些场景下，并发事务不需要严格隔离

• 修改事务可以暴露部分对象(expose)给对其他并发事务

• 弱隔离级别(weakerisolationlevel)系统提高系统的并发度

隔离级别(Isolation Levels)

在不同的隔离级别下，事务修改对象的值对其他并发事务的可见性不同

• 事务开始前可设置隔离级别

SETTRANSACTIONISOLATIONLEVEL; 

读未提交(ReadUncommitted)

未提交事务(uncommittedtxn)修改对其他事务可见

读提交(ReadCommitted)

只有已提交的事务(committedtxn)对其他事务进行修改。

可重复读(RepeatableRead)

如果一个事务不修改对象的X值，那么事务在任何时候读取的X值都等于事务开始时读取的X值。

可串行化(Serializable)

并发控制串行化

冲突可串行化

支持可串行化隔离等级DBMS实施(enforce)冲突可串行化

• 冲突可串行化的条件比一般可串行化

• 冲突可串行化更方便DBMS中实施

冲突(Con?icts)

两个操作冲突(conflict)，如果

• 这两个操作属于不同的事务
• 这两个操作涉及相同的对象，且至少一个操作是写

写-写冲突

写-写冲突可能导致脏写(dirtywrite)

写-读冲突

写-读冲突可能导致脏读(dirty read)

读-写冲突

读-写冲突可能导致不可重复读(unrepeatable read)

冲突等价(Conflict Equivalence)

两个调度冲突等价(conflictequivalent)，如果这两个调度涉及相同事务的相同操作

• 每一对冲突的操作在两个调度中的顺序都相同

冲突可串行化调度

如果一个调度冲突等价于某个串行调度，则该调度是冲突可串行化调度。

非冲突可串行化调度

1. 既然事务要满足事务的隔离性的原因是提高并行度

2. 非冲突可串行化调度

冲突可串行化调度

第1步: 将调度S表示为优先图(precedence graph)

• 每个顶点代表S中的一个事务

• 从事务Ti到事务Tj有一条有向边(arc)，如果Ti的某个操作oi和Tj的某个操作oj冲突，并且oi在S中先于oj

第2步: S是冲突可串行化调度，当且仅当其优先图没有环(acyclic)

• 优先图顶点的任意拓扑序(topologicalorder)表示了一个与S冲突等价的串行调度
   

视图可串行化

视图可串行化是比冲突可串行化更弱的概念

• 测试和实施冲突可串行化很难
• 没有DBMS实施视图可串行化

两个调度S1和S2视图等价，如果

• 如果S1中事务T1读了对象A的初始值，则S2中T1也读了A的初始值
• 如果S1中事务T1读了事务T2修改过的A值，则S1中T1也读了T2修改过的A值
• 如果S1中事务T1写了A的最终值，则S2中T1也写了A的最终值

如果一个调度视图等价于某个串行调度，则该调度是视图可串行化调度(view serializable schedule)。

冲突可串行化vs视图可串行化

冲突可串行化调度一定是视图可串行化调度

视图可串行化调度不一定是冲突可串行化调度

• 视图可串行化但非冲突可串行化的调度一定包含盲写(blind write)

并发控制协议

并发控制协议用于对并发事务实施正确的(运行时)调度，而无需预先确定整个(静态)调度

1. 悲观(pessimistic)并发控制协议

• 假定冲突很多
• 不允许任何冲突发生

1. 乐观(optimistic)并发控制协议

• 假定冲突很少
• 冲突发生了，再去解决

注意问题

1. 事务结束
2. 事务commit ：事务结束
3. 事务Abort ：事务终止
4. 正确的调度：可串行化调度
5. 不一定
6. 为了提高并发度
7. 可以
8. 为了方便实验

Lock-based Concurrency ControlLocks

锁

用锁(lock)来保护数据库对象

• 事务Ti只有获得了对象A的锁，才能操作A

• 如果事务Ti请求了对象A的锁，但并未获得，则Ti开始等待，直至获得A的锁为止

• 如果事务Ti已经获得了对象A的锁，则在Ti完成对A的操作后，Ti必须释放A的锁

使用锁的并发事务执行

LOCK(A): 请求对A加锁。

UNLOCK(A): 释放A的锁。

锁的类型(LockTypes)

共享锁(shared lock)/S锁(S-lock)

• 事务Ti只有获得了对象A的共享锁，才能读A

互斥锁(exclusive lock)/X锁(X-lock)

• 事务Ti只有获得了对象A的互斥锁，才能写A。Ti 获得了A的互斥锁后，亦可读A。

锁的相容性

如果对象A上有事务Ti加的共享锁，则事务Tj还可以对A加共享锁，但不可以对A加互斥锁

• 否则产生读-写冲突

如果对象A上有事务Ti加的互斥锁，则事务Tj对A既不能加共享锁，也不能加互斥锁

• 否则产生写-读冲突或写-写冲突

使用共享锁和互斥锁的并发事务执行

S-LOCK(A): 请求对A加共享锁

X-LOCK(A): 请求对A加互斥锁

Lock-based Concurrency Control Two-Phase Locking

两阶段锁

每个事务的执行分为两个阶段

增长阶段(Growing Phase)

• 事务向锁管理器(lockmanager)请求需要的锁

萎缩阶段(Shrinking Phase)

• 事务释放它获得的锁，但不能再请求加锁

Lock-based ConcurrencyControlStrictTwo-PhaseLocking

级联中止(CascadingAborts)：一个事务中止可能会导致其他事务级联中止(cascading abort)。

严格调度不会引发级联中止。

严格两阶段锁

增长阶段(GrowingPhase)

• 与2PL的增长阶段相同

萎缩阶段(ShrinkingPhase)

• 当事务结束时，释放它获得的全部的锁

严格2PL保证生成严格的冲突可串行化调度，因而不会产生级联中止

Lock-basedConcurrencyControl Deadlocks

死锁(Deadlocks)

一组事务形成死锁(deadlock)，如果每个事务都在等待其他事务释放锁。

死锁的处理

措施1:死锁检测(DeadlockDetection)

• DBMS检测死锁是否发生
• 如果发生了死锁，则采取办法解除死锁

措施2:死锁预防(DeadlockPrevention)

• 预防死锁的发生

死锁检测(DeadlockDetection)

1. 方法1: 超时检测(Timeout)

• 如果在给定的时间内没有任何事务执行，则认为死锁发生

1. 方法2: 等待图(waits-forgraph)检测

• DBMS用等待图表示事务关于锁的等待关系
• DBMS定期检查等待图中是否存在环(cycle)
• 如果等待图中有环，则死锁发生

等待图

等待图(waits-forgraph)

• 顶点代表事务
• 如果事务Ti正在等待事务Tj释放锁，则存在从Ti到Tj的有向边(arc)

事务产生死锁当且仅当等待图中有环(cycle)

死锁解除

从等待图的环(cycle)中选择一个事务作为“牺牲品”，中止该事务。

选择“牺牲品”时需要考虑多种因素

• 事务的年龄/启动时间
• 事务的进度(已执行的查询数量)
• 事务获得的锁的数量
• 需要级联中止的事务数量

还要考虑事务“被牺牲”的次数，防止事务“饿死”(starvation)

死锁预防

当事务启动时，DBMS为事务分配一个唯一且固定的优先级(priority)

• 开始得越早，优先级越高

当事务Ti请求事务Tj拥有的锁而无法获得时，DBMS根据Ti和Tj的优先级来裁决如何处理T1和T2。

规则1: Wait-Die(“Old Waits for Young”)

• 如果Ti比Tj的优先级高，则Ti等待
• 否则，Ti中止

规则2: Wound-Wait(“Young Waits for Old”)

• 如果Ti比Tj的优先级高，则Tj中止
• 否则，Ti等待

两个规则不能混合使用

锁的效率问题

锁越多，管理锁的开销越大
一个事务访问1亿条元组，就需要加1亿把锁
在不合适的粒度上加锁会降低事务并发度
一个事务只需访问1条元组，却在整个关系上加锁
提高锁管理的效率尽可能少加锁
在合适的粒度上加锁

锁的粒度

意向锁

1. 意向共享锁(Intension-SharedLocks)/IS锁(IS-Locks)

• 对一个对象加IS锁表示要对该对象的某个(些)后裔加S锁

1. 意向互斥锁(Intension-ExclusiveLocks)/IX锁(IX-Locks)

• 对一个对象加IX锁表示要对该对象的某个(些)后裔加X锁或S锁

1. 共享意向互斥锁(SharedIntension-ExclusiveLocks)/SIX锁(SIX-Locks)

• 对一个对象加SIX锁表示要对该对象及其所有后裔加S锁
• 并且对该对象的某个(些)后裔加X锁

相容矩阵

多粒度锁协议

任何事务都要服从下列规则：
从最高级别对象开始加锁，加锁过程自顶向下
对一个对象加IS或S锁之前，必须先获得其父亲对象的IS锁
事务对一个对象加IX、SIX或X锁之前，必须先获得其父亲对象的IX锁
解锁过程自底向上

锁升级

如果一个事务已经请求了大量低级别对象上的锁，则DBMS动态地将这些锁升级为上一级别对象上的锁

• 减少锁的数量
• 选择合适的锁粒度

Lock-basedConcurrencyControl Phantoms

动态数据库

前面假设事务只执行读操作(read)和更新操作(update)

冲突可串行化调度只在固定的数据库上保证

如果事务还执行插入(insert)或删除(delete)操作，则可能出现幻读问题(phantomproblem)

幻读

原因: T1只能锁定t中id>1的元组，无法给不存在的元组加锁

谓词锁(PredicateLocks)

可以用谓词锁(predicatelock)来解决幻读问题。谓词锁的实现代价很高

• DBMS实际上经常使用next-key锁(next-keylock)

（教妹学数据库系统）（十一）并发控制 - it610.com