不衰的经典: ARIES事务恢复 [数据库学习的成人试炼] - 知乎

一不小心文章又写长了。。。。

前言

已经好几个月没写东西了, 比较忙, 开的技能树有点多, 主要在刷概率/统计/优化/NLP相关的东西, 分布式的东西看的比较少, 只是偶尔刷刷小红书的推荐论文还有看看datalake相关的东西; 不过ARIES这篇论文还是很值得在知乎记个笔记的.

ARIES这篇是在刷 小红书的时候在第三章“Techniques Everyone Should Know”(很明显我还没入门啊, 这些paper几乎都没看过。。。。)一章里看到的, 全文69页，有点难读, 主要是因为作者在行文的时候穿插了大量的和SystemR和DB2等系统的算法各种对比, 使得不了解这两个系统的读者容易"走神", 和理解混乱；

92年的老论文了, 但是它提供了一个经典的“No Force, Steal” write-Ahead-Log的实现, 而“No Force, Steal”所带来的高性能，是(按小红书编者所言)“几乎是所有商用数据库都必定提供的”,

...these policies allow high performance are present in almost every commercial RDBMS offering but in turn add complexity to the database...

而这篇论文的重要性和难度, 对它的通读理解像是经历数据库学习的“成人试炼”

... it is perhaps the most complicated paperin this collection. In graduate database courses, this paper is a rite of passage. However, this material is fundamental, so it is important to understand...

(就笔者本人的读后感来讲, 这篇论文的复杂之处在于各个方面的环环相扣, 很难脱离开其他东西来单独理解其中的一面, 而需要整体有个印象之后，再精读一遍才能理解其中的奥妙配合;)

---

概念, 术语, 缩写, 和数据结构

Tx:指事务

硬盘页面：硬盘文件的一页

内存页面：硬盘页面被取出放进内存时的内存镜像, 被修改完后, 内存页面可以写回相应的硬盘页面;

脏页: 内存页面写了内容, 但是内容还没有同步回硬盘页面;

Buffer Manager(BM): 当有事务需要写某页面时, 负责把硬盘页面放进Buffer里变成内存页面, 同时负责把内存页面写回硬盘, 由于内存有限, Buffer Manager需要小心调节什么时候把内存页面写回硬盘并释放内存空间

Log Record: 数据库的页面操作和一些数据管理的操作都需要记录在一个log里; Log Record有3种, Redo/Undo/CLR(Compensation Log Record),

1. Redo Log记录了一个(Page-oriented级, 后边会解释)"写入/更改"数据库的操作所需要的的信息, 使得当脏页还没写回硬盘，系统就崩溃了的情况下, 可以通过Redo log来重复这个"写入/更改"操作, 恢复需要写的内容; Redo Log对已经Commit的Tx非常重要, 因为ARIES不要求tx commit时，tx所写的脏页都必须同步回硬盘；所以tx commit后，如果系统崩溃的话，我们就可以用Redo Log来replay对页面的更改来保证Committed Tx的写不丢失;（这就是Non-Force Policy）
2. Undo Log记录了rollback一个(Logical级，后边会解释)"写入/更改"数据库的操作所需要的的信息。 Undo Log对保证能够rollback Tx非常重要, 因为ARIES允许把还没commit的Tx所修改的页面被BM同步回硬盘，腾出内存空间给别的Tx使用（这就是Steal），那么如果最终我们需要rollback这个Tx, 我们需要Undo Log来rollback这个tx之前的"写入/更改"
3. CLR(Compensation Log Record)：CLR是ARIES的关键之一，当我们需要rollback，而使用Undo Log时，我们不仅需要按照Undo Log来更改(rollback)内存页面到之前的imge，(此后BM会决定什么时候把内存页同步回物理页面)，而且要记录具体如何修改这个页面的细节在log里作为一个CLR记录(由于Undo Log只是Logical Log，不具体指定需要修改哪个页面，比如Undo只是说要改哪个row，具体row在哪个页面不关心, CLR可以看作Undo Log的页面级执行细节log，或者伴随log), 这个CLR在Page-oriented级记录了如何更改一个页面来达到Undo的效果；由于CLR代表了页面级的修改, 所以CLR也看作是一种Redo Log(当Rollback需要redo时, 比如rollback更改了内存页面，但是内存页面还没有被同步回物理页面，此时系统崩溃重启，我们需要redo这个CLR)；

重点: ARIES使用Page-oriented级的Redo/CLR, 而使用Logical级的Undo

Log Record上需要记录的信息:

• TxID: 哪个Tx写了这个Log Record
• LSN(log sequence number):只增logNumber, 每个Log Record一个, 按写入顺序增长, 连续的log未必属于同一个Tx
• PrevLSN: 本Log Record上记录 同一个Tx的上一个写的Log Record的LSN
• PageId: 本Log Record要更改哪个数据页面
• UndoPrevLSN: 只存在于CLR这种Log Record上, 对应其所属的Undo Log Record的PrevLSN，或者说伴随的Undo Log处理完后，同一个Tx的上一个Log Record的LSN, (CLR是处理Undo Log时生成的), 它使得Tx的回溯Log Chain跳过了其相应的伴随Undo Log Record, 后边可以看到, 这是保证Undo Log不被多次处理的关键;

1, 2, 3可以看作合并的Redo/Undo log, 3‘ 和2’ 是3和2所的对应的CLR, 虚线代表它们的UndoPrevLSN“指针”

page_LSN: 内存/物理页面上的一个field, 记录的最后一个对当前页面进行修改的Log Record的LSN；对一个页面来说，ARIES只需要维护一个LSN即可，

Force the log: 强制把内存里的log按顺序写入硬盘, 直到某LSN, 系统可以运行后台进程来异步的force the log; （注意: 任何的log append都不需要立刻写入硬盘, 只需要存在于内存, BM会决定什么时候来把log写回硬盘;）

Physically undo/redo: 比如把记录更改前的row(或者此row的fields)的image作为undo log, 把更改后的row(或者此row的fields)的image作为redo log;

Operationally undo/redo: 相对于Physical，比如记录“add 5”到row15的field3上, 而不是记录add 5之后这个row或者这个field的image;

WAL(Write Ahead Log)协议：在ARIES的设计里,BM有很大的自由来决定什么时候来把脏页写回物理页面(主要体现在Non-Force, Steal里); BM只需要遵守WAL协议即可:

• 内存页面同步回物理页面之前, 必须保证所有对这个页面更改的Undo Log都已经force to disk了
• 在一个Tx Commit之前, 所有这个Tx的Redo Log都必须force to disk

Steal policy：如果对内存页面的更改可以随意同步回硬盘而不需要等待Tx commit, 那么我们称BM遵循了Steal policy；

使用Steal Policy主要是为了避免以下问题，如果我们使用“必须等待所有更改过页面的Tx都commit了才同步这个内存页到物理页面”的Non-Steal Policy, 那么

1. 如果需要支持行锁, 那么一个页面可能有多个行被不同的Tx更改, 那么这个页面必须等待所有的Tx都Commit, 但是如果不断有新的Tx来更改这个页面呢？这个页面就迟迟无法同步回物理页面，如果有长(持续时间)事务，那么情况会更糟
2. 在这种情况下, 要么我们每隔一段时间来锁住页面, 保证没有新的Tx可以更改这个页面, 这样等所有当前更改这个页面的Tx都commit之后就可以写回物理页面了（但是这样严重影响吞吐）；或者另外一种策略，持续不同步其回物理页面, 那么当内存页面持续被更改, 这个页面的物理页面内容就会远远落后于正确的内存页面; 那么failure recovery的时候, 就必须要花费非常多的Redo cost;
3. 同时non-steal policy也比Steal policy复杂, 因为要记录哪些脏页有uncommitted更改; 而steal policy写回物理页面时完全不在乎Tx commit了没有, 所以不需要区分脏页到底有没有uncommitted更改

Force policy: 之前也提到了, 如果我们要求Tx在commit前, 它所有的更改的页面必须写回到硬盘(同步回物理页面), 那我们说BM遵循force policy；相反, 如果我们没有这个要求, 那么BM遵循non-force policy

重点: ARIES的BM遵循 “Non-Force，Steal” Policy

除了Steal, 还有一个选择是完全不更改页面, 只等待commit时一起更改, 这叫做Deferred upating, 和ARIES的实现关系不大, 简单英文原文笔记下 （给未来的自己备注, 读者可以略过）

Deferred updatingis said to occur if, even in the virtual storage database buffers, the updates are not performed in-place when the transaction issues the corresponding database calls. The updates are kept in a pending list elsewhere and are performed in-place, using the pending list information, only after it is determined that the transaction is definitely committing. If the transaction needs to be rolled back, then the pending list is discarded or ignored. The deferred updating policy has implications on whether a transaction can “see” its own updates or not, and on whether partial rollbacks are possible or not.

Page-oriented redo:如果对页面的更改的伴随Redo log具体描述了一个页面是怎么更改的, 而不需要去查数据库的内部metadata, 且当failure recovery的时候, Redo发生在同一个页面; 那么我们说使用了Page-oriented redo; 注意: 这意味着页面的Redo是完全相互无关的, 可以independent的并行进行;

Logical redo:只在逻辑层面去记录修改, 比如我要把第n个row修改为xxx，但是具体第n个row是在哪个页面需要在redo的时候去检索, 由于磁盘管理或者index page leaf split的缘故, 一个逻辑row可能会从一个页面迁移到其他页面去, 那么一个对这个row的原始更改所发生的页面和failure recovery的时候需要redo的页面可能会不同;

page-oriented undo/ logical undo：同理

• Logical undo可以获得更高的并行度: 这是因为Logica undo允许一个Tx_A的uncommitted更改, 被另外一个Tx_B 移动到其他页面去(当Tx_B发生在Tx_A之后, 且需要分index的leaf page时)，如果只支持page-oriented undo, 那么Undo就已经写死了undo哪个页面了, 所以Tx-B必须等待Tx-A commit之后(绝对不会发生Undo Tx-A的情况), 才能进行分index leaf page，移动Tx-A的数据的操作;
• 支持logical undo, 那么即使逻辑row 被移动到了其他页面, 我们也可以在failure recovery的时候查询索引来找到row被移动到的页面来对其undo；

Tx Table: 用来记录所有正在进行的Tx信息的table, 包含

• LastLSN:Tx最新写的Log Record的LSN，注意，rollback时, 由于处理Undo log需要写CLR, 这些CLR会append在log queue里, 那么CLR也会被认为是"Tx最新写的Log Record" 而更新到Tx Table的LastLSN里；
• UndoNxtLSN:rollback时下一个需要处理的log record; 如果最新的log是CLR, 那么这个值就是CLR的UndoNxtLSN值, 而如果最新的log不是CLR, 那么这个值和LastLSN一致；

Dirty_Page Table和RecLSN: 用来记录脏页的Redo Log的“可能的”开始位置，由BM维护，每当BM把一个物理页面取出到内存之后，都会在Dirty_Page Table里注册一条关于这个页面的信息，并把当前Log队列的下一个要分配的LSN记录在Dirty_Page Table里的对应这个页面的RecLSN属性里, 这样无论之后这个脏页被更改多少次, 我们都可以知道，物理页面和内存页面的差异是从这个记录的RecLSN开始的, RecLSN之前的Log和这个脏页无关, 同时如果从RecLSN开始replay的话，可以保证找到所有这个页面从硬盘取出后的所有更改; 而当BM把内存页面同步回物理页面之后，则可以删除Dirty_Page table里对应的条目；

---

数据库的正常写操作和Rollback操作

相对Failure Recovery时如何利用log来恢复数据库, 我们先来看没有failure时, 数据库如何记录log和更改页面, 如何rollback更改;

首先所有的更改都必须完成(1)如果页面没有在buffer里, 申请BM把物理页面取出(如果是insert,有时需要创建新页面)；(2)对页面加短latch, 保证此期间没有其他进程可以修改页面, (3)对内存页面进行更改, 记录Undo和Redo log，更改Tx Table来update UndoPrevLSN和LastLSN (4)解latch (latch只是用来保证同一时间只有一个进程修改页面, 和数据库维护Tx Isolation的锁不是一个概念, 和Tx的commit/abort无关)

Commit流程

由于WAL协议的要求, 这个Tx所写的所有Redo Log都必须force到硬盘, 然后在log里记录一个End Record。

Rollback流程

当application需要Tx rollback, 或者deadlock需要杀掉某Tx时, 都需要在非系统崩溃的情况下rollback Tx; 当收到rollback请求后, 我们从此Tx的Tx table的UndoPrevLSN开始处理Log Record;

1. 当处理的log是Redo Log, 不做处理，继续通过PrevLSN往前找其他属于本Tx的log
2. 当处理的log是Undo Log, 查找应该更改哪个页面(因为Undo Log是Logical的), 然后对相应页面加latch, rollback页面并记录伴随的CLR并append到log里，更改Tx Table, 解Latch
3. 如此处理直到所有的属于这个Tx的Log都被处理完毕, 在log里记录一个End Record;

假设我们在log写到LSN3的位置时, 决定Rollback, 那么依次处理3，2，1的同时会往log队列里写CLR3‘ CLR2’， CLR1‘

可以看到当我们rollback一个Tx时, 我们会从Tx的当前UndoPrevLSN往回根据Log Record的PrevLSN(在failure Recovery的情况下有可能会遇到CLR，则需要用CLR的UndoPrevLSN来回溯，此乃后话)找Undo Log, 而对于每一个Undo Log, 都往当前的log队列里新append一个CLR;

UNDO/REDO Log的append顺序

如果一个逻辑修改操作的伴随Redo/Undo log比较小, 那么它们的信息可以记录在一个Record Log里, 否则我们需要分开记录Redo/Undo log, 此时, (1) Undo Log一定要先于Redo Log记录, 且(2) 内存页面的page_LSN要记录Redo log的LSN而不是Undo log的LSN； 条件(1)防止了刚记录完Redo, 系统就崩溃造成只有Redolog而没有undo log; 这会和之后的Failure Recovery 算法冲突, 由于Failure Recovery 算法需要先replay所有的Redo来“恢复历史”, 如果一个修改只有Redo, 那么redo完的页面无法undo; 而相反的, 如果只有Undo而没有Redo, 那么。。。=> 论文没写 -_- （大家可以自行思考下如何处理）条件(2)保证这个页面不会被Redo多次，这和之后的Failure Recovery相关，Redo pass的时候要根据页面上的page_LSN来决定当前的Redo内容是否已经apply到了此页面上

BM异步同步内存页面到物理页面

BM只需要遵守WAL协议，在这个唯一限制下，BM可以充分利用Batching来加速把内存页写回物理页面的吞吐; 对于经常被修改的Hot Page, BM可以选择对这个hot page制作一个in memory copy然后把这个copy同步回物理页面，这样可以防止同步时所加的latch影响对这个hot page的更改操作性能；

---

异步Checkpointing

ARIES的checkpointing是指把dirty_page table和Tx table（还有其他数据库的metadata比如tablespace, indexspace和主题相关性较小）备份起来, 这个过程可以是异步进行的, 而不需要锁住这两个表来保证checkpoint的时候没有别的进程更改它们，这就保证了系统在checkpointing的时候也可以正常进行所有其他操作；而在checkpointing的过程中Tx Table和dirty_page table有变化也不影响Failure Recovery的正确性(因为可以分析log来恢复准确的信息，后边会讲)

当Checkpointing开始时, 需要先写一个begin-chkpt Record到Log里，然后开始记录当前的Tx table和dirty_page table到硬盘, dirty_page table甚至可以100行100行的记录而不需要一口气全部记录写到硬盘去（这样可以加比较短时间和scope比较小的Latch, 而不必Latch住整个dirty_table）；

当所有需要记录的东西都记录好了，在log里记录一个end-chkpt record, 并在一个预定义好高可用性储存记录下master record，记录begin-chkpt的LSN；只有begin-chkpt而没有end-chkpt的checkpointing作废不用；

注意: ARIES不要求所有的脏页都同步回物理页面之后才开始checkpoint, 所以会有很多物理页很老的脏页的Redo log的LSN比begin-chkpt Record的LSN要小;

---

Failure Recovery

当数据库突然崩溃， 需要重新启动恢复状态时，所有还在进行的Tx都需要rollback; 且所有已经commit了的Tx都需要保证它们的更改可以恢复; 由于ARIES的"Non Force, Steal"策略，可以遇到以下情况:

1. 已经commit的tx的更改没有写回硬盘, 物理页面是老的落后于commit所需要的状态, 需要redo恢复commit后的的物理页面
2. 没有commit的page已经写回disk, 需要把这些更改从物理页面里Undo回去
3. 已经commit的tx的更改已经写回物理页面, 那么对这些Tx和页面不需要任何进一步操作

那么如何知道页面和Tx应该属于上边哪一种情况呢？ARIES首先使用一个Analysis Pass来分析log

Analysis Pass

Analysis Pass从checkpoint完成时记录在master record的begin-chkpt Record开始扫描log, 直到log末尾; 在这个过程中 只读log的内容而不会查看任何页面的内容;

首先, 从checkpoint里恢复Tx Table和Dirty_page table，

对于每个遇到的Redo Record(CLR也算Redo Log), 如果它所属的Tx不在Tx Table里则加入, 遇到Tx的End Record则从Tx Table里移除此Tx; 这样保证分析完log后, 所有系统崩溃时正在进行的Tx(还没commit或者还没rollback完毕的Tx)都在Tx Table里(也包括正在rollback但是还没完成的Tx)，同时Tx Table的每个Tx的UndoNxtLSN也会被更新到正确的位置(Tx写的最后一个Redo Log的LSN，而如果当系统崩溃时Tx正在进行Rollback, 那么Tx写的最后一个CLR的LSN会记录在Tx Table的这个Tx的UndoNxtLSN里)；

对于遇到的每个Redo Log Record(CLR也算Redo Log)的所对应的page, 如果它没有在Dirty_page table里，则把此页面加入并把当前Redo Log的LSN记录为其ResLSN；这样当log分析完毕后，Dirty_page table里有系统崩溃时所有“可能的脏页“记录（由于BM不在Log里记录它什么时候把脏页同步回物理页面, 所以我们不查看物理页面内容，是无法得知BM有没有把脏页写回的，而只能通过checkpoint的dirty_page table的snapshot来得知checkpoint时哪些是脏页，和通过Redo Log来判断哪些页面在checkpoint之后曾经被更改过, 从而最大程度恢复这个“可能的”Dirty_page table，如果想要精准的得知一个页面是否在系统崩溃时有未同步到硬盘的内容，我们需要把物理页面读出来检查其Page_LSN, 这会在Redo pass里提到)

根据恢复的“可能的”Dirty_page table，我们计算所有的“可能的”脏页的ResLSN, 那么最小的ResLSN就是我们RedoLSN, 即Redo开始扫描log的位置; 因为我们知道RedoLSN之前所有的Redo Log所伴随的更改，都已经被同步回硬盘页面了；

REDO Pass

从RedoLSN开始扫描log, 如果log是redo/CLR，且它们对应的页面在“可能的”Dirty_page table里，那么需要通知BM把页面从硬盘取出，如果此页面的page_LSN比当前的redo/CLR的LSN大，那么说明这个页面已经进行过这个更改了，跳过此Log Record, 否则按照Redo/CLR的log内容对页面进行更改；

在Redo Pass里，我们会恢复数据库的“历史状态”到Failure产生时的状态

• 如果系统崩溃时，Tx在正常进行数据修改，还没有commit, 且它的某个页面修改没有被BM同步到硬盘, 在系统崩溃时这些修改丢失，那么Redo pass可以正确的把这些页面取出到内存并进行修改, 这些修改会在之后的undo pass被rollback
• 如果系统崩溃时，Tx已经commit，但是由于NonForce Policy, 有些修改还没有被BM同步到硬盘，那么Redo pass也可以正确的把这些页面取出到内存并进行修改，由于这些Tx已经commit掉了，没有记录在Analysis pass结束时的Tx Table里，所以接下来的undo pass不会处理这些Tx的undo log，所以它们的更改不会被Undo；
• 如果系统崩溃时，Tx在进行Rollback, 那么这个Tx的Redo Log集合包括所有的正常写数据库时生成的Redo Log, 和之后rollback时产生的CLR, 这些Redo Log和CLR所更改的页面都有可能还没被同步回物理页面, 那么Redo pass会保证这些Redo/CLR对应的更改apply到相应的页面去, 那么就可以把rollback的进度恢复到数据库崩溃时的状态，由于Tx Table里记录了最新的CLR作为这个Tx的UndoNxtLSN，那么之后的Undo Pass会接着之前的Rollback进度继续进行Rollback操作（具体看Undo Pass）；

Redo pass时的BM算法更改

Redo pass开始后，BM就可以开始把脏页同步回物理页面了，但此时BM不能把任何页面从dirty_page table中删去, 这是因为目前的dirty_page table是提供了"可能的"脏页列表，Redo pass需要这个列表来判断需不需要把其中的页面拿出来，并对比它的page_LSN和其对应的所有Redo Log来判断是否需要修改页面， 比如一个页面的page_LSN是10，它被LSN11, LSN12, LSN20, LSN100的Redo Log记录的“更新”修改过，那么analysis pass会把这个页面记录在dirty_page table里, 假设Redo Pass刚处理到LSN50时, BM决定同步这个页面到物理页面去, 此时如果BM把这个页面从dirty_page table中删去, 那么LSN100的更改就丢失了;

UNDO Pass

Redo pass结束后, 系统就恢复正常了, 只是所有还在进行的Tx（此时还记录在Tx Table中的Tx）都必须被Rollback, rollback算法和正常情况一致，但是多了CLR的处理情况（重新贴一遍省去往回翻页）；

1. 当处理的log是Redo Log, 不用处理，通过PrevLSN继续往前找
2. 当处理的log是Undo Log, 查找应该更改哪个页面(因为Undo Log是Logical的), 然后对相应页面加latch, rollback页面并记录伴随的CLR并append到log里，更改Tx Table, 解Latch
3. 当处理的log是CLR, 那么通过UndoNxtLSN继续往前查找
4. 如此处理直到所有的属于这个Tx的Log都被处理完毕, 在log里记录一个End Record; 此Tx的Failure Recovery的Rollback结束

再次回到这个图，可以看到，如果Redo pass处理了CLR 2‘, 那么Undo Pass时，CLR2‘会直接跳到Log1，这样只有Log1的Undo被处理，生成新的CLR1‘；由于CLR3’和CLR2‘在redo pass时已经Replay过了，那么2和3的Undo都必定已经完成；

在Undo Pass开始时，BM算法恢复正常，可以随意把脏页写回物理页面后从dirty_page table中删去脏页(并不影响Undo pass的工作)

Undo pass结束后，整个数据库就恢复到了一个没有任何Tx的consistent状态了，就好像没有任何failure发生一样，只是所有的还在进行的Tx都被rollback了；

注意：在页面层，由于CLR是在Redo pass里处理的，所以如果Tx在Rollingback的时候出现failure，或者正在做Failure Recovery时再次出现failure, 那么CLR可能已经生成但是其伴随的对页面的具体undo更改只发生在内存页面而还没有被同步回物理页面；那么其实CLR是在Redo pass而不是Undo pass里被“重新replay的”; CLR是一种Redo, 这是理解ARIES的重点之一

无锁的ARIES

整个Failure Recovery的过程中，都不需要事务级的锁, 这是由于所有的更改在语意级都是绝对互斥的，一个还没commit的Tx如果可以进行某种“更改”并生成其伴随的Undo/Redo log，那么绝对不会有其他Tx可以更改同一个Object，从而生成冲突的Undo/Redo log, 换句话说，所有的Redo/Undo/CLR都在高层语意上是无冲突的，不同的Tx也许回改同一个页面，但是它们绝对不会更改同一个Row(如果数据库支持行锁)或者可以更改同一个Row，但是绝不会更改同一个Field(如果数据库支持field级锁)；无锁的Rollback是避免死锁的关键, 这样就不会发生Rollback和另外一个Rollback相互死锁的尴尬，此时需要Rollback一个Rollback, 这也是很多数据库设计力图避免的问题；

Failure Recovery的 并行化考虑

1. 由于Redo的时候需要把“可能的”脏页取出到内存，那么Analysis pass可以直接开始取这些页面而不必等待Redo pass开始
2. Redo是页面级的，那么不同页面的Redo可以并行恢复
3. Undo是Tx级的，不同的Tx可以并行进行Undo pass

Undo pass开始时就允许数据库接受新Tx

如果需要尽快恢复数据库使其可以接受新Tx，则需要在Redo时把需要加的事务锁都加好, 这样接受新的Tx也不会发生问题(比如阻止新Tx读到还在Rollback的Tx的更改数据); 一种方式是在checkpoint的时候把锁表也记录下来, 并在进行Redo时根据需要加事务锁，在Undo pass时，只要注意Undo/CLR的情况，如果一个obj的所有更改都已经被Rollback了, 那么这个obj的锁可以立刻去除，而不必等待这个Tx Rollback结束；

---

Nested Top Action

ARIES的设计使得它很容易实现“需要Rollback又不需要Rollback的inner Tx”，比如当一个Tx-A需要插入很多新数据，所以处理进程在这个Tx-A的context下拓展了一个文件空间用来insert，而数据库可以允许另外一个Tx-B在Tx-A commit之前来使用这块新区域；此时：

1. 如果拓展文件空间的操作还没完成系统就崩溃了，那么这个进行了一半的“拓展文件空间”的操作需要和Tx-A一起rollback
2. 如果拓展文件空间的操作完成了，那么这个操作则不需要和Tx-A一起rollback；这是因为 可能某Tx-B也把自己的内容写入到这个新区域了，此时Tx-A rollback连带rollback这个“拓展文件空间”操作的话，Tx-B的内容就被错误删除了；

ARIES的结构解决这个问题非常简单，在inner Tx完成前，把正常的Redo/Undo log写好，Undo里写正常的Rollback的逻辑，这样在完成前所有情况和一般情况一致，系统崩溃inner Tx会enclosing Tx一起rollback；而当inner Tx完成后，对已经写好的Undo立刻写一个伴随的dummy CLR来跳过这些Undo就好了，这样在Redo Pass的时候，这些Dummy CLR不会有任何作用，而在Undo pass的时候这些CLR的UndoNxtLSN可以跳过它们的伴随Undo Log；这样就保证enclosing Tx在Undo的时候自动跳过Undo这个完成的inner Tx.

Space Management

还有一个很好的例子来体现Logical Undo的好处，就是数据库的Space Management，一般数据库要维护一个free space inventory pages(FSIP)来记录每个页面还有多少空间；为了性能，只维护近似值，比如只有当阀值超过25%,50%,75%...才更新这个信息，这样就使得不必每个操作都update这个信息(比如很多时候free space的变化只有0.x%)；通过Logic Undo，Undo就和Redo解耦合了，比如Tx-A的更改正好使得页面从23%变成了%27，超过25%的阀值，所以Tx-A更新FSIP，但是后来Tx-B也更新这个页面使得页面使用率变成了44%，此时如果Rollback Tx-A，我们并不需要Undo我们对FSIP的更改；(实现Redo/Undo的非对称性)

---

一些总结思考

ARIES的"Non-Force，Steal"policy给了BM最大的灵活度，和对commit process的最小的限制；BM只需要保证WAL协议即可，除此之外ARIES的正确性完全不受BM自己的优化同步算法影响；

ARIES使用page-oriented Redo log和Logical Undo Log，这使得系统的其他部分实现非常灵活，如果暂时不考虑undo log的部分，只考虑Redo，那么其实Redo就是为了防止page在内存中更改的易失，而当page同步回硬盘后，则不需要redo log来重写了，所以page上要记录LSN作为进度来保证不会duplicate redo，而page的LSN是只前进的，其实就好像是对“前进”的操作的“确定性”记录，对于page来说，它只知道有人需要对它进行写，而不需要知道到底这个写是为了Redo还是为了Undo；

Redo log是为了“记住已经在page上进行过了的操作”，这些操作是已经发生了的(只是还没写回硬盘), 它们之所以可以进行，是因为很多check已经做完了，这是为什么Redo log设计为page-oriented的关键；

相比之下，Undo Log是为了“记住未来如果要rollback我们应该做什么”，如果把Undo设计为底层页面级应该做什么操作，我们就把现在的环境和未来“绑死”了，而未来是充满非确定性的(比如index分页), 而如果高层的Logical Undo没有写死我们应该对页面做什么，应该对哪个页面做什么， 而只是把语意层面必须要做的Undo信息留下了，这样，我们就允许了底层的各种细节可以发生变化，只要语意层面在未来把“更改”rollback即可，从而使得系统的其他逻辑可以对这些细节进行更改(比如移动未committed的数据到其他页面)而不必被Failure Recovery的逻辑所束缚；

Logical的Undo Log终归要被翻译成为对具体页面的更改，而CLR作为Undo Log的底层页面级伴随Log，为ARIES扣上了关键的一环，因为只有当Rollback成为事实, 才需要“现在立刻对页面进行Undo”时(而不是对“未来进行筹划")，那么CLR是page-oriented 的设计就非常自然了；CLR可以看作Undo的具像化，一个page的历史是由完成的Redo chain和CLR组成的，Undo只是为了在“更合适”的时间转化为CLR而已；

ARIES这篇论文讲了非常多的东西，这里只选笔者觉得比较有用有意思的节选出来用自己的理解；强烈推荐对数据库有兴趣的同学去读原文，经历完这个 rite of passage，可以承受ARIES的难度 ，你不会再害怕任何复杂的数据库论文（大概。。。）；

（完）