日志与恢复

数据库当中存在哪些故障？

简单来说可以分为三种故障：

  1. 事务故障
  2. 系统故障
  3. 存储介质故障

而事务故障也可分为两种：

  • 逻辑错误 (Logical Errors)：由于一些内部约束，如数据一致性约束，导致事务无法正常完成
  • 内部错误 (Internal State Errors)：由于数据库内部调度、并发控制，如死锁，导致事务无法正常提交

系统故障可以分为两种：

  • 软件故障 (Software Failure)：如 DBMS 本身的实现问题 (NPE, Divide-by-zero)
  • 硬件故障 (Hardware Failure)：DBMS 所在的宿主机发生崩溃，如断电。且一般假设非易失性的存储数据在宿主机崩溃后不会丢失

如果存储介质发生故障，通常这样的故障就是无法修复的，如发生撞击导致磁盘部分或全部受损，磁盘上的磁性介质被刮伤。在 L1 - RAID​ 就有介绍过这种情况，通常每个磁盘都会有对应的备份数据、备份磁盘，那么就保证了数据不会丢失。我们需要从备份记录中恢复数据

对于故障数据库的解决方案？

首先对于存储介质的故障，在数据库层面无能为力，只能通过硬件层面的备份与恢复进行解决。而对于上层的事务故障和系统故障，可以db层面尽可能的进行解决。

对于支持事务的数据库系统，在故障恢复上就要考虑合理编排或者恢复数据，以保证事务的特性不被违反。如不能出现不一致的中间态，或者说违反了原子性，存在部分指令成功执行而部分指令未执行的情况。

故障恢复机制包括两部分：

  • 在事务执行过程中采取的行动来确保在出现故障时能够恢复
  • 在故障发生后的恢复机制，如确保原子性、一致性和持久性

对于两方面总结的话，就是在事务执行过程中采用shadow page或者WAL的方式，再加上合适的 Buffer Pool Policy，维护相关数据，之后在发生故障时，对事务进行回滚或者重做

Buffer Pool Policies

修改数据时，DBMS 需要先把对应的数据页从持久化存储中读到内存中，然后在内存中根据写请求修改数据，最后将修改后的数据写回到持久化存储。在整个过程中，DBMS 需要保证两点：

  • 1DBMS 告知用户事务已经提交成功前，相应的数据必须已经持久化
  • 2.如果事务中止，任何数据修改都不应该持久化

如果真的遇上事务故障或者系统故障，DBMS 有两种基本思路来恢复数据一致性，向用户提供上述两方面保证：

  • Undo：将中止或未完成的事务中已经执行的操作回退
  • Redo：将提交的事务执行的操作重做

DBMS 如何支持 undo/redo 取决于它如何管理 buffer pool。我们可以从两个角度来分析 buffer pool 的管理策略：Steal Policy 和 Force Policy

STEAL：

steal所决定的是DBMS是否允许一个未提交的事务是否修改持久化存储当中的数据，如果允许，则为STEAL，如果不允许，则为NO-STEAL

如果允许(Steal)，当 T1 回滚时，需要把已经持久化的数据读进来，回滚数据，再保存回去。但是在不发生回滚时，DBMS 的 I/O 较低。

如果不允许(No-steal)，当 T1 回滚时，由于所有数据都只保存在内存中没有进入磁盘中，所以只需要丢弃这些内存中的 page 即可。但是假如 T1 是一个长事务，内存可能无法完全容纳进 T1 的所有 page，就需要将中间数据存储在额外的磁盘空间中，那么 DBMS 会带来额外的空间浪费。

FORCE：

force所决定DBMS是否要求在一个事务允许commit之前，该事务所作的所有更改应当被映射到数据库当中，即进行脏页回写，如果要求，则为FORCE，反之则为NO-FORCE

force所要求的是将该事务本身做出的更改映射到数据库当中，而对于T1所做的更改，应当将其剔除或避开，采用的解决方案为生成一个副本，在其中保存只由T2做出的更改，之后在commit时将这个副本映射到数据库当中，就只会将T2做出的更改映射到磁盘当中。

如果强制(Force)，每次事务提交之后，都必须要保证数据落盘，保证数据一致性。

如果不强制(No-Force)，DBMS 则可以延迟批量地将数据落盘，数据一致性可能存在问题，但 I/O 效率较高。

最终的buffer pool 策略为STEAL指标和FORCE指标的组合。

stealno-steal
forceSteal + ForceNo-Steal + Force
no-forceSteal + No-ForceNo-Steal + No-Force

通常实践中应用的为No-Steal + Force与Steal + No-Force

Shadow Page No-Steal + Force

在使用No-Steal + Force的策略组合下：

  • 当事务中止时，无需进行回滚，因为事务作出的修改不会主动进行持久化，也不允许被其他的事务捎带落盘
  • 当事务提交时，也无需进行重做，因为提交的数据已经全部进行持久化

最简单的实现方式为Shadow Page，其会维护两份数据：

  1. master：包含所有已经提交的事务的数据
  2. shadow：在Master之上增加为提交的数据变动

最开始，在内存当中维护一个Master的Page Table和指向该Table的DB Root，当有事务要进行写操作时，在内存当汇总给你创建一个Shadow Page Table，全部指向硬盘当中的Master，之后硬盘上也从Master 复制出来一个Shadow Page，并且令硬盘当中的对应的page table改变指向。

之后，所有的写操作都在Shadow Page上进行。在事务提交前，DB Root依旧指向Master Page Table，所有的Shadow Page 对其他的事务都不可见。

在事务提交时，则改变DB Root的指向，令其指向Shadow page Table。从而该事务作出的更改对于其他的事务全部可见

在 shadow paging​ 下回滚、恢复数据都很容易：

  • Undo/Rollback：删除 shadow pages (table)​，啥都不用做
  • Redo：不需要 redo​，因为每次写事务都会将数据落盘

Shadow Page的缺陷？

复制整个 page table 代价较大，尽管可以通过以下措施来降低这种代价：

  • 需要使用类似 B+ 树的数据结构来组织 page table​
  • 无需复制整个树状架构，只需要复制到达有变动的叶子节点的路径即可

事务提交的代价较大：

  • 需要将所有发生更新的 data page、page table 以及根节点都同时落盘。
  • 容易产生磁盘碎片，使得原先距离近的数据渐行渐远，IO 就会变成磁盘 IO ，拖缓速度。
  • 需要做垃圾收集
  • 只支持一个写事务或一批写事务一次性持久化，需要基于不同的并发策略分析。

Write-Ahead Log Steal + No-Force

WAL基于一个假设，每个修改操作都有一条对应的日志文件。

设立一个单独的日志文件，要求在进行持久化刷盘之前，必须要证对应的日志文件首先被持久化道磁盘当中，从字面意思上体现了write-ahead log 。当日志完成写入之后，即可认为此次事务已经提交，可以给予响应。

整个过程如下：

  1. 首先将事务进行的操作放在内存当中，即为redo buffer
  2. 在对内存中的数据进行修改(data page对应的buffer pool中的数据）
  3. 如果该data page要刷盘，需要把该事务对应的所有的日志强制全部刷盘
  4. 当一个事务进行提交时，无需将data page进行刷盘，只需要保证data page对应的日志全部刷盘，只要日志全部刷盘完成，则可以对外宣布此次事务成功commit
  5. 一个事务终止时，需要将其的所有日志全部刷盘，包括abort记录

WAL当中的日志格式？

每个事务开始时，先日志上写上一个<BEGIN>​标签

事务commit时，日志上写上一个<COMMIT>​​标签

日志上的每一条记录包含：

  • Transaction Id (事务 id)
  • Object Id (数据记录 id)：filename​​ 和 pageid/blocknum​​
  • Before Value (修改前的值)，用于 undo 操作
  • After Value (修改后的值)，用于 redo 操作

Log Sequence Numbers

DBMS为每条日志生成的全局唯一的序列号，一般LSN单调递增，并且为了进行crash recovery，需要在各个部分进行记录相关信息

每个page保存着一个pageLSN，DBMS本身维护者flushedLSN，表明上一次落盘的日志的LSN，而在一个$page_x$落盘之前，首先应当保证 $pageLSN_x <= flushedLSN$，这意味着在该page落盘时，该page的所有的日志都已经落盘。来保证 WAL的思想

存储和管理的位置如图：

Logging Scheme

就像SQL执行器那样可以分为物理计划和逻辑计划，在Logging Scheme(日志方案？)上同样可以分为物理和逻辑两种方案

  • Physical Logging：记录在数据库中的真实记录，在哪个page的什么位置的进行了修改
  • Logical Logging：逻辑日志只记录做的逻辑操作，如更新所有age=20的tuple，记录内容较少，但是相对的难以弄清楚具体做了什么变化，恢复的时候代价更为昂贵

还有一种混合策略，称为 physiological logging​，这种方案不会像 physical logging​ 一样记录 xx page xx 偏移量上的数据发生 xx 改动，而是记录 xx page 上的 id 为 xx 的数据发生 xx 改动，前者需要关心 data page 在磁盘上的布局，后者则无需关心。physiological logging​ 也是当下最流行的方案。

WAL如何解决了Shadow Page的缺陷

在Shadow Page策略当中，通过Page Table访问Shadow Page访问属于随机 IO ，会影响事务提交时的效率，影响并发事务的数量。而顺序写入永远比随机写入快，Write-Ahead Log即践行了这种思想，就好比那个粉板的例子，顺序写粉板永远必随机写到账本上的速度要快。

此外，WAL也不涉及到像是Page复制等操作，只需要维护一个日志文件，之后一致向其中追加写入即可。

说一说WAL当中的Checkpoint

WAL会一直进行记录，如果发生崩溃想要进行redo来恢复数据库状态，那么就要执行整个日志文件来进行恢复，耗时较长。

当缓存中的数据（data page）已经持久化到硬盘当中，此后便无需再担心这些数据的持久化问题，便可以打上一个checkpoint，通过checkpoint的方式，就像游戏中的检查点，后续的恢复只需要从checkpoint的位置开始恢复即可，之前的日志文件无需在意，甚至可以直接删除。

通过<CHECKPOINT>​标签来表明在此处打上了一个checkpoint

Checkpoint有什么相关优化？

目前描述的CheckPoint为 Non-Fuzzy Checkpoint，创建时：

  1. 停止创建任何的新事务
  2. 等待目前所有的活跃(active)事务执行完毕
  3. 将所有的脏页进行刷盘

由此可见，Non-Fuzzy Checkpoint的创建会严重影响DBMS的性能，因此在此基础上可以进行改进：

Slighly Better Checkpoint​

在进行checkpoint创建后，根据锁的暂停写事务，写事务可以向checkpiont开始前就已经加锁的page进行继续写入，但是不能获取新的锁，此时系统当中由于已经存在已经开始但被暂停的写事务，因此在之后创建checkpointj扫描整个buffer pool刷盘时，会将脏页也顺带写入磁盘当中，可能会出现不一致的问题，因此需要额外记录：

  • Active Transaction Table（ATT）：记录当前所有的活跃事务
  • Dirty Page Table（DPT）：记录目前buffer pool中的脏页

ATT当中记录着事务id、事务状态以及lastLSN，当之后事务中止或者提交时，响应的记录才会被删除

‍

Fuzzy Checkpoint

fuzzy的意思为checkpoint的创建为一个动态的模糊的过程，并不是在某一个事务的之前之后进行的创建，而是在事务的执行过程中进行创建。

fuzzy checkpoint的创建不中断任何一个事务的执行，在此期间允许事务继续执行和脏页的刷盘

由于创建为一个时间段，并且允许事务执行，因此需要标记开始的和结束的状态：

  • CHECKPOINT-BEGIN：表明开始创建检查点
  • CHECKPOINT-END：结束创建，包含ATT+DPT

当checkpoint创建成功后，checkpoint的LSN被写入到 DB的MasterRecord中

任何一个在CHECKPOINT-BEGIN之后开始的事务都不被记录到CHECKPOINT-END中的ATT当中，记录在CHECKPOINT-BEGIN之前开始但是还未执行完的事务

ARIES Database Recovery

Algorithms for Recovery and Isoation Exploiting Semantics

对于ARIES，其基础是日志策略必须使用WAL，即：

  • 任何更改在写入到数据库之前都要先记录在日志当中并且持久化到硬盘之上
  • buffer pool的管理策略必须使用 STEAL+NO-FORCE

并且通过redo 和 undo 来完成崩溃后的恢复：

  • 在crash后还是进行恢复时，最开始先重新执行日志中记录的操作，将数据库的状态恢复到崩溃之前
  • 在redo执行完之后，再进行undo操作，撤销未完成的事务，并且将undo操作记录到日志当中，来确保重复失败时不会重复操作

事务提交时的日志行为？

当事务提交时，首先写一条COMMIT记录当WAL当中，之后将COMMIT以及之前的日志进行落盘，之后将flushedLSN进行更新，之后即可清除掉内存当中COMMIT以及之前的日志。之后再写入一条TXN-END记录到日志当中，表示事务真正结束

事务中止时的日志行为？

要进行事务中止，就要在当前的状态的基础之上，根据先前写入的WAL日志，进行一条条的回退进行undo，恢复到事务开始时的状态。

因此在原本日志的基础上，需要引入一个额外的数据preLSN，表明当前事务日志的前一条日志，用于形成一个链表的形式将整个事务的相关日志串联起来，便于回退执行。

为了防止在回滚过程中再次故障导致部分操作被执行多次，回滚操作也需要写入日志中，等待所有操作回滚完毕后，DBMS 再往 WAL 中写入 TXN-END 记录，意味着所有与这个事务有关的日志都已经写完，不会再出现相关信息

因此引入了CLR，CLR作为一种操作，与COMMIT UPDATE等一样需要通过日志进行记录，CLR当中记录undo的具体操作，并且通过一个undoNext指针，指向下一条进行undo的日志。

永远不会对CLR本身进行undo

完整过程为：

  1. 首先在日志前添加一个ABORT记录，表示开始进行中止操作
  2. 找到日志当中该事务的最后一条日志，根据preLSN逆序进行操作
  3. 对于之前的每个UPDATE RECORD，添加一条CLR，之后将数据库当中的值恢复为原本的值
  4. 最终回滚结束时，在日志的末尾添加一条TXN-END，表明回滚结束

‍

ARIES -Recovery Phases

Crash Recovery主要分为三个过程：

  • Analysis：通过日志解析出在crash之前的数据库状态，找到上一个检查点 通过ATT和DPT获取崩溃时的数据库的状态，找到当时的脏页和活跃事务的情况，来确定那些需要redo，那些需要undo
  • Redo：从一个合适的点开始重复执行日志中记录的所有操作，即便该操作对应的事务在后续被abort
  • Undo：对于crash前的所有未commit的事务（包括没来得及进行commit，执行了一半的事务和最终需要abort的事务）反向执行，撤销其进行的操作和对磁盘的影响

Analysis phase

从最近的begin checkpoint进行扫描，如果扫描到了一个TXN-END​那么就把对应的事务移除ATT，而对于其他类型的记录：

  • 就将其加入到ATT当中，并设置status为UNDO
  • 如果扫描到了一个COMMIT​就将事务的状态改为COMMIT​
  • 对于UPDATE​ records，如果更新的page p不在 DPT当中，那么就将其加入到DPT当中，并且设置：recLSN = LSN​（表明这是第一次将该page加载到buffer pool当中并且进行更改）

当执行完Analysis过程，构建出ATT和DPT之后：

  • ATT表明在crash时有哪些事务处于活跃状态
  • DPT表明当时有哪些脏页还没来得及落盘

Redo Phase

重建起crash时db的状态，重新执行所有的update和CLRs

从 DPT 中找到最小的 recLSN，从那开始向后 redo​ 日志和 CLR日志，除了一下的两种情况，其他均应当进行redo操作：

  • 如果不在DPT中，则证明之前在某时间已经将其刷盘持久化到硬盘当中
  • 如果记录的LSN小于 page的recLSN，则证明，在此次操作将其刷盘之后，又有其他的事务读取了该页到内存当中进行了重新的修改，因此此次操作被后续的操作覆盖，因此可以忽略（参考 recLSN的定义）

最小的recLSN表明为数据库中最早的脏页状态，再此之前的日志均为产生脏页，因此不需要进行重新构建。

redo时，需要：

  1. 重新执行日志中的操作
  2. 将 pageLSN 修改成日志记录的 LSN
  3. 不再新增操作日志，也不强制刷盘

在 Redo Phase 结束时，会为所有状态为 COMMIT 的事务写入 TXN-END 日志，同时将它们从 ATT 中移除。

Undo Phase

将所有 Analysis Phase 判定为 U (candidate for undo) 状态的事务的所有操作按执行顺序倒序 Undo​，并且为每个 undo 操作写一条 CLR 更新到日志文件中。