数据库系统原理与实践 笔记 #12

事务管理和并发控制与恢复(续)

并发控制

• 数据库必须提供一种机制来保证所有调度(目标)是：
  • 冲突可串行化
  • 可恢复性，最好是无级联
• 一个策略是一个时间只允许一个事务，即产生一个串行调度，但是并发性能差
• 目标：建立一个能够保证串行化的并发控制协议

SQL-92中的并发级别

• 可串行化(serializable)—通常保证可串行化的执行
• 可重复读(repeatable read)—只允许读取已提交数据，一个事务对相同数据的重复读取要返回相同的值(其他事务不得更改该数据)
• 已提交读(read committed)—（默认）只允许读取已提交的数据，但不要求可重复读
• 未提交读(read uncommitted)—允许读取未提交数据
• 以上所有隔离性级别都不允许脏写：即如果一个数据项已经被另外一个尚未提交或中止的事务写入，则不允许对该数据项执行写操作
• 通过命令显式设置隔离性级别：

set transaction isolation level serializable

基于锁的协议

• 锁是用来控制对数据项的并发访问的一种机制
• 给数据加锁有两种方式：
  • 排他锁(X)：对数据项即可写又可读，使用lock-X指令
  • 共享锁(S)：对数据项只能读，使用lock-S指令
• unlock指令释放锁
• 申请锁请求发送给并发控制管理器，只有在并发控制管理器授予所需锁之后，事务才能继续其操作
• 锁相容性矩阵
    表示为comp(A, B)

	S	X
S	true	false
X	false	false

• 指令之间的冲突对应于锁类型之间的不相容性

• 如果被请求所与数据项上已有的锁相容，那么事务可以被授予该锁：

  • 一个数据项可以同时有多个共享锁
  • 如果一个事务在某个数据项上拥有排他锁，那么其他事物不能再在这个数据项上加任何锁

• 如果一个锁不能被授予，那么请求该锁的事务必须等待，直到该数据项上的其他不相容锁全部释放，然后再授予锁

• 事务执行锁的例子：
  $$\begin{gathered} T_2:lock-S(A); \\ read(A); \\ unlock(A); \\ lock-S(B); \\ read(B); \\ unlock(B); \\ display(A+B); \end{gathered}$$

• 上述锁无法有效地保证可串行化—如果A在read B的时候被其他事务更新了，那么最后的和将会是错误的答案

• 需指定合理的封锁协议：一组规定事务何时对数据项进行加锁、解锁的规则。封锁协议限制了可能的调度数目

基于锁的协议的隐患

• 考虑下面的调度：
  

• $T_3$和$T_4$都无法被处理—排他锁lock-S(B)导致$T_4$等待$T_3$释放其在B上的锁，而排他锁lock-X(A)导致$T_3$等待$T_4$释放其在A上的锁

• 这样的情况称为死锁(deadlock)：要处理$T_3$或$T_4$其中一个死锁，必须回滚并释放锁

• 大多数封锁协议都会产生死锁

• 如果并发控制管理器设计得差也有可能导致饿死(starved)

• 并发控制协议可以通过良好的设计，能够避免事务饿死

锁的授予

• 避免事务饿死的授权加锁方式：当事务$T_i$申请对数据项Q加M型锁时，并发控制管理器授权加锁的条件需满足：
  • 1.不存在在数据项Q上持有与M型锁冲突的锁的其他事务
  • 2.不存在等待对数据项Q加锁且**先于$T_i$申请加锁的事务
• 这样，一个加锁申请就不会被其后的加锁申请阻塞

封锁协议

• 令 { T 0 , T 1 , . . . , T n } \{T_0, T_1, ..., T_n\} {T0​,T1​,...,Tn​}是参与调度S的一个事务集，如果存在数据项Q，使得$T_i$在Q上持有A型锁。后来，$T_j$在Q上持有B型锁，且comp(A,B)=false，则我们称$T_i$先于$T_j$，记为$T_i\to T_j$
  • 如果$T_i\to T_j$，这一优先意味着在任何等价的串行调度中，$T_i$必须出现在$T_j$之前
• 如果调度S是那些遵从封锁协议规则的事务集的可能调度之一，我们称调度S在规定的封锁协议下是合法的
• 一个封锁协议当且仅当其所有合法的调度为冲突可串行化时，我们称它保证冲突可串行性
• 换句话说，对于任何合法的调度，其关联的事务优先关系是无循环的

两阶段封锁协议

• 这是一个能够保证冲突可串行化调度的协议
• 阶段1：增长阶段
  • 事务可以获得锁
  • 事务不能释放锁
• 阶段2：缩减阶段
  • 事务可以释放锁
  • 事务不能获得新锁
• 封锁点：在调度中该事务获得其最后加锁的位置（增长阶段结束点）
• 两阶段封锁协议保证可串行化：可以证明事务可以按照封锁点来排序（一种可串行化次序）
• 两阶段封锁不能保证不发生死锁
• 两阶段封锁下很有可能发生级联回滚
  • 为了避免这个问题，将该协议修改为严格两阶段封锁协议
• 严格两阶段封锁协议要求未提交事务所写的热河数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据
• 强两阶段封锁协议更加严格：要求是提交之前不得释放任何锁（在这个协议下，事务可以按其提交顺序串行化

多粒度

• 将多个数据聚成一组，作为同步单元，无需单独对单个数据项进行加锁
• 多粒度：允许各种大小的数据项，并定义数据粒度的层次结构，可以图形化的表示为树
• 如果一个事务显式地对树中的某个节点加了锁，那么它也给所有统一模式下的该节点的子节点隐式地加了锁
• 锁的力度：
  • 细粒度（树的低层）：高并发性，锁开销多
  • 粗粒度（树的高层）：低并发性，锁开销少

粒度层次的例子

• 如事务$T_i$需判定某个节点（如$r_{b_1}$）是否可以加锁，必须从根结点进行遍历至该节点（开销大）

意向锁类型

• 除了排他锁及共享锁类型，多粒度下还有其他三种锁类型：
  • 共享型意向锁(IS)：将在树的较低层进行显式封锁，但只能加共享锁
  • 排他型意向锁(IX)：将在树的较低层进行显式封锁，可以加排他锁或共享锁
  • 共享排他型意向锁(SIX)：以该节点为根的子树显式地加了共享锁，并且在树的更底层显式地加排他锁
• 意义：意向锁允许较高层的节点被加上共享锁或排他锁，而无需从树根遍历到子孙节点来检验锁的相容性，提升锁相容检验的效率

相容性矩阵

• 所有所类型的相容性矩阵
  

多粒度封锁模式

• 事务$T_i$按如下规则对数据项Q加锁：
  • 1.必须遵从锁类型相容函数
  • 2.必须首先是封锁树的根节点，并且可以加任意类型的锁
  • 3.仅当事务$T_i$当前对Q的父节点具有IX或IS时，对结点Q可加S或IS锁
  • 4.仅当事务$T_i$当前对Q的父节点具有IX时，对节点Q可加X、SIX或IX锁
  • 5.仅当$T_i$未曾对任何节点解锁时，$T_i$可对节点加锁(满足两阶段封锁)
  • 6.仅当$T_i$当前不持有Q的子节点的锁时，$T_i$可对节点Q解锁
• 加锁按自顶向下的顺序，锁的释放按自底向上的顺序

基于时间戳的协议

• 对于系统中每个事务$T_i$，我们把一个唯一的固定时间戳和它联系起来，此时间戳记为$TS(T_i)$；该时间戳是在事务$T_i$开始执行前由数据库系统赋予的。若事务$T_i$已被赋予时间戳$TS(T_i)$，并且有一新事务$T_j$进入系统，则$TS(T_i)<TS(T_j)$
• 事务的时间戳决定了串行化顺序
• 每个数据项Q需要与两个时间戳值相关联：
  • W-timestamp(Q)表示成功执行write(Q) 的所有事务的最大时间戳
  • R-timestamp(Q)表示成功执行read(Q) 的所有事务的最大时间戳
• 时间戳排序协议保证任何有冲突的read或write操作按照时间戳顺序执行
• 假设事务$T_i$发出指令read(Q)：
  • 1.若$TS(T_i)$ < W-timestamp(Q)，则$T_i$需要读入的Q值已被覆盖：read操作被拒绝，$T_i$回滚
  • 2.若$TS(T_i)\ge$W-timestamp(Q)：执行read操作，R-timestamp(Q)被设置为max(R-timestamp(Q), $TS(T_i)$)
• 假设事务$T_i$发出指令write(Q)：
  • 1.若$TS(T_i)$ < R-timestamp(Q)，则$T_i$所需更新Q的值已过时：write操作被拒绝，$T_i$回滚
  • 2.若$TS(T_i)$ <W-timestamp(Q)，则$T_i$试图写入的Q值已过时：write操作被拒绝，$T_i$被饿死
  • 3.其他情况：执行write操作，将W-timestamp(Q)设置为$TS(T_i)$

基于时间戳协议的正确性

• 时间戳排序协议保证冲突可串行化：冲突操作按时间戳的顺序来处理
• 保证无死锁：不存在等待，可能有长事务饿死
• 可能产生不可恢复的调度：事务可恢复性与事务提交顺序有关

基于有效性检查的协议

• 有效性检查协议（适用于大部分只读事务的情况） 要求每个事务$T_i$在其生命周期中按两个或三个阶段执行：
  • 1.读阶段：事务$T_i$的所有write操作都是对局部临时变量进行的
  • 2.有效性检查阶段：事务$T_i$进行有效性检查，判断是否可以write操作而不违反可串行性
  • 3.写阶段：如果$T_i$已通过有效性检查，则保存任何写操作结果的临时局部变量值被复制到数据库中。只读事务不进入此阶段
• 每个事务必须按照以上顺序经历这些过程。然而，并发执行的事务三个阶段可以是交叉执行的
• 每个事务$T_i$都有三个不同的时间戳：
  • Start($T_i$)：事务$T_i$开始执行的时间
  • Validation($T_i$)：事务$T_i$完成读阶段
• 利用时间戳Validation($T_i$)的值，通过时间戳排序技术决定可串行化顺序，以增加并发性：即$TS(T_i)=Validation(T_i)$

事务Ti的有效性检测

• 对于任何满足$TS(T_k)<TS(T_i)$的事务$T_k$必须满足下面两条件之一：
  • $Finish(T_k)<Start(T_i)$
  • $Start(T_i)<Finish(T_k)<Validation(T_i)$，并且需保证$T_k$锁写的数据项集与$T_i$所读数据项集不想交；即$T_k$的写操作不会影响到$T_i$的读操作
• 则有效性检测通过，$T_i$可以进入写阶段并提交，否则测试失败$T_i$中止
• 有效性检查协议能够自顶预防级联回滚，保证无死锁

恢复系统

故障分类

• 事务故障：
  • 逻辑错误：由于某些内部条件而无法继续正常执行
  • 系统错误：系统进入一种不良状态（如死锁），结果事务无法继续正常执行
• 系统崩溃：硬件故障，或者是数据库软件或操作系统的漏洞，导致易失性存储器内容丢失，并使得事务处理停止
• 磁盘故障：由于磁头损坏或故障造成磁盘块上的内容丢失：
  • 毁坏是可探测的：磁盘驱动器用校验和来检测故障

恢复机制

• 保证数据库一致性以及事务的原子性的算法称为回复算法：
  • 在正常事务处理时采取措施，保证有足够的信息可用于故障恢复
  • 故障发生后采取措施，将数据库内容恢复到某个保证数据库一致性、事件原子性及持久性的状态
• 存储器类型：
  • 易失性存储器(volatile storage)：易失性存储器中的信息在系统崩溃时通常无法保存下来
  • 非易失性存储器(nonvolatile storage)：非易失性存储器中的信息在系统崩溃时可以保存下来
  • 稳定存储器(stable storage)：稳定存储器中的信息永不丢失

数据访问

• 物理块是位于磁盘上的块

• 缓冲块是临时位于主存的块

• 磁盘和主存间的块移动是由下面两个操作引发的：**input(B)**传送物理块B到主存，**output(B)**传送缓冲块B至硬盘，并替换磁盘上相应的物理块

• 例子
  

• 每个事务$T_i$有一个私有工作区，用于保存$T_i$所访问及更新的所有数据项的拷贝：$T_i$的工作区中保存的每一个数据项X记为$x_i$

• 使用下面两个操作里完成数据在工作区和系统缓冲区之间的传递：

  • read(X) 将数据项X的值赋予局部变量$x_i$
  • write(X) 将局部变量$x_i$的值赋予缓冲块中的数据项X
  • 注意: output($B_x$) 不需要立刻在write(X)后执行。系统会在它认为合适的时候执行output操作

• 事务：必须在第一次访问X之前执行read(X)；**write(X)**可以在事务被提交前的任意时刻执行

恢复和原子性

• 为保证原子性，我们必须在修改数据库本身之前，首先向稳定存储器输出信息，描述要做的修改
• 目的：确保由中止事务所做的修改不会持久保存与数据库中，即回滚该中止事务
• 基于日志的恢复系统

基于日志的恢复机制

• 日志保存于稳定存储器中：日志是日志记录的序列它记录数据库中的所有更新活动
• 当一个事务$T_i$开始时，它记录$<T_{i}start>$
• 事务$T_i$执行write(X) 前，日志记录：$<T_{i}X,V_1,V_2>$，$V_1$是在write之前X的值(旧值)，$V_2$是需要写入X的值(新值)
• 当$T_i$结束了最后一条指令时，$<T_{i}commit>$写入日志
• 当事$T_i$中止时，日志记录$<T_{i}abort>$
• 使用日志的两种方法：延迟的数据库修改（事务提交后还未修改），立即的数据库修改（事务提交前已修改）

数据库修改

• 立即修改模式允许在事务提交前，将未提交的事务更新至缓冲区或磁盘
• 延迟修改模式直到事务提交时都没有更新到缓冲区/磁盘：简化了恢复，但是多了存储本地副本的开销
• 日志记录的更新必须在数据项被write(数据库修改)之前完成

事务提交

• 当事务将其关于提交的日志记录输出到稳定存储器时，该事务被认为已提交：之前的所有日志记录必须都已经输出
• 事务提交时，由该事务执行的write操作结果可能仍在缓冲区，随后被输出

并发控制和恢复

• 在并发事务中，所有事务共享一个磁盘缓冲区和日志：一个缓冲块中的数据项可以来自多个事务的更新
• 假设如果一个事务$T_i$习概了一个数据项，那么在$T_i$提交前，其他事务不能修改同一个数据项(即不允许脏写)：
  • 未提交事务的更新不能被其他事务所见
  • 可以通过在被更新数据项上获取排他锁，并持有该锁直到事务提交位置来保证（严格两阶段封锁）
• 不同事务的日志记录在日志中穿插(interspersed)存储

Undo和Redo操作

• 对日志记录$<T_i,X,V_i,V_2>$的Undo操作将旧值$V_1$写入X
• 对日志记录$<T_i,X,V_1,V_2>$的Redo操作将新值$V_2$写入X

事务的Undo和Redo

• undo($T_i$) 将事务$T_i$所更新的所有数据项的值恢复成旧值，回到$T_i$的最后一条日志记录：
  • 每次数据项X被恢复成旧值，日志记录$<T_i,X,V>$会被写入
  • 当事务的undo操作完成时，日志记录$<T_{i}abort>$被写入
• redo($T_i$) 将事务$T_i$所更新的所有数据项的值置为新值，从$T_i$的第一条日志记录开始执行（这个情况下没有任何日志记录）

从故障中恢复的Undo和Redo

从故障中恢复时

• 当日志是以下状态时，事务$T_i$需要undo操作：
  • 有日志$<T_{i}start>$
  • 没有日志$<T_{i}commit>$和$<T_{i}abort>$
• 当日志是以下状态时，事务$T_i$需要进行redo操作：
  • 有日志$<T_{i}start>$
  • 有日志$<T_{i}commit>$或$<T_{i}abort>$
• 如果事务$T_i$之前执行了undo操作，$<T_{i}abort>$被写入到日志，接着故障发生。为了从故障中恢复，$T_i$要执行redo操作
• 这样的redo操作重新执行了原先的所有操作，包括重新存储旧值：称为重复历史，看起来很浪费，但是最大程度地简化了恢复

检查点

• 对于日志中的所有事务做Redo/Undo
  • 1.如果系统已经运行了很长一段时间，那么处理整个日志很浪费时间
  • 2.那些已经将输出更新到数据库的事务没必要redo
• 流线型恢复过程周期性地执行检查点：
  • 1.将当前位于主存的所有日志记录输出到稳定存储器上
  • 2.将所有修改了的缓冲块输出到磁盘上
  • 3.将一个日志记录$<checkpointL>$输出到稳定存储器
  • 执行检查点时，所有数据更新都停止
• 恢复时，我们仅考虑在检查点前最近开始的事务$T_i$，及在$T_i$后开始的事务：
  • 从日志末尾反向扫描，找到最近的$<checkpointL>$记录
  • 只要在L未提交/中止的事务或者在检查点后开始的事务需要redo或undo
  • 检查点之前的已提交或者中止的事务已经将其更新输出到了稳定存储器
• undo操作可能需要一些早期的日志
  • 继续从日志末尾反向扫描直到找到在L的每个事务$T_i$的记录$<T_{i}start>$