课程地址
https://15445.courses.cs.cmu.edu/fall2021/schedule.html

Logging Protocols + Schemes

动机，buffer pool中的修改内容，和磁盘上的不一致，此时如果突然宕机
则会出现数据丢失
logging-1

failure classification

宕机恢复

  • 宕机恢复算法这种技术，可以确保即使失败了，数据库也能保证事务一致性、原子性、以及持久性
  • 恢复算法包含两个部分
  • 事务正常处理期间，可以确保DBMS能从故障中恢复
  • 在失败后，将数据库恢复到确保的一致性、原子性、持久性的状态
  • 数据库根据底层存储的不同，将其划分到不同的组件中
  • Volatile vs. Non-Volatile
  • 必须对DBMS需要处理的不同类型的故障进行分类

存储类型

  • Volatile Storage:
  • Data does not persist after power loss or program exit.
  • Examples: DRAM, SRAM
  • Non-volatile Storage:
  • Data persists after power loss and program exit.
  • Examples: HDD, SDD
  • Stable Storage:
  • A non-existent form of non-volatile storage that
  • survives all possible failures scenarios.

失败分类

  • Type #1 – Transaction Failures
  • Logical Errors，如违反了约束条件
  • Internal State Errors，比如出现死锁，DBMS必须在error条件下终止活跃的事务
  • Type #2 – System Failures
  • Software Failure，比如OS、DBMS的问题，如除0错误
  • Hardware Failure，拔掉电源插头这种故障
  • 停止假设，非易失性存储内容，不会因为系统故障而损坏
  • Type #3 – Storage Media Failures
  • Non-Repairable Hardware Failure
  • 磁头或者磁盘损坏，是破坏部分，全部的非易失性存储
  • 破坏假设是可以被检测的，如磁盘控制器使用checksum来检查失败
  • 没有DBMS可以从这种情况下恢复，不行从归档版本中恢复
  • 主要存储是非易失性的，但是比易失性存储要慢很多
  • 使用易失性存储来实现快速访问，首先拷贝目标记录到内存中
  • 在内存中执行操作，写脏记录到磁盘
  • DBMS需要确保：只要事务告知了已经提交，那么任务事务改变的内容都是持久化的
  • 如果事务终止了，不会出现部分改变的内容被持久化

undo VS redo

  • undo：清除不完整或中止事务的影响过程
  • redo：恢复提交事务持久化效果的过程
  • DBMS如何支持这些功能，取决于他们如何管理 buffer pool logging-2

buffer pool policies

steal 策略

  • DBMS是否允许未提交的事务，覆盖非易失性中最新提交的值
  • steal：允许
  • no-steal：不允许

强制策略

  • 是否要求DBMS在事务提交前，将所有更改都反映到非易失性存储上
  • force：要求
  • no-force：不要求
  • no-steal+force，这是方式是最简单的实现
  • 不需要undo一个终止事务的更改，因为事务还没有写入磁盘
  • 不需要redo 一个提交的事务，因为所有的更改在提交时刻 都保证写入到了磁盘，假设硬件写入是原子的
  • 前面的例子，不支持超过可用物理内存的写集合 logging-3

shadow paging

shadow paging

  • 维护两个独立的数据库拷贝
  • master，只包含提交事务的更变
  • shadow，临时数据库，带有未提交事务的变更
  • 事务只在shadow上做更新，当事务提交后，自动切换shadow变成新的master
  • buffer pool策略： no-steal+force
  • 为了安装更改，覆盖root以便指向shadow，这样就可以切换master和shadow
  • 在覆盖root之前，事务的所有更新都不属于驻留在磁盘上的数据库
  • 在覆盖root之后，事务的所有更新都是驻留在磁盘上的数据库一部分
  • 支持rollback 和 恢复 很容易
  • undo：删除shadow页，不要使用主指针和DB根指针
  • redo：任何时候都不需要 logging-4

shadow paging 的缺点和总结

  • 拷贝整个页表开销大
  • 使用页表结构类似B+树
  • 不需要拷贝整个树，只需要复制树中指向页节点的路径
  • 提交的开销也很高
  • 需要flush每个更新页，页表，root
  • 数据被分散
  • 需要垃圾收集
  • 每次只只是一个写事务，或者一批事务
  • observation：
  • shadow 页需要DBMS对磁盘上的随机、不连续的页执行写操作
  • 需要一种方式将随机写转换为顺序写

SqlLite(pre-2010)

  • 当事务修改一个页时，DBMS在覆盖master版本之前，会拷贝原始页到独立的journal 文件中
  • 重启后，如果journal 文件存在，DBMS将恢复它，以撤销未提交的事务更改
  • After restarting, if a journal file exists, then the DBMS restores it to undo changes fromuncommitted txns. logging-5

Write-ahead log

概述

  • 维护一个跟数据文件隔离的 log文件，这个文件包含了事务中的变更
  • 假设log是在持久存储中的
  • 日志中包含了足够的信息，可以执行需要的 undo、redo恢复操作
  • 在对象flush到磁盘之前，DBMS将日志文件中记录中对应的变更写入到磁盘
  • buffer pool策略：steal + no-force
  • DBMS将事务的所有日志记录保存到易失存储中，如buffer pool
  • 在非易失存储中的页覆盖自身之前，与页有关的所有日志更新都要写入非易失存储中
  • 直到所有的日志记录都被写入到持久存储中，事务才算提交

WAL 协议

  • 在每个事务开头，写一个<BEGIN>记录，表示开始点
  • 当事务结束，写一个<COMMIT>记录到日志中
  • 在它响应应用回复之前，要确保所有的日志都flush了
  • 每个日志条目包含的信息，关于变更单个对象的信息
  • Transaction Id、Object Id、Before Value(UNDO)、After Value(REDO)
  • 可以使用 group commit 批量提交多个日志，来平摊开销
  • 如何写dirty records 到磁盘？
  • 事务每执行一个更新就写磁盘；或者 等事务commit的时候写 logging-6
    logging-7

批量提交的例子
logging-8
logging-9

buffer pool策略
logging-10

logging 模式

  • Physical Logging
  • 记录数据库特定位置的变更
  • 如 git diff
  • Logical Logging
  • 记录事务的高级别操作
  • 不需要限制到单个页
  • 如 事务的update、delete、insert操作

物理日志 vs 逻辑日志

  • 逻辑日志相比物理日志，需要更少的数据写入
  • 并发事务情况下，从逻辑日志中恢复很困难
  • 很难确定数据库的哪些部分在crash之前被修改过
  • 需要长时间的恢复，因为必须重新执行所有的事务
  • 物理逻辑日志，日志记录针对单个页面，但不指定页面的组织
  • 识别tuple就他们的slot编号
  • 允许DBMS在日志写入磁盘后重新组织页面
  • 最流行的方式 logging-11

checkpoint

  • 方式WAL无限增长
  • crash之后，会恢复非常长的时间
  • DBMS定期执行checkpoint，将所有buffer flush到磁盘
  • 将当前驻留在内存中的所有日志记录输出到持久存储
  • 所有的修改block输出到磁盘
  • 写一个<CHECKPOINT>条目到日志记录中，并flush到持久存储
  • 挑战：DBMS必须暂停所有事务，当执行checkpoint时，因为要确保一致性快照
  • scan日志发现未提交的事务会花费很长时间
  • 多长时间执行一次checkpoint是个问题
  • checkpoint太频繁会对系统造成压力
  • checkpoint太久一次，会导致文件很大执行很慢，恢复时间也会很长

logging-12

总结

  • Write-Ahead Logging is (almost) always the best approach to handle loss of volatile storage.
  • Use incremental updates (STEAL + NO-FORCE) with checkpoints.
  • On Recovery: undo uncommitted txns + redo committed txns

相关文章

Crash Recovery Algorithms

ARIES

  • Algorithms for Recovery and Isolation Exploiting Semantics
  • 研发于1990年代早起的DB2系统
  • 不是所有的系统都 精确实现了 ARIES 论文中的定义，不过也足够了

ARIES 的主要思路

  • Write-Ahead Logging
  • 在数据库的变更写入到磁盘前，先将所有的变更记录稳定存储的日志中
  • 必须使用 steal + no-force的buffer pool策略
  • Repeating History During Redo
  • 重启后，回溯操作，并将数据库恢复到crash之前的确切状态
  • Logging Changes During Undo
  • 将undo操作记录到日志中，确保重复失败时不会重复执行该操作

Log Sequence Numbers

总结

  • 我们需要扩展日志记录格式，引入新的附加信息
  • 每个日志记录包括一个全局的唯一 日志顺序编号 LSN
  • 各种组件都记录他们自己的LSN
  • 每个数据页包含一个pageLSN，该页的最新更新的LSN
  • 系统跟踪flushedLSN，目前flushed最大的LSN
  • 在将页x写入磁盘之前，必须至少将日志刷到这个位置：pageLSNx <= flushedLSN
    recover-1

一个例子 recover-2
recover-3
recover-4
recover-5

Writing Log Records

  • 所有的日志记录都有LSN
  • 每当事务修改页中的记录时，都更新 pageLSN
  • 每当DBMS写WAL buffer到磁盘时，更新内存中的 flushedLSN

Normal Commit & Abort Operations

总结

  • 每个事务都调用一个顺序读或者写
  • 假设：
  • 所有的日志记录都能放到单个页中
  • 磁盘写是原子的
  • 单个版本的tuple有严格的2PL
  • steal + no-force buffer 管理有WAL
  • 协议个 COMMIT 记录到日志中
  • 所有的日志记录在事务提交之前会flush到磁盘
  • 日志flush是顺序的，同步写磁盘
  • 每个日志页包含多个日志记录
  • 当提交成功，写一个特殊的TXN-END 记录到日志中-
  • 这条信息不需要被立刻flush到磁盘上
    recover-6

事务终止

  • 事务终止是一个特殊ARIES的特殊case，它将undo 操作应用到唯一一个事务上
  • 我们需要增加其他字段到我们的日志记录中
  • prevLSN，事务的前一个LSN
  • 为每个事务维护一个链表结构，这样就可以方便的遍历到记录 recover-7
    recover-8

补偿日志记录

  • CLR描述对先前更新记录的 undo 操作
  • 他有更新日志记录的所有字段，加上 undoNext指针(next-to-be_undone LSN))
  • CLR 被添加到日志记录中，但DBMS在通知应用程序事务终止之前，不会等待他们被flush

终止算法

  • 首先为事务写一个 ABROT 记录到日志中
  • 然后逆序的方式重放事务更新，对于每个更新记录
  • 写一个 CLR 条目到日志中，

recover-9
recover-10
recover-11
recover-12

Fuzzy Checkpointing

概述

  • 当checkpoint开始时，DMBS暂停所有事务，确保一致性快照
  • 暂停所欲开始的新事务
  • 等待所有活跃事务完成
  • 刷新脏页到磁盘
  • 对于运行时的性能不利，但可以让恢复变的容易

slightly better checkpoint

  • 当DMBS开始checkpoint时，暂时事务修改
  • 预防查询在 表页、索引页上获取写 latch
  • 不要等到所有的事务都完成后再checkpoint
  • 我们必须记录checkpoint 开始的内部状态
  • Active Transaction Table (ATT)
  • Dirty Page Table (DPT) recover-13

活跃事务表

  • 每个当前活跃事务都有一个条目：
  • txnID，唯一的事务标识符
  • status，当前的事务模式
  • lastLSN，事务创建的最新的LSN
  • 通过 TXN-END消息，移除条目
  • Txn status code：
  • R：running； C：committing；U：candidate for undo

脏页表

  • 跟踪buffer pool中的哪些页，包含了变更的事务，并且还没有flush到磁盘
  • buffer pool中的每个脏页有一个条目
  • recLSN，导致页变脏的日志记录的LSN recover-14

fuzzy checkpoint

  • 系统在写日志到checkpoint时，允许活跃的事务继续运行
  • 不强制将脏页写到磁盘
  • 跟踪checkpoint边界的日志记录
  • CHECKPOINT-BEGIN: Indicates start of checkpoint
  • CHECKPOINT-END: Contains ATT + DPT recover-15

Recovery Algorithm

ARIES 恢复阶段

  • Phase #1 – Analysis
  • 从最近的MasterRecord(最近检查点的LSN)读WAL，识别buffer pool中的脏页，以及crash时刻的活跃事务
  • Phase #2 – Redo
  • 从日志中合适的位置开始，开始重复所有的操作，甚至包括终止的事务
  • Phase #3 – Undo
  • 在crash之前，倒序所有的未提交事务操作 recover-16

分析阶段

  • 从上一个成功的检查点开始，向前scan日志，如果发现了 TXN-END 记录，从对应的ATT中移除
  • 所有其他的记录：
  • 增加事务到ATT，标记状态undo
  • 提交时，将事务状态改为 COMMIT
  • 对于 UPDATE 记录：
  • 如果页p 不在DPT中，将p增加到 DTP，设置 recLSN = LSN
  • 分析阶段的结束：
  • ATT识别出，在crash时刻，哪个事务活跃的
  • DPT识别出，哪个脏页还没被放入磁盘 recover-17
    recover-18
    recover-19

redo 阶段

  • 目标是在crash的那一刻，重复历史来重建状态
  • 重新应用所有的更新，即使是中断事务，并redo CLR
  • 这里有一些技术可以允许DBMS避免不必要的读、写，不过这堂课就忽略这些内容
  • 在DPT中包含的最小的 recLSN的日志记录 向前扫描
  • 对于每个日志更新，或者CLR，给与一个LSN，redo这个操作，除非：
  • 影响的页不在DPT中，或者
  • 影响的页在DPT中，但是记录的 LSN 小于 页的recLSN
  • redo的动作：
  • 重复应用日志动作
  • 设置 pageLSN 到日志记录的LSN
  • 没有额外的日志，不强制flush
  • 当redo阶段完成，为状态C的所有事务写 TXN-END 日志记录，并从ATT中删除他们

undo阶段

  • undo所有的事务，这些事务在crash时刻活跃的，但是并没有提交
  • 在分析阶段之后，在ATT中所有带有 U 状态的事务
  • 使用 lastLSN 以反向LSN的顺序处理他们，以加速遍历
  • 对于每次修改写一个 CLR

一个完整的例子
recover-20
recover-21
recover-22

一个完整的例子，另一个视角
recover-23
recover-24
recover-25

附加的 crash问题

  • 如果crash发生在恢复过程的分析阶段会如何？
  • 没事，只要再运行一次恢复即可
  • 如果crash发生在redo阶段呢？
  • 也没事，再次redo 所有的事情
  • DBMS如何提高redo阶段的性能？
  • 假设不会发生crash，可以在后台异步的将所有更变flush到磁盘
  • DMBS如何提高undo阶段的性能？
  • 在新事务访问页之前，延迟的rollback变更
  • 重写应用避免长事务

结论

  • ARIES的主要思想： 带有 STEAL/NO-FORCE的 WAL
  • 模糊检查点，脏页page id的快照
  • 从最早的脏页开始redo所有事情
  • undo所有未提交事务
  • 在undo过程中写CLR，避免重启过程中的失败

相关文章

Reference