基于 undo/redo 日志的恢复算法缺陷、ARIES 优化策略、脏页表作用、活跃事务表和 PrevLSN

ARIES 介绍

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）是数据库管理系统中一种先进的数据恢复算法，专门用来在系统崩溃后确保数据的一致性和完整性。ARIES 的设计旨在解决传统 undo/redo 日志机制中的一些缺陷，使得数据恢复更高效、更可靠。

ARIES 算法的核心思想和目标

ARIES 的主要目标是：

1. 支持故障恢复：在系统崩溃后，可以将数据库恢复到最近的一致状态。
2. 保持高效：减少恢复时间，提高系统整体性能。
3. 支持并发：允许多个事务并发运行，同时能有效处理事务间的数据冲突和依赖。

ARIES 的主要组件

ARIES 算法引入了几个关键数据结构和机制：

1. 日志（Log）：记录事务的每一步操作。日志包含了操作类型、数据页的变化情况等信息，便于恢复时进行 redo 或 undo。
2. 脏页表（Dirty Page Table, DPT）：记录自上次检查点以来被修改过但尚未写回磁盘的数据页。DPT 使得系统在恢复时可以直接找到哪些数据需要 redo，从而节省了恢复时间。
3. 活跃事务表（Active Transaction Table, ATT）：记录当前活跃的事务及其状态，用于追踪哪些事务未提交，以便在恢复时进行适当的 undo 操作。
4. PrevLSN（Previous Log Sequence Number）：在日志链中每条记录包含指向上一个日志条目的指针，方便在回滚时倒序查找。

ARIES 的三阶段恢复流程

ARIES 的恢复过程可以分为以下三个阶段：

1. 分析阶段（Analysis）：
   • 通过读取日志和检查点来恢复 DPT 和 ATT，从而确定哪些页面需要 redo、哪些事务需要 undo。
   • 此阶段生成恢复的“路线图”，记录哪些页面是脏页、哪些事务尚未提交等信息。
2. 重做阶段（Redo）：
   • 根据 DPT 和日志内容，重做自上次检查点以来的所有必要操作，确保所有数据页都恢复到崩溃前的最新状态。
   • Redo 仅作用于需要更新的页面，避免无效的操作，从而提升了恢复效率。
3. 回滚阶段（Undo）：
   • 根据 ATT 回滚所有未完成的事务，通过反向应用日志中的 undo 记录，确保未提交事务的操作被撤销。
   • 使用 PrevLSN 跟踪并执行回滚的顺序，避免事务间相互干扰。

ARIES 算法的优化策略

为了进一步提高恢复效率，ARIES 在传统的日志机制上做了优化，包括：

• 检查点机制：通过设置检查点，减少恢复时需要分析的日志条数，缩短了恢复时间。
• 精确的 Redo 操作：通过 DPT 仅针对脏页进行 redo，避免重复操作。
• 并发事务处理：利用日志中的 PrevLSN、ATT 等信息，确保多个事务可以并发进行，并且即使出现崩溃也能保证一致性。

传统 undo/redo

传统的 undo/redo 日志机制是一种数据库事务管理和恢复技术，用于在数据库系统发生故障或崩溃时确保数据的一致性和完整性。它通过记录事务操作的“前镜像”（before image）和“后镜像”（after image）来支持数据库的恢复。传统的 undo/redo 日志机制包括以下两个部分：

1. Undo 日志

• 定义：Undo 日志记录事务更改之前的数据状态（即“前镜像”），用于在事务回滚时恢复数据到事务执行前的状态。
• 工作方式：在事务对数据页进行任何更改前，数据库会将该数据页的原始状态记录到日志中。
• 作用：当事务失败或系统崩溃时，数据库可以使用 Undo 日志将所有已开始但未提交的事务操作回滚（撤销），恢复到一致的状态。
• 示例：假设事务 T1 将数据项 A 的值从 10 改为 20，那么数据库在执行更改前会记录“将 A 从 10 改为 20”的 undo 日志条目。当 T1 失败时，系统可以利用 undo 日志将 A 的值恢复为 10。

2. Redo 日志

• 定义：Redo 日志记录事务更改之后的数据状态（即“后镜像”），用于在系统崩溃后重新应用已提交的事务。
• 工作方式：在事务完成并提交后，数据库会将修改后的新值写入 Redo 日志，以便在恢复过程中重复这些操作。
• 作用：在系统崩溃后，数据库通过 Redo 日志重新执行已提交的操作，以确保所有提交的事务操作得到反映，保持数据库一致性。
• 示例：如果事务 T1 已提交并将数据项 B 从 15 改为 25，Redo 日志会记录“将 B 的值改为 25”。系统重启时，即使 B 的数据页没有被写入磁盘，系统也可以通过 Redo 日志将 B 恢复到 25。

传统 undo/redo 日志机制的恢复流程

当系统崩溃时，传统的 undo/redo 机制按以下步骤恢复数据：

1. 检查提交状态：确定在崩溃发生前，哪些事务已提交、哪些未提交。
2. Undo 操作：对未提交的事务执行 Undo 操作，将数据恢复到其初始状态，确保未完成的事务对数据库无影响。
3. Redo 操作：对已提交的事务执行 Redo 操作，确保所有已提交的事务在系统中得到持久化应用。

传统 undo/redo 日志机制的缺陷

传统的 undo/redo 机制虽然简单，但也存在一些限制和缺陷：

• 恢复效率低下：恢复过程中需要扫描所有日志条目来确认哪些需要 redo 或 undo，特别是在没有检查点优化时效率较低。
• 对并发事务支持不足：无法有效处理多个事务并发写入的复杂情况，容易导致资源竞争或数据一致性问题。
• 未优化的数据恢复：在 redo 阶段可能会对不需要恢复的数据页重复执行操作，增加了恢复时间。

总结

传统 undo/redo 机制作为一种基本的数据恢复方法，在简单的单一事务环境下能提供数据一致性保障，但在复杂系统和高并发场景下则难以高效应对。因此，ARIES 等优化算法被引入，以改善恢复效率并支持更高的并发性。

ARIES 相较于 undotodo

1. 恢复效率更高

• 脏页表（Dirty Page Table, DPT）：ARIES 使用脏页表记录哪些页面被修改但尚未写回磁盘。在恢复时，只需要针对这些脏页执行 redo 操作，避免了对所有日志条目的扫描，提高了恢复效率。
• 检查点机制：通过周期性地创建检查点，ARIES 在恢复时可以从最近的检查点开始分析，而无需从日志的起点读取，进一步缩短了恢复时间。

2. 精确的 Redo 和 Undo 操作

• Selective Redo：ARIES 中的 Redo 阶段只针对那些确实需要重做的页面和数据，避免了重复执行不必要的 redo 操作，从而提升了恢复的精确性和效率。
• 逻辑回滚（Logical Undo）：ARIES 采用逻辑回滚机制，通过 PrevLSN 指针将未完成的事务逐步回滚，能够精确追踪并恢复崩溃时的状态，确保数据的一致性。

3. 更强的并发支持

• 活跃事务表（Active Transaction Table, ATT）：记录所有活跃的事务及其状态，使系统能够有效处理多个事务并发操作。ARIES 通过 ATT 管理事务的顺序和依赖关系，确保事务间不产生冲突，提高了并发事务的处理效率。
• 日志链（Log Chain）：每条日志记录包含指向前一条记录的 PrevLSN 指针，使得事务在回滚时可以快速访问相关日志记录，从而避免事务之间相互干扰。

4. 灵活的恢复流程

• 三阶段恢复（Analysis, Redo, Undo）：ARIES 在恢复流程中采用“分析（Analysis）、重做（Redo）、回滚（Undo）”三阶段，分别负责生成恢复策略、确保已提交的数据持久化、以及撤销未完成的事务。这种分阶段恢复方式可以根据实际情况灵活执行各个操作，适应性更强。
• 支持细粒度恢复：ARIES 在日志中记录了各个页面的更改时间、状态等信息，可以在恢复过程中根据细粒度的日志内容精准恢复，避免无关页面的恢复操作。

5. 优化的事务一致性保障

• 分离的 Undo 和 Redo 操作：ARIES 的设计保证了即使在系统崩溃时，redo 和 undo 操作可以分离处理，不会产生冲突。因此即使事务失败或崩溃，系统也能保持一致性。
• 避免级联回滚：由于 ARIES 能够精确地管理和恢复各个事务的状态，减少了事务相互影响，避免了传统方法中可能产生的级联回滚问题（即一个事务的回滚导致其他相关事务也需要回滚）。

脏页表

脏页表（Dirty Page Table, DPT）是数据库系统中的一个重要数据结构，用于记录哪些内存页面在上次检查点之后被修改但尚未写回磁盘。它的主要作用包括：

1. 跟踪修改的页面

• 脏页表记录了自上次检查点以来被修改过的所有数据页。这意味着，系统可以快速识别哪些页面需要进行重做（redo）操作，而不需要扫描所有数据页。

2. 提高恢复效率

• 在数据恢复过程中，系统只需针对脏页表中列出的页面进行重做。这大大减少了需要处理的页面数量，从而加快了恢复速度。

3. 避免不必要的 IO 操作

• 由于只处理脏页，脏页表帮助减少了不必要的磁盘写入和读取操作，优化了系统性能。

4. 支持高并发事务

• 在高并发环境中，脏页表帮助管理多个事务对页面的修改，确保系统能够有效地处理并发操作并保持一致性。

总结

脏页表在 ARIES 算法和其他现代数据库恢复机制中扮演着重要角色，通过精确跟踪被修改的数据页，提升了恢复效率和系统性能。

1. 刷回磁盘（Flush to Disk）

• 定义：将内存中的数据（如缓存或脏页）写入到永久存储设备（如硬盘）中。
• 作用：确保数据的持久性。当系统崩溃或断电时，内存中的数据可能会丢失，因此将其刷回磁盘可以确保数据不会丢失。
• 上下文：在数据库系统中，当事务提交后，通常会将该事务修改的数据刷回磁盘，以确保这些更改被永久保存。

2. 重做（Redo）

• 定义：在系统恢复过程中，将已提交事务的修改操作重新应用到数据库中，以确保这些更改在崩溃后依然存在。
• 作用：确保所有已提交的事务的结果都被持久化，尤其是在系统崩溃后重新启动时。
• 上下文：在 ARIES 算法中，重做操作是恢复过程的一部分，系统会根据脏页表和日志信息，重新执行必要的操作，以恢复数据到最新状态。

3. 回滚（Undo）

• 定义：撤销未完成或未提交事务的操作，将数据恢复到事务开始之前的状态。
• 作用：确保数据库的一致性，避免未提交事务的操作影响到其他事务。
• 上下文：在 ARIES 算法中，回滚是恢复过程中处理未完成事务的一步。

检查点

在数据库系统中，检查点（Checkpoint）是一种机制，用于定期保存数据库的当前状态，以加速系统崩溃后的恢复过程。检查点通过将一些数据和日志信息写入磁盘，使得恢复算法在崩溃时可以从最近的检查点开始，而不是从日志的开头扫描，大大减少了恢复时间。

检查点的工作方式

检查点操作通常包括以下步骤：

1. 暂停部分事务操作：在开始检查点时，系统会暂停新的写操作，确保数据的一致性。
2. 记录活跃事务表（ATT）和脏页表（DPT）：系统记录当前活跃的事务和自上次刷入磁盘以来被修改的脏页。
3. 将脏页刷入磁盘：将脏页表中的数据页写入磁盘，以便在崩溃时不需要重做这些修改。
4. 创建检查点记录：系统在日志中写入检查点记录，包含活跃事务表和脏页表的信息。

检查点的作用

• 减少恢复时间：在崩溃时，系统可以从最近的检查点恢复，而不是遍历整个日志文件。
• 确保数据一致性：通过记录活跃事务和脏页信息，检查点有助于维持系统的原子性和一致性。
• 优化性能：通过批量将脏页写入磁盘，检查点减少了频繁的写操作，提高了系统的整体性能。

模糊检查点（Fuzzy Checkpoint）

为了不影响系统的运行性能，有些数据库系统采用“模糊检查点”策略，即在创建检查点时允许其他事务继续运行，避免完全暂停写操作。这种方法确保在系统高负载时也能创建检查点，从而保持数据恢复能力。

lsn

LSN（Log Sequence Number，日志序列号）是数据库系统中用于标识日志记录的唯一编号。每条日志记录都会分配一个 LSN，通常以递增的顺序生成。LSN 在数据库的恢复、检查点和事务管理中发挥着关键作用。

LSN 的作用

1. 标记日志顺序：每条日志记录都有一个独特的 LSN，表示它在日志中的位置或顺序。这样可以准确跟踪每条记录的写入顺序。
2. 支持恢复操作：在数据库恢复过程中，系统可以利用 LSN 来确定哪些数据页需要重做（Redo）或回滚（Undo）。只要有 LSN 的记录，系统就可以根据其顺序，决定执行的恢复操作。
3. 维护数据一致性：每个数据页也会记录一个与之关联的 LSN，称为 pageLSN。通过对比数据页的 pageLSN 和日志中的 LSN，系统可以判断该页是否已经同步到最新状态。

常见的 LSN 类型

• flushedLSN：指示已写入磁盘的最大 LSN，用于判断哪些日志记录已经被安全地写入磁盘。
• pageLSN：记录在数据页上的最新更新 LSN，用于判断该页是否需要更新。
• lastLSN：指每个事务的最后一条日志记录的 LSN，便于追踪事务状态。
• recLSN：脏页表中的一个字段，指示导致该页变脏的第一条日志记录的 LSN，用于确定需要 redo 的最早位置【35†source】【36†source】。

总结

LSN 通过唯一标识和顺序控制，为数据库的故障恢复、事务一致性和检查点维护提供了基础保障。

举例说明（插入 ppt

场景

假设数据库在处理多个事务时崩溃了。我们在重启时会进入恢复过程，为了恢复数据库到崩溃前的状态，需要依靠日志记录来重做（redo）某些事务操作。而“脏页表”（Dirty Page Table, DPT）是帮助我们判断哪些页面需要重做的一个关键工具。

1. 什么是脏页和脏页表？

• 脏页：脏页是指曾被修改过但修改尚未写回磁盘的数据页。假设数据库某条数据被修改后只保存在内存中，尚未存入磁盘，那么这个数据页就叫“脏页”。
• 脏页表：脏页表在崩溃时刻记录了哪些页是脏的。每个脏页都有一个 RecLSN（最早的日志序列号，指的是该页从什么时候开始变“脏”），用于帮助判断页面的状态。

在恢复过程中，脏页表的作用是：只需要对脏页进行重做，因为只有它们可能包含未写回磁盘的最新修改。

2. 日志记录的 pageID 不在脏页表中，不需要重做

这是判断重做需求的第一个条件：

• 如果某条日志记录指向的 pageID（页面编号）不在脏页表中，说明这条记录的修改已经写入了磁盘。这是因为，只有未写入磁盘的修改才会导致页面被标记为“脏页”并记录在脏页表中。
• 因此，如果 pageID 不在脏页表里，这条日志记录的修改已经被安全地保存到磁盘了，不需要再重做。

比方说：
假设日志记录写着“pageID 3 被更新了”，但崩溃时 pageID 3 不在脏页表中，说明 pageID 3 的更新已经在崩溃前成功写入磁盘，因此不需要对它重做。

3. 日志记录 LSN <= RecLSN，数据修改已在磁盘页面号 RecLSN 生效，不需要重做

这是判断重做需求的第二个条件，关注 LSN 和 RecLSN 的比较：

• LSN：日志的唯一标识，每条日志记录的 LSN 都会比前一条更大，用来确保恢复操作按正确的顺序执行。
• RecLSN：脏页表中每个页面记录的 RecLSN，是指该页面自崩溃前最早一次“变脏”时的 LSN，也就是该页面从这个 RecLSN 开始进入了“脏”状态。

判断依据：

• 如果某条日志记录的 LSN **小于等于 RecLSN**，说明这条记录的修改在页面变脏时就已经写入磁盘了。
• 因此，不需要再对这条日志记录重做，因为崩溃前它已经生效了。

比方说：
假设 pageID 5 在脏页表中的 RecLSN 是 50，这表示从 LSN 50 开始，这个页面的数据变得不一致了（脏了）。如果我们遇到一个日志记录的 LSN 是 30（小于等于 50），那么这条记录的数据在页面变脏之前就已经在磁盘上生效了，不需要再重做这条记录的操作。

总结

在重做过程中：

1. 如果日志记录的 pageID 不在脏页表中，则不需要重做这条日志记录。
2. **如果日志记录的 LSN <= RecLSN**，说明这条记录对应的数据已经在崩溃前写入了磁盘，也不需要重做。

这两个条件帮助数据库系统节省了恢复时间，只对那些未保存到磁盘的、重要的日志记录进行重做，从而高效恢复到一致的状态。

是的，崩溃后内存中的脏页表会消失，因为内存数据在系统崩溃或断电时无法保留。这也是为什么数据库系统需要定期将 脏页表的快照（checkpoint）写入磁盘，以便在崩溃后恢复时可以使用。

崩溃恢复过程中脏页表的作用

1. 检查点（Checkpoint）：
   • 数据库系统会定期创建检查点，将当时的脏页表以及相关的事务状态记录（如活动事务表）持久化到磁盘。
   • 检查点中的脏页表记录了到检查点时为止的所有脏页及其 RecLSN。在崩溃恢复时，这个信息用于判断从哪里开始重做。
2. 崩溃后的恢复：
   • 恢复过程会首先加载最近的检查点状态，获取当时的脏页表，然后根据检查点后的日志记录继续恢复。
   • 这样，即使内存中的脏页表因崩溃而丢失，系统也能从检查点提供的“历史” DPT 状态中找到需要重做的页面范围。

恢复过程示例

• 重做（Redo）阶段：系统会从检查点的 DPT 开始，扫描检查点之后的日志，找出并重做所有需要更新的数据页。
• 避免重复重做：通过检查点中的 DPT 和日志中的 LSN，可以准确找到从哪开始恢复，避免不必要的重复操作。

总结

由于崩溃会导致内存中的 DPT 消失，数据库系统通过 定期检查点将 DPT 持久化到磁盘。在崩溃恢复时，系统利用检查点保存的 DPT 来重新构建需要重做的页面信息，从而有效地完成恢复操作。

p79

• RecLSN：脏页表中每个页面记录的 RecLSN，是指该页面自崩溃前最早一次“变脏”时的 LSN，也就是该页面从这个 RecLSN 开始进入了“脏”状态。
• 所以不需要将 c 4 改为 c 6

补偿日志

补偿日志记录（CLR，Compensation Log Record） 是数据库在执行 ARIES 恢复算法 时生成的一种特殊日志记录，用于在回滚操作中记录撤销的操作。它的主要作用是保证系统在执行回滚时具有可恢复性，并避免回滚操作重复执行。

补偿日志的作用

补偿日志的核心目的是确保数据库能够 安全地回滚事务，即使在回滚的过程中再次发生系统崩溃。补偿日志通过记录每个撤销的步骤，使得系统在恢复时可以识别哪些操作已经撤销，以防止重复执行相同的撤销。

补偿日志的关键内容

每条补偿日志包含的信息通常包括：

1. 被撤销的日志记录的 LSN：指向要撤销的原始日志记录，方便找到回滚的操作。
2. 撤销操作的影响：记录被回滚操作的反向效果，用于确保数据回到修改前的状态。
3. NextUndoLSN：指向下一个需要撤销的日志记录，用于链式回滚。如果崩溃发生在回滚过程中，恢复过程可以从 NextUndoLSN 开始继续回滚。

补偿日志的工作原理

在执行回滚时，数据库会按照 从后往前 的顺序逐条撤销操作。当撤销某条日志记录时，系统会生成一条补偿日志，将撤销的内容和 NextUndoLSN 记录下来。这样，即使在回滚的过程中再次崩溃，系统在重启后也可以通过补偿日志记录，继续从上次回滚的进度开始，避免重复回滚已经撤销的操作。

示例

假设我们有一个事务 T1，执行了以下操作：

1. 写操作 1：修改了 Page A（LSN = 100）。
2. 写操作 2：修改了 Page B（LSN = 150）。
3. 事务失败或被用户取消：系统开始回滚。

在回滚过程中：

• 系统会先撤销 写操作 2，并生成一条补偿日志 CLR1（指向 LSN = 150 的操作）。
• 接着，系统会撤销 写操作 1，生成另一条补偿日志 CLR2（指向 LSN = 100 的操作）。

如果在回滚的过程中发生崩溃，再次恢复时系统会查看这些补偿日志，确定哪些撤销操作已经完成，哪些尚未完成，从而继续回滚未完成的部分。

总结

• 补偿日志记录 是数据库在回滚时生成的日志，确保在回滚过程中崩溃依然可以恢复，避免重复回滚。
• CLR 的重要性 在于提供了一种“防重复”机制，即使发生崩溃，系统依然能够继续完成回滚操作，保持数据一致性。