关于数据库:数据库恢复子系统的常见技术和方案对比一

作者：实验室小陈 / 大数据凋谢实验室

对于事务型数据库而言，最要害的性能是要保障事物 ACID 属性，其中原子性和持久性依附复原子系统保障。事务在进行中如果发现无奈持续，就须要用复原子系统进行回滚；或者呈现零碎解体，也须要依附复原子系统把数据库复原到解体前状态。在本专栏中，咱们次要介绍 Logging Protocols / Recovery Algorithms，它们别离是事务型数据库复原子系统中的两个要害局部。

— Logging Schemes—

复原子系统中的要害是复原算法，目标是要实现两个过程。首先是事务执行过程中为零碎复原做的筹备工作，目前大多数零碎通常采纳日志记录形式，只管事务执行过程中同时记录数据更新日志会有额定开销，但如果没有日志，一旦零碎解体则无奈实现零碎复原和未实现事务的回滚。此外，还有 Shadow Paging 计划，即数据每次批改都通过 Copy-on-Write 的形式进行。在更新数据时，复制一份原数据的正本并在正本上进行更新，最初通过用正本替换原始数据的形式实现操作。Shadow Paging 计划开销较大，个别用在更新不频繁的场景下，如文本编辑器等相似场景，因而事务型数据库系统里大都采纳基于日志的计划。第二个过程是在呈现系统故障或事务回滚的状况时，如何利用零碎记录的日志信息并采纳适合策略来保障数据库可能复原到正确状态。

• Physical Logging & Logical Logging

Logging 分为 Physical Logging 和 Logical Logging 两类。Physical Logging 指在日志记录中记录对数据项的批改，如数据项 A 在批改之前的值为 90，批改之后是 100，Physical Logging 会将数据项 A 的变动过程记录下来。在一个数据库系统中，Physical Logging 可能是 Value Logging，即记录数据项、数据项 ID、批改前 / 后的属性值等信息；也可能是真正的物理 Logging，即记录磁盘页面 PageID、Offset 和长度，以及批改前后的值。

另外一类是 Logical Logging，不记录执行后果，只记录对数据批改的操作如 delete / update 等。较于 Physical Logging 依据批改前后的值进行复原或重放，Logical Logging 在重放时须要从新执行日志中的操作，在回滚时须要执行日志中所记录操作的逆操作，比方插入对应的删除等。

• Physical Logging VS Logical Logging

两种 Logging 各有优缺点。Logical Logging 记录的日志内容较少，比方 update 操作，Logical Logging 只须要记录一条 update 语句即可，日志记录开销少。毛病是在并发场景下较难实现，当同时有多个事务产生更新操作时，数据库外部会将这些操作调度为串行化序列执行，须要机制来保障每次回放操作的执行程序与调度产生的程序统一。所以，大多数数据库系统采纳 Physical Logging 来保障数据恢复的一致性，事务管理器（并发管制子系统）所产生的事务操作执行程序会以日志的形式被记录下来，复原子系统依据日志程序可能保障每一个数据项批改的回滚和重放都依照程序严格执行。但目前，有一些数据库系统仍旧应用 Logical Logging，如内存数据库引擎 VoltDB，这是因为 VoltDB 引擎设计上没有并发管制，每个 CPU 内核都程序执行所有操作，因而能够通过 Logical Logging 按序回放。

对于数据库管理系统而言，要保障故障产生状况下的数据持久性和正确性，因而复原子系统不可或缺。在事务执行过程中，须要撤销时可能回滚以保障原子性；但同时复原子系统会带来性能影响，因为所有日志记录只有刷到磁盘上才算真正落盘，即便事务所有操作全副实现，也肯定要等日志落盘后能力响应客户端，因而 Logging 的性能往往成为整个零碎的性能瓶颈。

— Recovery System Optimization—

对于日志或复原子系统的优化，次要有两类技术，一类是 Group Commit，另一类是 Early Lock Release。

• Group Commit

Group Commit 是将并行执行的一组事务日志一起刷到磁盘，而非分事务每条日志刷一次。日志有独自的日志缓冲区，所有事务先把日志写进日志缓冲区，通过设置独自线程定时将日志缓冲区中的内容刷进磁盘，或当日志缓冲区存储满时再刷到磁盘。

操作系统提供了 Sync、Fsync、Fdatasync 等不同写磁盘的形式，其中 Sync 把数据刷到操作系统文件缓冲区时就视为完结，随后靠操作系统后盾过程把缓冲区的内容刷到磁盘，因而通过 Sync 形式刷磁盘可能会造成数据失落。数据库系统通常采纳 Fsync 进行日志落盘，当记录真正写到磁盘外面时才返回。Fsync 是将文件数据以及文件元数据如批改工夫、文件长度等信息一起写到磁盘；而 Fdatasync 跟 Fsync 的区别在于其只刷数据而不刷元数据。

在一些 DBMS 中，会混用 Fsync 和 Fdatasync：当元数据批改不影响 Logging，比方只有文件批改工夫变动，这时只用 Fdatasync 即可；但如果操作批改了文件长度，这时就不能用 Fdatasync，因为 Fdatasync 并不保留元数据批改信息，在复原时会造成内容局部缺失。因为很多 DBMS 在写日志时不是以增量形式减少日志文件内容，而是一次性为日志文件调配足够空间，在之后的写日志过程中日志文件长度放弃不变，所以能够用 Fdatasync 将日志写到磁盘。能够看到，Group Commit 每次将一组事务应用一个零碎调用写到磁盘，合并很多事务 I /O，从而升高整个零碎的 I /O。

• Early Lock Release

在基于锁机制实现并发管制时，如果前序事务的锁没有开释，前面的事务只能处于期待锁的状态。图中彩色局部示意正在进行的事务操作，灰色局部是期待日志落盘的工夫，尽管此时对数据不做批改，但只有等日志刷到磁盘后能力开释锁。Early Lock Release 是一种面向此场景进步性能的优化办法，策略是当事务中解决工作的局部做完就开释锁，而后再将日志落盘，缩短下个事务期待锁的工夫，进步并发执行水平。

但这种形式同样存在缺点，比方第一个事务曾经开释锁，但在日志落盘时呈现故障须要回滚，但因为此时锁曾经被下一个事务取得，下一个事务要和上一个事务一起回滚，因而零碎须要保护事务间的依赖关系。在事实中，锁的提前开释技术在数据库中被宽泛应用。对于索引构造，如果对索引中的某个节点加锁，会产生较大影响范畴，因为一个索引叶子节点往往波及一连串的很多数据记录。如果对叶子节点加锁，相干记录都会被锁住。因而在索引的应用上，通常会采纳 Early Lock Release 而非两阶段封闭协定，以缩短数据记录被锁住的工夫。

— ARIES 算法—

在基于磁盘的数据库系统中，复原子系统大都是基于 ARIES（Algorithms for Recovery and Isolation ExploitingSemantics）算法实现。ARIES 对于数据缓冲区和日志缓冲区的治理采纳 Steal + No Force 的管理策略（对于 Steal + No Force 的介绍在《内存数据库解析与主流产品比照（一）》中有具体提到）。在 ARIES 中，每条日志会有一个顺序号 LSN（Log Sequence Number），如下图中 LSN 10 号的日志是事务 T1 写 Page 5 的更新操作；20 号 LSN 是事务 T2 写 Page 3 的更新操作。须要留神的是，日志中会保留有事务 end 记录，标识事务已 commit 并返回客户端，示意该事务所有操作曾经实现。如果日志中只有 commit 而没有 end，那可能意味着事务曾经实现，但客户端可能没有收到响应。

• ARIES 三阶段复原

ARIES 的复原算法分三个阶段：Analysis、Redo、Undo，每阶段具体细节前面会具体介绍。

1. Analysis：在呈现 crash 重启后，零碎首先会从磁盘上读出日志文件，剖析日志文件内容，判断哪些事务在零碎 crash 时处于 Active 状态，以及哪些 Page 在呈现故障时被批改过。
2. Redo：零碎在 redo 阶段依据日志重现故障现场，包含将内存中的 Dirty Page 复原到 crash 时的状态，相当于重放日志历史记录（Repeating History），并将每条日志记录都执行一遍，包含没有 commit 的事务日志。
3. Undo：Undo 阶段零碎开始撤销没有实现的事务。上图是日志记录的简略示例，零碎在 LSN 60 后 crash，其中日志中有事务 T2 end 的标记，所以 T2 曾经提交，而事务 T1 和 T3 都尚未实现，事务 T1 和 T3 对于 P1、P3 和 P5 的批改如果已落盘，就须要从磁盘上撤销。

• 日志记录的数据结构

对于 ARIES 复原子系统，复原过程须要基于 Logging 所存储的信息进行。ARIES 中日志由多条日志记录组成，一条日志记录里蕴含批改数据项的事务 ID、Page ID + Offset、长度、批改前后的数值以及额定的管制信息。

ARIES 的日志类型包含 Update、Commit、Abort、End 以及弥补日志记录 CLR（Compensation Log Record）。CLR 用于预防因事务回滚过程中呈现故障造成影响，当事务回滚时，每回滚一条日志就记录一条 CLR，零碎能够通过 CLR 判断哪些操作曾经回滚，如果不记录 CLR 则可能呈现操作回滚两次的状况。

在失常记录日志时，ARIES 会记录 redo 和 undo 信息，记录的日志蕴含批改前后的值等。一般来说，日志落盘是程序写，因而数据库在配置上会为日志服务独自安顿磁盘，不和存储数据记录的盘混用，以晋升日志写的性能。

上面是 ARIES 中日志落盘示意图，图中右侧序列代表所有日志，青蓝色局部代表曾经落盘的日志，橙色局部示意还在日志缓冲区里的日志。ARIES 会记录 Flushed LSN，代表目前已有哪些缓冲区的日志曾经刷到磁盘。此外，保留数据的每个磁盘块中都会记录一个 Page LSN，用来示意批改此数据 Page 的所有操作中对应的最大日志号（即最初一个批改数据 Page 的操作所对应的日志号）。在把数据缓冲区里的数据刷到磁盘时，通过判断 Page LSN 与 flushed LSN 的大小决定是否能够将数据刷到磁盘。如果 Page LSN 小于等于 Flushed LSN，阐明批改这个数据页面的所有日志记录都已落盘，因而数据也能够落盘，这就是所谓的 WAL（Write-Ahead-Log），日志总是先于数据写到磁盘。

此外，日志记录中还保留了 Prev LSN 来对应日志所属事务的前一个日志号。因为在零碎中所有事务共享日志缓冲区，因而产生的日志是穿插在一起的，能够通过 Prev LSN 把属于同一个事务的所有 LSN 串联起来，来找到事务所对应的所有日志。

复原子系统中还须要保护 Xact Table 和 Dirty Page Table。Xact Table 用来记录所有流动的 Transaction 的状态如 active、commit、abort、end 等；同时还记录事务最初产生的日志号 Last LSN。Dirty Page Table 用来记录哪些数据 Page 从磁盘上加载到缓冲区后被批改过，以及每个 Page 最早批改时的日志号 Rec LSN（即数据 Page 被加载到缓冲区后第一个批改操作所对应的日志号）。

除了在日志中记录信息外，为保障复原能够胜利实现，数据库系统还须要用 Master Record 记录 Checkpoint 的 LSN，保障在每次复原时只须要从最近的 Checkpoint 开始即可。因为数据库系统在做 Checkpoint 时须要停机（不容许任何事务执行），这对于使用者很难承受，因而 ARIES 中的 Checkpoint 采纳 Fuzzy Checkpoint 形式，即在进行 Checkpoint 时容许事务能够继续一直执行。Fuzzy Checkpoint 会产生两个日志记录：Begin_Checkpoint 和 End_Checkpoint。Begin_Checkpoint 负责记录开始 Checkpoint 的工夫点，End_Checkpoint 记录 Xact Table 和 Dirty Page Table，而 Checkpoint 的 LSN 会写到磁盘的 Master Record 上进行长久存储。以上即复原所需的全副数据结构，各类 LSN 的整顿总结如下表所示。

— 数据库系统的事务复原—

• 简略事务复原

对于简略事务复原(零碎没有呈现故障，而是事务在执行过程中不再持续)，此时须要进行回滚。回滚时，零碎首先从 Xact Table 中找出最新的 LSN 进行 undo，随后通过该日志记录的 Prev LSN 找到前序日志记录再持续 undo，直到整个事务彻底回放到开始时的状态。和失常事务操作类似，undo 时的数据实际上须要加锁，并在回滚前会记录弥补日志 CLR。CLR 会记录 undo next 的 LSN 号以指向下一条须要 undo 的 LSN，在 undo 到 Transaction Start 的 LSN 时，记录 Transaction Abort 和 Transaction End 表明回滚完结。

• 呈现故障的事务复原

在前文咱们提到，ARIES 的故障复原分为三个阶段，上面将具体介绍三个阶段的执行细节。

1. Analysis 阶段

   在 Analysis 阶段，零碎从磁盘上的 Master Record 中获取最初一个 Checkpoint 日志记录，重构出 Xact Table 和 Dirty Page Table，并从 Begin_Checkpoint 日志记录开始程序解决后续的日志记录。在遇到一个事务的 end 日志时，将其从 Xact Table 中去除；如果遇到事务的 commit 日志，则更新 Xact Table 中对应事务的状态；如果遇到其它日志记录，判断该事务是否在 Xact Table 中，不在则将其退出 Xact Table，并更新 Xact Table 中该事务的 Last LSN 为以后日志记录的 LSN。此外，零碎会判断日志记录中更新的数据 Page 是否在 Dirty Page Table，如不在则将该数据 Page 退出到 Dirty Page Table，并将其 Rec LSN 设为以后日志号。

2. Redo 阶段

   零碎在 Redo 阶段首先找出 Dirty Page Table 中所有 PageRec LSN 中最小的，作为 redo 的起始地位，因为再往前的日志记录对应的数据批改都已落盘，不会呈现在 Dirty Page Table 中。随后零碎从 redo 的起始地位开始，按程序对后续更新日志记录（包含 CLR）执行 redo 操作（重放）。如果遇到操作更新的 Page 不在 Dirty Page Table 中，或 Page 在 Dirty Page Table 中但 Rec LSN 大于以后 LSN，或磁盘上的 Page LSN 大于以后的 LSN，则都示意该 LSN 对应记录曾经落盘，能够间接跳过，不须要执行 redo。在 redo 时，零碎不须要再记录日志，因为 redo 只是实现整个内存状态的重构，如果在 redo 时又呈现了系统故障，则依照原来操作从新进行一遍。

3. Undo 阶段

   Undo 阶段目标是撤销在系统故障时未实现的事务，开始时会建设一个须要 undo 的日志汇合，把每个须要回滚的事务的最初一条日志号放入该汇合中，而后开始进行循环解决。首先零碎从汇合里挑出最大的 LSN 即最初一条进行 undo，如果这条日志是 CLR 弥补日志，且它的 undo-next 为空，那么阐明事务曾经实现 undo，能够记录一条 End 日志表明事务完结；如果弥补日志的 undo-next 不等于空，阐明还有下一条须要 undo 的日志，那么就将下一条日志的 LSN 放入汇合；如果是更新日志，就回滚该日志且记录一条 CLR 日志，而后把日志的 Prev LSN 退出汇合。零碎会依照上述过程一直循环，直到整个 undo 汇合为空。

   接下来通过例子梳理一下整个过程。零碎首先做了 Fuzzy Checkpoint，呈现了两次更新：T1 批改了 P5，T2 批改了 P3。随后，T1 abort 勾销，LSN40 记录了弥补日志——回滚 LSN10，随后 T1 End。接下来其余事务持续进行：T3 批改了 P1，T2 批改了 P5。此时呈现了 Crash，该怎么做复原呢？首先在 Analysis 过程，由 Checkpoint 开始向后扫描，发现 T1 曾经 End 不须要 redo，T2、T3 没有 end 能够进行 redo，因而 Xact Table 里仅有 T2、T3，Dirty Page Table 包含 P1、P3、P5。在剖析实现后，进行 redo 重做过程复原故障现场，随后在 T2、T3 进行 undo 每一条日志时记录 CLR，直到 undo 到每个事务最后的一条。

   如果在复原的过程中又呈现了 Crash（如下图所示），曾经 undo 的两个操作因为记录了 CLR，新 redo 会重做这两个 CLR，而新 undo 过程不会再从新回滚。复原零碎会在原有根底上持续进行，直到所有的事务全副 undo 实现。

• ARIES 小结

ARIES 是一个具备成熟设计，可能保障事务原子性和持久性的复原零碎，应用 WAL 和 Steal + No Force 缓冲区管理策略，且不影响零碎正确性。ARIES 中 LSN 是枯燥递增的日志记录惟一标识，通过链接形式把一个事务的所有日志串联在一起。Page LSN 用来记录每个页面最初批改操作对应的日志号，零碎通过 Checkpoint 缩小 Recovery 的开销。整个复原分为 Analysis、Redo、Undo 三个步骤，剖析的目标是找进去哪些事务须要 redo，哪些页面被批改过，批改是否曾经落盘；随后通过 redo 复原故障现场，利用 undo 将须要撤销的事务回滚。

— 本文小结—

本文介绍了复原零碎 Logging 和 Recovery 的基本概念，并探讨了传统基于磁盘的数据库管理系统中复原子系统 ARIES 的技术原理。下一篇文章会持续摸索数据库的复原子系统，探讨 DBMS 复原中的 Early Lock Release、Logical Undo，介绍两种数据库的复原技术以及内存数据库的复原办法。

参考文献：

1. C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz. 1992. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking And Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17, 1 (March 1992), 94–162.
2. Antonopoulos, P., Byrne, P., Chen, W., Diaconu, C., Kodandaramaih, R. T., Kodavalla, H., … & Venkataramanappa, G. M. (2019). Constant time recovery in Azure SQL database. Proceedings of the VLDB Endowment, 12(12), 2143-2154.
3. Zheng, W., Tu, S., Kohler, E., & Liskov, B. (2014). Fast databases with fast durability and recovery through multicore parallelism. In 11th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 14) (pp. 465-477).
4. Ren, K., Diamond, T., Abadi, D. J., & Thomson, A. (2016, June). Low-overhead asynchronous checkpointing in main-memory database systems. In Proceedings of the 2016 International Conference on Management of Data (pp. 1539-1551).
5. Kemper, A., & Neumann, T. (2011, April). HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. In 2011 IEEE 27th International Conference on Data Engineering (pp. 195-206). IEEE.