恢复
1. 动机
在前面的模块中，我们讨论了事务的ACID属性。在本文中，我们将讨论如何使数据库具有故障恢复能力。我们将在本注释中学习如何实施的两个ACID属性是：
持久性：如果事务完成（提交），我们将永远不会丢失事务的结果。
原子性：事务中的所有或所有操作都将保持。这意味着我们永远不会让数据库处于中间状态。例如，在CalCentral中交换类。有两个操作：删除旧类和添加新类。如果数据库在添加新类之前崩溃，您实际上不想从旧类中删除。
2 .强制非强制
如果我们使用强制策略，持久性可以是一个非常简单的属性。强制策略声明，当事务完成时，在事务提交之前，强制将所有修改的数据页发送到磁盘。这将确保持久性，因为磁盘是persistent1；换句话说，一旦页面进入磁盘，它将被永久保存。这种方法的缺点是性能。我们最终做了很多不必要的写入。我们更喜欢的策略是不强制，即只在页面需要从缓冲池中退出时才写回磁盘。虽然这有助于减少不必要的写入，但会使持久性复杂化，因为如果在事务提交后数据库崩溃，某些页面可能尚未写入磁盘，因此会从内存中丢失，因为内存是易失性的。为了解决此问题，我们将在恢复期间重新执行某些操作
3 Steal/No-Steal
类似地，使用No-Steal策略很容易确保原子性。No-Steal策略规定，在事务提交之前，不能从内存中逐出页面（从而写入磁盘）。这确保了我们不会让数据库处于中间状态，因为如果事务没有完成，那么它的任何更改实际上都不会写入磁盘并保存。这个政策的问题在于它限制了我们如何使用内存。我们必须将每个修改过的页面保留在内存中，直到事务完成。我们更希望有一个Steal策略，允许在事务完成之前将修改过的页面写入磁盘。这将使执行原子性变得复杂，但我们将通过在恢复期间撤消错误操作来解决此问题。
4 Steal, No-Force
回顾一下，我们选择使用两种策略（steal，no-force），这使得很难保证原子性和持久性，但可以获得最佳性能。本说明的其余部分将介绍如何确保原子性和耐用性，同时使用steal、No-Force
5.提前写入日志
为了解决这些复杂问题，我们将使用日志记录。日志是描述数据库所做操作的一系列日志记录。
5.1更新日志记录
每个写操作（SQL插入/删除/更新）都将获得自己的日志更新记录。
更新日志记录如下所示：
这些字段包括：
•XID：事务ID-告诉我们哪个事务执行了此操作
•页面ID：已修改的页面
•偏移量：页面上数据开始变化的位置（通常以字节为单位）
•长度：更改了多少数据（通常以字节为单位）
•旧数据：原始数据（用于撤销操作）
•新数据：数据更新为什么（用于重做操作）
5.2其他日志记录
我们将在日志中使用其他一些记录类型。随着对这些字段的需求变得明显，我们将在整个注释中将这些字段添加到这些日志记录中。
•提交：表示事务正在启动提交过程
•中止：表示事务正在启动中止过程
•结束：表示事务已完成（通常意味着它已完成提交或中止）
5.3 WAL要求
和常规数据页一样，日志页需要在内存中操作，但需要写入磁盘以永久存储。提前写入日志（WAL）对何时必须将日志写入磁盘提出了要求。这两条规则如下：
日志记录必须在相应的数据页写入磁盘之前写入磁盘。这就是我们将如何实现原子性。对此的直觉是，如果先写入数据页，然后数据库崩溃，我们就无法撤消操作，因为我们不知道发生了什么操作！
事务提交时，所有日志记录都必须写入磁盘。这就是我们将如何实现持久性。直觉是，我们需要持续跟踪提交的事务执行了哪些操作。否则，我们将不知道需要重做哪些操作。通过将所有日志写入磁盘，我们可以准确地知道在修改后的数据页写入磁盘之前，如果数据库崩溃，我们需要重做哪些操作！
6 WAL实施
为了实现预写日志记录，我们将在日志记录中添加一个名为LSN的字段，它代表日志序列号。LSN是一个唯一的递增数，有助于表示操作顺序（如果您看到LSN=20的日志记录，则该操作发生在LSN=10的记录之后）。在这个类中，LSN将每次增加10，但这只是一个约定。我们还将在每个日志记录中添加一个prevLSN字段，该字段存储来自同一事务的最后一个操作（这将有助于撤消事务）。数据库还将跟踪存储在RAM中的flushedLSN。flushedLSN跟踪已刷新到磁盘的最后一条日志记录的LSN。刷新页面时，表示页面已写入磁盘；这通常还意味着我们将页面从内存中逐出，因为我们不再需要它了。flushedLSN告诉我们，之前的任何日志记录都不应写入磁盘，因为它们已经存在。日志页通常附加到磁盘上的上一个日志页，因此多次写入相同的日志意味着我们存储了重复数据，这也会扰乱日志的连续性。我们还将向每个数据页添加一段元数据，称为pageLSN。页面LSN存储上次修改页面的操作的LSN。我们将使用它来帮助告诉我们哪些操作实际进入磁盘，哪些操作必须重做。
7.不等式练习
在允许将第一页刷新到磁盘之前，必须保持什么不等式？
pageLSNi ___ flushedLSN
答复:≤, 这来自WAL的第一条规则——在将数据页刷新到磁盘之前，必须刷新相应的日志记录。仅当上次修改数据页的操作的LSN小于或等于flushedLSN时，数据页才会刷新到磁盘。换句话说，在将页面i刷新到磁盘之前，必须将修改页面i的所有操作的日志记录刷新到磁盘。
8.中止交易
在从崩溃中恢复之前，让我们先了解数据库如何中止正在进行的事务。我们可能希望由于死锁而中止事务，或者用户可能因为事务花费太长而决定中止。如果操作违反某些完整性约束，也可以中止事务，以保证ACID中的一致性。最后，由于系统崩溃，事务可能需要中止！我们需要确保，一旦中止过程完成，所有操作都不会保留到磁盘。
8.1中止和CLR日志记录
我们要做的第一件事是在日志中写入一条中止记录，表示我们正在启动进程。然后，我们将从该事务日志中的最后一个操作开始。我们将撤消事务中的每个操作，并为每个撤消的操作将CLR记录写入日志。CLR（补偿日志记录）是一种新类型的记录，表示我们正在撤消特定操作。它本质上与更新记录相同（它存储以前的状态和新状态），但它告诉我们，该写操作是由于中止而发生的。
9 恢复数据结构
我们将保留两个状态表，以使恢复过程更容易一些。第一个表称为事务表，它存储关于活动事务的信息。事务表有三个字段：
•XID：交易ID
•状态：运行、提交或中止
•lastLSN：此交易最近一次操作的LSN
交易表示例如下：
我们维护的另一个表称为脏页表（DPT）。DPT跟踪哪些页面是脏的（回想以前的许多模块，脏意味着页面已经在内存中修改，但尚未刷新到磁盘）。这些信息将非常有用，因为它将告诉我们哪些页面具有尚未进入磁盘的操作。DPT只有两列：
•页面ID
•recLSN：第一个弄脏页面的操作
DPT的示例如下：
需要注意的是，这两个表都存储在内存中；因此，当从崩溃中恢复时，必须使用日志重建表。我们将在本说明的后面讨论一种使这更容易的方法（检查点）。
10更多不等式问题
- 填写以下等式以强制执行WAL规则，即在事务T提交之前，必须将所有日志刷新到磁盘：
flushedLSN ___ lastLSNT
回答：≥ 如果flushedLSN 大于事务的最后一次操作，则我们知道该事务的所有日志都在磁盘上。
对于DPT中的页面P，填写以下不等式，该不等式必须始终为真：
recLSNP ___ in memory pageLSNP
回答:≤ 如果页面位于脏页表中，则该页面必须是脏的，因此上次更新一定没有将其更新到磁盘。recLSN是第一个弄脏页面的操作，因此它必须小于修改该页面的最后一个操作。
recLSNp ____ 磁盘上的recLSNP页
答案：>如果页面是脏的，则导致页面变脏的操作（recLSN）一定没有将其发送到磁盘，因此它一定是在将页面发送到磁盘的操作之后
那一页。
11撤消日志记录
我们已经介绍了数据库如何写入日志以及在正常运行时如何中止事务的大量背景信息。现在，让我们最终了解所有这些日志记录的原因——从失败中恢复。一种可能的恢复机制是撤消日志记录。请注意，撤销日志记录实际上并没有使用我们之前讨论过的提前写入日志记录（WAL）（我们稍后将回到这一点）。此外，它在缓冲池管理方面使用强制和窃取机制。