数据库事务处理
并发控制
为什么需要并发? 三种不一致现象
丢失修改 AB同时修改并写回,先写的会被覆盖掉(无关commit)
不能重复读 A读完,B修改并写回,A在当前事务里如果再读值不一样了(还没commit)
脏读 B修改并写回,A读了修改后的值,但B又Rollback了,所以A读的是无效值
事务
概念
DBMS提供的一种操作手段,将一系列基础操作组合,保证一致性
宏观性(程序员看到的事务):多条语句的一次执行 事务由程序员提出,结束前需要commit或rollback
微观性(DBMS看到的事务):语句的整体性执行
事务的并发执行:多个事务从宏观上看是并行执行的,
但其微观上的基本操作(读、写)则可以是交叉执行的
特性:ACID
原子性 事务不可分,要么全做,要么不做
一致性 不能出现三种不一致现象
隔离性 互相不受影响
持久性
已提交事务的影响是持久的,被撤销事务的影响
是可恢复的
事务调度
若干事务的内部基本步(读写、锁)的执行顺序
串行调度:两个事务完全串行
并发调度:宏观并行,微观交错
并发调度的正确性:仅当并发和串行的执行结果
在内容上一致时
可串行性
除了内容一致,形式也一致
可串行化的等效串不唯一
冲突
两个操作冲突=不可交换顺序
同一事务的任何两个操作都是冲突的
不同事务对同一元素的两个写操作是冲突的
不同事务对同一元素的一读一写操作是冲突的
冲突可串行性
冲突可串行性 是比 可串行性 要严格的概念
判别算法
构造一个有向图,结点是每一个事务ABC
如果A的一个操作与B的一个操作发生冲突,且A
在B前执行,则绘制一条由A指向B的有向边,表
示A要在B前执行。
如果此有向图没有环,则是冲突可串行化的。
并发控制方法
基于锁的并发控制
锁的类型
排他锁X:只有一个事务有所有权力
共享锁S:所有都能读,都不能写
更新锁U:先读,可升级为写
增量锁I:增量更新
锁本身不能保证冲突可串行性,需要配合协议
相容性矩阵
0-3级锁协议
0级协议对读没有任何要求,可以不申请锁强行读
三种不一致都消除不了
丢失修改
不可重复读
脏读
可以防止丢失修改,因为在别人不能在你提交前进行修改(有写排他锁)
不能防止不可重复读和脏读,理由完全同0级协议的图,因为对读没有任何
限制,你排他锁关我读操作什么事
可以防止脏读,因为读操作需要申请共享锁,申得到共享锁就说明没有排他锁
不能防止重复读错误
不可重复读现象不会发生,因为有了共享锁,根本不会有排他锁的写,期间
你怎么读都没事
封锁粒度
指封锁数据对象的大小
属性值 < 元组 < 元组集合 < 整个关系 < 整个 DB
对象越大,并发度越小,封锁开销也小
两阶段封锁协议
每个事务分两个阶段提出加锁和解锁申请
增长阶段:事务可以获得锁,但不能释放锁
缩减阶段:事务可以释放锁,但不能获得新锁
两阶段完全分离,确保后者不会有人先释放(保持并请求)
可以保证冲突可串行性的,但是可能产生死锁
基于撤回的并发控制
基于时间戳
时间戳
唯一性和递增性,可以表征一系列事务执行的先后次序
使用了时间戳后,事务仍然是交叉并发执行的,但是其结
果就仿佛一个特定顺序(即时间戳升序)的串行调度
因此先并发执行,如果冲突,撤销这个动作对应的整个事
务,并重启该事务,让他的时间戳变大(变大后必不可能
冲突了,相当于串行里最后执行的)
没有讲撤销重启的具体操作,应该不考
可能发生的冲突
时间戳大的先写(读),时间戳小的后读(写)
时间戳大的先写,时间戳小的后写
每次操作前检查TS和WT或RT,
如果TS大一定行,否则除非读-读
一定冲突
第二种改进调度
基于有效性确认
三阶段
三集合
有效性确认规则
故障恢复
宏观思路
DBMS的运行方式
三种故障类型
事务故障
某一个程序(事务)自身运行错误所引起的故障
系统故障
介质故障
日志
缓冲区处理策略
缓冲区策略与日志类型
三种日志
Undo
Redo
Undo/Redo
第一种简单调度规则
不能避免脏读:时间戳小的写完但撤回
实际上写-写冲突不需要撤销的(放行),但要考
虑放行后先写的又rollback的情况
加上提交位C(x)避免脏读
托马斯写规则
不可实现的读(必冲突) 时间戳大的先写,时间戳小的后读
可实现的读(读的时间戳大于写)
如果C(x)为1,直接读
如果C(x)为0还没提交时,读可能是脏的,推迟
直到C(x)为1或者rollback
回滚
不可实现的写(必冲突) 时间戳大的先读,时间戳小的后写
可实现的写
写的时间戳大于读和写 直接写,并置C(x)=0直到提交或回滚
写的时间戳大于读但小于写
如果C(x)为1,过时的写-写操作可以直接被忽略
如果C(x)为0,推迟,看最后时提交还是roll,提
交就同上,roll就补写
读写并发
写写并发
总结
所有事务按结束FIN排序确认,第一个先确认
看当前事务,如果其之前的事务的FIN,大于当
前事务的START,则检查当前读与之前写
看当前事务,如果其之前的事务的FIN,大于当
前事务的VAL,则检查当前写与之前写
都为空则确认,继续下一个,否则回滚当前事务
内存(主存)和外存(辅存)
内存中, 又将其分为程序数据(事务数据)和系统数据
故障恢复意义 由当前不正确状态恢复到已知正确的某一状态
需要保证事务的
持久性
原子性 要么全都执行,要么全都不执行
影响是持久的
由于掉电、非正常关机等所引起的故障
影响该程序(事务)本身
影响正在运行的事务以及数据库缓冲区(数据库
缓冲区涉及正在运行和已经运行的事务)
由于介质(数据库)损坏等所引起的故障
影响是全面的,既影响内存中的数据, 又影响介
质中存储的数据
通过重做事务(Redo)和撤消事务(Undo)来恢复
通过运行日志(System Log)来恢复
日志的使用
当事务对数据库进行操作时,先写运行日志。写
成功后,再与数据库缓冲区进行信息交换
运行日志直接写入介质存储上,会保持正确性
该文件以流水方式记录了每一个事务对数据库的
每一次操作及操作顺序
日志用来恢复
故障时已结束的,重做;未结束的,撤销
保存的信息
定期设置及更新检查点:强制使 DB 缓冲区中的内容与 DB 中
的内容保持一致,即将 DB 缓冲区更新的所有内容写回 DB 中
保证在检查点之前内存中数据与 DB 中数据是保
持一致的,即检查点之前结束的事务不需要恢复
通过副本(Copy)来恢复
定期在其他介质存储上产生另一份等同记录
设置转储点,介质故障后只需在转储点后恢复到
故障点(检查点此时没用)
过频,影响系统效率
过疏,运行日志过大
因此运行日志的长度只要到上一个转储点
Force
No steal
No force
Steal
不允许在事务 commit 之后把缓冲区中的数据写入磁盘
不允许在事务 commit 之前把缓冲区中的数据写入磁盘
允许在事务 commit 之后把缓冲区中的数据写入磁盘
允许在事务 commit 之前把缓冲区中的数据写入磁盘
但commit后若崩溃可能还没写入,需要Redo
但在commit前若崩溃可能已经写入,需要Undo
最常用的
不强制(可延迟)
窃取(可提前)
必须output完才能commit(参考Steal)
故障恢复
日志的尾部开始按日志记录的反序,撤销未完成
事务的所有修改
忽视< START T >....< COMMIT T >,已提交的肯定Output了
忽视<START T>….<ABORT T>,这是主动rollback
检查点
静止检查点
周期性地对日志设置检查点,设置时停止接受新
的事务, 等到所有当前活跃事务提交或终止
非静止检查点
将日志刷新到磁盘,写入日志记录<CKPT>
在设置检查点时不必关闭系统,允许新事务进入
写入一条<START CKPT(T1,…,Tk)>
其中T1,…,Tk 是所有活跃的未结束的事务
直到T1,…,Tk都完成时,写入<END CKPT>
中间的作为检查区间
恢复<START T>……………,做了一半的,回滚
检查点
静止 遇到<CKPT>时结束
非静止
遇到<START CKPT>结束
遇到<END>不能结束,因为检查区间里面可能还有<START T>
先commit再output(参考No force)
故障恢复
从日志的起始位置开始按日志记录的正序处理每
一日志记录,重做已提交事务的所有修改
忽视<START T>……………,还没提交就肯定没output
恢复< START T >....< COMMIT T >,因为提交了
但是可能还没output完或者丢失了
Force + No Steal
No Steal+No Force
Steal + Force
Steal + No Force
检查点
非静止
找到上一个<END CKPT>,从其对应的<START
CKPT>里包含的事务T的最早那个<START>开始
静止 找到上一个<CKPT>,开始顺序处理
因为这些都可能会有< START T >....< COMMIT T >
则无所谓谁先谁后,只要保证<T,X,u,v>被先于OUTPUT写完即可
故障恢复
自前向后地,按日志记录的正序,重做所有已提交的事务;自后向
前,按日志记录的反序,撤销所有未完成事务的所有修改
先恢复<START T>……………,做了一半的,回滚
再恢复< START T >....< COMMIT T >,因为提交了但是可能还没
output完或者丢失了
一定要先撤销再重做!
区别
4、解决的问题:
3、恢复:
2、写的顺序:
1、Undo 型日志保留的是旧值,而 Redo 型日
志保留的是新值, Undo/Redo结合型日志是既
保留旧值又保留新值;
Undo 型日志是从日志的尾部开始恢复,按日志
记录的反序处理,直至遇到第一个检查点为止结
束;
Undo 型日志是先将数据写回磁盘 OUTPUT,再
将Commit 记录写入日志
Redo 型日志是从第一个检查点开始恢复,按日
志记录正序处理,直至日志记录的尾部结束。
Undo 型日志用于解决“当发生系统故障时,未提
交事务已提前写入磁盘的问题“
Redo 型日志用于解决“当发生系统故障时,已提
交事务的数据滞留内存未被写入磁盘的问题”
Redo 型日志是先将 Commit 记录写入日志,
再将数据写回磁盘OUTPUT
Undo/Redo 结合型日志则可以不限制它们的次
序
可以保证事务的持久性,不需恢复
但读写效率最低
会出现当发生系统故障时,已经提交事务却并未
写入磁盘等问题
需要 Redo 型日志,以便重做事务保证持久性
数据必须在 Commit 后才可见,灵活性差
会出现当发生系统故障时,未提交事务提早写入
磁盘等问题
可能频繁地写磁盘,性能下降
需要 Undo 型日志,以便撤销事务保证持久性
会出现已经提交事务却并未写入磁盘等问题,也
会出现未提交事务提早写入磁盘等问题
需要 Undo/Redo 结合型日志既执行已完成事务
的重做,又执行未完成事务的撤销,才能保证持
久性
但读写效率最高
事务的地位
异同点
相同 事务在启动时刻被赋予唯一的时间戳,以示其启动顺序
不同
时间戳
为每一数据库元素保存读时间戳和写时间戳
在事务读写数据时判断是否存在冲突来强制事务
以可串行化的方式执行
有效性
为每一活跃事务保存其读写数据的集合
多个事务的读写集合,判断是否有冲突(存在事实
上不可实现的行为),即有效性确认,来完成事务
的提交与回滚,强制事务以可串行化的方式执行
可串行化一定是正确的