数据库概论

事务管理、并发控制与故障恢复

2020-01-01 00:13 CST
2020-01-01 00:13 CST
CC BY-NC 4.0

事务管理、并发与故障处理

5.1 事务处理(概念)

  • 事务的定义与ACID性质

  • 事务活动及其状态转换图

  • 事务控制及相关的参数设置语句:事务的提交与回滚,事务的读/写类型与隔离级别

  • 事务的语句组成成分

    5.2 并发控制技术(概念)

  • 事务

    • 事务的并发性,并发控制
    • 调度,串行调度,可串行化调度,冲突与冲突可串行化,视图可串行化
    • 冲突可串行化的判定方法
    • 不正确的事务并发所导致的数据不一致现象:丢失修改lost-update,脏读dirty-read,不可重复读unrepeatable-read
  • 封锁

    • 共享锁(S锁),排它锁(X锁),锁相容矩阵,锁申请/锁释放算法
    • 基于封锁技术的并发控制实现方法
      • 三级封锁协议,三级封锁协议与数据不一致现象之间的关系
      • 两阶段封锁协议
      • 两阶段封锁协议与冲突可串行化的关系
  • 多粒度封锁

    • 封锁粒度/并发度/并发控制实现开销 之间的关系
    • 多粒度树,多粒度封锁
    • 基于意向锁的多粒度封锁协议
      • 意向锁:IS, IX, SIX
      • 意向锁锁相容矩阵:S,X,IS, IX, SIX
      • 意向锁锁申请算法,意向锁锁释放算法
  • 死锁的检测与预防

    • 死锁 & 活锁
    • 死锁的检测及其处理办法
      • 等待图法

      • 超时死锁检测法:锁申请等待超时 & 事务执行超时

      • 时间戳死锁检测法

        5.3 数据库恢复技术

  • 数据库恢复的含义、方法和常用措施

  • 数据库故障的分类

  • 数据库故障恢复三大技术:数据转储,日志,数据库镜像

  • 数据转储:静态转储/动态转储,海量转储/增量转储,

  • 日志:

    • 日志的内容、组成、作用与记载原则
    • 在日志中设置检查点的作用
    • 事务的撤销(UNDO)与重做(REDO)
    • UNDO日志
      • UNDO日志的内容,记载规则,作用
      • 基于UNDO日志的故障恢复流程
    • REDO日志
      • REDO日志的内容,记载规则,作用
      • 基于REDO日志的故障恢复流程
    • UNDO/REDO日志
      • UNDO/REDO日志的内容,记载规则,作用
      • 基于UNDO/REDO日志的故障恢复流程
    • UNDO日志、REDO日志、UNDO/REDO日志的优点与缺点
  • 恢复策略:小型/中型/大型故障的恢复策略

事务处理

事务:访问并可能更新数据库上数据的一个程序执行单元(unit)

在关系数据库系统中,一个事物是由一条SQL语句或者一组SQL语句所构成的一个执行过程,并具有ACID四个特性

事务是恢复和并发控制的基本单位

事务:某个用户执行的一个不能被打断的对数据库的操作序列

四条ACID性质:

  • 原子性Atomicity:一个事务中的操作要么全部执行结束,要么一个都不执行。数据库管理系统会通过事务管理子系统、事务日志自动维护原子性
  • 一致性Consistency:一个事务的成功执行总是将数据库从一个一致的状态转移到另一个一致的状态,包括了数据库中显式定义的各种完整性约束与用户心目中的隐式数据约束,可以通过DBMS的数据完整性保护子系统和编写事务的应用程序员两方面进行保护
  • 隔离性 Isolation:一个事务的执行与并发执行的其他事务独立,互不干扰,由并发控制子系统实现
  • 持久性 Durability:一个事务完成操作后,对数据库的更新永久反映在数据库中,即使以后故障也能通过故障恢复保留结果,由DBMS的恢复管理子系统实现

事务活动的流程

活动状态:事务开始执行后,进入活动状态,事务将执行数据库的访问操作,对于读操作,将数据读入用户的私有工作区间,如果该数据当前不存在DBMS系统缓冲区,那么DBMS首先将该数据从磁盘读入系统缓冲区,再将其拷贝到用户事务的私有工作区。对于写操作,可能并不是立即将数据永久写入磁盘,可能会暂时存放在DBMS系统缓冲区。

预提交状态:事务最后一个访问语句执行结束后,事务进入预提交状态,此时写操作的结果可能还在缓冲区内,要确保当前事务的所有修改操作都真正被写入数据库的磁盘中,当所有写磁盘操作执行结束后,进入提交状态,否则如果执行过程中发生故障导致执行失败猫就进入失败状态

失败(abort)状态:事务执行完最后一条语句前中断或者预提交失败都会进入失败状态,原因可能是用户或应用程序主动放弃,因为并发控制被放弃(如封锁申请超时等待、死锁)或者发生系统故障

异常中止(aborted)状态:对于失败状态事务,可能已经进行了一部分修改,为保证原子性,需要撤销已经进行的修改(回退rollback,由DBMS的恢复子系统实现),进入异常中止状态,此时系统可以取消事务,也可以作为一个新的事务重新启动。

提交状态:进入预提交后,并发控制子系统检查是否发生干扰,检查通过后执行提交操作,执行后进入提交状态

有关事务的语句

主要有三条语句:

  • 事务的开始(begin transaction): 事务的启动是隐式的,可以通过三种方式启动一个新的事务:数据定义命令DDL(每一条数据定义命令作为一个单独事务执行,在此之前当前用户事务自动提交),将系统设置为自动提交方式即打开自动提交标志(每一条数据库访问指令都将作为一个单独的事务执行并根据执行结果自动提交或者回退),数据操纵命令DML(前一个事务执行结束后,下一个数据访问操作执行之前,自动为用户启动一个新的事务)。
  • 提交事务(commit transaction):提交可能因为系统故障或者数据完整性检查而导致失败,事务提交失败后可以通过回退来取消当前事务,系统自动提交的事务将会自动进行回退操作
  • 回退事务(rollback transaction):取消事务执行过程中的所有操作,回滚至起点,在事务执行过程中,用户可以设置若干保存点(savepoint),用户事务可以使用rollback回滚到某一个保存点并继续执行当前事务,不带保存点的回退将结束并放弃整个事务

设置事务的自动提交: SET AUTOCOMMIT ON|OFF

设置事务的类型(只读型事务与读/写型事务,缺省定义为读/写型事务): SET TANSACTION READONLY | READWRITE

设置事务的隔离级别:

SET  TRANSACTION  ISOLATION  LEVEL
    READUNCOMMITTED
  | READCOMMITTED
  | READREPEATABLE 
  | SERIALIZABLE

设置了不同的隔离级别,系统所采取的封锁策略也不同

  • 未提交读:不申请封锁,可能读到未提交结果,禁止以此方式执行写操作
  • 提交读:读数据A前申请对A的共享性封锁,读结束后立即释放该封锁
  • 可重复读:读数据A前申请对A的共享性封锁并将封锁维持到事务结束
  • 可序列化(可串行化):以一种可串行化的调度策略实现并并发执行,以避免干扰现象

但是不管设置了何种隔离级别,在写数据对象A的时候,会申请对A的排他性封锁并维持到事务结束

事务的组成

数据对象:

  • 数据对象的大小:可以是一个属性值/元组/表/整个数据库,我们不严格区分只是称为数据对象A
  • 数据对象的地址空间:存在三种有关的地中空间概念(保存数据的磁盘空间、内润缓冲区、事务的局部地址空间即内存变量)

一个事务有关的操作分为两类:

  • 事务控制操作(其中T0为事务标识符,每启动一个事务,DBMS自动分配一个唯一的事务标识符)
    • 事务的开始:START T0
    • 提交事务:COMMIT T0
    • 回退(放弃事务): ABORT T0
  • 数据访问操作:
    • INPUT(A):将数据A从磁盘读入内存缓冲区
    • OUTPUT(A):将数据A从内存缓冲区写入磁盘
    • READ(A,t):将内存缓冲区的数据对象A的值读入内存变量t(可能包含INPUT操作)
    • WRITE(A,t) :将内存变量的值写入对象A

并发控制技术

事务的并发执行

并发控制技术:实现多个用户事务的并发执行

并发执行的可串行化: 一组事务并发执行的结果等价于他们之间的某种串行执行的结果,称为可串行化调度

并发控制的目标就是要实现并发事务的可串行化调度

各个事务的数据库访问操作在DBMS中的实际执行序列构成了事务之间的一个调度,一组事务的调度必须包括所有操作包括一个事务的结束命令,且保证单个事务内部执行顺序不变

值得注意的是,不同事务的访问请求在DBMS内部的执行顺序可能与到达顺序不一样,但是同一个事务内部的操作顺序一定与到达顺序一致

串行调度:首先是一个事务的所有操作,然后是另一个事务的所有操作,依次类推,称调度是串行的

我们用符号 $T\_1,T\_2..$ 标识事务,用$r\_i(X)$标识事务$T\_i$读数据库对象X,类似的有$w\_i(x)$

冲突:调度中的一对相邻操作(op1,op2)如果交换他们的顺序,那么涉及的事务中至少有一个的行为会改变,那么称这对相邻操作为冲突

冲突包括:同一个事务的任意两个相邻操作,对于不同事务的两个相邻操作中涉及同一对象且至少有一个为写操作

如果对于初始给定的一个调度,可以通过一组非冲突化操作变成一个串行调度,那么认为最初的调度是一个可串行化调度且称为冲突可串行化调度

注意:冲突可串行化调度一定是一个可串行化调度,但是可串行化调度不一定是一个冲突可串行化的

如果两个事务$T\_1,T\_2$分别存在动作$A\_1,A\_2$,在调度H中,$A\_1$在$A\_2$之前执行,如果两个动作涉及同一个数据对象并且至少有一个为写动作,那么称$T\_1$优先于$T\_2$,记为$T\_1 <\_S T\_2$,上述情况下,A1与A2不能交换,在H的冲突等价串行调度中,T1必在T2之前

判断是否冲突可串行化:如果$T\_i <\_S T\_j$,那么从i到j引一条有向边,如此寻找所有冲突对(可以根据所有被访问的数据对象来发现冲突对)构造优先图,如果事务优先图中无环,则为冲突可串行化调度,否则不是。

利用优先图,如果一个点不存在指向该节点的有向边,就先执行这个节点对应的事务,再考虑其他节点的优先图。

三种可串行化调度:视图可串行化是可串行化调度的子集,冲突可串行化是视图可串行化的子集

视图可串行化调度指的是视图等价为一个串行调度,S与H视图等价当且仅当满足以下三个条件:对每一个数据项D

  • 如果在调度S中事务Tk读到D的初始值,则在调度H中事务Tk也必须读到D的初始值;
  • 如果在调度S中事务Tk执行了$r\_k(D)$,并且读到的是由事务Tj写入的D的值,则在调度H中事务Tk的$r\_k(D)$读到的也必须是由事务Tj 所写入的D的值;
  • 如果在调度S中是由事务Tk来执行最后一条关于D的写操作$w\_k(D)$,则在调度H中也一定是事务Tk执行最后一条关于D的写操作$w\_k(D)$。

视图可串行化调度不一定是冲突可串行化调度的原因在于:可能存在盲写现象(一个事务没有读取数据项D的值并直接用write操作修改D的值)

数据不一致现象:

  • 丢失修改(lost-update):一个事务的修改破坏了另一个事务的修改结果,原因在于对多个并发修改同一个值没有限制
  • 脏读(dirty-read):一个事务读到了另一个事务未提交的结果
  • 不可重复读(unrepeatable-read):在两次读操作之间差入了另一个事务的写操作

封锁

封锁一段事件内禁止其他事务执行某些操作同时也表明持有该封锁的事务在被封锁的数据对象上执行什么样的操作

排他锁:X锁:只有在数据A上没有任何封锁的时候能申请,如果一个事务申请了X锁,那么其他事务都不能获得A上的任何类型的封锁,获得X锁后可以进行读、写操作,其他事务禁止访问,降低了并行性,但是保证了正确性与一致性,X锁必须维持到事务结束

共享锁:S锁: 如果数据A没有被封锁或者是以S锁的形式封锁时,可以申请S锁,事务T可以读,但是不可以写,S锁不一定要维持到事务结束

合适事务:一个事务访问前按照要求申请封锁,操作结束后释放封锁,这种事务称为合适事务

合适事务时保证并发事件正确执行的基本条件

封锁管理器的数据结构:数组LOCK(A)记录数据对象A上的封锁状态,分别是Read\_locked(共享锁)、Write\_locked(排他锁)、Unlocked(无封锁),数组no\_of\_reads(A)记录A上的共享锁的个数。

基于封锁技术的并发控制实现方法:

  • 在DBMS的封锁管理器上维护一张锁表,包括了封锁的持有情况(哪些事务在哪些数据对象上持有什么锁)与封锁的申请等待情况(有哪些事务正在等待哪些数据对象上的什么类型的封锁)
  • DBMS对于请求op(A),将访问操作发送给并发控制子系统的调度器。调度器根据系统的封锁协议来决定是否需要为该操作申请封锁以及申请何种类型的封锁,并将封锁请求发送给封锁管理器,封锁管理器根据锁表的情况决定能够立即满足,并将结果返回给调度器,如果得不到满足,则调度器将访问操作放入被推迟的访问操作序列,否则将该操作发送给系统的执行引擎去执行。

封锁协议

封锁协议规定了何时申请封锁,申请何种类型封锁,何时释放封锁

最常见的有三级封锁协议两阶段封锁协议

三级封锁协议:以单条数据访问操作为单位,定义了锁的申请和释放要求,根据具体要求不同,可以将其分为一级封锁协议、二级封锁协议、三级封锁协议三种级别不同的封锁协议

  • 一级封锁协议(可以预防丢失修改):写对象A之前必须先申请A上的X锁并维持到事务T的结束才释放
  • 二级封锁协议(可以预防丢失修改、脏读):满足一级封锁,在读对象A之前必须先申请A上的S锁并在操作完成后即可以释放S锁(此处未规定释放时间)
  • 三级封锁协议(可以预防丢失修改、脏读、不可重复读):满足一级封锁,事务在读对象A之前,必须先获得A上的S锁,并保持到事务结束后才释放

两阶段封锁协议(2PL协议):以事务为单位规定封锁的使用规则

  • 第一阶段:申请并获得锁,在此阶段可以申请整个执行过程中需要的锁,但是不能释放,锁的数量不断上升,可以称为扩展阶段
  • 第二阶段:释放所有的锁,包括释放被挂起的锁申请请求,称为收缩阶段

在两阶段封锁协议中,如果$T\_i$已经持有A上的S锁,当处理$xl\_i(A)$请求时,会直接将S锁改为X锁

2PL事务产生的任意合法调度都是冲突可串行化的

封锁粒度

封锁粒度:一把锁可以封锁的数据对象的大小,可以时数据库中的逻辑数据单元(属性值、元组、关系、索引、整个数据库),也可以是物理数据单元(页、块)

封锁粒度大,则系统并发性低,并发控制开销小。封锁粒度小,则并发性高,对应的并发控制开销大

如果在一个系统中同时支持多种封锁粒度供事务选择使用,这种方法称为多粒度封锁

可以根据封锁粒度的大小构造一棵多粒度树,以每个节点作为封锁对象,构成一个多粒度封锁协议(显式封锁是可以对每个节点独立加锁,隐式封锁是该节点的所有后裔也被加以同类型的锁)

意向锁:如果对一个节点加意向锁,说明该节点的下层节点正在被加锁,对任一节点加锁前必须先对他的上层节点加意向锁

常见的意向锁:

  • 意向共享锁(IS锁):后裔准备加S锁
  • 意向排他锁(IX锁):后裔准备加X锁
  • 共享意向排他锁(SIX锁):后裔准备加X锁且自身加S锁

相容表 |准备申请的\目前有的|S|X|IS|IX|SIX| |:--|--|--|--|--|--| |S|YES|NO|YES|NO|NO| |X|NO|NO|NO|NO|NO| |IS|YES|NO|YES|YES|YES| |IX|NO|NO|YES|YES|NO| |SIX|NO|NO|YES|NO|NO|

申请封锁的顺序:从上至下

释放封锁的顺序:由底而上

死锁与活锁

死锁:每个事务拥有一部分锁,同时申请其他事务的锁而等待,由此形成的循环

处理办法:

  • 预防法:顺序申请法;一次申请法
  • 解除法:
    • 超时死锁检测法:事务执行时间超时;锁申请等待时间超时
    • 等待图法
    • 时间戳死锁检测法:每个事务有一个用于死锁检测的时间戳,时间戳反映事务的新老程度,如果事务T必须等待另一个事务U持有的锁,有两种策略:
      • 等待-死亡方案:如果T比U老,那么允许T等待U持有的锁;如果U比T老,那么事务T死亡(被回滚);
      • 伤害-等待方案:如果T比U老,他将伤害U,U必须被回滚;如果U比T老,那么T等待U持有的锁

活锁:有部分事务因为封锁得不到满足长期处于等待状态,而其他事务仍可以继续进行;解决方式:先来先解决

数据库恢复技术

数据库恢复:在暑假库遭受破坏后及时进行恢复的功能

方法:利用数据冗余原理,将数据库中的数据在不同存储介质上进行冗余存储,在本身遭到破坏时利用冗余信息进行恢复

常用措施:数据转储、日志、数据库镜像

故障分类

小型故障:事务内部故障

中型故障:系统故障;外部影响(可能导致整个系统停止工作,但是磁盘数据不受影响,系统重启时可以根据日志进行恢复)

大型故障:磁盘故障;计算机病毒;黑客入侵;(可能导致内存及磁盘数据的严重破坏,需要对数据库做彻底的恢复)

转储

数据转储:定期的将数据库中的内容复制到其他存储设备中去的过程

转储可分为:静态转储/动态转储;海量转储/增量转储

转储过程得到的后备副本并不能保证数据库中数据的一致性,如果使用该副本进行故障恢复,需要解和当时记载的日志信息,日志中应该记载:

  • 转储的开始点与结束点
  • 转储执行过程中,事务的更新情况:&lt;事务标识,更新对象,更新前的值,更新后的值>
  • 转储执行过程中完成的事务的结束状态:Commit/Abort

日志

数据库系统创建并维护的,用于自动记载数据库中修改型操作的数据更新情况的文件

内容包括了每个更新操作的事务标识、更新对象、更新前的值 和/或 更新后的值;每个事务的开始、结束等情况;其他信息

日志是日志记录的一个序列,每个日志记录记载有关某个事物已执行操作的情况

作用:

  • 保证事务执行的原子性
  • 实现增量转储
  • 实现故障恢复
    • 为了修复故障产生的影响,某些事务操作将会被重做,而另一些事务的操作将会被撤销
    • 为了区分哪些事务重做,哪些事务撤销,日志中需要记载每个事务的结束标志:commit:将被重执,abort将被撤销
    • 日志中没有结束标志的事务在恢复时被当作被放弃的事务

先写日志,再修改数据库

undo日志

undo日志:用于被放弃事务的撤销工作

记录格式:

  • 开始一个事务:<START T>
  • 提交事务:<COMMIT T>
  • 放弃事务: <ABORT T>
  • 更新记录: <T,X,V>(事务T修改X,X的旧值是V)

记载规则:如果事务T修改了数据库元素X,则更新日志必须在新值写入磁盘前写到磁盘,如果事务T提交,则日志记录必须在事务T改变的所有元素已经写到磁盘后再写到磁盘

恢复过程:

  • 将事务区分为已提交事务与未提交事务(有无Commit)
  • 从日志尾向日志头部扫描,对每一条更新记录,如果已经扫描到\则继续扫描下一条,否则恢复为V
  • 在日志尾部未每一个未结束的事务T写入一条日志记录<ABORT T>并刷新日志(Flush Log)

检查点:为了降低数据库恢复的开销,定期在日志文件中加入检查点

加入检查点的处理过程:

  • 系统停止接受‘启动新事务的请求’
  • 等到所有当前活跃的事务被提交或中止,并且在日志中写入了\或\记录
  • 将日志记录刷新到磁盘
  • 写入日志记录\,并再次刷新日志
  • 重新开始接受新的事务

在故障恢复时,只要逆向扫描到第一条\记录(最后一个被记入的检查点)就可以结束故障恢复工作

非静止检查点:设置过程中,允许新的事务进入

  • 写入日志记录\,并刷新日志;其中:T1,…,Tk是当前所有活跃事务的标识符
  • 等待T1,…,Tk中的每一个事务的提交或中止,在这个过程中允许启动执行新的事务
  • 当T1,…,Tk都已经完成时,写入日志记录\并刷新日志

恢复时从日志尾部向前扫描,可能遇到两种情况

  • 先遇到\记录:继续向后扫描,直到出现与之相对应的\记录就可以结束故障恢复工作,在这之前的日志记录是没有用处的,可以被抛弃
  • 先遇到\记录,此种情况下的故障恢复工作需要撤消两类事务的操作:在\记录之后启动的事务(在扫描到\记录时,这类事务的操作已经被撤消);T1,…,Tk中在系统崩溃前尚未完成的事务(继续向后扫描日志,直至其中未完成事务的访问操作被全部撤消)

undo日志不足:事务改变的所有数据写到磁盘前不能提交事务,导致增加了很多写磁盘操作,增加了事务提交的时间开销

redo日志

格式与undo差不多,唯一的差别在于更新记录中V记载的时更新后的值

记载规则:在修改磁盘上的任何数据库元素X之前,要保证所有与X的这一修改有关的日志记录(包括更新记录\ 和提交记录 \)都必须出现在磁盘上。(这也就意味着从缓冲区写到磁盘上的数据在commit日志已经被写到了磁盘上之后)

恢复:

  • 确定所有已提交的事务(先扫描一遍日志文件)
  • 从日志文件的头部开始扫描日志,对遇到的每一条更新记录\:如果T是未提交事务,则继续扫描日志如果T是已提交的事务,则为数据库元素X写入新值V
  • 对每个未完成的事务T,在日志的尾部写入结束标志\并刷新日志

在redo日志中插入(非静止)检查点的步骤:

  • 写入日志记录\,并刷新日志;其中:T1,…,Tk是当前所有活跃事务的标识符,同时获得当时所有已提交事务的标识符集合S
  • 将集合S中的事务已经写到内存缓冲区但还没有写到数据库磁盘的数据库元素写入磁盘;
  • 写入日志记录\并刷新日志,不必等待事务T1,…,Tk或新开始事务的结束

恢复:找到最后一个被记入日志的\(记为记录t),假设与之相对应的检查点记录是\(记为记录t’),并找到最早出现的\(记为记录ti).故障恢复方法如下:针对事务T1,…,Tk以及在t’之后开始的那些事务,重做其中已经被提交的事务

不足:增加了平均缓冲区的数量

undo/redo日志

与之前基本一致,不过更新记录变为了\,其中v为之前值,w为修改后值

记载规则:由于某个事务T所作的改变而修改磁盘上的元素X之前,关于X的更新记录(\)必须先出现在磁盘上。每一条Commit日志记录后面必须紧跟一条Flush Log操作

此时,commit操作和写磁盘(output)操作顺序是随机的

恢复: 根据\是否已经出现在磁盘中来决定事务T是否已经被提交。按照从后往前的顺序,撤消(undo)所有未提交的事务,按照从前往后的顺序,重做(redo)所有已提交的事务

插入检查点:写入日志记录\,并刷新日志。其中:T1,…,Tk是当前所有活跃事务的标识符,将所有被修改过的缓冲区写到数据库的磁盘中去,写入日志记录\并刷新日志

恢复策略

小型故障:利用未结束事务的undo操作

中型故障:

  • 非正常中止:undo
  • 已完成提交,结果还在缓冲区中:redo

大型故障:先利用后备副本进行恢复,在利用日志进行数据库恢复(逆向搜未完成undo,正向搜完成redo)

数据库镜像

将整个数据库中数据或者主要数据实时复制到另一个磁盘中