数据库复习 - PART3 - 物理存储实现

• 数据库复习 - PART3 - 物理存储实现
• • 8. 物理存储
  • • 8.1 存储体系结构
    • 8.2 磁盘的特性与结构
    • • 8.2.1 磁盘的数据访问
      • 8.2.2 RAID技术
    • 8.3 DBMS数据存储与查询实现的基本思想
    • 8.4 记录与磁盘块的映射
    • 8.5 数据库文件组织方式
  • 9. 数据库索引
  • • 9.1 索引基本概念列表
    • 9.2 B+树索引
    • 9.3 B树
    • 9.3+ B VS B+比较
    • 9.4 散列索引
    • 9.5 逆索引
  • 10. 数据库查询算法
  • • 10.1 查询概述
    • 10.2 I/O复杂性
    • 10.3 迭代器构造查询实现
    • 10.4 基于索引的算法
    • 10.5 两趟扫描算法
  • 11. 查询优化技术
  • • 11.1 概述
    • 11.2 关系代数操作次序交换等价性
    • • 11.2.1 L1：连接与连接，积与积交换律
      • 11.2.2 L2：连接与连接，积与积结合律
      • 11.2.3 L3：投影串接律
      • 11.2.4 L4：选择串接律
      • 11.2.5 **L5：选择和投影交换律
      • 11.2.6 **L6：选择和积交换律
      • 11.2.7 **L7：投影和积交换律
      • 11.2.8 L8：选择和并的交换律
      • 11.2.9 L9：选择和差的交换律
      • 11.2.10 L10：投影和并的交换律
    • 11.3 逻辑层优化算法
    • 11.4 物理层/执行优化
  • 12 事务处理
  • • 12.1 事务的概念
    • 12.2 事务的特性
    • 12.3 事务相关概念
    • 12.4 判断并发调度正确方法 - 冲突可串行性判别方法
    • 12.5 如何产生正确的并发调度
    • • 12.5.1 基于*的方法
      • 12.5.2 基于时间戳的方法
      • 12.5.3 基于有效性确认的方法
  • 13 故障恢复技术
  • • 13.1 概述
    • 13.2 日志技术
    • • 13.2.1 日志缓冲区处理策略
      • 13.2.2 UNDO型日志
      • 13.2.3 REDO型日志
      • 13.2.4 UNDO/REDO型日志

数据库复习 - PART3 - 物理存储实现

8. 物理存储

8.1 存储体系结构

• 磁盘
• 内存
• 缺页、换页

8.2 磁盘的特性与结构

磁盘结构：

• 磁盘
• 磁道
• 扇区
• 磁头
• 柱面，多个盘面的相同位置的磁道构成一个虚拟的圆柱体

8.2.1 磁盘的数据访问

例：

目标磁盘参数如下：

磁盘以7200r/min旋转；

柱面之间移动磁头组合从启动到停止花费1ms，每移动4000个柱面需要1ms，即磁头在0.00025ms内移动一个磁道；

一个磁盘块 = 4个扇区 = 16KB

假设磁盘块传输时间为0.13ms，问最长时间与平均时间。

解：

最长时间 = 最长寻道时间（最内圈到最外圈）+ 最长旋转时间（旋转一周）+ 传输时间；

旋转一周耗时 = 60 s / 7200 = 8.33ms

最长寻道时间 = （启动时间 + 结束时间）+ 移动时间 = 1ms + 65536 * （1ms / 4000） = 17.38ms

故最长时间 = 17.38s

平均时间 = 平均寻道时间（走1/3）+ 平均旋转时间（旋转半周） + 传输时间；

平均寻道时间 = （启动时间 + 结束时间）+ 移动时间 = 1ms + 65536 * （1ms / 4000 * 3） = 6.46ms

平均旋转时间 = 8.33ms / 2 = 4.17ms

故平均时间 = 10.76ms

8.2.2 RAID技术

• RAID0：块级拆分无冗余；（坏盘处理）
• RAID1：每一个磁盘有一个镜像磁盘C；（IO开销、成本增大）
• RAID2：位交叉纠错，4个磁盘存储4位 + 3个校验盘P存储3校验位；
• RAID3：位交叉检验，4个磁盘存储4位 + 1个校验盘P存储1位（借助于扇区读写校验判断出错磁 盘，再依据校验盘进行纠错）；（对校验盘要求较高，每次IO都需要访问该校验盘）
• RAID4：块交叉检验，块拆分存储；
• RAID5：块交叉分布式校验，块拆分存储，各块互为校验盘；

位拆分： 将一个字节拆分成8个bit位，不同比特位存储在不同磁盘上；

块拆分： 文件由多个块组成，不同块存储于不同磁盘中；

8.3 DBMS数据存储与查询实现的基本思想

基本思想：从磁盘读入至内存缓冲区，在缓冲区中进行查询操作，可利用索引文件操作

8.4 记录与磁盘块的映射

• 简介

  逻辑层：表、属性、记录；

  物理层：磁盘块、0/1数据；

• 数据库中记录的区分和记录内属性的区分

  • 定长记录：按长度区分；
  • 变长记录：块头指针、标志位；

• 记录与磁盘块关系

  • 非跨块：浪费存储空间，磁盘块间可并行查找；（以空间换时间）
  • 跨块：节省存储空间，磁盘块间有关联需串行；（以时间换空间）

• 表在磁盘块中的分配方式：

  • 连续分配：拓展问题；
  • 链接分配：指针指，访问速度不行；
  • 按簇分配：结合前二者，簇之间指针连接；
  • 索引分配：类似extfs中的inode；

8.5 数据库文件组织方式

• 文件组织

  指数据组织成记录、块和访问结构的方式，包括把记录和块存储在磁盘上的方式，以及记录与块之间相互联系的方法；

• 存取方法

  指对文件所采取的存取操作方法；

• 无序文件组织（堆文件 heap file或 桩文件pile file）

  • 基本思想：LOG型，记录总是插入文件末尾或者插入被标记过期的位置；
  • 特点：更新效率高、检索效率低
  • 垃圾回收机制：数据库重组，即每隔一段时间进行垃圾回收，内存紧缩；

• 有序文件组织（排序文件 Sequential file）

  • 基本思想：按照某属性顺序插入数据；被排序关键字被称为排序字段或排序码，通常为主键；

  • 特点：当按照排序字段检索时，效率会大大提高；但按照非排序字段检索时，速度可能没有很大的提升；有序文件更新效率低下，因为更新时要移动其他记录；

  • 改进方法：

    使用溢出（Overflow）策略：为未来将插入的元组预留空间（造成空间浪费），或使用一个临时的无序文件（溢出文件）保留新增记录；

    此时，检索操作既要操作主文件，又要操作溢出文件；

    因此，我们利用数据库重组机制来将溢出文件合并入主文件，以此恢复主文件中的记录顺序；

• 散列文件（Hash File）

  • 基本思想：计算记录的某属性或属性组的Hash值，将其放入对应的Hash桶中；被用于计算散列的属性或被称为散列字段或散列码；

  • 特点：检索效率和更新效率都有所提高；

  • 溢出处理：

    桶大小有限，当桶溢出后，利用链接法创建新的溢出桶；

• 聚簇文件（Clustering File）

  • 基本思想：将具有相同或相似属性值的记录存放于连续的磁盘簇块中；（还有多表聚簇，如下图所示）

9. 数据库索引

9.1 索引基本概念列表

• 主文件： 目标存储表；

• 索引文件： 存储索引项的文件；

• 索引项：（索引字段，行指针）；（也有不是这样的，例如对于顺序存储文件，我们就不该这么做）；

• 索引字段： 通常存储了索引字段的每一个值；

• 行指针： 指向包含索引字段值的记录在磁盘上的物理位置；

• 两种文件组织方式： 排序索引文件、散列索引文件；

• 稠密索引： 对于主文件中每一个记录，都有一个索引项和它对应，指明该记录所在位置，这样的索引称为稠密索引；

  • 候选键： 索引文件包含每一条记录；索引文件无，主文件无；

  • 非候选键：

    • 方案一：索引文件中索引字段不重复，要求主文件排序；

    • 方案二：索引文件中索引字段存在重复；

    • 方案三：引入指针桶处理索引字段多记录情况，如下图；

    

• 稀疏索引：与稠密索引相对，主文件中只有部分记录与索引项相对；要求主文件必须按索引字段排序存储；

• 主索引：对每一个存储块有一个索引项，索引项的总数和存储表所占的存储块数相同，记录每块第一条记录；被称为锚记录或块锚；主索引文件一般是排序文件，也一般建立在排序文件之上；

• 辅助索引：是稠密索引，定义在主文件的任一或多个非排序字段上的辅助存储结构；

• 聚簇索引：是指索引中邻近的记录在主文件中也是临近存储的；聚簇索引通常定义在聚簇字段上（即该字段的每个记录取值不唯一）；索引项指向块号；

• 非聚簇索引：是指索引中邻近的记录在主文件中不一定是临近存储的；索引项指向记录；

• 主索引/聚簇索引能够决定记录存储位置；但非聚簇索引只能用于查询，指出已存储记录位置（答案显而易见，因为前者有序，后者无序，有序即可规划存放位置，无序则无法规划）；

• 一个主文件只能有一个主索引，但可有多个辅助索引；

• 一个主文件只能有一个聚簇索引，但可有多个非聚簇索引；（显而易见，因为只能同时保证对一个字段排序）；

• 倒排索引： 用关键词索引文章；

• 多级索引： 如B/B+树索引；

• 多属性索引： 索引字段由表中的多个属性构成；

• 散列索引： Hash桶相关；

• 网格索引： 使用多索引字段进行交叉联合定位与检索；

9.2 B+树索引

• 基本结构
  < p 1 , k 1 , p 2 , k 2 . . . p n − 1 , k n − 1 , p n > <p_1,k_1,p_2,k_2...p_{n-1},k_{n-1},p_n> <p1​,k1​,p2​,k2​...pn−1​,kn−1​,pn​>
  其中，pi指向 k（i-1）≤ k < ki的索引块，pn指向下一个索引块；

  对于叶节点，pi 指向 k = ki的主文件记录；

• 约束

  • 一个索引块中的实际索引指针个数d，满足（根节点除外）：
    n / 2 ≤ d ≤ n n/2 \le d \le n n/2≤d≤n
    即至少用一半的指针

  • 根节点至少两个指针被使用；

  • 给出公式（此时n为Key的数量）：
    非 叶 节 点 ： 至 少 ⌈ ( n + 1 ) / 2 ⌉ 个 指 针 叶 节 点 : 至 少 ⌊ ( n + 1 ) / 2 ⌋ 个 指 针 非叶节点：至少\lceil (n+1)/2 \rceil个指针 \\ 叶节点:至少\lfloor (n+1)/2 \rfloor个指针 非叶节点：至少⌈(n+1)/2⌉个指针叶节点:至少⌊(n+1)/2⌋个指针

• 插入

  要点：插入处分裂，调整上面的节点，能分裂就不要加Key；

• 删除

• 应用：

  • 用B+树建立主键属性稠密索引

    索引字段是主文件的主键，索引是稠密的；

• 用B+树建立稀疏索引（或主索引）

  索引字段是主文件的主键，索引是稀疏的。主文件必须按主键排序。指针指向的是数据块；
  

• 用B+树建立非键属性稠密索引

  索引字段是主文件的非主键属性，索引是稠密的。主文件按非键属性排序，索引文件的索引字段是无重复的。指针指向的是记录。（通过记录继续往下走）；

• 用B+树建立非键属性稠密索引

  索引字段是主文件的非主键属性。主文件不按此非键属性排序，索引文件的索引字段值是有重复的。指针指向的是记录。

  

9.3 B树

• 索引字段仅出现一次，或者在叶节点，或者在非叶节点；
• 指向主文件的指针出现于叶结点或非叶结点；
• 所有结点才能覆盖所有键值的索引；

9.3+ B VS B+比较

对比项	B树	B+树
一块中，索引项个数	较少，因为加入主文件指针	较多
索引字段值出现在哪	或叶节点、或非叶节点	叶节点
指向主文件的指针存在哪里	或叶节点、或非叶节点	叶节点
分裂与合并方法是否一致	不一致	不一致

9.4 散列索引

• 基本散列索引

  思想：Hash桶，插入时桶满则申请溢出桶；删除时，尝试合并溢出桶；

  问题：Hash函数问题；键值数过多问题等；

• 静态散列索引 - 桶数固定

  按照基本散列索引来搞；

• 动态散列索引 - 桶数不固定

  • 可拓展散列索引（散列二进制，调整使用位数，从前算起；桶数组翻倍）
  • 线性散列索引（散列二进制，容纳阈值，超过即分裂，线性增长，允许溢出桶，位数为log2n向上取整，从右算起）

9.5 逆索引

例如：

id = 1234

reverse id = 4321，建立逆索引，使相似的数据相隔较远；

• 缺点：聚集性差，范围查询支持得不好；

• 优点：

  防止叶节点过热；

  读入后保存在内存中的数据也有顺序；

10. 数据库查询算法

10.1 查询概述

• 基本思想：

  解析语句为各种基本运算组合，调用基本动作执行；

• 查询优化：

  尽早做投影、选择

• 操作总览：

  • 一次单一元组的操作：
    • 选择；
    • 投影；
  • 一次整个关系的操作：
    • 去重；
    • 聚合；
    • 排序；
  • 二元操作：
    • （包）交
    • （包）并
    • （包）差
    • 连接、笛卡尔积

10.2 I/O复杂性

计算读入磁盘块数的次数即可，后面有时间再补充

10.3 迭代器构造查询实现

• 提出

  两种策略：

  • 物化策略：每一次输出的中间结果都写回磁盘；
  • 流水线策略：每一次输出的中间结果都作为下一个模块的输入；

10.4 基于索引的算法

• 示例

  假设B（R）=1000, T（R）=20000, 即：R有20000个元组存放到1000个块中。a是R的一个属性，在a上有一个索引，并且考虑σ（a=0）（R）操作；

  • 如果R是聚簇的（a字段排序），且不使用索引，则查询代价为1000个I/O；
  • 如果R是非聚簇的（a字段无序），且不使用索引，则查询代价为20000个I/O；
  • 如果V（R，a）= 100，且索引是聚簇的，则每个值平均占有1000 / 100 = 10个块，可由聚簇索引直接定位，故查询代价为10个I/O，其中V（R，a）代表a属性在R中出现的不同值个数；
  • 如果V（R，a）= 100，且索引是非聚簇的，也就是带有重复，每个索引项指向一条记录，平均每个值对应20000 / 100 = 200个元组，每个元组可能散布在磁盘的各个块中，因此至多需要200次I/O；
  • 如果V（R，a）= 20000，即代表a是主键，不管聚簇还是非聚簇，索引项都指向一条记录，因此，I/O为1次；

• ZIG-ZAG算法

  跳来跳去算法

  基本思想：

  通过B+树索引比较R与S的索引项a与b完成：如果a大，则移动b；否则移动a。具体算法如下：

  1. 读R的第一个索引项至a，读S的第一个索引项至b；
  2. 若 a ！= b，则：
     1. a < b，读R的下一个索引项至a，继续执行步骤2；
     2. a > b，读S的下一个索引项至b，继续执行步骤2；
  3. 若 a = b，则输出R与S对应关系的连接，直到R与S的连接处理完毕；若还未处理完毕，则读R的下一个索引项至a，继续执行2；

10.5 两趟扫描算法

问题驱动：

若关系所占块远远大于内存块，则一趟扫描不再能够处理一些情形；

• 两阶段多路归并排序（TPMMS）

  1. 对集合R分组；
  2. 对分组进行内排序，读出写回I/O次数共 2B（R）；
  3. 对内排序结果做第二趟扫描归并排序，读出写回 I/O次数共2B（R）；
  4. 共4B（R）次I/O次数；

  显然：

  分组的组数 ≤ M - 2；（一个比较块，一个输出缓冲块）

  分组的块数 ≤ M；

  即TPMMS适用于：

  B（R）≤ M（M - 2）＜ M²

  如果B（R）> M²，TPMMS不再适用，可能需要更多趟的排序，例如：内存大小3块，待排序关系30块；

  由于内存块只有3块，其中一块作为输出缓冲块，于是可用块数为2，两两比较时，逻辑较为简单，不需要建立比较块，因此用两块作为输入缓冲区即可；

  1. 显然，为了内排序，我们将原关系分为10组，每组3块，刚好可以进行内排序；
  2. 然后两两归并，得到5组具有6块已排序的子关系；
  3. 再两两归并，得到2组具有12块已排序的子关系，一个具有6块已排序的子关系；
  4. 再两两归并，得到一组具有24块已排序的子关系，一组具有6块已排序的子关系；
  5. 最后两两归并，得到30块已排序的关系；

• 基于排序的两趟扫描算法

  通常可以通过修改TPMMS的第二趟扫描算法实现

  • 去重操作

    保证当且仅当输出缓冲区已满，还要向其输出记录时，才写回，向其输出记录时，要保证该记录在输出缓冲区中无重复；在每组输出元素到比较块时，要保证每组的输出与上一次的输出结果不同；

  • 聚集操作

    在第二趟扫描的过程中，对重复记录做分组聚集计算；

  • 包交、并、差

    • 包并 R ∪ S

      直接合并即可，无需两趟算法；

    • 包交 R ∩ S

      在第二趟扫描时统计重复次数；

      输出t的次数是它在R和S中出现的最小次数；

    • 包差 R - S

      输出t的次数是它在R中的次数减去其在S中出现的次数；

  • 集合交、并、差（集合中无重复元素）

    • 集合并 R ∪ S

      重复的只输出一次；

    • 集合交 R ∩ S

      只输出R与S中重复的；

    • 集合差 R - S

      只输出R中有的，S中没有的

  • 基于排序的连接算法

    • 先TPMMS；
    • 再利用TPMMS结果做连接；

• 基于散列的两趟扫描算法

  思想： 元组在子表上满足的关系，在大关系中也满足

  第一趟：

  散列子表，用散列函数h将原始关系划分成M - 1个子表并存储

  第二趟：

  处理每个子表，用另一散列函数**h’**将子表读入内存并建立内存结构，进行不同的操作；

  • 去重

    h = 计算元组部分属性值 % M；

    h‘ = 计算整个元组的值 % M；

    元组在子表上不重复，则在大关系中亦不重复

  • 分组聚集

    h = 计算“分组属性”的值 % M；

    h’ = 以“分组属性”的二进制位串重新计算值，然后 % M；

  • 并、差、交

    这里只介绍集合并

    • 第一趟：以相同散列函数散列散列两个操作对象R和S，形成R1,…,RM 和 S1,…,SM；（R1对应的散列计算结果应该等于S1对应的散列计算结果，例如：都是1）

    • 第二趟：

      将Si再整体散列读入到内存中，再依次处理Ri的每一块。如判断在Ri,Si都出现元组t,则仅输出t的一个副本，否则输出Si和Ri。

  • 基于散列的连接

    • 第一趟：使用相同散列函数散列两个操作对象R和S，形成R1,…,RM 和 S1,…,SM

    • 第二趟：

      将Si再整体散列读入到内存中，再依次处理Ri的每一块。进行连接。

11. 查询优化技术

11.1 概述

三个层面的优化：

• 语义优化：利用模型的语义及完整性规则，优化查询；

  去掉无关属性、无关表

• 语法优化：利用语法结构，优化操作执行顺序；

  尽可能早做连接和投影操作

• 执行优化：存取路径和执行算法的选择与执行次序优化；

  代价评估，选择代价最少的例行程序及确定相应参数

逻辑优化基本策略：

• 尽可能早地做选择和投影；
• 把选择和投影串接起来；
• 把投影与其前后地二元运算结合起来；
• 把某些选择与其前的笛卡尔积合并成一个连接；
• 执行连接运算前对关系进行适当预处理；
• 找出表达式的公共子表达式；

11.2 关系代数操作次序交换等价性

设E1、E2是两个关系操作表达式，若E1、E2表示相同的映射，即当E1，E2地同名变量带入相同关系后产生相同的结果，则说E1、E2是等价的。记为E1 ≡ E2；

11.2.1 L1：连接与连接，积与积交换律

11.2.2 L2：连接与连接，积与积结合律

11.2.3 L3：投影串接律

11.2.4 L4：选择串接律

11.2.5 **L5：选择和投影交换律

即，把E先变小，再做选择，再做投影；（即尽早做投影、选择）

11.2.6 **L6：选择和积交换律

11.2.7 **L7：投影和积交换律

11.2.8 L8：选择和并的交换律

11.2.9 L9：选择和差的交换律

11.2.10 L10：投影和并的交换律

11.3 逻辑层优化算法

1. 依据定理L4：选择串接律，把原式变为σF1（σF2（E））的形式；

2. 对每个选择，依据定理L4到L9，尽可能将它移至树的底部；

3. 对每个投影，依据定理L3，L7，L10和L5；

4. 依据定理L4至L5把串接的选择和投影组合为单个选择、单个投影，或者 一选择 后跟一个投影。

5. 对修改后的语法树，将其内结点按以下方式分组：

   每个二元运算结点(积、并、 差、连接等)和其所有一元运算直接祖先结点放在一组；对于其后代结点，若后代结点是一串一元运算且以树叶为终点，则将这些一元运算结点放在该组中；若该二元运算结点是笛卡儿积，且其后代结点不能和它组合成等连接，则不能将后代结点归入该组。

6. 产生一个程序：它以每组结点为一步，但后代组先执行；

11.4 物理层/执行优化

• 概述

  各种基本操作的实现，例如：一趟扫描算法、两趟扫描算法等；

• 收集表信息

  • DB2

    runstats on table xxx;

  • Oracle

    analyze table xxx compute statistics for table;

• 代价估算

  符号	意义
  T（R）	关系R的元组数
  B（R）	关系R的块数
  I（R）	关系R的每个元组的字节数
  f（R）	关系R一块存储的元组数
  V（R，A）	A属性出现的不同值
  SC（R，A）	R中属性A的选择基数，即，满足A上等值条件的平均记录数

  • 投影运算估计

    例

    磁盘块大小=1024 Byte ，R的元组长度=100 Byte, 10元组/块，T®=10,000，求B（ΠL（R）），设ΠL（R）的元组长度 = 20 Byte, 50元组/块，则B（ΠL（R））= 200；

  • 选择运算

    • 类型1： S = σ（A=C）（R）

      1. T（S）介于0到T（R） - V（R，A） + 1 之间；
      2. 当V（R，A）已知时，T（S） = T（R）/ V（R，A）；
      3. 当V（R，A）未知时，T（S） = T（R）/ 10；

    • 类型2： S = σ（A < C）（R）

      T（S） = T（R） / 3；（注意，＞，=，＜分别占三分之一）

    • 类型3： S = σ（A = C and B < 20）（R）

      1. T（S） = T（R）/ 30
      2. T（S） = T（R） / （3 * V（R，A））

    • 类型4： S = σ（C1 or C2）（R）

      T（S） = （1 - （1 - p（C1））* （1 - p（C2）））* T（R）

  • 连接运算（以相同元素出现可能性小的集合为准）

    T（S） = T（R）* T（S）/max（V（R，Y），V（S，Y））

    例

    T（R）=10000, T（S）=50000, V（R, Y） = 500, V（S, Y）=1000，估计T（R 自然连接 S）；

    T = 10000 * 50000 / 1000 = 500000

12 事务处理

12.1 事务的概念

事务是数据库管理系统提供的控制数据操作的一种手段，通过这一手段，应用程序员将一系列的数据库操作组合在一起作为一个整体进行操作和控制， 以便数据库管理系统能够提供一致性状态转换的保证；

12.2 事务的特性

• 宏观性：多条语句被打包执行；

• 微观性：事务内部的基本操作可以交叉执行；

• ACID

  • 原子性（Atomicity）

    DO or Nothing

  • 一致性（Consistency）

    不能出现三种典型不一致性：修改丢失、重复读错误、脏读；

    • 丢失修改： 都读入，都写入，某个事务看不到另一个事务的写入操作；
    • 重复读错误： 某事务读两次，两次结果不一致；
    • 脏读： 某事务读入一个被撤销的属性修改；

  • 隔离性（Isolation）

    DBMS保证并发执行的事务之间不受影响。串行性；

  • 持续性（Durability）

    DBMS保证已提交的事务的影响是持久的，被撤销的事务的影响是可恢复的；

12.3 事务相关概念

• 事务调度

  一组事务的基本步骤的一种执行顺序称为对这组事务的一个调度；

  并发调度：多个事务宏观上看是并行执行的，但微观上是交叉执行的；

• 并发调度的正确性：

  当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全一致，则说调度是正确的；

• 可串行性

  不管数据库初始状态如何，一个调度对数据库状态的影响都和某个串行调度相同，则我们说这个调度是可串行化的 （Serializable）或具有可串行性（Serializability）；

  可串行性强调结果

  • 可串行化调度一定是正确的调度；
  • 正确的调度，却不一定是可串行化的调度（和数据相关）；

• 冲突

  调度中一对连续的动作：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变；

  • 同一事务内任何两个动作间；
  • 不同事务对同一元素的写；
  • 不同事务对同一元素的一读一写；

• 冲突可串行性

  一个调度，如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度，则称此调度为冲突可串行化的调度；

  • 满足冲突可串行一定满足可串行
  • 反之不然

• 总结

  并发调度正确 > 可串行 > 冲突可串行

12.4 判断并发调度正确方法 - 冲突可串行性判别方法

1. 构造一个有向图；
2. 节点是每一个事务Ti。如果Ti的操作与Tj的操作发生冲突，且Ti在Tj前执行，则绘制一条边，由Ti指向Tj，表示Ti要在Tj前执行；
3. 若无环，则冲突可串行化；

12.5 如何产生正确的并发调度

12.5.1 基于*的方法

• 锁的类型

  • 排他锁（X）：不允许同时读写；
  • 共享锁（S）：允许同时读；
  • 更新锁（U）：可升级为同时写；
  • 增量锁（I）：增量更新锁，例如：A += X；

• 相容性矩阵

• *协议

  • 0级协议

    1. 加入写锁，能够让另外的事务看到对A的修改，而不至于丢失修改；
    2. 由于可能会事务回滚，因此，0级协议不能保证脏读不发生；
    3. 由于另一个事务可以先后两次读A，因此0级协议不能保证重复读错误；

• 1级协议

  1. 写锁直到Commit时才释放，此时A要么提交修改，要么回滚，其他事务能够清除看到该事务的写操作，因此，在避免丢失修改的同时，有效防止脏读；
  2. 对于另一个事务而言，对A的重复读操作还是存在？

• 2级协议

  1. 为读数据加入共享锁；
  2. 对读入数据B而言，重复读仍可能发生，因为另一个事务写入了B；

• 3级协议

  1. 均在Commit时释放锁；
  2. 可防止重复读错误；
  3. 可防止所有不一致性；
  

• *粒度

  • 并发度小，*开销小；
  • 并发度大，*开销大；

• 两段*协议

  • 描述

    读写数据之前要获得锁。每个事务中所有*请求先于任何一个解锁请求；解锁后不得再次*；

  • 优势

    是冲突可串行的；

  • 缺陷

    可能产生死锁；

12.5.2 基于时间戳的方法

RT（X）：元素X最后读时间戳；

WT（X）：元素X最后写时间戳；

TS（T）：事务T的时间戳；

• 调度规则1

  有冲突即回滚事务，并重启；

• 托马斯写规则

  过时的写可直接被忽略，而无需撤销；

• 调度规则2

  引入C（X），代表X的提交位，用于防止脏读；

  • 读请求

    • TS（T） ≥ WT（X），可发生，检查C（X）位，若真，则同意请求，修改RT（X）；若为假，则推迟T的读请求；

    • TS（T）< WT（X），回滚；

  • 写请求

    • TS（T） ≥ RT（X），TS（T） ≥ WT（X），修改WT（X），置C（X）为假，表示事务T未提交；
    • TS（T） ≥ RT（X），TS（T） < WT（X），根据托马斯写规则，该请求可发生。若C（X）为真，那么表示可以忽略该次写入请求；若C（X）为假，表示不可忽略该次请求，推迟事务T的写请求，直到C（X）为真或事务T终止；
    • TS（T） < RT（X），回滚；

12.5.3 基于有效性确认的方法

RS（T）：事务T读数据集合；

WS（T）：事务T写数据集合；

• 基本思想

  • 每个事务具有时间戳表明起始时间；
  • 事务分三个阶段进行：读阶段，有效性确认阶段，写阶段；
  • 每个成功确认的事务是在其有效性确认的瞬间执行的；

• 具体做法

  看FIN——FIN（T‘）包含在START（T）到FIN（T）之间，就要考察FIN（T’）和START（T），以及FIN（T‘）和VAL（T）；前者检查RS（T）与WS（T’）的关系，后者检查WS（T‘）和VAL（T）的关系；

13 故障恢复技术

故障恢复技术设计到保障事务的原子性和持久性

13.1 概述

• 三种类型故障
  • 事务故障
  • 系统故障：掉电、关机等；
  • 介质故障：0、1翻转；
• 三种恢复手段
  • 事务撤销与重做；
  • 运行日志；
  • 备份；
• 两个重要时刻：
  • 转储点；
  • 检查点；

13.2 日志技术

13.2.1 日志缓冲区处理策略

• Force

  内存中的数据最晚在commit时写入磁盘；（无需REDO）；

• No Steal

  不允许事务在commit之前把内存中的数据写入磁盘；（无需UNDO）；

• No Force

  内存中的数据可以一直保留，在commit之后过一段时间写入磁盘；（不保证写入，要REDO）

• Steal

  允许事务在commit之前把内存中的数据写入磁盘；（恢复到崩溃前的状态，要UNDO）；

13.2.2 UNDO型日志

写入日志的顺序：

1. <T, X, v>；（v为旧值）
2. OUTPUT（X）
3. 或；

写盘前不提交

恢复方法：

自底向上恢复，跳过COMMIT，若某条记录已经COMMIT，则跳过；若某条记录没有COMMIT或已被ABORT，则重做该记录；

检查点应用：

• 静态检查点（停止接受新事务）

• 动态检查点（可接受新事务）

13.2.3 REDO型日志

写入日志的顺序：

1. <T, X, v>；（v为新值）
2. 或；
3. OUTPUT（X）；

写盘前提交

恢复方法：

自顶向下恢复，重做成功COMMIT的记录，其他数据不管；

检查点应用：

• 静态检查点

  从处向下REDO；

• 动态检查点

13.2.4 UNDO/REDO型日志

写入日志的顺序：

1. <T, X, u，v>；（v为新值，u为旧值）
2. 或；
3. OUTPUT（X）；

或

1. <T, X, u，v>；（v为新值，u为旧值）
2. OUTPUT（X）；
3. 或；

写盘前提交（REDO）或写盘后提交（REDO）

恢复方法：

先UNDO，后REDO，通过COMMIT关键字判断REDO，UNDO；

下述日志经过恢复过程：

1. UNDO

   • 发现ABORT T3，即T3未完成，UNDO T3：

     X3 = m1；

     X1 = v2；

   • T1、T2均COMMIT，即事务T1、T2均已完成，无需UNDO；

2. REDO

   • 发现T1、T2均COMMIT，需要REDO

     X1 = v1；

     X1 = v2；

     X2 = k1；

     X3 = m1；

   • 发现T3没有COMMIT，则无需REDO

综上，最终结果为：

x1 = v2；x3 = m1；x2 = k1；