​ 数据库系统7——并发控制&数据库恢复。

并发控制

事务概念

• 事务：用户定义的一个数据库操作序列，这些操作耀目全做，要么全不做，是一个不可分割的工作单位。
• 事务与程序不同
  • 在关系数据库中，一个事务可以是一条SQL语句，一组SQL语句或整个程序
  • 一个程序通常包含多个事务

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

• 事务的特性（ACID）

  • 原子性（Atomicity）：完全执行或者完全不执行
  • 一致性（Consistency）：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态
    • 一致性状态：数据库中只包含成功事务提交的结果
    • 不一致性状态：发生故障，有些事务被迫终端，而一部分修改已经写入物理数据库，此时数据库处于一种不正确的状态
  • 隔离性（Isolation）：表面看起来，每个事务都是在没有其他事务同时执行的情况下执行的
    • 一个事务内部的操作及使用的数据对其他并发事务是隔离的
    • 并发执行的各个事务之间不能相互干扰
  • 持久性（Durability）：一个事务一旦提交，它对数据库中数据的改变就应该是永久性的
    • 接下来执行的其他操作或故障不应该对其执行结果有任何影响
• 保证事务ACID特性是事务处理的任务

• 破坏ACID特性的因素：

  • 多个事务并行运行时，不同事务的操作交叉执行
  • 事务在运行过程中被强行停止

• 事务运用以下两个操作访问数据：

  • Read(X)：从数据库把数据项X传送到事务的局部缓冲区
  • Write(X)：从事务的局部缓冲区把数据项传回数据库

事务的并发执行和调度

调度：一个或多个事务的重要操作按时间排序的一个序列

• 串行调度

可串行化调度：不管数据库初始状态如何，一个调度对数据库状态的影响都和某个串行调度相同，则称这个调度时可串行化的

冲突：调度中一对连续的动作，满足，如果二者顺序调换，那么涉及的事务中至少有一个的行伪会改变

• 同一事务的两个动作冲突
• 不同事务对同一数据库元素的写冲突
• 不同事务对同一数据库元素的读和写冲突

冲突可串行化：

• 我们说两个调度是冲突等价的，如果通过一系列相邻动作的非冲突交换能将它们中的一个转换为另一个
• 如果说一个调度冲突等价于一个串行调度，那么我们说该调度是冲突可串行化的

优先关系：

• 已知调度S，其中涉及事务T1和T2，可能还有其他事务。我们说T1优先于T2，记作T1<T2，如果有T1的动作A1和T2的动作A2，满足：
  • 在S中A1在A2前；
  • A1和A2都涉及同一组数据库元素，且，A1和A2中至少有一个动作是写
• 因此，在任何冲突等价于S的调度中，A1将出现在A2前。所以，如果这些调度中有一个是串行调度，那么该调度必然使T1在T2前。

优先图

• Ti < Tj，有i到j的边

冲突可串行性判断

• 构造优先图，判断其中是否有环

并发控制协议

包括：基于锁的协议、基于时间戳的协议、多版本机制、快照隔离

基于锁的并发控制协议

• 锁的概念

  一个保证可串行性的方法使在互斥的方式下存取数据项，即，当一个事务存取一个数据项时，不允许其他事务修改这个数据项。（可以通过基于锁的并发控制协议实现）

  • 锁的两种类型：

    • 共享锁：获取后可读不可写
    • 互斥锁：获取后可读也可写

  • 每个事务在存取一个数据项之前必须获得这个数据项上的锁

  • 一个事务需要获得的锁的类型依赖于它将在数据项上执行什么样的操作

  • 相容关系：

    

• 事务通过执行LOCK-S(Q)操作申请数据项Q上的共享锁

• 事务通过执行LOCK-X(Q)操作申请数据项Q上的互斥锁

• UNLOCK(Q)操作用来释放数据项Q上的锁

• 一个事务完成了对一个数据项的最后一次存取后立刻放弃锁，可能无法确保调度的可串行性

  • 释放操作放到最后——可能死锁
  • 死锁时必须放弃至少一个处于死锁状态的事务以使其他事务可以继续运行

• 死锁、死锁的处理

  • 死锁预防：
    • 产生原因：两个或多个事务都已封锁了一些数据对象，然后又都请求对已经被其他食物封锁的数据对象加锁，从而出现死等待
    • 因此要破坏产生死锁的条件
    • 两个预防方法：
      • 一次封锁法
        • 要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行
        • 问题：降低系统并发、难于实现精确确定封锁对象
      • 顺序封锁法
        • 预先对数据对象规定一个封锁顺序，所有事务都按照这个顺序进行封锁
        • 问题：维护成本高、难以实现
  • 死锁的检测与恢复
    • 死锁的诊断：
      • 超时法：等待时间超过规定
        • 优点：实现简单
        • 缺点：可能误判或不及时发现
      • 事务等待图法：用等待图动态反应所有事务的等待情况
        • 有向图G=(T,U)
        • T为节点集合，每个节点表示正运行的事务
        • U为边的集合，每条边表示事务等待的情况
        • 若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2。
        • 并发控制子系统周期性地生成等待图，如果发现图中存在回路，则表示出现了死锁
    • 死锁的恢复
      • 选择牺牲者：必须决定回滚哪一个（哪一些）事务以打破死锁，使事务回滚代价最小
      • 回滚：彻底回滚、部分回滚
      • 饿死：总是同一事物被选为牺牲者
        • 需保证一个事务被选为牺牲者的次数有限

• 两段锁并发控制协议

  • 两段锁协议：要求每个事务分两个进行数据项加锁和解锁
    • 加锁阶段：事务申请可以获得任何数据项上的任何类型的锁，但是不能释放任何锁
    • 解锁阶段：事务申请可以释放任何数据项上的任何类型的锁，但是不能申请任何锁
  • 每个事务开始运行后即进入加锁阶段，申请获得所需要是所有锁
  • 当一个事务第一次释放锁时，该事务进入解锁阶段。进入解锁阶段的事务不能再申请任何锁
• 两段锁改进：
  • 用UPGRADE表示共享锁到互斥锁转换的操作，用DOWNGRADE表示互斥锁到共享锁的转换操作。
    • UPGRADE只能在加锁阶段使用，DOWNGRADE只能在解锁阶段使用
  • 当事务T提交一个READ(Q)操作时，系统先执行LOCK-S(Q)操作，然后再执行READ(Q)操作。当事务T提交一个WRITE(Q)操作时，先检查T是否已持有共享锁。是则先执行UPGRADE(Q)操作，再执行WRITE(Q)操作；否则先执行LOCK-X(Q)操作，再执行WRITE(Q)操作。
  • 任何一个满足两段锁协议的合理调度都是冲突可串行的，但是，不是每组具有冲突可串行调度的事务都有一个满足两段锁协议的调度。

基于时间戳的并发控制协议

实现决定事务的次序，最常见的方法是时间戳排序机制

对于系统中每个事务Ti，我们把一个唯一的固定时间戳和它联系起来，记为TS(Ti)，如果新引进Tj进入系统，则TS(Ti)<TS(Tj)。

• 事务的时间戳决定了串行化顺序

• 每个数据项Q需要与两个时间戳值相关联

  • W-timestamp(Q)：表示成功执行write(Q)的所有事务的最大时间戳
  • R-timestamp(Q)：表示成功执行read(Q)的所有事务的最大时间戳

• 优点：保证冲突可串行化、保证无死锁

• 缺点：一系列冲突的短事务可能引起长事务反复重启，导致长事务饿死

• 可能产生不可恢复的调度

• Thomas写规则

  

本章重点：掌握事务的概念及性质、掌握事务调度和并发控制的概念、掌握基于锁的并发控制协议、掌握死锁的检测。

数据库恢复

数据库恢复的必要性

• 保证事务的原子性
• 发生故障后可以恢复到正确状态

故障分类：

• 事务故障
  • 逻辑故障：非法输入、找不到数据、溢出或超出资源限制
  • 系统错误：系统进入不良状态，如死锁，使事务无法正常执行
• 系统崩溃
  • 硬件故障/软件或系统漏洞导致易失性存储器内容丢失
• 磁盘故障

使用日志的数据库恢复技术

• 数据库系统日志：记录有关事务的数据库操作信息的存储结构使数据库系统日志，简称日志
• 格式：
• 为了保证日志在系统和磁盘发生故障时仍可使用，它必须永久地存在磁盘上

推迟更新技术

把所有数据库更新操作推迟到该事务提交时执行

遵循下述推迟更新协议：

• 每个事务达到提交点之前不能更新数据库
• 在一个事务的所有更新操作的对应日志记录永久写入存储器之前，该事务不能到达提交点。

当一个事务达到提交点时，称该事务到达部分提交状态

• 推迟更新协议保证，当一个事务部分提交时，该事务的所有更新状态都已经记录在了日志中
• 当一个事务部分提交时，推迟更新技术可以使用日志中有关该事务的数据库更新操作的信息更新数据库。如果一个事务部分提交之前异常结束或者发生系统故障，则有关该事务的信息会被删除。

使用日记的数据库恢复技术：

• 进行redo(T)操作。（redo操作必须时幂等的）

• 当系统发生故障并被修复以后，考察日志确定需要redo的事务T。（包含start和commit）

• 恢复过程如下：从后向前扫描，确定提交事务表和未提交事务表，对于前者执行redo，后者进行删除。

即时更新技术

允许事务直接更新数据库。处于活动状态的事务直接在数据库上实施的更新称为非提交更新。

即时更新协议：

• 所有型日志安全地、永久存储到存储器之前，事务T不能更新数据库。
• 所有型日志安全地、永久存储到存储器之前，不允许事务T提交。

即时更新技术需要如下两个操作：

• undo(T)
• redo(T)
• 恢复处理过程如下：
  • 从后向前扫描，建立提交事务表和未提交事务表
  • 对于提交事务表执行redo，对于未提交事务表执行undo并写日志记录表示撤销完成

使用检查点的数据库恢复技术

日志技术太耗时且恢复过程过长

改进方式：在日志文件中增加检查点记录(checkpoint)

• 恢复子系统在登陆日志文件期间动态地维护日志

检查点执行过程如下：

• 将当前位于主存的所有日志输出到稳定存储器
• 将所有修改的缓冲块输出到磁盘
• 将输出到稳定的存储器，其中L是执行检查点时正在活跃的事务列表

在检查点执行过程中，不允许任何事务执行任何更新

建立检查点的时间：

• 定期：预定时间间隔，如每隔一小时
• 不定期：遵循某种规则，如日志文件写满一半

检查点技术的优点：高效、执行redo、undo时只需要考虑L以及记录写道日志中后才开始执行的事务

恢复过程：

• 找到最后一条记录
• 对于L及检查点之后开始的操作，没有commit或abort记录则undo；否则redo。

恢复算法

正常操作时，事务T的回滚执行如下操作：

• 从后往前扫描，对于每个的日志记录，把v1写入X，并往日志中写入一个特殊的只读日志记录，称为补偿日志记录，这样的记录不需要undo。
• 一旦发现，就停止扫描并往日志中写入

系统崩溃后的恢复：

• 重做阶段：从最后一个检查点开始正向扫描，将undo-list初始设置为L，一旦遇到或者则重做；一旦发现则将T添加到undo-list；一旦发现commit和abort则将T从undo-list删除。
• 撤销阶段：从尾部反向扫描，发现undo-list中的就undo。发现start就写入abort并将其从undo-list删掉。undo-list为空则结束。

缓冲技术

• 日志缓冲技术

  • 一个日志记录远小于存储器读写单位，单个进行开销过大

  • 主存中设置缓冲区，其大小等于永久存储其的读写单位，缓冲区满一起永久写入存储器。

  • 需增加如下协议：

    • commit记录永久写入存储器后才可以进入提交状态
    • 非commit型日志记录必须在commit型记录之前永久写入存储器
    • 主缓冲区中的数据库数据必须在有关日志记录永久写入后才可以永久写入存储器中的数据库。

• 数据库缓冲技术
  

本章重点：掌握故障的分类、掌握使用日志的数据库恢复技术。

---