共计 9206 个字符,预计需要花费 24 分钟才能阅读完成。
作者:实验室小陈 / 大数据凋谢实验室
上一篇文章《数据库复原子系统的常见技术和计划比照(一)》中,咱们根本介绍了数据库管理系统中的 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.