15. Recovery System

约 6771 个字 预计阅读时间 34 分钟

Abstract

• Failure Classification
• Storage Structure
• Data Access
• Recovery and Atomicity
• Log-Based Recovery
• Remote Backup Systems
• Recovery with Early Lock Release and Logical Undo Operations
• ARIES Recovery Algorithm

15.1 Failure Classification

• Database application —— transaction failure

  • 逻辑错误：比如不满足数据库约束条件（主键）

  • 系统错误：死锁。

  常用方法是撤销 undo, 把这个事件抹掉。（基于日志，在产生修改之前先记日志，故障后可以根据日志进行撤销）

• DBMS

  • 掉电
  • 硬件故障
  • 软件故障

  system crash 是全局性的，所有运行的程序都会受到影响。分为两类：一类是事务已经提交（但是数据还在缓冲区），另一类是正在执行的事务（还没有提交）。

  已经提交的事务要 redo(数据可能没写回去), 没有完成的事务要 undo.

  先记日志，现在的数据库采用 repeating history 的方法。

• Database

  • 介质故障 head crash
  • other disk failure

  要防止介质故障，需要做备份（拷贝或者远程）

15.2 Storage Structure

日志可能也会出故障？我们假设日志存储在 Stable storage 里。

• Volatile storage 易失性存储: main memory, cache

  会在system crash（power，hardware，software failure）中损失，符合掉电易失

• Nonvolatile storage 非易失性存储：disk, tape, flash memory，battery backed up RAM

  survives system crashes，但仍然存在丢失数据的可能

• Stable storage:

  • a mythical(虚拟的) form of storage that survives all failures

    能在所有故障中幸存下来

  • approximated by maintaining multiple copies on distinct nonvolatile media

    通过在不同的非易失性介质上维护多个拷贝来近似

  这里，我们假设日志都会记录到stable storage中，不会发生丢失

15.2.1 Implementation

• Maintain multiple copies of each block on separate disks

  在单独的磁盘上维护每个块的多个副本

• Failure during data transfer can still result in inconsistent copies

  数据传输过程中的失败仍可能导致副本不一致

• Protecting storage media from failure during data transfer

  保护存储介质在数据传输过程中不会出现故障

Stable Storage的实现方法是：利用多个非易失性的存储介质存储多个副本，进行备份处理。但是仍然存在着数据传输过程中的失败导致副本数据不一致的现象，例如partial failure，目标块接受的信息不正确，total failure目标块没有被更新

所以我们需要保护存储介质在数据传输过程中不发生故障。解决方法：先将数据写入第一个物理块中，只有第一个块成功且正确的写入，才将相同的数据写入到第二个物理块中，以此类推

如果已经发现错误了，该怎么办？方法一（expensive）：比较每个磁盘块的两个副本，少数服从多数，直接覆盖。方法二（better）:记录过程中的磁盘在非易失性存储上写入。

如果检测到一个不一致的块的副本有错误（校验和错误），请通过其他副本覆盖它。 如果两者都没有错误，但有所不同，请用第一个块覆盖第二个块。

15.2.2 Database Recovery

Recovery algorithms are techniques to ensure database consistency and transaction atomicity and durability despite failures.

恢复算法是在发生故障时确保数据库一致性以及事务原子性和持久性的技术

Recovery algorithms have two parts

• Actions taken during normal transaction processing to ensure enough information exists to recover from failures

  在正常事务处理期间为确保存在足够的信息以从故障中恢复(写日志)而采取的操作

  存在tradeoff，事务处理和故障恢复性能之间的权衡

  理想的算法：恢复得很快，对事务正常操作没有影响（记录信息的时候不能消耗太多性能），即兼顾上面两个部分。

• Actions taken after a failure to recover the database contents to a state that ensures atomicity, consistency and durability

  出现failure之后，采取措施使数据库的内容恢复到某状态以确保原子性、一致性、持久性

• 恢复算法包含两部分：一部分是在事务执行时保存信息，用于日后的恢复。一部分是在故障发生之后，采取措施使得数据库恢复到原来的一致性原子性持久性状态

We assume that strict two-phase locking ensures no dirty read.

使用严格两阶段封锁协议保证没有脏数据。

基本两阶段封锁协议可以保证冲突可串行化，但是无法保证数据可恢复性（因为假如事务A和事务B保持基本两阶段封锁协议，那么假如A要进行数据写入，会在写入之后立马放开X锁，那么事务B就有可能读取A的脏数据。假设B先提交，A再回滚，那么B提交的数据将不可恢复）。

Idempotent(幂等性): An recovery algorithm is said to be idempotent if executing it several times gives the same result as executing it once.

算法恢复多次的效果是一样的。（恢复过程中可能也发生 crash，重新恢复一次即可）

15.3 Log-Based Recovery

15.3.1 Log Records

A log is kept on stable storage(稳定存储器).

The log is a sequence of log records, and maintains a record of update activities on the database.

• When transaction \(Ti\) starts, it registers itself by writing a “start” log record: \(<T_i\ start>\)

  事务开始. \(Ti\) 表示事务的 id.

• Before \(Ti\) executes write(X), writing “update” log record \(<T_i, X, V_1, V_2>\)

  事务把 X 数据项的值从 V1(old value) 改为 V2(new value).

  这个就是恢复的基础. undo 得到 old value, redo 得到 new value.

  Insert 就是 old 为空, Delete 就是 new 为空。

• When \(Ti\) finishes it last statement, writing “commit” log record: \(<T_i\ commit>\)

• When \(Ti\) complete rollback, writing “abort” log record: \(<T_i\ abort>\)

先记日志，能够实现事务执行顺序化（优化调度）

Log Example

这里当执行到 T2 回滚的时候我们会进行恢复（绿色的行表示补偿日志）比如 T2 把 C 恢复为 500, T3 把 B 恢复为 300, 最后 T2 abort. (undo 操作也会记录到日志中)

绿色部分是补偿日志，用于rollback的恢复

发生 crash 的时候 repeat history(undo 正常的操作也会重复), 随后得到并执行 undo list.(事务开始后先把事务放进去，如果提交或者回滚了就把事务移除) 只需要把 T4 undo.(假设故障前只执行到 15 行)

发生crash，先恢复现场，Repeating history，不管有没有做过，把所有的操作重新做一遍（这是没有问题的，原因在于执行update时，new value恒定，并不会得到新的数据库结果），将各个事务的每一个操作写入到undo list，遇到commit，再把该事务所有的操作去除即可。

第二个阶段是undo pass，例如T4重新将A变为100，并且记录补偿日志，做完了再写<T4 abort>.从数据库发生crash的地方，一直undo到<T4,start>。

15.3.2 Write-Ahead Logging

先写日志原则

Before a data in main memory is output to the database, the log records pertaining to data must have been output to stable storage.

在主存中的数据输出到数据库之前，必须先将与数据有关的日志记录输出到稳定存储器中。

Concurrency Control and Recover

• 对于并发事务，所有的事务共享一个 disk buffer 和 log buffer
  • 缓冲区块内能够包含一个或者多个事务更新的数据项
• 我们假定，如果事务 $Ti $修改了某个项，则在 $Ti $提交或中止之前，其他事务都不能修改同一个项。即未提交事务的更新对其他事务不可见，确保隔离性
  • 可以使用X锁，一直到事务即将提交才解锁（严格两阶段封锁协议）

Database Modification

• immediate-modification scheme(立即修改方案) 允许在事务提交之前对缓冲区或磁盘本身进行未提交事务的更新
  • 写入数据库项之前必须先写入更新日志记录
• deferred-modification schema（延迟修改方案）仅在事务提交时对缓冲区/磁盘执行更新

15.3.3 Transaction Commit

• A transaction is said to have committed when its commit log record is output to stable storage

  commit 日志经由log buffer写入到log file（stable storage）表示该事务已经完成提交

• all previous log records of the transaction must have been output already

  commit是当前事务的最后一条，显然前面的log records已经写入到log file

• Writes performed by a transaction may still be in the buffer when the transaction commits, and may be output later.

  但此时修改的数据项不一定已经写回到数据库里 。如果立刻将 block 写回磁盘可能引起大量 I/O 操作

15.3.4 Undo(撤销) and Redo（重做） Operations

特别需要注意的就是执行undo时，需要写补偿日志，<T,X,V>,在完成undo之后，需要一条log record <T abort>

一般是先全部做一遍，然后把有头无尾的undo即可

15.3.5 Checkpoints

刚刚repeating history的过程，是从日志的头部开始重演，一直重演到我们发生crush的地方。重演的操作太多，浪费太多的资源。

每隔一定的时间，或者每隔一定日志的量，就会设置一个检查点。检查点的作用是确认一下，检查点之前的所有数据和操作，都已经正确反映到数据库里面了。

Redoing/undoing all transactions recorded in the log can be very slow.

Streamline recovery procedure by periodically performing checkpointing.

重演历史可能很长。checkpoint 是确认之前的操作都已经反映到数据库里去了，这样重演的时候就可以直接从 checkpoint 开始。

• Output all log records currently residing in main memory onto stable storage.

  日志不是生成就往内存写，而是有一个日志缓冲区(stable storage)。

• Output all modified buffer blocks to the disk.

  把所有修改过的内存块写回到磁盘中

• Write a log record \(<checkpoint\ L>\) onto stable storage where L is a list of all transactions active at the time of checkpoint.

  写一个日志的标记（新的日志类型）. L 是当前正在工作的事务的表。（用来做 undo list 的初始化列表）

• All updates are stopped while doing checkpointing!!!

  做 checkpoint 的时候其他活跃事务都要停下来.这时候就存在一个tradeoff，性能会收到影响。

设置检查点时，有以下三个步骤：

1. 将所有日志中的记录存储到稳定存储器中。

2. 把所有修改过的内存块写回到磁盘中。

3. 在日志文件中写入一条记录：。其中，L表示处于该checkpoint的时候，恰好正在活跃的事务。

Example "Log File with Checkpoint : Example"

重演历史从最近的 checkpoint 重演. {T2 T4} 作为 undo list 的初始化值。

Undo List的初始值就是checkpoint中保存的正在活跃的事务。

??? Example "Example of Recovery"

设置了checkpoint，活跃的事务的初始值是T0和T1。重演历史的时候，从这个checkpoint开始即可。在重演历史的过程中，发现T1 commit，T0 abort。但是T2 start且没有commit或abort。因此，最终我们得到的Undo List只有T2。

Undo 到T2开始的地方，并且记录补偿日志即可。

checkpoint 之间的间隔应该如何确定？ 根据日志量。

15.3.6 Log Buffer & Database Buffer

Log record buffering（日志记录缓冲）：日志记录缓冲在主内存中，而不是直接输出到稳定存储。当缓冲区中的日志记录块已满或执行日志强制操作时，日志记录将输出到稳定存储。

执行日志强制通过强制所有日志记录（包括commit记录）进入稳定存储来提交事务。

我们在把数据 buffer 中的块写到数据库时，要先把块对应的日志先写到日志文件（直接把日志全部刷写一遍）。

事务提交之后有一个对日志的强制刷写。commit时，要求commit日志写入到log file，确保已经实现，并且database buffer中修改的block也写入到disk

缺点：会打断事务，事务集中，commit过多，checkpoint也过多,IO操作过多

如果事务commit写到log buffer，还不算是commit，所以发生掉电故障，log buffer丢失也没有关系。事务提交只能是commit写入到log file

组提交：可以使用单个输出操作输出多个日志记录，从而降低 I/O 成本。

**Group commit: several log records can be output using a single output operation, reducing the I/O cost. commit **

可能在日志里等待一段时间, 等到 buffer 里有足够多的日志记录再写出去。

如果事务commit写到log buffer，还不算是commit，所以发生掉电故障，log buffer丢失也没有关系。事务提交只能是commit写入到log file

• The recovery algorithm supports the no-force policy(非强制):

  i.e., updated blocks need not be written to disk when transaction commits.

  事务commit后，不要求内存中的数据立即写入到磁盘中。（较好的方式）

• The recovery algorithm supports the steal policy(窃取策略):

  i.e., blocks containing updates of uncommitted transactions can be written to disk, even before the transaction commits.

  即使在事务提交之前，也可以将包含未提交事务更新的块写入磁盘

  事务提交之前脏数据能不能被写到磁盘里去？（同样地需要先把日志写出去）

15.3.7 Fuzzy Checkpointing

Fuzzy 模糊

做 checkpoint 的时候我们如果要求其他活跃事务都停下来，一次性把脏数据都刷写出去，吞吐率会忽高忽低，系统的可用性就比较差。

Fuzzy Checkpoint ：做check point的时候，把内存中的脏页全部记下来，后面慢慢写回到磁盘去即可。此时不会造成数据库系统短暂的停顿

check point设置之后，脏页慢慢写回到磁盘中去的过程中，当脏页全部写出后，该check point变为一个成功的check point。在硬盘上面，有一个指针last_checkpoint，指向最后一个成功的check point。Repeating history的时候，从最后一个成功的check point开始。

• Temporarily stop all updates by transactions
• Write a \(<checkpoint\ L>\) log record and force log to stable storage
• Note list M of modified buffer blocks
• Now permit transactions to proceed with their actions
• Output to disk all modified buffer blocks in list M

15.3.8 Failure with Loss of Nonvolatile Storage

要从磁盘故障中恢复，从最近的转储中恢复数据库。

查阅日志并重做转储后提交的所有事务

可以扩展以允许事务在转储期间处于活动状态；称为模糊转储或联机转储。类似于模糊检查点

15.4 Recovery with Early Lock Release and Logical Undo Operations

15.4.1 Logical Undo Logging

之前，采取的是严格两阶段封锁协议（不读脏数据），即在一个事务提交之前，这个事务修改过的数据不会被其他事务读取或写入

现在，我们可以针对一般两阶段封锁协议（允许早放锁），提供数据恢复算法。一般两阶段封锁协议，支持一个事务还未提交的时候，其写入过的数据就可以被其他事务再次写入。

如果早放锁，后续恢复为 old value 可能没有意义。

比如存款 100, 转入 100. 那么我们恢复为 100(物理撤销) 就没有意义。这个时候应该采用逻辑撤销，即如果 a+=100, 恢复时就应该 a-=100.

逻辑undo是执行反操作，物理undo是执行恢复成原来的值。但是早放锁，意味着别人能够读取你最新写入的数据，会在此基础上发生更改，如果恢复成原值，意味着你忽略了更改，这显然是不对的。所以我们执行逻辑undo，执行反操作

如 B+ 树的插入和删除操作。

我们需要对逻辑操作记日志。

和之前的transaction commit/abort类似，对应的存在operation-begin和operation-end。如果operation-end存在，还需要包含logic undo U，记录如何恢复

!!! Example "Transaction Rollback with Logical Undo"

例如，对C进行更改的时候，做了一个+（-100）的操作。这时候，要记录一个日志：

operation-end 后面跟的(C, +100)表示，要恢复这个操作，需要给C加100。（要撤销操作应怎么做）。

这样记录的原因是：假如给C减去100的操作没有完成，即

还未记录的时候，就发生了crush。那么，此时就要对C进行物理Undo，直接把C由600恢复为旧数据700即可。

在这句话后面：

---

T0 事务决定abort。

此时，对T0事务进行Undo操作，并记录补偿日志如下：

C 加上100，而不是恢复为700。

需要把每个操作的日志项记录下来（开始和结束）. C 表示自加操作。这里在 end 时会记录 logical undo 的操作(减法撤销对应加法)

注意我们是在 end 的时候记录逻辑撤销的方法，如果这个操作还没有结束，那么我们只能物理撤销。

这里我们早放锁了，没有遵循严格两阶段放锁协议。在 T0 还没有提交的时候 T1 就对数据进行了修改.

恢复中做的是物理撤销(old+new), begin/end 这些日志就不需要记录了。

!!! Example "Failure Recovery with Logical Undo"

发生crush之后，先从check point开始向下重现历史，得到Undo List：T1、T2。

然后，从crush的地方，Undo到T1事务开始的地方。由于crush的地方操作O5还没有完成，因此对C数据进行恢复的时候，进行物理Undo就可以。

因此，先做物理Undo，将C设置回400，然后补偿日志中记录；再回滚操作O4，对C自增300，因此此时C变为700，也要记录在补偿日志中；然后在补偿日志中记录。

最后，将B设置回2050，并记录在补偿日志中。最后，记录。

注意第五题，redo之后的D的值为97，恢复时执行+1操作，得到的结果为98，而不是99

注意第六题，增加<T2,D,97,98>; <T2 , operation-abort>, <T2,B,20>, <T2 abort>

15.5 ARIES Recovery Algorithm

ARIES is a state of the art recovery method.

15.5.1 ARIES Data Structures

• Log sequence number (LSN) identifies each log record

  • Must be sequentially increasing 顺序递增

• Page LSN

  • 每一个内存页中，都有一个Page LSN，用来标记这个页最近反映的是哪一个日志项修改的结果。

• Log records of several different types

• Dirty page table

  • 脏页表记录在日志当中，在设定CheckPoint的时候，当前的内存中脏页的表，需要记录下来。
  • 每一个脏页表中的页，都有一个Page LSN，反映当前页是哪一个日志项最后修改了它；

Page LSN

每一个内存页中，都有一个Page LSN，用来标记这个页最近反映的是哪一个日志项修改的结果。

如果需要修改页面，需要以下步骤：

• X-latch the page, and write the log record
• Update the page
• Record the LSN of the log record in Page LSN 在 Page LSN上记录log record的LSN
• Unlock page

Page LSN 在恢复期间用于防止重复重做，从而确保幂等性

Log Record

• LSN表示该条日志的编号；

• TransID表示该条日志对应的事务是什么。

• UndoNextLSN表示，如果要Undo这一个事务，下一个需要Undo的日志项是什么。把所有相同事务的Undo项串起来，方便Undo的加速。

  例如undo某一个特定的transaction时，把该transaction的操作串行起来，一次性undo

• RedoInfo表示重复历史的相关信息。

上面，日志项一项一项地记下来，4’为4 Undo的结果，也就是4的补偿日志。4’指向3表示，记录完补偿日志4’，下一个需要Undo的日志项是3。

Dirty Page Table

Dirty Page Table: List of pages in the buffer that have been updated

用于表示buffer中已经被修改的数据页

• PageLSN of the page

• RecLSN is an LSN such that log records before this LSN have already been applied to the page version on disk

  每一个页还会记录一个Rec LSN，反映这个数据页到达了磁盘之前，是哪一个日志项最后修改了它。

ARIES Data Structures

stable data表示正确反映到数据库中的内容，对于ID=7200的页，最后更改这一页的日志的编号为4404.但是在database buffer中，ID=7200的页，最后更改这一页的日志的编号为7565，这表明这一页既在内存中，又被日志更改。

stable log（PrevLSN and UndoNextLSN fields not shown）中，对于7565（LSN）这条日志记录，表示对于事务T143，将编号为7200页的第二个数据，由60改为80.对于7563这条日志记录，表示对于事务T145，事务begin

日志记录，有的在Stable Storage中，有的在内存中。例如，对于编号为4894的数据页，数据内存中显示最后对这一数据的更改是编号7567的日志，对应log buffer中的7567日志项

脏页表：例如，记录7200 7565 7565表示，缓冲区中page_ID为7200的页是脏的，最新修改它的是7565这个日志，并且从7565这条日志之后的更改，都没有反映到数据库系统之中。

又例如，4894 7567 7564表示，缓冲区中page_ID为4894的页是脏的，最新修改它的是7567这个日志，但是，从7564这个日志开始，更改就没有反映到数据库中了。看log buffer，7567日志项还没有写入到stable log

这边特别注意Page LSN和Rec LSN的不同之处

可以理解为：Rec LSN记录的是磁盘中，最后一次对该数据产生更改的日志项编号；

Page LSN 记录的是日志内存中，最后一次对该数据产生更改的日志项编号。

一个是磁盘中，一个是日志内存中，日志内存还没有写入到stable log中

• Checkpoint log record

  • Contains:

    • Dirty Page Table and list of active transactions

    • For each active transaction, Last LSN, the LSN of the last log record written by the transaction

      要记最近的事务项（从哪里开始恢复）

      做check point时，需要记录以下内容：1. 当前活动事务表 2. 脏页表 3. 对于每一个当前活动的事务，需要记录修改该事务最近的一个日志项Last LSN

  • Fixed position on disk notes LSN of last completed checkpoint log record

• Dirty pages are not written out at checkpoint time

  Instead, they are flushed out continuously, in the background

  脏页不会在 check 的时候写出去。

• Checkpoint is thus very low overhead can be done frequently

15.5.2 ARIES Recovery Algorithm

• Analysis pass

  • Which transactions to undo (undo-list)
  • Which pages were dirty (disk version not up to date) at time of crash
    得到 dirty page table.
  • RedoLSN: LSN from which redo should start
    真正的 redo 要从哪里开始(RecLSN 的最小值就是 redo 的起点)

  1. 得到undo list，哪些事务需要撤销undo

  2. 得到dirty page table。也就是当crash发生时，发生update但是么有写入到数据库的脏页。check point处得到的dirty page table还不是最新，因为距离crash发生还执行新的update，所以我们需要从check point开始向下更新

  3. 得到Redo LSN，即真正的Redo操作，应当从哪里开始（Repeating history的起始地点）。在ARIES算法中，Redo可能发生在check point之前，不一定在check point开始。Redo的起点是所有Rec LSN的最小值，这是因为Rec LSN表示是磁盘中最后一次对该数据产生更改的日志编号，Rec LSN之前的日志项，都已经正确地反应在数据库中。所以我们从Rec LSN的最小值开始执行repeat history

• Redo pass

  RecLSN and PageLSNs are used to avoid redoing actions already reflected on page.

  用来优化，有些日志不用 redo(没有意义)

  从所有脏页表中Rec LSN中最小的那个日志项（Redo LSN）开始，repeat history。

• Undo pass

  和前面的原理相同，利用Undo List，直到Undo 到Undo List中所有事务到达开始（begin）的地方。

Example

crash 之后，得到上页的 Dirty Page Table 和 Active TXN Table 以及磁盘里的日志。

Example

check point中记录了什么？

1. 活动事务表：T145，并且最后对事务T145进行修改的是Last LSN是7567

2. 脏页表：

   • 最新的对数据页4894进行修改的日志项时7567，正确反应到磁盘中的最后一个对4894页进行修改的日志项时7564
   • 最新对页号7200的页产生更改的是日志项7565，而正确反映到磁盘中的最后一个对7200页产生更改的日志项是7565；

3. Analysis：从最近的check point开始，分析到发生crash的地方，这一过程中需要更新脏页表，并得到Undo List，以及Redo LSN

   这是因为check point处的脏页表不是最新的发生在crash处的脏页表，需要先继续执行

   例如，首先碰到T146 begin, 因此在活动事务表中记录一项T146；然后碰到T146的修改操作，然后在脏页表中记录一项T146。 2390 7570 ？

4. Redo 阶段

   Redo的起点，是更新过后的脏页表张，Rec LSN的最小值

5. Undo 阶段

   Undo的结束点，在Undo List中开始最早的事务的开始点（此处undo的事务是T145，到begin位置）。并且对于每一事务的undo，由于各事务的日志项存在undonextLSN，所以undo的时候不是一条一条的undo，而是跳跃性的。

总结来说：在生成Check Point的时候，Check Point中会记录当前活动事务表，和脏页表

在当前活动事务表中，记录了活动事务，以及最后一次对该事务的更改，处于哪一个日志项当中。在脏页表中，记录了页号，以及Page LSN（表示这个页最后被更改，处于哪一个日志项）、Rec LSN（表示这个页最后被存储，处于哪一个日志项）。

在数据恢复的过程中，第一阶段是分析阶段，从上一个有效的检查点开始，一直分析到crush发生的地方。在分析的过程中，不断更新当前活动事务表，以及脏页表。

• 假如遇到一个事务开始了，那么就在当前活动事务表中增添一项，遇到一个事务commit或者abort了，就在当前活动事务表中减少一项；
• 假如遇到某个日志项对某一页产生了更改，就要更新脏页表中的Page LSN，
• 假如遇到某个日志项对脏页表中没有的页号的页产生了更改，就要在脏页表中添加一项，Page LSN和Rec LSN设置为当前日志项。

最后，当分析到crash的地方，我们就得到了一个更新后的活动事务表，作为Undo List，并且得到了一个更新后的脏页表。

第二阶段是Redo阶段，Redo阶段的起点是更新后的脏页表中，Rec LSN的最小值的日志项。一直Redo到crush的地方。

第三阶段是Undo阶段，Undo阶段的起点是活动事务表中，记录的Last LSN中的最大值，从Last LSN开始，对活动事务表中的每一个事务向前进行串在一起的指针遍历，直到Undo到各个事务都经过了< start>。