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

对于事务型数据库而言，最要害的性能是要保障事物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.