CMU 15-445 -- Logging Schemes - 17

这篇具有很好参考价值的文章主要介绍了CMU 15-445 -- Logging Schemes - 17。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


引言

本系列为 CMU 15-445 Fall 2022 Database Systems 数据库系统 [卡内基梅隆] 课程重点知识点摘录,附加个人拙见,同样借助CMU 15-445课程内容来完成MIT 6.830 lab内容。


数据库在运行时可能遭遇各种故障,这时可能同时有许多正在运行的事务,如果这些事务执行到一半时故障发生了,就可能导致数据库中的数据出现不一致的现象:

CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle
这时就需要故障恢复机制来保证数据库的原子性、一致性、持久性。故障恢复机制包含两部分:

  • 在事务执行过程中采取的行动来确保在出现故障时能够恢复 (本节课)
  • 在故障发生后的恢复机制,确保原子性、一致性和持久性 (下节课)

Index

  • Failure Classification
  • Buffer Pool Policies
  • Shadow Paging
  • Write-Ahead Log
  • Logging Schemes
  • Checkpoints

Failure Classification

世上并不存在能够容忍任何故障的容错机制,即便做了异地多活,一次小行星撞地球也能将你的系统一举歼灭,因此在讨论故障恢复之前,我们必须先为故障分类,明确需要容忍的故障类型。

一般故障类型可以分为 3 种:

  1. 事务故障 (Transaction Failures)
  2. 系统故障 (System Failures)
  3. 存储介质故障 (Storage Media Failures)

Transaction Failures

事务故障可以分为两种:

  1. 逻辑错误 (Logical Errors):由于一些内部约束,如数据一致性约束,导致事务无法正常完成
  2. 内部错误 (Internal State Errors):由于数据库内部调度、并发控制,如死锁,导致事务无法正常提交

System Failures

系统故障可以分为两种:

  1. 软件故障 (Software Failure):如 DBMS 本身的实现问题 (NPE, Divide-by-zero)
  2. 硬件故障 (Hardware Failure):DBMS 所在的宿主机发生崩溃,如断电。且一般假设非易失性的存储数据在宿主机崩溃后不会丢失

Storage Media Failures

如果存储介质发生故障,通常这样的故障就是无法修复的,如发生撞击导致磁盘部分或全部受损。所有数据库都无法从这种故障中恢复,这时候数据库只能从归档的备份记录中恢复数据。


Buffer Pool Policies

修改数据时,DBMS 需要先把对应的数据页从持久化存储中读到内存中,然后在内存中根据写请求修改数据,最后将修改后的数据写回到持久化存储。在整个过程中,DBMS 需要保证两点:

  1. DBMS 告知用户事务已经提交成功前,相应的数据必须已经持久化
  2. 如果事务中止,任何数据修改都不应该持久化

如果真的遇上事务故障或者系统故障,DBMS 有两种基本思路来恢复数据一致性,向用户提供上述两方面保证:

  • Undo:将中止或未完成的事务中已经执行的操作回退
  • Redo:将提交的事务执行的操作重做

DBMS 如何支持 undo/redo 取决于它如何管理 buffer pool。我们可以从两个角度来分析 buffer pool 的管理策略:Steal Policy 和 Force Policy。以下图为例:

CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle
如上图所示,有 2 个并发事务 T1 和 T2,T1 要修改 A 数据,T2 要修改 B 数据,A、B 数据都位于同一块数据页上。在 T2 事务提交时,T1 事务尚未结束,这时 T1 已经修改了 A 数据,此时 DBMS 会允许被修改但未提交的 A 数据进入持久化存储吗?

  • Steal Policy:DBMS 是否允许一个未提交事务修改持久化存储中的数据?

Steal Policy 有两种可能:允许 (Steal) 和不允许 (No-Steal)。如果选择允许,若 T1 事务回滚,则需要把已经持久化的数据读进来,回滚数据,再存回去,但在不发生回滚时 DBMS 的 I/O 较低;如果选择不允许,若 T1 事务回滚,DBMS 不需要做任何额外的操作,但在不发生回滚时 DBMS 的 I/O 较高。因此这里存在数据恢复时间与 DBMS 处理效率的取舍。

在 T2 事务提交时,是否需要将他的数据改动持久化?

  • Force Policy:DBMS 是否强制要求一个提交完毕事务的所有数据改动都反映在持久化存储中?

Force Policy 有两种可能:强制 (Force) 和非强制 (No-Force)。如果选择强制,每次事务提交都必须将数据落盘,数据一致性可以得到完美保障,但 I/O 效率较低;如果选择非强制,DBMS 则可以延迟批量地将数据落盘,数据一致性可能存在问题,但 I/O 效率较高。

因此我们有 4 种实现组合:

Steal No-Steal
Force Steal + Force No-Steal + Force
No-Force Steal + No-Force No-Steal + No-Force

在实践中使用的主要是 No-Steal + Force 和 Steal + No-Force。


Shadow Paging: No-Steal + Force

最容易实现的一种策略组合就是 No-Steal + Force:

  • 事务中止后,无需回滚数据,因为该事务修改的数据不会被别的事务捎带落盘
  • 事务提交后,无需重做数据,因为该事务修改的数据必然会被落盘持久化

当然,这种策略组合无法处理"写入的数据量超过 buffer pool 大小"的情况。

CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle

shadow paging 是 No-Steal + Force 策略的典型代表,它会维护两份数据库数据:

  1. Master:包含所有已经提交事务的数据
  2. Shadow:在 Master 之上增加未提交事务的数据变动

正在执行的事务都只将修改的数据写到 shadow copy 中,当事务提交时,再原子地把 shadow copy 修改成新的 master。当然,为了提高效率,DBMS 不会复制整个数据库,只需要复制有变动的部分即可,即 copy-on-write。通常,实现 shadow paging 需要将数据页组织成树状结构,如下图所示:
CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle
左边是内存中的数据结构,由一个根节点指向对应的 page table,其中 page table 对应着磁盘中的相应的数据页。在写事务执行时,会生成一个 shadow page table,并复制需要修改的数据页,在其上完成相应操作。在提交写事务时,DBMS 将 DB Root 的指针指向 shadow page table,并将对应的数据页全部落盘,如下图所示:

CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle
在事务提交前,任何被修改的数据都不会被持久化到数据库;在事务提交后,所有被修改的数据都会被持久化到数据库。在 shadow paging 下回滚、恢复数据都很容易:

  • Undo/Rollback:删除 shadow pages (table),啥都不用做
  • Redo:不需要 redo,因为每次写事务都会将数据落盘

shadow paging 很简单,但它的缺陷也很明显:

  • 复制整个 page table 代价较大,尽管可以通过以下措施来降低这种代价:
    • 需要使用类似 B+ 树的数据结构来组织 page table
    • 无需复制整个树状架构,只需要复制到达有变动的叶子节点的路径即可
  • 事务提交的代价较大
    • 需要将所有发生更新的 data page、page table 以及根节点都落盘
    • 容易产生磁盘碎片,使得原先距离近的数据渐行渐远
    • 需要做垃圾收集
    • 只支持一个写事务或一批写事务一次性持久化

在 2010 年之前,SQLite 采用的就是类似 shadow paging 的策略,当写事务需要修改某页数据时,DBMS 会先将原始数据页保存到一个独立的 journal 文件中,然后再将对应的修改持久化到磁盘中。当 SQLite 重启后,如果发现磁盘中存在 journal 文件,则之间将对应的数据页覆盖到磁盘中即可。


Write-Ahead Log (WAL): Steal + No-Force

通过刚才对 shadow paging 的讨论,我们可以发现导致其效率问题的主要原因是:DBMS 在实现 shadow paging 时需要将许多不连续的数据页写到磁盘中,随机写对磁盘来说并不友好,如果能将这种随机写入转化为顺序写入,那么效率自然能够提升。于是 WAL 来了。

WAL 指的是 DBMS 除了维持正常的数据文件外,额外地维护一个日志文件,上面记录着所有事务对 DBMS 数据的完整修改记录,这些记录能够帮助数据库在恢复数据时执行 undo/redo。使用 WAL 时,DBMS 必须先将操作日志持久化到独立的日志文件中,然后才修改其真正的数据页。通常实现 WAL 采用的 buffer pool policy 为 Steal + No-Force,下面我们将详细地介绍 WAL Protocol。

WAL Protocol

  1. DBMS 先将事务的操作记录放在内存中 (backed by buffer pool)
  2. 在将 data page 落盘前,所有的日志记录必须先落盘
  3. 在操作日志落盘后,事务就被认为已经提交成功

事务开始时,需要写入一条 <BEGIN> 记录到日志中;事务结束时,需要写入一条 <COMMIT> 记录到日志中;在事务执行过程中,每条日志记录着数据修改的完整信息,如:

  • Transaction Id (事务 id)
  • Object Id (数据记录 id)
  • Before Value (修改前的值),用于 undo 操作
  • After Value (修改后的值),用于 redo 操作

WAL Group Commit

每次事务提交时,DBMS 都必须将日志记录落盘,由于落盘的操纵对于内存操作来说用时较长,因此可以利用 group commit 来批量刷盘从而均摊落盘成本

CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle
通过以上的分析,我们可以发现,不同的 buffer pool policies 之间存在着运行时效率与数据恢复效率间的权衡:
CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle

  • 运行时效率:No-Steal + Force < Steal + No-Force
  • 数据恢复效率:No-Steal + Force > Steal + No-Force

大部分数据库更看重运行时效率,因此几乎所有 DBMS 使用 No-Force + Steal 的 buffer pool policy。


Logging Schemes

在记录操作信息时,通常有两种方案:physical logging 和 logical logging。前者指的是记录物理数据的变化,类似 git diff 做的事情;后者指的是记录逻辑操作内容,如 UPDATE、DELETE 和 INSERT 语句等等。

logical logging 的特点总结如下:

  • 相比 physical logging,记录的内容精简
  • 恢复时很难确定故障时正在执行的语句已经修改了哪部分数据
  • 恢复时需要回放所有事务,这个过程可能很漫长

还有一种混合策略,称为 physiological logging,这种方案不会像 physical logging 一样记录 xx page xx 偏移量上的数据发生 xx 改动,而是记录 xx page 上的 id 为 xx 的数据发生 xx 改动,前者需要关心 data page 在磁盘上的布局,后者则无需关心,举例如下:
CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle

physiological logging 也是当下最流行的方案。


Checkpoints

如果我们放任 WAL 增长,它可以随着新的操作执行而无限增长。如此这般,在故障恢复时,DBMS 需要读取更多的日志,执行更多的恢复和回滚操作。为了避免这种情况出现,DBMS 需要周期性地记录 checkpoint,即将所有日志记录和数据页都持久化到存储设备中,然后在日志中写入一条 < CHECKPOINT > 记录,举例如下:
CMU 15-445 -- Logging Schemes - 17,# CMU 15-445,数据库,oracle
当 DBMS 发生崩溃时,所有在最新的 checkpoint 之前提交的事务可以直接忽略,如 T1。T2 和 T3 在 checkpoint 前尚未 commit。其中,T2 需要 redo,因为它在 checkpoint 之后,crash 之前提交了,即已经告诉用户事务提交成功;T3 需要 undo,因为它在 crash 之前尚未 commit,即尚未告诉用户事务提交成功。

实现 checkpoints 有需要要考虑的问题:

  1. 在于要保证 checkpoint 的正确性,我们需要暂停所有事务
  2. 故障恢复时,扫描数据找到未提交的事务可能需要较长的时间
  3. 如何决定 DBMS 执行 checkpoint 的周期,太频繁将导致运行时性能下降;等太久将使得 checkpoint 的内容更多,更耗时,同时数据恢复也要消耗更长的时间

小结

WAL 几乎永远是最佳选择。

本节对应教材PDF文章来源地址https://www.toymoban.com/news/detail-612939.html

到了这里,关于CMU 15-445 -- Logging Schemes - 17的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • CMU15445 (Fall 2020) 数据库系统 Project#2 - B+ Tree 详解(上篇)

    考虑到 B+ 树较为复杂,CMU15-445 将 B+ 树实验拆成了两部分,这篇博客将介绍 Checkpoint#1、Checkpoint#2 删除操作和迭代器的实现过程,搭配教材 《DataBase System Concepts》食用更佳。 许多查询只涉及文件中的少量记录,例如“找出物理系所有教师”的查询就只涉及教师记录中的一小部

    2024年02月08日
    浏览(43)
  • 大数据技术①|大数据第15章|HBase数据库与Cassandra数据库|18:00~18:15

    目录 15章习题 15.1 HBase 数据库有何基本功能?  15.2 Big Table 如何对稀疏数据进行存储的?  15.3 面向行的数据存储具有何特点?面向列的数据存储具有何特点?  15.4 HDFS 与 HBase 有何区别?  15.5 HBase 集群主要由哪几类节点构成?它们在集群中起到什么作用?  15.6 HBase 中的数

    2024年02月10日
    浏览(41)
  • 数据库数据恢复-Oracle数据库数据恢复案例

    数据库数据恢复环境: Oracle数据库ASM磁盘组有4块成员盘。 数据库故障分析: Oracle数据库ASM磁盘组掉线 ,ASM实例无法挂载,用户联系我们要求恢复oracle数据库。 数据库数据恢复工程师拿到磁盘后,先将所有磁盘以只读方式进行扇区级别的镜像备份,后续的数据分析和数据恢

    2024年02月13日
    浏览(64)
  • Oracle数据库

    ①层次型数据库 ②网状型数据库 ③关系型数据库(主要介绍) E-R图:属性(椭圆形),实体(矩形),联系(菱形-一对一、一对多、多对多) 注:有的联系也有属性 关系型数据库的设计范式: 第一范式(1NF):属性不可再分,字段保证原子性 第二范式(2NF):在满足1

    2024年02月08日
    浏览(57)
  • Oracle 数据库恢复删除的数据

    需求描述: 同事让删除脏数据,结果删错了,需要恢复数据 思路: 利用闪回恢复数据只能恢复15分钟之内的,后面undo空间会被重写,就恢复不了,所以删除数据后,要谨慎再三确认,若发现不对,则利用闪回恢复 先查询删除时的时间节点的快照 查到时间戳之后 闪回恢复数

    2024年01月24日
    浏览(68)
  • MySQL数据库基础 17

    在实际开发中,我们经常会遇到这样的情况:有 2 个或者多个相互关联的表,如 商品信息 和 库存信息 分别存放在 2 个不同的数据表中,我们在添加一条新商品记录的时候,为了保证数据的完整性,必须同时在库存表中添加一条库存记录。 这样一来,我们就必须把这两个关

    2024年02月11日
    浏览(38)
  • 【数据库】日常使用PL/SQL 登录ORACLE 数据库查询数据

    一、PL/SQL 登录方式 username: ##访问数据库的账号 password: ##访问数据库的密码 Databse: ##数据库IP地址/实例名 数据库集群心跳地址/实例名 Connect as : ##Normal,如果使用sysdba账户登录选择SYSDBA 二、PL/SQL使用SQL语句查询 点击上方导航栏,New,选择SQL Window,即可再次输入要查询的

    2024年02月19日
    浏览(68)
  • Oracle数据库面试题 精选 Oracle 面试题

    1.解释冷备份和热备份的不同点以及各自的优点 冷备份 发生在数据库已经正常关闭的情况下,将关键性文件拷贝到另外位置的一种说法。适用于所有模式的数据库。 优点 1. 是非常快速的备份方法(只需拷贝文件) 2. 容易归档(简单拷贝即可) 3. 容易恢复到某个时间点上(只

    2024年02月05日
    浏览(99)
  • 【Oracle】收集Oracle数据库内存相关的信息

    【声明】文章仅供学习交流,观点代表个人,与任何公司无关。 编辑|SQL和数据库技术(ID:SQLplusDB) Oracle数据库包含多个内存区域,每个区域都包含多个子组件。 Oracle Database Memory Structures 根据具体问题的需要,可以通过如下命令收集Oracle数据库内存相关的信息。 例: 注:SET

    2024年01月21日
    浏览(67)
  • Oracle数据库概念简介

    一般意义上的数据库包含两个部分 库:就是一个存储一堆文件的文件目录 数据库管理系统:管理库的系统 数据库管理系统(Database Management System),是一种操纵和管理数据库的大型软件,用于建立、使用和维护数据库,简称 DBMS ; 它对数据库进行统一的管理和控制,以保证数

    2024年02月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包