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

Logging Protocols + Schemes

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

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

buffer pool policies

steal 策略

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

强制策略

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

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:任何时候都不需要

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.

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的时候写

批量提交的例子

buffer pool策略

logging 模式

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

物理日志 vs 逻辑日志

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

checkpoint

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

总结

  • 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

一个例子


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到磁盘上

事务终止

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

补偿日志记录

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

终止算法

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




Fuzzy Checkpointing

概述

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

slightly better checkpoint

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

活跃事务表

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

脏页表

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

fuzzy checkpoint

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

Recovery Algorithm

ARIES 恢复阶段

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

分析阶段

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

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

一个完整的例子


一个完整的例子,另一个视角


附加的 crash问题

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

结论

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

相关文章

Reference