核心问题：数据库在崩溃后，如何恢复到一致状态。
问题模型
- 系统故障发生时必须保护数据，可用方法包括日志和备份。
- 多个没有错误的查询或修改同时执行时，不能让数据库被破坏。
故障处理要求：
| 场景 | 处理要求 |
|---|---|
| 错误数据输入 | 有些能通过约束/触发器发现，有些不能 |
| 介质故障 | 轻微故障可用校验，严重故障需要 RAID、归档、冗余副本 |
| 灾难性故障 | 依靠归档和分布式冗余 |
| 系统故障 | 使用非易失日志记录数据库变更，并在必要时恢复 |
事务
数据库通常被多个用户或进程同时访问，包括查询和修改。与操作系统不同，DBMS 必须避免多个进程之间产生有害交互。
例如，两个人几乎同时从一个银行的不同 ATM 中取钱。DBMS 必须保证一个账户扣款不会被另一个操作覆盖或丢失。类比为两个人同时编辑同一文档，后写入的人可能覆盖前一个人的修改。
事务：由数据库查询和/或修改组成的过程。通常带有并发控制方面的强性质。SQL 中可以由单条语句隐式形成，也可以由程序员显式控制。
定义事务
显式方式：
|
|
以BEGIN TRANSACTION开始，开始，COMMIT提交，ROLLBACK回滚。
COMMIT表示事务正常结束，修改永久生效。该事务对数据库的修改现在成为数据库中的永久修改。ROLLBACK表示事务异常结束，撤销已做操作，回到事务开始前。中止后该事务对数据库没有效果。
除零、违反约束等错误也可能导致回滚，即使没有显式请求。
隐式方式：每条查询或修改语句就是一个事务。
ACID事务
ACID事务满足以下特性：
| 特性 | 定义 |
|---|---|
| 原子性（Atomic） | 事务要么全做，要么全不做，由恢复机制实现 |
| 一致性（Consistency） | 保持数据库约束，由并发控制机制保证 |
| 隔离性（Isolated） | 对用户看起来像只有一个进程在执行，由并发控制保证 |
| 持久性（Durable） | 提交后的效果在崩溃后仍存在，由恢复机制保证 |
事务的执行
数据库由若干元素组成。不同数据库系统对元素的粒度定义不同，常见包括：关系、磁盘块/页、单个元组或对象。
数据的完整性和正确性
数据完整性或正确性条件希望数据在所有时刻都是准确/正确的。数据库具有状态，可以区分一致状态和不一致状态。
- 完整性/一致性约束：数据必须满足的谓词。例如：$x$ 是关系 $R$ 的键；某个值必须在另一个表中存在；账户余额不能为负等。
- 正确性原则：数据库有状态，状态是每个元素的值，一致状态满足所有约束。如果一个事务在没有其他事务和系统错误的情况下，从一致状态开始执行，那么结束后也应处于一致状态。
事务可以看作一组保持一致性的动作。从一致状态的数据库开始，事务完成后应回到一致状态的数据库。如果事务 $T$ 从一致状态开始，并且 $T$ 独立执行，那么 $T$ 会留下一个一致状态。
事务的原语操作
事务的原语操作涉及三个地址空间：磁盘、缓冲区/内存、事务局部变量。
三个地址空间：
- 磁盘块空间：非易失，可能共享。
- 数据库缓冲区：内存中的块副本。
- 事务变量空间：事务执行时使用的局部变量。
数据库恢复需要区分数据在磁盘、内存和变量中的位置。
| 原语操作 | 操作步骤 |
|---|---|
INPUT(x) |
把包含x的块从磁盘读到缓冲区 |
OUTPUT(x) |
把包含x的块从缓冲区写到磁盘 |
READ(x,t) |
必要时先INPUT，然后把x读入变量t |
WRITE(x,t) |
把变量t写回缓冲区中的x |
undo日志
日志是日志记录的文件，每条记录说明某个事务做了什么。可以把日志想象成只能追加写入的文件。
undo日志通过撤销未完成事务造成的修改来修复数据库状态。
日志记录形式
| 日志 | 记录内容 |
|---|---|
<START T> |
事务 $T$ 开始 |
<COMMIT T> |
事务 $T$ 完成提交 |
<ABORT T> |
事务 $T$ 中止 |
<T, X, v> |
记录值的变化，表示事务 $T$ 改变了数据库元素 $X$，$X$ 原来的值是 $v$ |
undo日志只记录旧值，因为恢复时要把未完成事务改回旧值。
日志先写在内存中，不是每个动作都立刻写到磁盘。因此它主要支持“撤销”。
undo日志规则
- 每个修改动作生成包含旧值的 undo 日志记录。
- 在 $X$ 被写入磁盘前，相关日志记录必须已在磁盘上。
- 在
commit记录写入磁盘前，该事务修改过的所有数据库元素必须已写入磁盘。
为了强制将日志记录写到磁盘，日志记录需要一条刷新日志命令FLUSH LOG，告诉缓冲区管理器：将以前没有拷贝到磁盘的日志记录、从上一次拷贝以来已发生修改的日志记录拷贝到磁盘。
事务管理器需要告诉缓冲区管理器：在某个数据库元素上执行 OUTPUT 动作
undo恢复规则
从日志末尾向前扫描：
- 找到有
start但没有commit/abort的未完成事务集合 $S$。 - 逆序扫描
<Ti,X,v>，若 $T_i$ 属于 $S$，则把 $X$ 写回旧值 $v$ 并输出。 - 对每个 $T_i \in S$ 写入
<Ti,abort>。
redo日志
为什么使用redo日志：
- undo日志先将所有改变的数据写入磁盘，再提交事务，造成大量磁盘读写。
- 为了节省磁盘I/O：改变的数据暂时只留在主存中。当有崩溃事件发生时，使用 redo 日志恢复。
redo 日志和 undo 日志的不同：
| undo日志 | redo日志 |
|---|---|
| 撤销未完成事务的影响，在恢复过程中忽略已提交的事务 | 忽略未完成的事务，重复已提交事务所做的更改 |
在COMMIT日志到达磁盘之前写入改变的数据库元素到磁盘 |
在任何改变的值到达磁盘之前写入COMMIT记录到磁盘 |
| 记录旧值 | 记录新值 |
redo日志规则
<T, X, v>：事务 $T$ 为数据库元素 $X$ 写入新值 $v$。
当使用 redo 日志时，与事务相关的材料写到磁盘的顺序是：
- 指出被修改元素的日志记录（更新 redo 日志）
COMMIT日志- 改变的数据库元素自身（更新数据库）
redo恢复规则
只要日志没有<COMMIT T>记录，则事务 $T$ 对数据库所做的更新都没有写到磁盘上。（日志先行）
恢复策略：
- 确定提交的事务
- 从起始处开始扫描日志，每遇到一个
<T, X, v>：若 $T$ 是未完成事务，恢复时视为从未发生；若 $T$ 是已完成事务，写 redo 日志中的新值 $v$ 到磁盘上 - 对于未完成事务，写入
<ABORT T>并FLUSH LOG
undo/redo日志
undo/redo 日志：
- 通过保存更多的信息在日志中，提供更高的灵活性
<Ti, X, v, w>：事务、数据库元素、旧值、新值
undo/redo 日志的恢复：
- 从前往后，重做已提交的事务
- 从后往前，撤销未提交的事务
三种日志的特点比较：
| 类型 | 特点 |
|---|---|
| 纯Undo日志 | 只记录旧值。要求：事务提交前，所有修改必须写盘。恢复时，对于未提交事务执行Undo；已提交事务无需操作。缺点：频繁刷盘，性能差 |
| 纯Redo日志 | 只记录新值。要求：事务提交后，所有修改必须立即写盘。恢复时，只需Redo已提交的事务。缺点：仍可能增加提交延迟 |
| Undo/Redo日志 | 无以上限制。提交前可刷盘，提交后也可缓存，提供了最大灵活性。因此成为主流选择 |
检查点
没有检查点时，恢复需要扫描整个日志文件（可能非常巨大）。检查点定期将内存中的脏页（被修改但未写回磁盘的页）强制写入磁盘，并记录当前所有活动事务。
作用：
- 限制恢复时需要扫描的日志范围（只需从最后一个成功检查点之后开始）。
- 加快恢复速度：检查点之前提交的事务，其所有修改已落盘，无需Redo；检查点之前未提交但已回滚的事务，无需Undo。
工作流程（以常见模糊检查点为例）：
- 写入日志记录
<CHECKPOINT_START>，记录当前所有活动事务列表。 - 强制将所有脏页刷入磁盘（此过程可能持续一段时间）。
- 写入日志记录
<CHECKPOINT_END>。