作者：实验室小陈 / 大数据凋谢实验室
上一篇文章《数据库复原子系统的常见技术和计划比照（一）》中，咱们根本介绍了数据库管理系统中的 Logging & Recovery 复原子系统，具体探讨了基于 Physical Logging 的支流复原算法 ARIES 的概念和技术实现。本文将华师大宫学庆传授对于介绍 Logical Undo Logging 的原理以及两种数据库系统 SQL Server(Azure)和 Silo 的复原技术的介绍分享给大家。
— Logical Undo Logging —
在上篇文章中，咱们简略介绍了 Early Lock Release 的优化思路：通过将索引上的 Lock 提前开释以进步并发水平，但同时会在事务之间产生依赖关系，导致级联回滚。比方第一个事务曾经开释锁，但在刷日志时呈现故障须要回滚，此时锁已被下一个事务取得，那下一个事务要和后面的事务一起回滚，极大地影响零碎性能。
基于这样的状况，复原零碎中引入了 Logical Undo Logging，在肯定水平上解决了上述问题。Logical Undo Logging 的根本思维是在事务回滚时撤销批改操作，而不是对数据的批改，如插入的撤销是删除，对数据项 + 1 的撤销是对数据项 -1。
此外解决 Logical Undo 时引入了 Operation Logging 的概念，即记录日志时对事务一些操作采纳非凡的日志记录形式，称为 Transaction Operation Logging。当 Operation 开始时，会记录一条非凡的 Operation Logging，模式为 log<Ti, Oj, operation-begin>，其中 Oj 为惟一的 Operation ID。在 Operation 执行过程中，零碎失常进行 Physical Redo 和 Undo 日志记录；而 Operation 完结后，则会记录非凡的 Logging <Ti, Oj, operation-end, U>，其中 U 便是对于曾经进行的一组操作的 Logical Undo 操作。
举例来说，如果索引插入新键值对（K5, RID 7）到叶子节点 Index I9，其中 K5 存储在 Index I9 页面的 X 地位，替换原值 Old1；RID7 存储在 X + 8 地位上替换原值 Old2。对于该事务，记录日志时会在最后面增加操作开始记录 <T1, O1, operation-begin>，两头 Physical Logging 失常记录数值的更新操作，完结时记录完结日志 <T1, O1, operation-end,（delete I9, K5, RID7）>，其中（delete I9, K5, RID7）是对 T1 操作的 Logical Undo，即删除 I9 节点页面的 K5 和 RID7。
在 Operation 执行完结后，能够提前开释锁，容许其余事务能胜利向该页面插入 < Key，Record ID>，但导致所有 Key 值从新排序，使得 K5 和 RID7 来到 X 和 X + 8 的地位。此时如果进行 Physical Undo，须要将 K5 和 RID7 从 X 和 X + 8 撤回，但理论中二者的地位已产生扭转，按原日志记录进行 Physical Undo 并不事实。但从逻辑上看，Undo 只须要把 K5 和 RID7 从索引节点 I9 删掉即可，因而在日志中退出操作日志（delete I9, K5, RID7），示意如果进行 Undo，只须要依照这个逻辑指令进行即可。
在回滚时，系统对日志进行扫描：如果没有 operation-end 的日志记录，则进行 Physical Undo，这是因为只有在 Operation 完结时才会开释锁，否则就阐明锁还没有被开释，其余事务不可能批改其锁定的数据项。如果发现存在 operation-end 日志，阐明锁曾经被开释掉，此时只能进行 Logical Undo，把 begin operation 和 end operation 之间的所有日志跳过，因为这些日志的 Undo 已被 Logical Undo 代替。如果在 Undo 时发现了 <T,O, operation-abort> 日志，则阐明这个 Operation 曾经 Abort 胜利，能够间接跳过两头日志，回到该事务的 <T, O,operation-begin> 持续往上 Undo；当 Undo 到 <T,start> 的日志时，表明该事务的全副日志均曾经撤销实现，记录 <T, abort> 日志示意 Undo 完结。
其中须要留神的是，所有 Redo 操作都是 Physical Redo，这是因为 Logical Redo 的实现非常复杂，例如须要决定 Redo 程序等，因而大多数零碎里所有的 Redo 信息都是 Physical 的。此外，Physical Redo 和锁提前开释并不抵触，因为 Redo 只有在呈现故障时才会进行，此时零碎挂掉导致所有的锁曾经都没有了，重做的时候要从新申请锁。
— SQL Server：Constant Time Recovery —
对于大多数商业的数据库系统如 SQL Server 等，大多采纳 ARIES 复原零碎，因而 Undo 所有未 Commit 事务的工作量与每个事务所做的工作内容成正比。事务做的操作越多，Undo 所破费的工夫就越长。因为事务操作可能是一条语句但更新很多记录，Undo 就须要对记录逐条撤销，导致撤销工夫可能过长。尽管正确性失去保障，但对于云服务或者对可用性要求高的零碎将难以承受。为了应答这种状况，呈现了 CTR 优化技术（Constant Time Recovery），将 ARIES 零碎和多版本并发管制相结合，实现固定工夫复原。固定工夫复原是指不论遇到什么状况，都利用数据库系统中的多版本信息，保障复原操作在确定的工夫内实现。其根本思维是利用多版本数据库系统中的不同数据版本，确保数据 Undo 到一个正确的状态，而不是用原来 WAL 日志里的信息进行复原。
- MS-SQL 的并发管制
SQL Server 在 05 年开始引入了多版本并发管制，但晚期多版本仅用来实现 Snapshot 隔离级别而非复原，支持系统依据 Snapshot 的工夫戳去读数据库中的数据。在更新数据时，多版本并发管制能够在数据 Page 上对记录进行就地更新，但旧版本没有丢掉，而是被独自放在 Version Store 中。Version Store 是一个非凡的表，只容许一直的增加数据（Append-Only），通过指针链接指出该记录的老版本，老版本又会指向上一个更老的版本，进而形成一个数据版本链。在拜访数据时，能够依据事务的工夫戳来决定读取哪个版本数据。因而，晚期多版本 Version Store 的更新并不需要记录日志，因为一旦呈现故障，重启当前所有工夫戳都是最新的，只有放弃最初一个版本即可，不会有比这个版本更早的 Snapshot 拜访需要。对于以后 Active 的事务，能够依据当下工夫戳，通过 Garbage Collection 机制将老版本抛弃。
CTR 基于原 Version Store 进行优化，实现了 Persistent Version Store，使得旧版本可能长久化存储。在 CTR 技术下，零碎更新 Version Store 时会记录日志为复原进行的筹备，使得 Version Store 的体量和开销变大，于是呈现两种实现老版本存储的策略 In-Row Versioning 和 Off-RowVersioning。
In-Row Versioning是指对于更新一条记录的操作，如果只是改变很小的数据量，就不须要放进 Version Store 存储，而是在记录后加一个 delta 值，阐明属性的数值变动。其目标是为了升高 Versioning 时的开销，因为同一个地位改变的磁盘 I / O 绝对较小。
Off-Row Versioning 则 有一个非凡的零碎表，用来存储所有表的老版本，通过 WAL 记录 Insert 操作的 Redo 记录。当批改量较大导致 In-Row Versioning 无奈齐全保留数据更新时，便采纳 Off-Row Versioning 形式。如下图中，A4 行的 Col 2 为 444，在更新为 555 后会写入一个 delta，用于记录版本变动。但这种批改受限于数据量的大小，以及记录自身所在的页面上是否有闲暇空间。如果有闲暇空间就能够写入，若没有就须要把更新的记录放入 Off-Row Versioning 表中。
复原过程中，CTR 分为三个阶段实现（Analytics、Redo 和 Undo）。分析阶段和 ARIES 相似，用来确定每一个事务的当下状态如 Active、Commit 和须要 Undo 的事务。在 Redo 时，零碎会把主表和 Version Store 的表重放一遍，都复原到呈现 crash 的状态。Redo 实现后，数据库就能够上线对外服务。CTR 的第三步是 Undo，在分析阶段完结后，曾经晓得哪些事务未提交，Undo 阶段能够间接将这些事务标记为 Abort。因为每条 Record 的不同版本都会记录与该版本相干的事务号，因而后续事务在读到该版本时，首先判断相干事务的状态，如果是 Abort 就疏忽掉该版本而读上一个旧版本。这样的复原形式使得在读到不可用版本时，须要依据链接去找前一个版本，尽管会带来额定性能开销，但缩小了数据库的下线工夫。在持续提供服务后，零碎能够在剩下工夫进行 Garbage Collection，将生效老版本缓缓革除，这样的机制叫做 Logical Revert。
- Logical Revert
Logical Revert 有两种形式。第一种是用后盾过程 Background Cleanup 把所有数据块扫描一遍，判断哪些是 Garbage 能够回收。判断条件为：如果主表中最初一个版本来自于曾经 Abort 的事务，那就从 Version Store 里拿上一个曾经 Commit 的旧版本放到主表。即便此时不做这件事件，前面应用数据时也是会到 Version Store 中读数据。因而，能够通过后盾的 Garage Collection 过程，缓缓进行版本搬迁。第二种是如果事务在更新数据时，发现主表里的版本是 Abort 的事务的版本，就会笼罩该版本，而此时这个事务的正确版本应该在 Version Store 中。
能够看到，CTR 的复原是一个固定工夫，只有前两个阶段完结即可，而前两个阶段所需工夫实际上只与事务的 Checkpoint 无关。如果做 Checkpoint 的距离是依照固定的日志大小决定，当 Redo 阶段完结，数据库便能够复原工作，且复原工夫不会超过一个固定值。
— Silo：Force Recovery —
Silo 是哈佛大学和 MIT 单干钻研的一个高性能内存数据库系统原型，解决了并发水平过高导致的吞吐率降落问题。如果一个 CPU 内核对应一个线程来执行事务，在不存在竞争的状况下，吞吐率随着核数减少而减少，但高到肯定水平后会呈现降落，可能的状况是因为呈现了某些资源竞争所导致的瓶颈。只管在事务执行过程中每个线程独自执行，但最终所有事务在提交前都须要拿到事务 ID，事务 ID 是全局范畴的，事务通过原子性操作 atomic_fetch_and_add(&global_tid)取得 commit 时的 ID。而事务 ID 的调配通过全局的 Manager 角色实现，在事务申请 ID 时，Manager 会通过计数 + 1 来更新事务计数器，保障事务 ID 的全局惟一且递增，因而 Manager 写操作的速度会是零碎性能的下限。当并发越来越高且事务都去申请 ID 时，就会呈现竞争关系使得等待时间变长，导致吞吐率降落。
- 乐观的并发管制
对于性能瓶颈问题，Silo 的解决思路是多核并发工作 + 共享内存的数据库里采纳乐观并发管制。乐观并发管制在《内存数据库解析与主流产品比照（三）》中介绍过，指事务在执行时认为相互之间没有任何影响，仅在提交时查看是否存在抵触，如果没有抵触再去申请全局的事务 ID 实现 Commit。而 Silo 通过设计 Force Recovery 勾销了所需的全局事务 ID，应用 Group Commit 的概念，将工夫分成多个 Epoch，每个 Epoch 为 40 毫秒。Epoch 蕴含了以后时间段波及的多个事务，因而能够通过提交 Epoch 的形式将这一组事务一起提交，不须要为每个事务逐个申请全局事务 ID。但这种设计的缺点在于如果事务执行工夫超过 40 毫秒，带来的跨级会对提交和复原带来影响。
在 Silo 中，每个事务由 Sequence Number + Epoch Number 来辨别，Sequence Number 用来决定执行过程中事务的程序，通过 Sequence Number 和 Epoch Number 独特决定复原策略。每个事务会有事务 ID（TID），事务依照 Epoch 来进行 Group Commit，整体的提交依照 Epoch Number 的先后实现序列化。事务 ID 为 64 位，由状态位、Sequence Number 和 Epoch Number 独特组成，其中高位是 Epoch Number，两头是 Sequence Number，前三位是状态位。每条记录都会保留对应的事务 ID，其中状态位用来寄存拜访记录时的 Latch 锁等信息，内存数据库和传统基于磁盘的 DBMS 数据库相比，其中一个重要区别就是锁的治理是和记录放在一起，并不会另外治理 Data Buffer 和 Locking Table。
- 事务提交的三个阶段
因为 Silo 采纳规范的乐观并发管制，因而只有在提交时才会查看是否存在抵触。在 pre-commit 阶段，读数据项时会把数据项中的事务 ID 存入 Local Read-Set，随后再读取数值；而在批改数据记录时，也须要把批改的数据记录放入 Local Write-Set 里。
Silo 事务提交时候三个阶段，第一步为 Local Wite-Set 里所有要写的记录拿到锁，锁信息保留在事务 ID 中的状态位，通过原子操作 Compare and Set 获取；随后从以后的 Epoch 读出全副事务。零碎里有专门线程负责更新 Epoch（每 40ms+1），所有事务不会去竞争写 Epoch Number 而只有读该值即可。事务提交的第二步是查看 Read-Set，Silo 中每个数据项都蕴含最初一个对其进行更新的事务的 ID，如果记录的 TID 发生变化或记录被其余事务锁住，阐明从读到提交的过程中记录曾经更改，须要进行 Rollback。最初是生成事务 TID，在新事务 Commit 时，TID 中的 Sequence Number 应该是一个大于所有读到的 Record 的事务 ID 的最小值，以保障事务递增。提交后只有全副事务落盘后，才会返回后果。
- Recovery——SiloR
SiloR 是 Silo 的复原子系统，应用 Physical Logging 和 Checkpoints 来保障事务的持久性，并在这两个方面采纳并行复原策略。后面提到，内存数据库中的写日志操作速度最慢，因为日志波及写盘，磁盘 I / O 是整个零碎架构的性能瓶颈。因而 SiloR 采纳并发形式写日志，并存在以下假如：零碎里每个磁盘有一个日志线程，用来服务一组工作线程，日志线程和一组工作线程共享一个 CPU Socket。
基于此假如，日志线程须要保护日志缓冲区池（池中有多个日志缓冲区）。一个工作线程如果要执行，首先须要向日志线程索要一个日志缓冲区写日志，写满后交还日志线程落盘，同时再取得新的日志缓冲区；如果没有可用的日志缓冲区，工作线程便会阻塞。日志线程会定时将缓冲区刷到磁盘，缓冲区空进去后，能够持续交给工作线程解决。对于日志文件，每 100 个 Epoch 生成 1 个新日志文件，旧日志文件依照固定规定生成文件名，文件名最初局部用来标识日志中最大的 Epoch Number；日志内容则记录了事务的 TID 和 Record 更新的汇合(Table, Key, Old Value -> New Value)。
下面介绍了多核 CPU 中一个核所解决的事件，实际上 CPU 中每个核都以同样的形式工作，会有一个专用线程来追踪目前哪些日志曾经全副刷到磁盘上，并把最新曾经落盘的 Epoch 写到磁盘上的固定地位。所有事务通过比拟本人以后的 Epoch 和曾经落盘的 Persistent Epoch（以下简称 Pepoch），如果小于等于 Pepoch，表明日志曾经落盘，能够向客户端返回。
- 复原过程
和 ARIES 复原零碎一样，SlioR 也要做 Checkpoints。SlioR 的第一步是把最初一个检查点的数据读出再进行复原；因为内存数据库不对索引做日志，因而索引须要在内存中重构。第二步是日志回放，内存数据库只做 Redo 不做 Undo，Redo 操作并不是和 ARIES 一样按失常日志程序进行，而是从后向前执行间接更新到最新版本。在日志回放时，先查看 Pepoch 的日志文件，找出最新的 Pepoch 号，但凡超过该 Pepoch 号的日志记录，则认为对应的事务没有返回给客户端，因而能够疏忽。日志文件的复原采纳 Value Logging，对于每条日志，检查数据的 Record 是否曾经存在，如果不存在就依据日志记录生成数据 Record；如果存在则比拟 Record 和日志中的 TID。如果日志中的 TID 大于 Record 中的 TID，就证实须要 Redo，用日志中的新数据值来替换旧值。能够看到，SiloR 的 Redo 不是像 ARIES 一样一步步复原到故障现场，因为 ARIES 的目标是要将磁盘上的数据恢复到最终正确状态，而 SiloR 是要把内存当中的数据恢复到最新正确状态。
— In-Memory Checkpoint —
对于内存数据库，复原零碎相比磁盘 DBMS 零碎较为简单些，只有对数据做日志即可，索引则不须要，且只需 Redo 日志而不需 Undo 日志。所有数据都是间接笼罩批改，不须要治理 Dirty Page，不会存在 Buffer Pool 和缓冲区落盘问题。但内存数据库仍受限于日志同步工夫开销，因为日志仍旧要刷到非易失性存储（磁盘）。晚期 80 年代时，内存数据库的钻研都是假如内存数据不会失落，如带电池的内存（断电后还能够用电池撑持一段时间工作）；还有非易失性内存 NVM（Non-Volatile Memory）等技术，但目前这些技术还远达不到广泛应用，仍旧要思考长久化存储。
长久化零碎要求对性能影响最小，不能影响到吞吐量和提早。为缩小对事务执行的影响，内存数据库谋求的第一指标是复原速度，即在故障后能够最快工夫内实现复原。因而串行复原无奈满足速度要求，目前有很多钻研工作都集中在对内存数据库的并行日志钻研，而并行使得对于锁和 Checkpoints 的实现都变得复杂。
对于 In-Memory 的 Checkpoints，实现机制通常和并发管制严密交融，并发管制设计决定了检查点如何实现。现实的 In-Memory 中 Checkpoints 第一个要求是不能影响失常的事务执行，并且不能引入额定提早以及占用太多内存。
Checkpoints 品种：Checkpoints 分为一致性 Checkpoints 和 Fuzzy Checkpoints 两类。一致性 Checkpoints 指产生的查看点中的数据不蕴含任何未提交的事务，如果蕴含则在 Checkpoints 时去掉未提交的事务；Fuzzy Checkpoints 蕴含曾经提交和未提交的事务，在复原时才把未提交的事务去掉。
Checkpoints 机制：Checkpoints 机制分为两种，第一种能够通过开发数据库系统本身性能来实现 Checkpoint，比方应用多版本存储来做 Snapshot；第二种能够通过操作系统级别的 Folk 性能，拷贝出过程的子过程；随后把内存中所有数据拷贝一遍，但须要额定操作去回滚正在执行且还未提交的批改。
Checkpoints 内容：内容上 Checkpoint 分两种类型，一种是每次 Checkpoint 都全量拷贝数据；还有一种是增量 Checkpoint，每次只做本次与上一次之间产生的增量内容。二者差别在于 Checkpoint 时数据量以及复原时所须要的数据量的区别。
Checkpoints 频率：有三种 Checkpoint 频率。一是基于工夫的定周期 Checkpoint；二是基于固定日志的大小的 Checkpoint；最初一种是强制性 Checkpoint，如数据库下线后强制进行 Checkpoint。
— 本文小结 —
在本次两篇文章专栏中，咱们对数据库系统的复原子系统进行了介绍，别离介绍了 Physical Logging 的支流复原零碎 ARIES 和 Logical Undo Logging 的相干概念和技术实现。此外，咱们介绍了两个数据库系统的复原策略——SQL Server 的 CTR 固定工夫复原以及内存数据库系统 Silo 的 Force Recovery 复原原理。下一讲将探讨数据库系统的并发控制技术。
参考文献：
- 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.
- 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.
- 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).
- 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).
- 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.