第9章 恢复系统

null第9章 恢复系统第9章 恢复系统本章内容参考: 数据库概念(第四版) by A. Silberschatz Chapter 17 Recovery System 补充内容 本章内容特色: 数据库恢复的“道理”较容易理解 但编程实现较难，算法较多 本章要解决的关键问题： 如何预防和应付各种”故障”,保证ACID性质主要内容主要内容故障分类 存储器结构 恢复与原子性 基于日志的恢复 Shadow Paging 并发事务的恢复 缓冲管理 非易失性存储器丢失信息的故障 Advanced Recovery Techniques ARIES Recovery Algorithm故障分类故障分类故障(Failure,fault)：系统在工作过程中，因某种原因导致“丧失规定功能，无法正常运行” 的现象。 根据故障的影响范围，我们可以将故障分为以下类型: 事务故障 系统故障 介质故障事务故障事务故障事务故障指影响单个事务正常运行的任何事件 有两类错误可能引起事务故障，迫使事务执行失败 逻辑错误: 因为某些内部错误条件导致事务不能完成 系统错误: 因为某种错误条件(如死锁)导致数据库系统终止一个活跃事务 有的事务故障可以通过事务程序本身发现并处理，而有的则是非预期的，不能由事务程序自身处理 一般而言, 事务故障更多是非预期的，不能由应用程序自身处理。如: 运算溢出、并发事务发生死锁而被选中撤消该事务、违反了某些完整性限制等 以后，事务故障一般是指这类非预期的故障 事务故障事务故障事务故障意味着事务没有达到预期的终点(COMMIT或者显式的ROLLBACK)，因此，数据库可能处于不正确状态。 恢复程序要在不影响其它事务运行的情况下，强行回滚(ROLLBACK)该事务，即撤消该事务已经作出的任何对数据库的修改，使得该事务好象根本没有启动一样。 这类恢复操作称为事务撤消(UNDO)。 系统故障系统故障系统故障是指造成系统停止运转的任何事件，使得系统要重新启动 例如，特定类型的硬件错误(如CPU故障)、操作系统故障、DBMS错误、突然停电等等 系统故障将影响所有正在运行的事务，虽然不破坏数据库, 但是主存内容，尤其是数据库缓冲区中的内容都被丢失，导致所有运行事务都非正常终止 故障-停止假设: 假设非易失性存储器的内容不会因系统崩溃而破坏 数据库系统可通过许多完整性检查来防止磁盘数据被破坏系统故障系统故障发生系统故障时，一些尚未完成的事务的结果可能已送入物理数据库，有些已完成的事务可能有一部分甚至全部留在缓冲区，尚未写回到磁盘上的物理数据库中，从而造成数据库可能处于不正确的状态 为保证数据一致性，恢复子系统必须在系统重新启动时让所有非正常终止的事务回滚，强行撤消(UNDO)所有未完成事务, 并且要重做(Redo)所有已提交的事务，以将数据库恢复到一致状态介质故障介质故障介质故障是指外存故障，包括磁盘损坏、磁头碰撞，瞬时强磁场干扰、文件损坏等。 这类故障将破坏数据库或部分数据库，并影响正在存取这部分数据的所有事务 介质故障比前两类故障发生的可能性小得多，但破坏性最大 在对介质故障恢复时，可利用其它磁盘上的数据备份或档案数据库进行重构，然后利用事务日志(log)对最近后备副本以后提交的所有事务进行重做(redo) 假设损坏是可以检测到的: 磁盘驱动器使用校验和来检测故障恢复算法恢复算法恢复算法是指即使发生故障也能确保数据库一致性和事务原子性及持久性的技术 恢复算法两个部分 在正常事务处理过程中采取动作来确保有足够的信息用于从故障恢复, 即事前预防措施，保证有尽量多的信息在故障中保存下来 在故障发生后采取行动作将数据库内容恢复到一个确保原子性, 一致性和持久性的状态, 即事后的恢复措施，保证原子性，一致性，耐久性 存储器结构存储器结构易失性(Volatile)存储器 不能在系统崩溃后保存下来 例如: 主存, 高速缓存 非易失性(Nonvolatile)存储器 可以在系统崩溃后保存下来 例如: 磁盘, 磁带, 闪存, 非易失性RAM (电池供电) 稳定(Stable)存储器 虚构的能够经受任何故障的存储器 可用多个非易失性介质存储相同的副本来近似稳定存储器的实现稳定存储器的实现在不同磁盘上维持多个副本 副本可以在远程站点上, 以防止象火灾或洪水之类的灾难 在数据传输过程中的故障仍然可导致不一致的副本，块传输的结果可能是 成功完成 部分失败: 目标块有错误信息 完全失败: 目标块根本没有更新 在数据传输过程中防止存储介质出故障的解决方法：输出操作如下执行 (假设每个块有两个副本): 将信息写到第一个物理块 当第一个写操作成功完成, 再将相同信息写到第二个物理块 仅当第二个写操作成功完成之后输出才算完成稳定存储器的实现稳定存储器的实现在数据传输过程中防止存储介质出故障 (续): 块的副本间可能因输出操作过程中的故障而有不同,为了从故障恢复: 首先找到不一致的块 高代价的解决方法: 比较每个磁盘块的两个副本 更好的解决方法 将正在进行的磁盘写操作记录在非易失性存储器上(非易失性RAM或者磁盘的特定区域) 恢复时利用此信息找到可能不一致的块, 只需比较这些块的副本 用于硬件RAID系统 如果不一致块的一个副本上检测到错误(错误的校验和), 则用另一副本覆盖它即可 如果两个副本都没有错误但却不一致, 则用第二个块覆盖第一个块 数据存取数据存取物理块是位于磁盘上的块 缓冲块是临时位于主存中的块 磁盘和主存之间的块移动通过下列两个操作来引发: input(B) :将物理块 B 传入主存 output(B): 将缓冲块 B 传到磁盘, 并且替换相应的物理块 每个事务Ti 都有自己的私有工作区, 用来保存它存取和更新的所有数据项的局部副本 Ti 对应于数据项 X 的局部副本记为xi 为简单起见, 假设每个数据项都能存入并且确实存储在单个块中数据存取数据存取事务使用下列操作来在系统缓冲块和它的私有工作区之间传送数据项: read(X) 将数据项X 的值赋给局部变量xi write(X) 将局部变量 xi 的值赋给缓冲块中的数据项 X 这两条命令在赋值前都可能要求发出 input(BX) 指令, 如果X 所在的块 BX 当前不在主存中的话数据存取数据存取事务第一次访问 X 时执行read(X) 以后的访问是对局部副本进行的 最后一次访问之后, 执行write(X) output(BX) 不必紧随write(X)立即执行 系统可在它认为适当的时候执行output 操作数据存取：例数据存取：例xYABx1y1 缓冲区缓冲块 A 缓冲块 Binput(A)output(B) read(X)write(Y)磁盘T1的工作区T2的工作区内存x2恢复与原子性恢复与原子性问题 一个较长事务进行若干查插删改操作 设计时假定整个事务作为原子是保持一致性 但执行可能半途而废（意外原因，停电等） 如何恢复？恢复与原子性恢复与原子性为了在故障的情况下仍确保原子性, 应首先输出描述修改操作的信息到稳定存储中(先记账)，描述将作的操作，然后动作(恢复有据） 下面介绍两种方法: 基于日志的恢复 影子分页shadow-paging 先假设事务是串行执行的基于日志的恢复基于日志的恢复日志(log)是日志记录的序列，用来记录事务对数据库的更新操作 日志保存在稳定存储器上 当事务Ti 启动, 写入一条登记自己的日志记录 Ti 执行write(X)之前, 写入日志记录 , 各分量依次是:事务,变量,前值,后值 当Ti 完成了最后一条语句, 写入日志记录基于日志的恢复基于日志的恢复目前假设日志记录直接写入稳定存储器(即不经过缓冲) 两种使用日志的方法 延迟更新数据库(先记账，后补工，保守，稳妥) 立即更新数据库(边记，边做，积极，冒险)延迟更新数据库延迟更新数据库延迟更新数据库 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 在日志中记录所有更新, 但推迟write 直至部分提交之后 假设事务串行执行 事务启动时向日志写入 记录 write(X) 操作导致写入日志记录, 其中V 是X的新值 注: 这种方案不需要保留旧值 这时并未执行对X 的写操作, 而是延迟了 当Ti 部分提交时, 向日志写入 最后, 读取日志记录并用来实际执行前面延迟的写操作(把被延迟的写动作（欠工账） 补作完成) 生活中，一个“拖”字或“研究研究”就是这种延迟策略延迟更新数据库延迟更新数据库故障后恢复过程中，事务需要重做(redo)，当且仅当日志中存在和(这样恢复有据) 重做事务Ti ( redoTi) 将事务更新过的所有数据项的值置为新值(即有底子，有工账，在底子上，重来一次) 但正在恢复时出错有怎么办? 例如事务T0 和T1 (T0 在T1 之前执行): T0: read (A) T1 : read (C) A := A - 50 C:= C- 100 Write (A) write (C) read (B) B:= B + 50 write (B)延迟更新数据库延迟更新数据库下面给出了日志在三个时刻的情形 如果故障发生时稳定存储器上的日志处于情形: (a) 不需重做(因为工账并未实施) (b) 必须执行redo(T0), 因为存在 (c) 必须先执行redo(T0) 再执行redo(T1), 因为存在 和立即更新数据库立即更新数据库立即更新数据库方案允许一个未提交事务在发出写操作时更新数据库 由于可能需要取消操作, 日志记录必须包含旧值和新值 对更新的日志记录必须在数据库数据修改之前写入稳定存储器 假设日志记录直接输出到稳定存储器 可以扩展成推迟日志记录的输出, 只要满足: 在执行数据块B的output(B) 操作之前, 所有对应于B 的日志记录都已写入稳定存储器 被更新块的输出可能发生在事务提交之前或之后的任何时刻 块输出的次序可以与修改块的次序不同立即更新数据库立即更新数据库恢复过程需要两种操作: undo(Ti) 复原所有被Ti 更新了的数据项的旧值, 从Ti 的最后一条日志记录向前进行（后退） redo(Ti) 将所有被Ti 更新了的数据项的值置为新值, 从Ti 的第一条日志记录向后进行（朝前） 两种操作都必须是幂等的 亦即, 即使该操作被执行多次, 效果与只执行一次是一样的 由于在恢复过程中可能重复执行这两个操作, 所以需要此性质立即更新数据库立即更新数据库故障后恢复 如果日志中包含但不包含, 则事务Ti 需要取消(undo)(即日志中有头无尾时要复旧，这是急性子将有的麻烦) 如果日志中包含和, 则事务Ti 需要重做(redo)(即日志中有头有尾时，需要重作) 取消(undo)操作先做, 重做(redo)操作后做立即更新数据库的例子立即更新数据库的例子检查点检查点前述恢复过程的问题 搜索整个日志很费时 可能不必要地重做事务(已经将更新输出到数据库的事务) 通过周期性地执行检查点来精简恢复过程 将当前驻留在主存中的所有日志记录输出到稳定存储器 将所有更新过的缓冲块输出到磁盘 将一条日志记录写入稳定存储器检查点检查点恢复时仅需考虑在检查点之前启动的最近的事务Ti, 以及在Ti 之后启动的事务 从日志末尾反向扫描, 找到最近的记录 继续反向扫描直到找到一个记录 仅需考虑日志中在上面这个启动记录之后的部分，之前的部分在恢复时可以忽略, 如果愿意可以随时删除 对所有没有的事务(Ti 或更晚), 执行undo(Ti ) (仅当立即更新数据库时才如此) 正向扫描日志，对所有有的事务(Ti 或更晚), 执行 redo(Ti)检查点的例子检查点的例子 T1 可以忽略 (由于检查点, 其更新已经输出到磁盘) T2 和 T3 重做 T4 取消TcTfT1T2T3T4检查点系统故障影子页面（Shadow Paging）影子页面（Shadow Paging）Idea 保持真身和影子，影子在非易逝内存 事务前留影，事务中影子不被修改 事务成功，则影子与时俱进 事务失败，则恢复到影子 技巧 影子不是数据页面的副本，只要页面指针 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 的副本Sample Page TableSample Page TableExample of Shadow PagingExample of Shadow PagingShadow and current page tables after write to page 4 Shadow PagingShadow PagingTo commit a transaction :事务提交时 1. Flush 变动的值块到磁盘 2. Output current page table to disk 当前表写盘 3. Make the current page table the new shadow page table, as follows: keep a pointer to the shadow page table at a fixed (known) location on disk to make the current page table the new shadow page table, simply update the pointer to point to current page table on diskShadow PagingShadow PagingOnce pointer to shadow page table has been written, transaction is committed No recovery is needed after a crash — new transactions can start right away, using the shadow page table 出错后复旧 pCurrPag= pShadow Pages not pointed to from current/shadow page table should be freed (garbage collected)释放不用的指针 Show PagingShow PagingAdvantages优点 no overhead of writing log records(快) recovery is trivial(易恢复) Show PagingShow PagingDisadvantages :缺点 Copying the entire page table is very expensive复制原指针表费时 Can be reduced by using a page table structured like a B+-tree No need to copy entire tree, only need to copy paths in the tree that lead to updated leaf nodes 可用B树解决，只复制路径 Commit overhead is high even with above extension 提交花销大 Need to flush every updated page, and page table Data gets fragmented related pages get separated on disk磁盘上数据不连续 After every transaction completion, the database pages containing old versions of modified data need to be garbage collected 需要回收内存空间 Hard to extend algorithm to allow transactions to run concurrently 并发程序难写并发事务的恢复并发事务的恢复对基于日志的恢复方案扩展，以允许多个事务并发执行 简化模型的3 个假定： 所有事务共享单个磁盘缓冲区和单个日志 缓冲块可以具有被一个或多个事务更新的数据项 假设使用严格两阶段锁的并发控制，即未提交事务所做的更新对其他事务是不可见的 否则如果T1 更新A, 然后T2 又更新A 并提交, 最后T1 必须夭折时, 该怎样执行undo ? 日志登记与前面描述的相同 不同事务的日志记录在日志中可能交错分布 检查点技术及恢复时的操作必须改变 并发，多检查点导致复杂并发事务的恢复并发事务的恢复检查点的执行基本同前, 除了检查点日志记录现在形如 < checkpoint , L> 其中 L 是检查点时活跃事务列表 假设当执行检查点时没有正在进行的更新操作 (以后对此可放宽) 当系统从崩溃恢复时, 首先做下列动作: 初始化 undo-list 和redo-list 为空 从末尾开始反向扫描日志, 直至发现第一条 记录时停止, 对在反向扫描过程中发现的每条记录: 如果是, 将Ti 加入redo-list 如果是, 并且Ti 不在 redo-list 中, 则将Ti 加入undo-list 对L 中的每个Ti, 如果Ti 不在redo-list 中, 则将Ti 加入undo-list并发事务的恢复并发事务的恢复至此undo-list 包含必须取消操作的未完成事务, 而redo-list 包含必须重做的已完成事务 现在恢复可以如下继续: 从最近的记录开始反向扫描日志, 对undo-list 中的每个Ti 当遇到 记录时停止 扫描过程中, 对属于undo-list 中事务的每条日志记录执行undo 定位于最近的 记录 从记录开始正向扫描日志, 直至日志末尾 扫描过程中, 对属于redo-list 中事务的每条日志记录执行redo恢复例恢复例对下列日志按照恢复算法的步骤走一遍:日志记录缓冲日志记录缓冲模型约定 日志记录缓冲: 在主存中缓冲日志记录, 而不是直接输出到稳定存储器 当缓冲区中的日志记录块满时, 或者当执行日志强制(log force)操作时,将日志记录输出到稳定存储器 日志强制用来提交事务, 方法是将它的日志记录(包括提交记录)强行输出到稳定存储器 由于一次输出操作可以输出多条日志记录, 从而减少I/O 代价日志记录缓冲日志记录缓冲日志缓存的规则 日志记录按其创建次序输出到稳定存储器 仅当日志记录已经输出到稳定存储器, 事务Ti 才进入提交状态 在主存中的数据块输出到数据库之前, 所有属于该块中数据的日志记录必须已经输出到稳定存储器 这条规则称为先写日志(write-ahead logging)或WAL规则 严格地说，WAL只需要输出undo信息数据库缓冲数据库缓冲数据库维护一个数据块在内存中的缓冲区 当需要新块时, 如果缓冲区已满, 则需要将一个现有块移出缓冲区 如果所选的移出块被更新过(“脏块”), 则必须将它输出到磁盘 由于先写日志规则, 如果要将一个带有未提交更新的块输出到磁盘, 必须先将记有那些更新的取消(undo)信息的日志记录输出到稳定存储器上的日志中数据库缓冲数据库缓冲当一个块输出到磁盘时, 其上不能有正在进行的更新，可以用下列方法确保这一点 写数据项之前, 事务在包含数据项的块上获得排它锁 一旦完成写, 锁即可释放 这种持有时间很短的锁称为latch (插销) 在一个块输出到磁盘之前, 系统在该块上获得排他插销 确保该块上没有更新正在进行数据库缓冲数据库缓冲数据库缓冲区的实现可以是 在实际主存中为数据库保留的一个区域 在操作系统虚拟内存中 在保留的主存中实现缓冲区有下列缺点: 预先划分内存给数据库缓冲区, 限制了灵活性 需求可能改变, 尽管操作系统最清楚在什么时刻应该如何分配内存, 它却不能改变内存分配数据库缓冲数据库缓冲数据库缓冲区可以在操作系统的虚拟内存中实现, 尽管有下列缺点: 当操作系统需要移出一个被更新过的页以便为另一页腾出空间时, 该页被写到磁盘上的交换区(swap space) 当数据库决定将缓冲页写到磁盘时, 缓冲页可能在交换区中, 于是可能必须从磁盘上的交换区读入该页再输出到磁盘上的数据库中, 导致一次多余的I/O! 称为dual paging 问题 当换出数据库缓冲页时, 理想的情况是操作系统将控制交给数据库, 由数据库输出该页到数据库中而不是交换区中 (首先确保输出日志记录) 因此Dual paging 被避免, 但通常的操作系统不支持此功能 缺点：间接管理，有extra I/O!非易失性存储器丢失信息的故障非易失性存储器丢失信息的故障到目前为止我们都假定非易失性存储器不会丢失信息 使用类似检查点的技术来处理非易失性存储器的丢失信息 周期性地转储(dump)数据库的全部内容到稳定存储器 转储过程中不能有活跃事务：必须有一个类似于检查点的过程 输出当前在主存中的所有日志记录到稳定存储器 输出所有缓冲块到磁盘 复制数据库内容到稳定存储器 输出记录到稳定存储器的日志中 从磁盘故障恢复时 从最近的转储恢复数据库 查看日志并重做所有在转储后提交的事务 可以扩展以允许转储过程中有活跃事务:称为模糊转储(fuzzy dump)或联机转储(online dump)Advanced Recovery AlgorithmAdvanced Recovery AlgorithmAdvanced Recovery TechniquesAdvanced Recovery TechniquesSupport high-concurrency locking techniques, such as those used for B+-tree concurrency control支持并行B-树 Operations like B+-tree insertions and deletions release locks early They cannot be undone by restoring old values (physical undo), since once a lock is released, other transactions may have updated the B+-tree. 简单的物理恢复不能复旧，因为其他事务可能干扰 Instead, insertions (resp. deletions) are undone by executing a deletion (resp. insertion) operation (known as logical undo) 因此，采用逻辑复旧Advanced Recovery TechniquesAdvanced Recovery TechniquesFor such operations, undo log records should contain the undo operation to be executed called logical undo logging(逻辑撤消日志) in contrast to physical undo logging(物理撤消日志) Redo information is logged physically (that is, new value for each write) even for such operations Logical redo is very complicated， since database state on disk may not be “operation consistent” 由于磁盘上的数据库状态可能不是”操作一致的”，故逻辑重做比物理重做复杂的多 Advanced Recovery TechniquesAdvanced Recovery TechniquesOperation logging is done as follows: When operation starts, log ，Here Oj is a unique identifier of the operation instance While operation is executing, normal log records with physical redo and physical undo information are logged When operation completes, is logged, where U contains information needed to perform a logical undo U中包含完成逻辑撤消所需要的信息Advanced Recovery TechniquesAdvanced Recovery TechniquesIf crash/rollback occurs after the operation completes: the operation-end log record is found, and in this case logical undo is performed using undo information U physical undo information for the operation is ignored(忽略) Redo of operation (after crash) still uses physical redo information Advanced Recovery TechniquesAdvanced Recovery TechniquesRollback of transaction Ti is done as follows: Scan the log backwards If a log record is found, perform the undo and log a special redo-only log record . If a record is found Rollback the operation logically using the undo information U Updates performed during rollback are logged just like during normal operation execution At the end of the operation rollback, instead of logging an operation-end record, generate a record Skip all preceding log records for Ti until the record is foundAdvanced Recovery Techniques Advanced Recovery Techniques If a redo-only record is found ignore it If a record is found: skip all preceding log records for Ti until the record is found Stop the scan when the record is found Add a record to the logAdvanced Recovery TechniquesAdvanced Recovery TechniquesSome points to note: Cases 3 and 4 above can occur only if the database crashes while a transaction is being rolled back 当事务回滚期间发生系统崩溃导致Cases 3 and 4 出现 Skipping of log records as in case 4 is important to prevent multiple rollback of the same operation 避免同一个操作被多次撤消Advanced Recovery TechniquesAdvanced Recovery TechniquesThe following actions are taken when recovering from system crash Scan log forward from last < checkpoint L> record Repeat history by physically redoing all updates of all transactions Create an undo-list during the scan as follows undo-list is set to L initially Whenever is found Ti is added to undo-list Whenever or is found, Ti is deleted from undo-list This brings database to state as of crash, with committed as well as uncommitted transactions having been redone Now undo-list contains transactions that are incomplete, that is, have neither committed nor been fully rolled backAdvanced Recovery TechniquesAdvanced Recovery TechniquesScan log backwards, performing undo on log records of transactions found in undo-list Transactions are rolled back as described earlier When is found for a transaction Ti in undo-list, write a log record Stop scan when records have been found for all Ti in undo-list This undoes the effects of incomplete transactions (those with neither commit nor abort log records) Recovery is now completeAdvanced Recovery TechniquesAdvanced Recovery TechniquesCheckpointing is done as follows: Output all log records in memory to stable storage Output all modified buffer blocks to stable storage Output a < checkpoint ,L> record to log on stable storage Transactions are not allowed to perform any actions while checkpointing is in progress Fuzzy checkpointing allows transactions to progress while the most time consuming parts of checkpointing are in progress Performed as described on next slideAdvanced Recovery TechniquesAdvanced Recovery TechniquesFuzzy checkpointing is done as follows: Temporarily stop all updates by transactions Write a log record and force log to stable storage Note list M of modified buffer blocks Now permit transactions to proceed with their actions Output all modified buffer blocks in list M to disk blocks should not be updated while being output Follow WAL: all log records pertaining to a block must be output before the block is output Store a pointer to the checkpoint record in a fixed position last_checkpoint on diskAdvanced Recovery TechniquesAdvanced Recovery TechniquesWhen recovering using a fuzzy checkpoint, start scan from the checkpoint record pointed to by last_checkpoint Log records before last_checkpoint have their updates reflected in database on disk, and need not be redone Incomplete checkpoints, where system had crashed while performing checkpoint, are handled safelyARIES Recovery AlgorithmARIES Recovery AlgorithmIntroductionIntroductionName Algorithm for Recovery and Isolation Exploiting Semantics(ARIES) 参考文献: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging C. MOHAN IBM Almaden Research Center DON HADERLE IBM Santa Teresa Laboratory BRUCE LINDSAY, HAMID PIRAHESH and PETER SCHWARZ IBM Almaden Research Center IntroductionIntroductionIntroductionIntroductionARIES is a state of the art (最新成果) recovery method Incorporates numerous optimizations to reduce overheads during normal processing and to speed up recovery 核心思想:融合多种优化技术，减少开销，即尽量不作多余的事 The “advanced recovery algorithm” we studied earlier is modeled after ARIES, but greatly simplified by removing optimizationsIntroductionIntroductionSupports Page-level logical logging Updates in place就地更新 (as opposed to multi-versioning) Record-level locking 行级锁 Partial and total rollbacks部分及完全回滚 Media recovery 介质故障恢复 Nested transactions 嵌套事务 IntroductionIntroductionAdvantages:优点 (1) Allows fine-grain concurrency (2) Uses only one type of log to record page-level actions (3) Compared to physical logging, produces small log files (4) Allows flexible buffer management (no-force, steal) (5) Fast checkpointing with minimal delay of transactions (6) Allows relatively fast restart (7) No locking or deadlocks during restart or rollbacks (8) Avoids undoing the same log record multiple times (9) Incurs招致only a small overhead per page (page LSN) (10) Allows flexible structures with good storage reclamation(回收)IntroductionIntroductionDisadvantage:缺点 Very tricky implementation 实现非常有技巧 比较难理解 ARIES: AssumptionsARIES: AssumptionsConcurrency control is in effect Strict 2PL, in particular Updates are happening “in place”(就地更新) i.e. data is overwritten on the disk Handling the Buffer PoolHandling the Buffer PoolBuffer pool is finite, so… Issue: How do we guarantee durability of committed data? Solution: Policy on what happens when a transaction completes, what transactions can do to get more pagesHandling the Buffer PoolHandling the Buffer PoolForce every write to disk? 优点：Provides durability(保证持久性) 缺点： But Poor response time(响应时间差) Steal(偷窃) buffer-pool frames from uncommited Xacts? If not, poor throughput (如果不允许，则吞吐率差) If so, how can we ensure atomicity? (如果允许，如何保证原子性)More on Steal and ForceMore on Steal and ForceNO FORCE (why enforcing Durability is hard) What if system crashes before a modified page is written to disk? Write as little as possible, in a convenient place, at commit time to support REDOing modifications 为支持REDO，在提交时，尽可能少写(在方便的地方) STEAL (why enforcing Atomicity is hard) To steal frame F: Current page in F (say P) is written to disk; some Xact holds lock on P What if the Xact with the lock on P aborts? Must remember the old value of P at steal time to support UNDOing the write to page P 为支持UNDO，必须记录偷窃时的旧值ARIES LoggingARIES LoggingARIES Log: An ordered list of REDO/UNDO actions Record REDO and UNDO information, for every update, in a log Log record contains: Sequential writes to log (put it on a separate disk)按顺序写日志 Minimal info (diff) written to log, so multiple updates fit in a single log page 将最少量的信息写入日志，这样多个更新可以放入一个日志页中ARIES Write-Ahead Logging (WAL)ARIES Write-Ahead Logging (WAL)The Write-Ahead Logging Protocol: Must force the log record for an update before the corresponding data page gets to disk在数据页写入磁盘之前，必须强制将日志记录写盘 guarantees Atomicity 保证原子性 Must write all log records for a Xact before commit 在事务提交之前必须将其所有日志记录写盘 guarantees Durability 保证持久性ARIES OptimizationsARIES OptimizationsUnlike the advanced recovery algorithm(ARIES特色)： Uses log sequence number (LSN) to identify log records用日志顺序号 (LSN)标识日志记录 Stores LSNs in pages to identify what updates have already been applied to a database page 在数据页中存储LSNs 表示已经用于该数据页的更新 Support Physic-logical redo 支持物理逻辑重作 Dirty page table to avoid unnecessary redos during recovery 使用”脏”页表，避免恢复过程中不必要的重作 Fuzzy checkpointing that only records information about dirty pages, and does not require dirty pages to be written out at checkpoint time ARIES OptimizationsARIES OptimizationsPhysical-logical redo(物理-逻辑重做) Affected page is physically identified, action within page can be logical 受影响的页被物理标识，而页中的操作可以是逻辑的 Used to reduce logging overheads 用于减少日志费用 e.g. when a record is deleted and all other records have to be moved to fill hole Physic-logical redo can log just the record deletion Physical redo would require logging of old and new values for much of the pageARIES OptimizationsARIES OptimizationsPhysical-logical redo(物理逻辑重做) Requires page to be output to disk atomically 需要页面可以自动输出到磁盘 Easy to achieve with hardware RAID 可以通过硬件RAID实现 Incomplete page output can be detected by checksum techniques 不完整的页面输出可以通过校验和检测到 But extra actions are required for recovery 但恢复时需要额外操作 Treated as a media failure 作为介质故障处理ARIES Data StructuresARIES Data StructuresLog sequence number (LSN) identifies each log record Must be sequentiall